Logic / Nested Quantifiers
Least You Need to Know: Nested Quantifiers
When a statement has **more than one quantifier**, the order matters. Negating the statement flips each quantifier and negates the predicate.
The least you need to know
- The order of quantifiers can change the meaning completely.
- Negating `for every` gives `there exists`, and negating `there exists` gives `for every`.
- To test a nested statement, ask who gets to choose first.
- A single witness does not prove a universal-existential claim.
Key notation
∀x ∃y
for every x there exists a y
∃y ∀x
there exists one y that works for every x
¬
negation
Tiny worked example
- Statement: `∀x∈{1,2} ∃y∈{1,2,3}` such that `x+y=3`.
- For x=1 choose y=2, and for x=2 choose y=1.
- Different x-values may use different witnesses.
Common mistakes
- Students often reuse one witness for all values when the statement only says `there exists` after `for every`.
- Students often negate only the first quantifier.
- Students often forget that the predicate must be negated too.
How to recognize this kind of problem
- If the same y must work for every x, the existential quantifier must come first.
- For a negation, flip every quantifier in order from left to right.
- Try a tiny finite domain and check each choice explicitly.