Nested quantifiers
Every whole number has a bigger whole number. Does that mean some whole number is bigger than all of them? How do you say exactly which of the two you mean?
Where you are 4 in Quantifiers
Why this exists
A single quantifier, for all or there exists, is enough for a claim about one variable: every real number has a square of at least 0, some integer is even. But most claims worth making tie two things together. “Every integer has an integer bigger than it” is about a pair of numbers, the one you are given and the one you answer with, and it quantifies each of them.
Once there are two quantifiers, their order starts to matter, and English is careless about order. Compare
- for every integer there is a bigger integer, and
- there is an integer bigger than every integer.
The first is true: whatever integer you name, add 1. The second is false: no single integer beats all the others, since it cannot beat itself. The words are almost the same and the claims are opposite. Mathematics needs a way to write each one so that nobody can mistake it for the other, and a way to decide which one a proof has actually shown.
Definition
A predicate in two variables, written P(x, y), is a sentence about x and y that becomes a statement, true or false, as soon as both x and y are replaced by members of their domains. “x + y = 0” and “x divides y” are examples.
A nested quantifier statement puts one quantifier inside the reach of another:
It is read from the left, and each quantifier governs everything to its right. So this one says: for every x in D, the statement \exists y \in E,\ P(x, y) is true. In words, whatever x is chosen, some y can be found to go with it. The y is found after x is known, so it may be a different y for each x.
Reversing the order gives a different statement:
This says: there is one y in E for which \forall x \in D,\ P(x, y) is true. Now the y is chosen first, before any x is seen, and that single y has to work for every x at once.
A useful way to hear the difference is as a game. In \forall x\ \exists y, an opponent picks x and then you answer with y; the statement is true if you can always answer. In \exists y\ \forall x, you must commit to your y first and then the opponent picks any x they like against it.
Two quantifiers of the same kind can sit together too. \forall x \in D,\ \forall y \in E,\ P(x, y) says every pair makes P true, and \exists x \in D,\ \exists y \in E,\ P(x, y) says at least one pair does.
Intuition
When both domains are small, a two-variable predicate is a grid: one row for each x, one column for each y, and a cell marked T wherever P(x, y) is true.
Read the two orders off the grid.
- \forall x\ \exists y asks whether every row has at least one T. On the left it does, with the T in a different column each time.
- \exists y\ \forall x asks whether some column is T all the way down. On the left no column is; on the right the column y = 3 is.
A full column puts a T in every row, so whenever \exists y\ \forall x holds, \forall x\ \exists y holds as well. The left grid shows that the reverse can fail: T in every row, scattered across different columns, with no single column full. That picture is the whole content of the Results below.
Results
Reading a grid. On finite domains, each arrangement of two quantifiers is a question about the grid of P(x, y):
| Statement | True exactly when |
|---|---|
| \forall x\ \forall y\ P(x, y) | every cell is T |
| \exists x\ \exists y\ P(x, y) | at least one cell is T |
| \forall x\ \exists y\ P(x, y) | every row has a T |
| \exists y\ \forall x\ P(x, y) | some column is all T |
| \exists x\ \forall y\ P(x, y) | some row is all T |
| \forall y\ \exists x\ P(x, y) | every column has a T |
Same kinds may swap. Two quantifiers of the same kind can be written in either order:
Mixed kinds may not. One direction always holds:
and the reverse direction is false in general.
Why it is true
Same kinds. \forall x\ \forall y\ P(x, y) says that P(a, b) is true for every choice of a and every choice of b, which is to say for every pair. \forall y\ \forall x\ P(x, y) says the same thing about the same pairs, only listed in a different order. Likewise, both \exists x\ \exists y\ P(x, y) and \exists y\ \exists x\ P(x, y) say that at least one pair (a, b) makes P(a, b) true.
One direction of the mixed case. Suppose \exists y\ \forall x\ P(x, y) is true. Then there is some b in E with P(x, b) true for every x in D. Now take any x in D. The same b works for it, so there is a y with P(x, y), namely y = b. Since x was any member of D, \forall x\ \exists y\ P(x, y) is true. The statement with the single y chosen first is the stronger one: a y that works for everybody works for each person in turn.
The other direction can fail. One example where \forall x\ \exists y\ P(x, y) is true and \exists y\ \forall x\ P(x, y) is false is enough to show that the first does not force the second. Take both domains to be the integers \mathbb{Z}, and let P(x, y) be x < y.
- \forall x \in \mathbb{Z},\ \exists y \in \mathbb{Z},\ x < y is true: given x, answer with y = x + 1.
- \exists y \in \mathbb{Z},\ \forall x \in \mathbb{Z},\ x < y is false: whatever y is proposed, the choice x = y gives y < y, which is false.
So \forall x\ \exists y and \exists y\ \forall x are not logically equivalent, and a proof of the first is never a proof of the second.
Worked examples
Deciding from a grid
Let D = \{1, 2, 3\} and let P(x, y) be x + y = 4, with both x and y in D. Decide whether each statement is true.
(a) \forall x \in D,\ \exists y \in D,\ x + y = 4
(b) \exists y \in D,\ \forall x \in D,\ x + y = 4
SolutionThe domains have three members each, so write out all nine cells. This is the left grid of Figure 1.
| y = 1 | y = 2 | y = 3 | |
|---|---|---|---|
| x = 1 | F | F | T |
| x = 2 | F | T | F |
| x = 3 | T | F | F |
For (a), check every row for a T. Row x = 1 has one at y = 3, row x = 2 at y = 2, row x = 3 at y = 1. Every x has a partner, so (a) is true. Notice the partner is y = 4 - x, different for each x, which (a) allows.
For (b), look for a column that is T all the way down. Column y = 1 fails at x = 1, since 1 + 1 = 2. Column y = 2 fails at x = 1, since 1 + 2 = 3. Column y = 3 fails at x = 2, since 2 + 3 = 5. No single y works for every x, so (b) is false, although it differs from (a) only in the order of its quantifiers.
The order changes the answer
Decide each statement, where \mathbb{Z} is the set of integers.
(a) \forall x \in \mathbb{Z},\ \exists y \in \mathbb{Z},\ x + y = 0
(b) \exists y \in \mathbb{Z},\ \forall x \in \mathbb{Z},\ x + y = 0
Solution(a) Given any integer x, answer with y = -x, which is an integer. Then x + y = x + (-x) = 0. Since this works whatever x is, (a) is true. A rule that produces y from x is the natural way to prove a “for every, there is” statement.
(b) This asks for one integer y that adds to 0 with every integer at once. Suppose some y did. Then it would have to work for x = 1 - y as well, which is an integer, but
So no y works, and (b) is false. To show a “there is, for every” statement false, show that each proposed y is beaten by some x; here the beating x is built from y.
When the domain decides
Decide \forall x\ \exists y,\ xy = 1 first with both variables in \mathbb{R}, the real numbers, and then with both in the nonzero real numbers. Then decide \exists y\ \forall x,\ xy = 1 on the nonzero real numbers.
SolutionOn \mathbb{R} the first statement is false. For it to be true, every x would need a partner, including x = 0. But 0 \cdot y = 0 \ne 1 for every real y, so x = 0 has no partner.
On the nonzero real numbers, x = 0 is no longer in the domain. Given any nonzero x, answer with \displaystyle y = \frac{1}{x}, which is a nonzero real number, and \displaystyle xy = x \cdot \frac{1}{x} = 1. So the statement is true there. Nothing in the symbols changed; only the domain did.
The reversed statement is false even on the nonzero reals. Whatever nonzero y is proposed, take \displaystyle x = \frac{2}{y}, which is also nonzero. Then xy = 2 \ne 1. Every reciprocal belongs to one number only.
Translating English into symbols
Write each sentence with quantifiers, then decide whether it is true.
(a) There is a smallest positive real number.
(b) Every nonnegative real number is the square of some real number.
Solution(a) “Smallest” means no bigger than any of the others, so the sentence says one positive real x sits at or below every positive real y. The x is fixed first, so its quantifier comes first:
It is false. Whatever positive x is proposed, take \displaystyle y = \frac{x}{2}, which is positive too; then x \le y would say \displaystyle x \le \frac{x}{2}, which fails because x > 0. On the positive integers the same sentence is true, with x = 1.
(b) “Every nonnegative real number” is the outer quantifier, and “some real number” is found after it, so it goes inside:
It is true. Given x \ge 0, answer with \displaystyle y = \sqrt{x}, a real number because x is not negative, and y^2 = x. Here too the answer depends on the question: \displaystyle \sqrt{x} changes as x does.
Three quantifiers: a number between any two
Decide the statement
and then the same statement with every \mathbb{R} replaced by \mathbb{Z}.
SolutionRead it from the left: for every pair of real numbers with x < y, some real z lies strictly between them. The two outer quantifiers are of the same kind, so their order does not matter; the z is found after both x and y are known, so it may depend on both.
Answer with the midpoint, \displaystyle z = \frac{x + y}{2}. Since x < y, adding x to both sides gives 2x < x + y, so \displaystyle x < \frac{x + y}{2}. Adding y to both sides instead gives x + y < 2y, so \displaystyle \frac{x + y}{2} < y. So x < z < y, and the statement is true on \mathbb{R}. It says that no two real numbers are next-door neighbors, and it is close kin to the fractions filling the line.
On \mathbb{Z} it is false. The pair x = 1, y = 2 satisfies x < y, but no integer z has 1 < z < 2.
Moving \exists z to the front would change the claim again, even on \mathbb{R}: it would ask for one number between every pair. The pair x = z, y = z + 1 beats any proposed z, since it would need z < z.
A limit statement
Show that
is true, and that it becomes false if the first two quantifiers are swapped. (This is the exact claim that 2x approaches 6 as x approaches 3. The part 0 < \lvert x - 3 \rvert leaves out x = 3 itself, since a limit is about the values near 3, not at it.)
SolutionThe statement is a game with three moves. An opponent names a tolerance \varepsilon > 0; you answer with a window \delta > 0; then the opponent may pick any x \ne 3 within \delta of 3, and 2x must land within \varepsilon of 6.
Since \delta is chosen after \varepsilon, it may depend on it. Try \displaystyle \delta = \frac{\varepsilon}{2}, which is positive because \varepsilon is. For any x with 0 < \lvert x - 3 \rvert < \delta,
So every \varepsilon has an answer, and the statement is true.
Swapped, it reads: there is one \delta > 0 such that for every \varepsilon > 0 and every x \ne 3 within \delta of 3, \lvert 2x - 6 \rvert < \varepsilon. That asks one window to meet every tolerance at once. Given any proposed \delta, take \displaystyle x = 3 + \frac{\delta}{2}, which is within \delta of 3 and is not 3, and \varepsilon = \delta. Then \lvert 2x - 6 \rvert = \delta, and \delta < \delta is false. So the swapped statement is false. The whole definition of a limit rests on this order: the window is allowed to shrink as the tolerance does.
Boundaries
Swapping works only within one kind. Two \forall in a row may trade places, and so may two \exists. A \forall moved past an \exists changes the claim, and only \exists y\ \forall x \implies \forall x\ \exists y survives.
The domain is part of the statement. \forall x\ \exists y,\ xy = 1 is false on \mathbb{R} and true on the nonzero reals (Example 3). With its domains left unstated, a nested statement is not yet a claim anybody can check.
The grid test needs finite domains. On \mathbb{Z} or \mathbb{R} the rows cannot all be inspected, so a true “for every, there is” needs a rule that produces y from any x, and a false one needs a single x that no y can answer.
A variable exists only inside its quantifier. In \forall x\ \exists y,\ x < y, the y belongs to one particular x. Once the sentence ends there is no “the y” left to talk about, and a later line of a proof cannot use it as if it were one fixed number.
English order is not quantifier order. “Every student read a book” can mean one book that all the students read, or a book for each student, possibly all different. Before a sentence is turned into symbols, decide which quantity is chosen first, and put its quantifier on the left.
Negation and “exactly one” are separate moves. Denying a nested statement flips every quantifier in turn; that is negating a quantified statement. Claiming that exactly one y works is unique existence, which is more than \exists says.
Where this goes next
The most important nested statement in school mathematics is the definition of a limit. It is exactly the three-move game of Example 6, \forall \varepsilon\ \exists \delta\ \forall x, and the idea of a limit leads through the epsilon delta idea to the formal definition, where reading the order correctly is most of the difficulty.
Showing that a limit does not exist means denying such a statement, which turns \forall \varepsilon\ \exists \delta into \exists \varepsilon\ \forall \delta; see negating a quantified statement.
In proofs, the shape of the statement tells you the shape of the proof. A “for every, there is” claim is proved by taking an arbitrary x and building its y, as in existence proofs. A false “there is, for every” claim is killed the way any false universal is, by a Counterexample to each candidate.
Exercises
Reading a grid
Let D = \{1, 2, 3\} and E = \{2, 3, 4\}, and let P(x, y) mean “x divides y”, for x in D and y in E. Decide whether each statement is true, and give the reason.
- \forall x \in D,\ \exists y \in E,\ P(x, y)
- \exists y \in E,\ \forall x \in D,\ P(x, y)
- \exists x \in D,\ \forall y \in E,\ P(x, y)
- \forall y \in E,\ \exists x \in D,\ x > 1 \text{ and } P(x, y)
- \forall x \in D,\ \forall y \in E,\ P(x, y)
Integers and real numbers
Decide whether each statement is true. If it is true, give a witness or a rule that produces one; if it is false, give a value that shows it. \mathbb{Z}^{+} is the set of positive integers.
- \forall x \in \mathbb{Z},\ \exists y \in \mathbb{Z},\ x + y \text{ is odd}
- \exists y \in \mathbb{Z},\ \forall x \in \mathbb{Z},\ x + y \text{ is odd}
- \exists x \in \mathbb{Z},\ \forall y \in \mathbb{Z},\ xy = y
- \forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y^2 = x
- \forall x \in \mathbb{Z},\ \exists y \in \mathbb{Z},\ 2y = x
- \forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ 2y = x
- \forall x \in \mathbb{Z}^{+},\ \exists y \in \mathbb{Z}^{+},\ x + y = 10
- \exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ x \le y^2
Translating
Write each sentence in symbols, then decide whether it is true.
- There is a real number whose product with every real number is 0.
- Every real number is less than some integer.
- For every positive real number \varepsilon there is a positive integer n with \displaystyle \frac{1}{n} < \varepsilon.
- Every even integer is the sum of two odd integers.
Order
- Show that \forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ x + y = 5 is true and \exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ x + y = 5 is false.
- Take D = \{1, 2\} for both variables. Give a predicate P(x, y) for which \forall x \in D,\ \exists y \in D,\ P(x, y) is true but \exists y \in D,\ \forall x \in D,\ P(x, y) is false.
- In the right-hand grid of Figure 1, P(x, y) is x \le y on \{1, 2, 3\}. Which rows are T all the way across, and which columns are T all the way down? Use this to decide \exists x\ \forall y,\ x \le y and \exists y\ \forall x,\ x \le y.
Reasoning
- Explain why \forall x\ \forall y\ P(x, y) and \forall y\ \forall x\ P(x, y) always say the same thing, while \forall x\ \exists y\ P(x, y) and \exists y\ \forall x\ P(x, y) need not.
- Let L(x, y) mean “x likes y”, for people x and y in one room. Write “everybody likes somebody” and “somebody is liked by everybody” in symbols. Which one guarantees the other? Explain.
- Prove that for every \varepsilon > 0 there is a \delta > 0 such that for every real x, if 0 < \lvert x - 1 \rvert < \delta then \lvert 3x - 3 \rvert < \varepsilon.
- Show that the statement in Exercise 23 becomes false when its first two quantifiers are swapped, so that one \delta > 0 must work for every \varepsilon > 0.
Answers
- True. x = 1 divides 2, x = 2 divides 2, and x = 3 divides 3, so every row has a T.
- False. No y in E is divisible by all of 1, 2 and 3: 3 does not divide 2 or 4, and 2 does not divide 3.
- True. x = 1 divides every y in E.
- True. y = 2 and y = 4 are divisible by x = 2, and y = 3 by x = 3.
- False. x = 2 and y = 3 give P(2, 3) false, since 2 does not divide 3.
- True. Given x, the integer y = x + 1 gives x + y = 2x + 1, which is odd.
- False. Whatever y is proposed, x = y gives x + y = 2y, which is even.
- True. x = 1 gives 1 \cdot y = y for every integer y.
- False. x = -1 has no partner, since y^2 \ge 0 for every real y.
- False. x = 1 would need \displaystyle y = \frac{1}{2}, which is not an integer.
- True. Given x, the real number \displaystyle y = \frac{x}{2} gives 2y = x.
- False. x = 10 would need y = 0, which is not a positive integer. Every x from 1 to 9 has a partner, 10 - x, but one x without a partner is enough.
- True. x = 0 works, since 0 \le y^2 for every real y. Any negative x works too.
- \exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ xy = 0. True, with x = 0.
- \forall x \in \mathbb{R},\ \exists n \in \mathbb{Z},\ x < n. True. Take n = \lfloor x \rfloor + 1, one more than x rounded down. Rounding down takes off less than 1, so x - 1 < \lfloor x \rfloor, which gives x < n. For x = 2.5 that is n = 3.
- \displaystyle \forall \varepsilon > 0,\ \exists n \in \mathbb{Z}^{+},\ \frac{1}{n} < \varepsilon. True. Take \displaystyle n = \left\lfloor \frac{1}{\varepsilon} \right\rfloor + 1, a positive integer, which is greater than 1/\varepsilon for the reason in Exercise 15. Since n > 1/\varepsilon > 0, taking reciprocals gives 1/n < \varepsilon. For \varepsilon = 0.3 that gives n = 4, and 1/4 = 0.25 < 0.3.
- \forall n \in \mathbb{Z}, if n is even then \exists a \in \mathbb{Z},\ \exists b \in \mathbb{Z} with a and b odd and a + b = n. True. Take {a = n - 1} and b = 1. Writing n = 2k, {a = 2(k - 1) + 1} is odd, b is odd, and a + b = n.
- For the first, given x answer with y = 5 - x, and x + y = 5. For the second, whatever y is proposed, x = 6 - y gives x + y = 6 \ne 5, so no single y works.
- One answer: P(x, y) is x = y. Row x = 1 has its T at y = 1 and row x = 2 at y = 2, so every row has a T; column y = 1 fails at x = 2 and column y = 2 fails at x = 1, so no column is full.
- Row x = 1 is the only full row, and column y = 3 is the only full column. So \exists x\ \forall y,\ x \le y is true, with x = 1, and \exists y\ \forall x,\ x \le y is true, with y = 3.
- Both \forall x\ \forall y and \forall y\ \forall x say that every pair (x, y) makes P true; the order only changes how the pairs are listed. In \forall x\ \exists y the y may change with x, while in \exists y\ \forall x one y must serve every x, which is a stronger demand (Example 1 has the first true and the second false).
- \forall x\ \exists y\ L(x, y) and \exists y\ \forall x\ L(x, y). The second guarantees the first: if one person b is liked by everybody, then everybody likes somebody, namely b. The first does not guarantee the second, since everybody could like a different person.
- Given \varepsilon > 0, take \displaystyle \delta = \frac{\varepsilon}{3} > 0. If {0 < \lvert x - 1 \rvert < \delta} then \lvert 3x - 3 \rvert = 3\lvert x - 1 \rvert < 3\delta = \varepsilon.
- The swapped statement says some \delta > 0 meets every tolerance. Given any such \delta, take \displaystyle x = 1 + \frac{\delta}{2}, which is within \delta of 1 and is not 1, and \varepsilon = \delta. Then \displaystyle \lvert 3x - 3 \rvert = \frac{3\delta}{2}, which is not less than \delta because \delta > 0. So no \delta works.