Recipe

Evaluate a nested quantifier statement

Use when: you have a statement with two quantifiers, such as $\forall x\, \exists y\, P(x,y)$ , over finite domains, and need a verdict

Goal: a settled verdict for the whole statement, found by resolving the inner quantifier separately for each fixed outer value

Taught in Nested quantifiers

Quick recipe

Fix the outer variable at its first value
Solve the inner quantifier for that value, then repeat for the rest
Combine every outer value's result into one verdict

1
Read the statement outside-in: hold the outermost variable fixed at one specific domain value, before touching the inner variable at all.

Example

For $\forall x \in \{1,2,3\}, \exists y \in \{1,2,3\}, x+y\ge4$ , fix $x=1$ first.

Why: the inner quantifier's truth value can depend on which outer value is fixed, so nothing can be evaluated until the outer variable is pinned down.
2
With the outer variable fixed, evaluate the inner quantifier as its own claim, then return to the next outer value and repeat until every outer value is resolved.

Example

$x=1$ : $y=1$ gives $2\ge4$ , false; $y=2$ gives $3\ge4$ , false; $y=3$ gives $4\ge4$ , true -- witness $y=3$ . $x=2$ : $y=2$ gives $4\ge4$ , true -- witness $y=2$ . $x=3$ : $y=1$ gives $4\ge4$ , true -- witness $y=1$ .
- the inner quantifier is $\exists y$ — a fresh witness search is enough for each outer value, and different outer values may use different witnesses.
- the inner quantifier is $\forall y$ — every inner value must be checked for that fixed outer value, since one failing pair breaks that outer value's turn.
Why: a nested $\forall x$ still demands every outer value succeed on its own, so the witness for one value never has to work for another.
3
The whole statement is true only if every outer value found a witness in the previous step. One outer value with no witness makes the entire statement false.

Example

$x=1,2,3$ each found a witness ( $y=3,2,1$ respectively), so $\forall x \in \{1,2,3\}, \exists y \in \{1,2,3\}, x+y\ge4$ is true.
- every outer value found a witness — $\forall x\,\exists y\,P(x,y)$ is true.
- even one outer value found no witness — the statement is false at that value, so the whole statement is false.
Why: $\forall x\,\exists y\,P(x,y)$ is true exactly when the inner claim holds for every outer value, by the outside-in reading this whole recipe follows.

Common mistakes

Reusing the same witness $y$ for every outer $x$ instead of searching fresh at each outer value.
Evaluating the inner quantifier before fixing the outer variable, reading the statement out of order.
Declaring the whole statement true after only one outer value succeeds, instead of checking every one.
Losing track of which variable is fixed and which is still being searched over, partway through a step.