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?

CombinationOrder 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)

StatementTrue whenFalse when
P(x,y) true for every pairsome pair makes it false
for each x, some y (depending on x) workssome x has no y
one x works with every yevery x fails with some y
some pair worksevery 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

StatementValueReason
aF1 + 2 ≠ 0
bTpick y = −x
cFno single y works for all x
dT1 + (−1) = 0

Example 2 — Q(x, y): x · y = 0

StatementValueReason
aF1 · 2 ≠ 0
bTy = 0
cTy = 0 works for every x
dT1 · 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