Nested Quantifiers

Most definitions in mathematics use two quantifiers at once: "for every $x$ there is a $y$ such that…" With negation of quantifiers in hand, this lesson shows how to read, decide and negate such statements, and why the order of the quantifiers matters.

Key idea

Read quantifiers from left to right: each one is decided after the ones before it, so a later variable may depend on an earlier one. $\forall x\, \exists y\, P(x, y)$ says each $x$ has its own partner $y$. $\exists y\, \forall x\, P(x, y)$ says one single $y$ works for every $x$, which is a much stronger claim.

Why it works

Think of a game. In $\forall x\, \exists y\, (y > x)$ over the real numbers, an opponent picks $x$, and then you pick $y$: you answer $y = x + 1$ and always win, so the statement is true. In $\exists y\, \forall x\, (y > x)$ you must commit to $y$ first, and the opponent then picks $x = y$ and wins. So that statement is false. Swapping two quantifiers of the same kind changes nothing ($\forall x\, \forall y$ is the same as $\forall y\, \forall x$), but swapping a $\forall$ with an $\exists$ can change everything.

A table of $P(x, y)$ makes this visible. Rows are values of $x$, columns are values of $y$, on the domain $\{1, 2, 3\}$: $$\begin{array}{c|ccc} P(x, y) & y = 1 & y = 2 & y = 3 \\ \hline x = 1 & \mathrm{F} & \mathrm{T} & \mathrm{F} \\ x = 2 & \mathrm{T} & \mathrm{F} & \mathrm{F} \\ x = 3 & \mathrm{F} & \mathrm{F} & \mathrm{T} \end{array}$$ $\forall x\, \exists y\, P(x, y)$ asks for a T in every row: true. $\exists y\, \forall x\, P(x, y)$ asks for a column of all T's: false.

Worked examples

Worked example: Deciding over the real numbers

Decide $\forall x\, \exists y\, (x + y = 0)$ and $\exists y\, \forall x\, (x + y = x)$ over the real numbers.

First statement: for any $x$, choose $y = -x$. Then $x + y = 0$. The choice depends on $x$, which is allowed: true.
Second statement: we need one $y$ that works for every $x$. Try $y = 0$: $x + 0 = x$ for every $x$. True.
Both are true, but for different reasons: the first needed a $y$ for each $x$, the second found a single $y$.

Answer: true, true

Worked example: Negating a nested statement

The domain is the students in a class, and $F(x, y)$ means "$x$ is friends with $y$." Negate "Every student has a friend in the class."

In symbols: $\forall x\, \exists y\, F(x, y)$.
Move the negation through both quantifiers, switching each: $\exists x\, \forall y\, \neg F(x, y)$.
In words: "Some student is friends with nobody in the class."

Answer: $\exists x\, \forall y\, \neg F(x, y)$

Worked example: When the order matters

Over the real numbers, decide $\forall x\, \exists y\, (xy = 1)$.

We need a partner $y$ for every $x$. For $x \ne 0$, $y = \frac{1}{x}$ works.
But $x = 0$ has no partner: $0 \cdot y = 0$ for every $y$.
One $x$ without a partner makes the statement false. (Over the nonzero real numbers it would be true.)

Answer: false

Common mistake

Swapping mixed quantifiers as if nothing changed. "Every lock has a key that opens it" ($\forall$ lock $\exists$ key) is not "there is a key that opens every lock" ($\exists$ key $\forall$ lock); the second describes a master key. Check: say the statement as a game. Whoever is named first moves first, and the later player may react to that choice.

Nested Quantifiers

Worked examples

Practice

Builds on

Leads to

Sources and further reading