Section 6.2 Negation of quantifiers
This last example brings us to the negation of quantifiers. This isn’t difficult, but we should still be careful. Consider the statement
\begin{equation*}
\forall n \in \mathbb{N}, n^2+1 \text{ is prime}.
\end{equation*}
In order for this to be true, we require that no matter which natural number \(n\text{,}\) the number \(n^2+1\) is prime.
- \(n=1\)
\(1^2+1 = 2\) which is prime.
- \(n=2\)
\(2^2+1 = 5\) which is prime.
- \(n=3\)
\(3^2+1 = 10 = 2 \times 5\) is not prime.
Since it fails when \(n=3\text{,}\) the statement is false.
Think carefully about what we have actually done here. We showed that this statement is false, by demonstrating that we could find \(n\in\mathbb{N}\) so that \(n^2+1\) is not prime. That is, we proved that the statement
\begin{equation*}
\exists n \in \mathbb{N} \st n^2+1 \text{ is not prime}
\end{equation*}
is true. What we are really doing here is proving that our original statement is false, by demonstrating that the negation of that statement is true.
Now consider the statement
\begin{equation*}
\exists n \in \mathbb{N} \st n^2 \lt n
\end{equation*}
You can convince yourself that this is false just by plugging in a few numbers or by drawing some graphs. However convincing is not the same as proving. In order for this to be false, we need to show that no matter which \(n \in \mathbb{N}\) we choose, \(n^2 \geq n\text{.}\) That is, we have to show that
\begin{equation*}
\forall n \in \mathbb{N}, n^2 \geq n.
\end{equation*}
We’ll do that shortly. But again, we are showing that the original is false by proving the negation to be true.
Notice that our first statement was
\begin{equation*}
\forall n \in \mathbb{N}, P(n)
\end{equation*}
and we showed that it was false by proving that
\begin{equation*}
\exists n \in \mathbb{N} \st \neg P(n)
\end{equation*}
is true. And similarly, our second statement was
\begin{equation*}
\exists n \in \mathbb{N} \st Q(n)
\end{equation*}
and to prove it false, we have to show that
\begin{equation*}
\forall n \in \mathbb{N}, \neg Q(n)
\end{equation*}
is true.
More generally, when we negate a “for all” we get “there exists” and when we negate “there exists” we have “for all”. This is a very important result and we’ll summarise it by a theorem.
Theorem 6.2.1.
Let \(P(x)\) be an open sentence over the domain \(A\text{,}\) then
\begin{align*}
\neg(\forall x \in A, P(x)) & \quad \equiv \quad \exists x\in A \st \neg(P(x))\\
\neg(\exists x \in A \st P(x)) & \quad \equiv \quad \forall x\in A, \neg(P(x))
\end{align*}
Note that the negated statement still has the same domain.
Let us do a couple of simple examples and we’ll get to more difficult ones in the next section.
Example 6.2.3.
Determine whether or not the following statements are true or false and then prove your answer.
\(\exists n \in \mathbb{Z} \st \frac{n+7}{3} \in \mathbb{Z}\text{.}\)
\(\exists n \in \mathbb{Z} \st \frac{n^2+1}{4} \in \mathbb{Z}\text{.}\)
Solution.
We tackle each in turn.
-
This is true. It suffices to find one example of an integer \(n\) so that \(\frac{n+7}{3}\) is an integer. Our proof just has do that — notice that it does not have to say how we found the example, just demonstrate that it works.
Proof.
The statement is true. Let \(n=2\text{.}\) Then \(\frac{n+7}{3} = \frac{9}{3} = 3 \in \mathbb{Z}\) as required.
-
This is a little harder. Notice that the statement is really saying that \(n^2+1\) is divisible by 4. Try a few values of \(n\text{:}\)
\begin{align*}
n=1: \amp \frac{1^2+1}{4} = \frac{2}{4}=\frac{1}{2}
\amp
n=2: \amp \frac{2^2+1}{4} = \frac{5}{4}\\
n=3: \amp \frac{3^2+1}{4} = \frac{10}{4}=\frac{5}{2}
\amp
n=4: \amp \frac{4^2+1}{4} = \frac{17}{4}
\end{align*}
Not looking promising. Notice it fails both when \(n\) is even and \(n\) is odd. We can use that to form our proof. Now, we don’t directly prove the statement is false, instead we prove the negation is true. So we can start our proof by saying just that.
Proof.
The statement is false; we demonstrate this by proving the negation to be true. The negation is
\begin{equation*}
\forall n \in \mathbb{Z}, \frac{n^2+1}{4} \not\in \mathbb{Z}
\end{equation*}
Assume \(n \in \mathbb{Z}\text{,}\) then \(n\) is either even or odd.
When \(n\) is even, we can write \(n=2k\) for some integer \(k\text{.}\) Then \(n^2+1 = 4k^2+1 = 4(k^2)+1\text{.}\) Hence \(n^2+1\) is not divisible by 4.
On the other hand, when \(n\) is odd, we can write \(n=2k+1\) for some integer \(k\text{.}\) Then \(n^2+1 = 4k^2+4k+2 = 4(k^2+k)+2\text{.}\) Hence \(n^2+1\) is not divisible by 4.
In either case \(\frac{n^2+1}{4}\) is not an integer. Since the negation is true, the original statement is false.
Example 6.2.4.
Determine whether or not the following statements are true or false and then prove your answer.
\(\forall n \in \mathbb{Z}, \frac{n^2+n}{2} \in \mathbb{Z}\text{.}\)
\(\forall n \in \mathbb{Z}, n^2-8n+1 \lt 0 \text{.}\)
Solution.
We tackle each in turn.
-
This one is quite similar to the second statement in the previous example. It is actually true, and we can leverage the parity of \(n\) to get the result we need.
Proof.
The statement is true. Let \(n \in \mathbb{N}\text{,}\) then \(n\) is even or odd.
When \(n\) is even, \(n=2k\) for some \(k \in \mathbb{Z}\text{.}\) Hence \(n^2+n = 4k^2+2k = 2(2k^2+k)\) and so is even.
When \(n\) is odd, \(n=2k+1\) for some \(k \in \mathbb{Z}\text{.}\) Hence \(n^2+n = 4k^2+6k+2 = 2(2k^2+3k+1)\) and so is even.
Since in both cases \(n^2+n\) is even, it is divisible by 2. The result follows.
Alternatively, we might try to prove the result by noticing that \(n^2+n = n(n+1)\) is the product of successive integers. Hence one if \(n, n+1\) must be even, and the product of any integer and an even number is even, so the result must be even. That would work, excepting that we have not actually proved that “product of any integer and an even number is even”. Its not a hard result, but we should prove it before using it.
-
If we just try plugging in a few small integers, the result holds. However, we know that \(n^2\) gets bigger much faster than \(n\) does, so the result should be false when \(n\) is big. Consequently we can show it is false by just plugging in a sufficiently large value of \(n\text{.}\)
Proof.
The result is false. We prove that the negation is true. The negation is
\begin{equation*}
\exists n \in \mathbb{Z}, n^2-8n+1 \geq 0.
\end{equation*}
Let \(n=10\) then \(n^2-8n+1 = 100-80+1 = 21 \geq 0\) as required. Since the negation is true, the original statement is false.
