FOL 06 · Nested Quantifiers
Definition
Quantifiers are nested when one is in the scope of another: . Treat the inner part as a propositional function: .
Does the order matter?
| Combination | Order matters? |
|---|---|
| ❌ no | |
| ❌ no | |
| vs | ✅ YES |
The key implication
If one y works for every x, then certainly every x has some y. The converse fails.
- : “for every x there’s a y” — y may depend on x.
- : “one fixed y works for all x” — y is chosen first and can’t change.
Meaning table (two variables)
| Statement | True when | False when |
|---|---|---|
| P(x,y) true for every pair | some pair makes it false | |
| for each x, some y (depending on x) works | some x has no y | |
| one x works with every y | every x fails with some y | |
| some pair works | every pair fails |
Game view — ∀ is your opponent, ∃ is you
Read left to right. The opponent picks values for ∀ variables (trying to make it false); you pick values for ∃ variables (trying to make it true), and you see the opponent’s earlier choices. True ⟺ you can always win.
Slide examples (domain: real numbers)
Example 1 — P(x, y): x + y = 0
| Statement | Value | Reason | |
|---|---|---|---|
| a | F | 1 + 2 ≠ 0 | |
| b | T | pick y = −x | |
| c | F | no single y works for all x | |
| d | T | 1 + (−1) = 0 |
Example 2 — Q(x, y): x · y = 0
| Statement | Value | Reason | |
|---|---|---|---|
| a | F | 1 · 2 ≠ 0 | |
| b | T | y = 0 | |
| c | T | y = 0 works for every x | |
| d | T | 1 · 0 = 0 |
Contrast Ex 1(c) and Ex 2(c)
∃y∀x is true only if a universal y exists. For ”+” there’s none; for ”·” zero is universal. The same reasoning answers most GATE order questions.
Example 3 — Q(x, y, z): x + y = z
- → T (z = x + y)
- → F (z = 2 fails for x = 2, y = 3)
Prev ← FOL 05 Translating English · Next → FOL 07 Nested Translation and Negation