MathLabs
TheoremProved

Quantifier order is not commutative

Statement

For any structure M\mathcal{M} and formula R(x,y)R(x,y): ∃y ∀x R(x,y)⇒∀x ∃y R(x,y)\exists y\, \forall x\, R(x,y) \Rightarrow \forall x\, \exists y\, R(x,y). The converse implication does not hold in general.

Why is it true?

∃y ∀x R(x,y)\exists y\, \forall x\, R(x,y) demands a single witness yy that works for every xx (a "fixed" witness), while ∀x ∃y R(x,y)\forall x\, \exists y\, R(x,y) only demands that each xx has some witness, possibly a different one for each xx (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 M⊨s∃y ∀x R(x,y)\mathcal{M} \models_s \exists y\, \forall x\, R(x,y). By the semantic clause for ∃\exists, M⊨s∃y φ  ⟺  there is d∈M with M⊨s[y↦d]φ\mathcal{M} \models_s \exists y\, \varphi \iff \text{there is } d \in M \text{ with } \mathcal{M} \models_{s[y \mapsto d]} \varphi; applying it here gives some d0∈Md_0 \in M with M⊨s[y↦d0]∀x R(x,y)\mathcal{M} \models_{s[y \mapsto d_0]} \forall x\, R(x,y).

By the clause for ∀\forall applied to this, M⊨s[y↦d0][x↦a]R(x,y)\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y) holds for every a∈Ma \in M, since the ∀x\forall x ranges over all of MM regardless of which aa we later pick.

Now fix an arbitrary a∈Ma \in M to verify ∀x ∃y R(x,y)\forall x\, \exists y\, R(x,y). From the previous paragraph, taking x↦ax \mapsto a gives M⊨s[y↦d0][x↦a]R(x,y)\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y), which exhibits d0d_0 itself as a witness for ∃y R(x,y)\exists y\, R(x,y) under x↦ax \mapsto a; hence M⊨s[x↦a]∃y R(x,y)\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y).

Since a∈Ma \in M was arbitrary, M⊨s[x↦a]∃y R(x,y)\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y) holds for every aa, which is exactly the semantic clause for M⊨s∀x ∃y R(x,y)\mathcal{M} \models_s \forall x\, \exists y\, R(x,y). This proves ∃y ∀x R(x,y)⇒∀x ∃y R(x,y)\exists y\, \forall x\, R(x,y) \Rightarrow \forall x\, \exists y\, R(x,y).

Converse fails: a counterexample. Let M\mathcal{M} have domain M=ZM = \mathbb{Z} (the integers) and interpret R(x,y)R(x,y) as "x<yx < y". Then ∀x ∃y R(x,y)\forall x\, \exists y\, R(x,y) is TRUE: for every integer xx, taking y=x+1y = x+1 gives x<yx < y. But ∃y ∀x R(x,y)\exists y\, \forall x\, R(x,y) is FALSE: it would require a single integer yy larger than every integer xx, and no such maximum integer exists (for any candidate yy, the integer y+1y+1 violates y+1<yy+1 < y). So ∀x ∃y R(x,y)\forall x\, \exists y\, R(x,y) holds while ∃y ∀x R(x,y)\exists y\, \forall x\, R(x,y) 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

  1. Herbert B. Enderton (2001). A Mathematical Introduction to Logic
  2. David Hilbert, Wilhelm Ackermann (1928). Grundzüge der theoretischen Logik