1
Inner variables may depend on outer ones
In ∀x ∃y P(x, y) the y is chosen after x is known, so it may be a different y for each x. That dependence is the whole content.
Lesson · Logic and Proof · Predicate logic
Nested Quantifiers
When quantifiers stack, order decides meaning. ∀x ∃y lets y depend on x; ∃y ∀x demands one y that works for all of them. One implies the other, in one direction only.
∀x ∃y P(x, y) each x gets its own y (y may depend on x)
∃y ∀x P(x, y) ONE y works for every x (strictly stronger)
∃y ∀x P ⟹ ∀x ∃y P and NOT conversely
Same-kind quantifiers commute: ∀x∀y ≡ ∀y∀x, ∃x∃y ≡ ∃y∃x
Order matters, in one direction
Core ideas
What this lesson establishes
Nested quantifiers are where careful readers and careless ones separate. The difference is a single swap and a change of meaning.
2
∃∀ is strictly stronger than ∀∃
One y serving every x implies each x has some y. The converse fails — and the lab lets you build the case where it fails.
3
Like quantifiers commute; unlike ones do not
∀x ∀y may be swapped freely, and so may ∃x ∃y. Swapping ∀ past ∃ changes the claim.
The material
Stacked quantifiers
The six two-variable forms, and the implication that holds between two of them.
With one two-place predicate and two quantifiers there are eight strings to write — but same-kind quantifiers commute, so ∀x ∀y and ∀y ∀x are one claim, and likewise the two ∃∃ forms. Six distinct statements remain, and the mixed ones pair up as mirror images: a claim about rows and a claim about columns.
∀x ∀y P(x, y) P holds for every pair
∀x ∃y P(x, y) for each x there is SOME y (which may depend on x)
∃y ∀x P(x, y) there is ONE y that works with every x
∀y ∃x P(x, y) for each y there is SOME x (the mirror of the second)
∃x ∀y P(x, y) there is ONE x that works with every y
∃x ∃y P(x, y) some pair works
Keep the two mirror pairs apart. ∃y ∀x P(x, y) asks for one y serving every x; ∃x ∀y P(x, y) asks for one x serving every y. Over the grid in the lab those are a full column and a full row, and a grid can have either without the other. The theorem below pairs each ∃∀ with the ∀∃ that shares its variables — mixing a row claim into a column argument is how proofs about quantifier order go quietly wrong.
Theorem · The one implication
∃y ∀x P(x, y) ⟹ ∀x ∃y P(x, y), and the converse does not hold in general.
Suppose ∃y ∀x P(x, y), and let b be such a y. Then P(x, b) holds for every x. So given any x, the value b witnesses ∃y P(x, y). Hence ∀x ∃y P(x, y).
For the converse, take the domain ℤ and P(x, y) = "y is greater than x". Every integer has something larger, so ∀x ∃y P(x, y) holds. But no single integer is larger than every integer, so ∃y ∀x P(x, y) is false.
□
The English versions are worth having by heart. ∀x ∃y is "everybody has somebody"; ∃y ∀x is "somebody is everybody's". The first is a mild claim; the second is a strong one.
Example · The same swap, in analysis
Continuity of f at every point is ∀ε ∀x ∃δ, where δ may depend on both ε and x. Uniform continuity is ∀ε ∃δ ∀x: one δ that works at every point. The entire difference between the two definitions is where the ∃δ sits.
Three or more quantifiers behave the same way. ∀x ∃y ∀z is read left to right, and each variable may depend on those bound to its left and on no others. Reading the string in the order written is the whole technique.
Definition · Order of evaluation
A nested quantified statement is evaluated outside in. To decide ∀x ∃y P(x, y), take each x in turn and ask whether some y works for that particular x.
Interactive
Quantifier order
A finite universe you can edit
Method
Reading a nested statement
Left to right, and never rearrange.
1
Read the quantifiers in written order
∀x ∃y is "for each x… there is a y". Reading it as "there is a y for each x" in the sense of one shared y is the error itself.
2
Ask what each variable may depend on
A variable may depend on everything bound to its left. If your witness for y mentions x, you are proving ∀x ∃y, not ∃y ∀x.
3
To prove ∃∀, produce the single witness
Name one value and show it works for every x. If you cannot name it without knowing x, the statement is probably false.
4
To refute ∃∀, argue against every candidate
For each candidate y, exhibit an x that defeats it. The x may depend on y, which is exactly what the negation permits.
Order of quantifiers
Score 0 / 0Choose the answer you can justify.
Two statements over the integers
Domain ℤ, P(x, y) = "x + y = 0".
∀x ∃y (x + y = 0) TRUE
given x, take y = −x. The witness DEPENDS on x, which is allowed.
∃y ∀x (x + y = 0) FALSE
a single y would need x + y = 0 for every x at once;
x = 0 forces y = 0, and then x = 1 gives 1 + 0 = 1 ≠ 0.
∀x ∀y (x + y = y + x) TRUE — order of two ∀ is irrelevant
∃x ∃y (x + y = 5) TRUE — x = 2, y = 3
In the first, the witness y = −x mentions x, which is the signature of a ∀∃ proof. If a proof of an ∃∀ statement produces a witness mentioning the universally quantified variable, the proof is wrong.
Common mistakes
1
Swapping ∀ and ∃ while "simplifying"This changes the statement into a strictly stronger or weaker one. It is not a simplification and it is not valid.
2
Producing an x-dependent witness for an ∃∀ claimIf the witness mentions the universally quantified variable, you have proved the ∀∃ version instead. This is the most common invalid proof in the whole course.
3
Assuming English word order settles it"There is a key for every door" is genuinely ambiguous in English. The symbols are not, which is why the translation must be done deliberately.
Check your understanding
✓
Finish when you can build a predicate separating ∀∃ from ∃∀.
Using the lab's grid, construct a relation where ∀x ∃y holds and ∃y ∀x fails, and one where both hold — then say, for the successor preset on {1, …, 4}, why ∀x ∃y fails there and for which x. Being able to build the separating case, and to name the element a truncated domain breaks, is stronger evidence of understanding than recognising either.
Note: The ∀ε ∃δ versus ∃δ ∀ε distinction is the single place this lesson pays off outside discrete mathematics: pointwise and uniform continuity differ by precisely this swap, and so do pointwise and uniform convergence.