Quantifier order is not commutative
Statement
For any structure and formula : . The converse implication does not hold in general.
Why is it true?
demands a single witness that works for every (a "fixed" witness), while only demands that each has some witness, possibly a different one for each (a "moving" witness). A fixed witness is automatically a moving witness (just reuse it), but not conversely — this is exactly the difference between "someone loves everybody" (one universal lover) and "everybody is loved by someone" (possibly different admirers), a classic source of ambiguity in natural language that predicate logic disambiguates.
Proof sketch
Forward direction. Assume . By the semantic clause for , ; applying it here gives some with .
By the clause for applied to this, holds for every , since the ranges over all of regardless of which we later pick.
Now fix an arbitrary to verify . From the previous paragraph, taking gives , which exhibits itself as a witness for under ; hence .
Since was arbitrary, holds for every , which is exactly the semantic clause for . This proves .
Converse fails: a counterexample. Let have domain (the integers) and interpret as "". Then is TRUE: for every integer , taking gives . But is FALSE: it would require a single integer larger than every integer , and no such maximum integer exists (for any candidate , the integer violates ). So holds while fails, showing the converse implication is false in general.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Herbert B. Enderton (2001). A Mathematical Introduction to Logic
- David Hilbert, Wilhelm Ackermann (1928). Grundzüge der theoretischen Logik