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.
Least you need to know
- The order of quantifiers can change the meaning completely.
- Negating
for everygivesthere exists, and negatingthere existsgivesfor 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
Worked example
- Statement:
∀x∈{1,2} ∃y∈{1,2,3}such thatx+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 existsafterfor every. - Students often negate only the first quantifier.
- Students often forget that the predicate must be negated too.
How to recognize it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Quantifiers.
Least You Need to Know: QuantifiersRelated lessons
Keep going with nearby lessons in the same topic.