Section 6.3 Nested quantifiers
Example 6.3.1.
Rewrite the following using quantifiers, and then write out their negations.
Solution.
Translating the statements into symbols gives
\(\displaystyle \exists y \in \mathbb{R} \st 1/y=y+1\)
\(\displaystyle \forall z \in \mathbb{Z}, \exists w\in \mathbb{N} \st z^2 \lt w\)
The negations are then:
\begin{align*}
\neg( \exists y \in \mathbb{R} \st 1/y=y+1 )
\amp \equiv \forall y \in \mathbb{R} \st \neg( 1/y=y+1 )\\
\amp \equiv \forall y \in \mathbb{R} \st 1/y \neq y+1.
\end{align*}
and
\begin{align*}
\neg( \forall z \in \mathbb{Z}, \exists w\in \mathbb{N} \st z^2 \lt w )
\amp \equiv
\exists z \in \mathbb{Z} \st \neg( \exists w\in \mathbb{N} \st z^2 \lt w )\\
\amp \equiv
\exists z \in \mathbb{Z} \st \forall w\in \mathbb{N}, \neg( z^2 \lt w )\\
\amp \equiv
\exists z \in \mathbb{Z} \st \forall w\in \mathbb{N}, z^2 \geq w.
\end{align*}
Notice how we can slide the negation from left to right, and along the way \(\forall\) becomes \(\exists\) and \(\exists\) becomes \(\forall\text{.}\) And, of course, the domains are unchanged by negation.
The first statement is, in plain(er) english
You can pick some real number \(y\) to make \(1/y=y+1\text{.}\)
In writing it in this way, the authors have tried to take a mathematical statement into an exercise for the reader. “You — dear reader — can find (go on!) some real number \(y\) that has the property that \(1/y\) is equal to \(1+y\)”. Similarly, we can write the statement \(\forall z \in \mathbb{R}, z^2 \geq 0\) as
No matter which real number \(z\) you pick, \(z^2\) is non-negative.
Again, we have made this into an exercise for the reader. “You — dear reader — can pick any value of \(z\) you want, it will always turn out that \(z^2 \geq 0\text{.}\)” So far, nothing too controversial, but lets move on to the second example above since it contains nested quantifiers. But a warning first.
The second example above contains nested quantifiers. Let us work through it slowly and carefully by writing it as a task for the reader.
No matter which \(z \in \mathbb{Z}\) you pick, there is a choice of \(w \in \mathbb{N}\) so that \(z^2 \lt w\text{.}\)
This statement is true. To see why, we should think of it as a 2-player game. Player 1 picks any \(z\) they want, and Player 2 has to choose a value of \(w\) so that \(z^2 \lt w\text{.}\) Player 1 goes first and Player 2 goes second.
Player 1 picks some integer \(z\text{.}\)
Player 2 knows the value of \(z\) and can make their choice accordingly. With a little thought, Player 2 realises that choosing \(w = z^2+1\) will work nicely (though they should be careful to make sure their choice is from the correct domain).
This is then the basis for proving the statement is true.
Proof.
Let \(z \in \mathbb{Z}\text{.}\) Then choose \(w = z^2+1\text{.}\) Since \(z\in\mathbb{Z}\) we know that \(w\) is a positive integer and so \(w \in \mathbb{N}\text{.}\) Then \(z^2 \lt z^2+1 = w\text{.}\) Hence the statement is true.
What if we reverse the order of the quantifiers?
\begin{equation*}
\exists w \in \mathbb{N} \st \forall z \in \mathbb{Z}, z^2 \lt w.
\end{equation*}
Again, we translate this into an exercise for the reader
You can choose some \(w \in \mathbb{N}\text{,}\) so that no matter what integer \(z\) is then chosen, \(z^2 \lt w\text{.}\)
This is false. Player 1 now has to pick \(w\) first, and Player 2 picks \(z\) second. Player 1 knows nothing about what Player 2 is going to do. So Player 1 might think “I’ll pick a really big number, say \(w=100\)”, but then Player 2 knows this value of \(w\) and can just pick a large value of \(z\text{.}\)
The best way (arguably) to prove the statement false, is to show that its negation is true. So a disproof of the statement is just a proof of the negation of the statement. So write down the negation:
\begin{equation*}
\forall w \in \mathbb{N}, \exists z \in \mathbb{Z} \st z^2 \geq w.
\end{equation*}
and again write it as a task for the reader:
No matter which \(w\in \mathbb{N}\) you pick, there will always be some choice of \(z \in \mathbb{Z}\) so that \(z^2 \geq w\text{.}\)
Again, Player 1 goes first and Player 2 goes second. Player 1 knows nothing about what Player 2 will do, but Player 2 knows what Player 1 did.
Player 1 picks some \(w \in \mathbb{N}\text{.}\)
Player 2 knows the value of \(w\text{,}\) and then (after some thought) picks \(z=w+1\)
It is now sufficient to check that Player 2 has chosen \(z\) from the correct domain, and that \(z^2 = (w^2+2w+1) \geq w\) (which it is since \(w \geq 1\)).
Proof.
The original statement is false, so we prove the negation to be true. The negation is
\begin{equation*}
\forall w \in \mathbb{N}, \exists z \in \mathbb{Z} \st z^2 \geq w.
\end{equation*}
Let \(w \in \mathbb{N}\) and then choose \(z = w+1\text{.}\) Since \(w\in\mathbb{N}\text{,}\) we know that \(z \in \mathbb{Z}\text{.}\) Further since \(w \geq 1\) we know that
\begin{equation*}
z^2 = (w+1)^2 = w^2+2w+1 = (w^2+w+1) + w \geq w
\end{equation*}
as required. Since the negation is true, the original is false.
When students encounter nested quantifiers for the first time they typically find them quite difficult. They are quite difficult but they do become easier with practice. Accordingly, the following example is one of this author’s favourites. It, and its kin, have appeared on nearly every exam the author has given for this topic. The author’s students are likely to have chosen a different type of question as their favourite. We will provide lots of similar exercises for you — dear reader — to practice, so that any dislike of nested quantifiers can be dispelled.
Example 6.3.4.
Consider the following four statements:
\(\displaystyle \exists x \in \mathbb{R} \st \exists y \in \mathbb{R} \st xy=x+y \)
\(\displaystyle \exists x \in \mathbb{R} \st \forall y \in \mathbb{R} , xy=x+y\)
\(\displaystyle \forall x \in \mathbb{R}, \exists y \in \mathbb{R} \st xy=x+y \)
\(\forall x \in \mathbb{R}, \forall y \in \mathbb{R}, xy=x+y \text{.}\)
Determine the truth value of the following four statements and prove your answers.
We will work through the statements in order, thinking about them as two-player games as we did above. We will also drop “\(\in \mathbb{R}\)” from the quantifiers; the reader should understand, by context, that all our variables are selected from \(\mathbb{R}\text{.}\)
Finally — remember to be careful of the order of the quantifiers.
Scratchwork.
This is true.
Then \(xy = 0 = 0+0 = x+y\text{.}\)
-
Again think about the 2 players:
This feels unlikely to work because we can “solve” the equation for \(y\) to get \(y = \frac{x}{x-1}\text{.}\) That is, for any given \(x\)-value there is going be exactly one \(y\)-value. So it feels like it will likely be false.
To see that it is false, write down the negation:
\begin{equation*}
\forall x, \exists y \st xy \neq x+y.
\end{equation*}
Player 1 can choose any real number \(x\) they want.
Player 2 then has to be able to choose a real number \(y\) so that \(xy \neq x+y\text{.}\) A good choice is \(y=1\) (though there are infinitely many other good choices)
Now no matter what \(x\)-value, \(xy = x\) and \(x+y = x+1\text{,}\) and \(x \neq x+1\text{.}\) We just have to write it up.
-
This one is a bit tricky. Again, think about our two players.
Player 1 chooses whatever \(x\)-value they feel like.
-
Player 2 knows that value of \(x\) and based on that has to make a very careful choice of \(y\text{.}\) But that just requires Player 2 to solve \(x+y=xy\text{.}\) Easy!
\begin{align*}
x+y \amp=xy \\
y-xy \amp= -x \\
y \amp = \frac{-x}{1-x} = \frac{x}{x-1}
\end{align*}
All good? Not quite — things go wrong when \(x=1\text{.}\)
When \(x=1\text{,}\) our equation is \(y+1 = y\text{.}\) There is no real number \(y\) that makes that true.
So everything seemed fine until we considered \(x=1\text{.}\) So perhaps it is false?
You know the drill now; write down the negation and think about our two players:
\begin{equation*}
\exists x \st \forall y, xy \neq x+y.
\end{equation*}
Player 1 makes a single careful choice of \(x=1\)
Then no matter what \(y\)-value Player 2 chooses, \(xy = y\) and \(x+y=y+1\text{,}\) so \(xy \neq x+y\text{.}\)
So it is false. We just need to write out the proof.
This one is also false, and it is easy to see why from the negation:
\begin{equation*}
\exists x \st \exists y \st xy \neq x+y.
\end{equation*}
It suffices for Player 1 to pick \(x=1\text{,}\) and Player 2 to then pick \(y=1\text{.}\) Then \(xy = 1\) and \(x+y=2\text{.}\)
Proof of (a).
The statement is true. Pick \(x=y=0\) then \(xy = 0\) and \(x+y = 0\text{.}\)
We give two proofs of (b), depending on how we choose \(y\text{.}\)
Proof of (b).
We prove this to be false by showing the negation is true. The negation is
\begin{equation*}
\forall x, \exists y \st xy \neq x+y.
\end{equation*}
Pick any \(x \in \mathbb{R}\text{,}\) and then set \(y=1\text{.}\) Since \(xy = x\) and \(x+y = x+1\text{,}\) we have that \(xy \neq x+y\) as required. Since the negation is true, the original statement is false.
Another proof of (b).
The statement is false. Let \(x\) be any real number. Then either \(x=0\) or \(x \neq 0\text{.}\)
In both cases \(xy \neq x+y\) as required.
Proof of (c).
The statement is false. We prove the negation
\begin{equation*}
\exists x \st \forall y, xy \neq x+y.
\end{equation*}
is true. Pick \(x=1\text{,}\) then no matter what \(y\) is chosen, \(xy = y\) and \(x+y = y+1\text{,}\) and Consequently \(y \neq y+1\text{.}\) Since the negation is true, the original statement is false.
Proof of (d).
The statement is false. We prove the negation:
\begin{equation*}
\exists x \st \exists y \st xy \neq x+y.
\end{equation*}
Pick \(x=1\) and \(y=1\text{,}\) then \(xy=1\) and \(x+y=2\text{.}\) Since the negation is true, the original is false.
I hope the reader can see why the above example makes for a good exam question. It is a good mathematical and logical workout. With that in mind, we (and the author really means you) should do another one. But before we leap into another fun example, a quick warning about negating implications:
On with the fun!
Example 6.3.6.
Determine the truth value of the following four statements and prove your answers.
\(\displaystyle \exists x \in \mathbb{R} \st \exists y \in \mathbb{R} \st (y \neq 0) \implies xy=1\)
\(\displaystyle \exists x \in \mathbb{R} \st \forall y \in \mathbb{R}, (y \neq 0) \implies xy=1\)
\(\displaystyle \forall x \in \mathbb{R}, \exists y \in \mathbb{R} \st (y \neq 0) \implies xy=1\)
\(\displaystyle \forall x \in \mathbb{R}, \forall y \in \mathbb{R}, (y \neq 0) \implies xy=1\)
Remember that we must pick the value of \(x\) before we pick the value of \(y\) in every single case. You might find it helpful to write out the negations before deciding how to approach these.
Scratchwork.
-
As suggested, we’ll write out the negation:
\begin{equation*}
\forall x, \forall y, (y \neq 0) \land (xy\neq 1)
\end{equation*}
where we have dropped the “\(\in \mathbb{R}\)”, assuming the reader will understand by context.
Now, in order to make an implication true, we just have to make the hypothesis false and that is quite easy in this case. Pick any \(x\) you want and then choose \(y=0\text{.}\) That’s enough to make a proof (it also gives us a hint for one of the other statements).
-
Consider the original statement and what our two players have to do.
Player 1 has to choose some \(x\)
Now, no matter what Player 2 picks, the implication must be true.
Let us assume Player 1 has chosen some \(x\) we don’t know what it is yet, but let us assume they have chosen it. What can player 2 do to make the implication true. There are three ways to make it true: (hypothesis, conclusion) = (T,T), (F,T), (F,F). When Player 2 picks \(y=0\text{,}\) the hypothesis is false making the implication true. However, when they pick something else, the conclusion is only true when \(y=1/x\text{.}\) But this means for every other choice of \(y\text{,}\) the conclusion will be false. It really looks like this statement is false.
Time to think about the negation:
\begin{equation*}
\forall x, \exists y \st (y \neq 0) \land (xy \neq 1)
\end{equation*}
What do our players do?
Player 1 can pick whatever \(x\) they like, so they do.
Player 2 knows the value of \(x\) and so can choose \(y\) to make the conjunction true. In particular, if Player 1 picked \(x=0\text{,}\) then Player 2 can choose \(y=1\text{.}\) On the other hand, if Player 1 picked any other value of \(x\text{,}\) then Player 2 can choose \(y=-x\text{.}\)
In both cases, \(y\neq 0\) and \(xy =0\) or \(xy = -x^2 \neq 1\text{.}\) Now just write it up!
Think about our two players.
Since Player 2 can always make the hypothesis false, the implication is true.
-
Last one. Oof.
Again, let us think about our two players.
So, no matter what \(x\) was chosen, when Player 2 chooses \(y=0\text{,}\) the implication is true. But what about all the other choices? This feels unlikely.
Look at the negation:
\begin{equation*}
\exists x \st, \exists y \st (y \neq 0) \land xy \neq 1
\end{equation*}
Ah - this is much easier. Player 1 can choose \(x=0\) and Player 2 can choose \(y=1\text{.}\) Then \(y \neq 0\) and \(xy = 0 \neq 1\text{.}\) There are, many other choices that would also work.
Proof of (a).
The statement is true. Take \(x=0,y=0\text{.}\) Since the hypothesis is false, the implication is true.
Another proof of (a).
The statement is true. Take \(x=y=2\text{,}\) then the hypothesis and conclusion are both true, so the implication is true.
Proof of (b).
The statement is false, so we prove the negation:
\begin{equation*}
\forall x, \exists y \st (y \neq 0) \land (xy \neq 1)
\end{equation*}
Let \(x\) be any real number. Then either \(x = 0\) or \(x \neq 0\text{.}\)
If \(x=0\) then pick \(y=1\text{.}\) Then \(xy =0\)
On the other hand, if \(x \neq 0\) then pick \(y = -x\text{,}\) so that \(xy = -x^2\)
In both cases, \(y \neq 0\) and \(xy \neq 1\text{.}\) Since the negation is true, the original statement is false.
Another proof of (b).
We prove the negation. Let \(x\) be any real number. Either \(x=1\) or \(x \neq 1\text{.}\) If \(x=1\) then pick \(y=2\text{,}\) so that \(xy = 2\text{.}\) On the other hand, if \(x\neq 1\text{,}\) then pick \(y=1\) so that \(xy = x \neq 1\text{.}\) In both cases we have that \(y \neq 0\) and \(xy \neq 1\) as required. Since the negation is true, the original is false.
Proof of (c).
The statement is true. Let \(x\) be any real number and then choose \(y=0\text{.}\) Since the hypothesis is false, the implication is true.
Another proof of (c).
Let \(x\) be any real number. Either \(x = 0 \) or \(x \neq 0\text{.}\) If \(x = 0\) then pick \(y=0\) making the hypothesis false. On the other hand, if \(x \neq 0\) then set \(y = \frac{1}{x} \neq 0\text{.}\) In that case both the hypothesis and conclusion are true. In either case the implication is true.
Proof of (d).
We prove the negation:
\begin{equation*}
\exists x \st, \exists y \st (y \neq 0) \land xy \neq 1.
\end{equation*}
Pick \(x=0, y=1\text{.}\) Then \(xy = 0 \neq 1\) and \(y \neq 0\text{.}\) Hence the negation is true and the original statement is false.
