2.4 Negations
Being able to negate statements is important for two reasons:
Instead of proving \(P\) is true, it might be easier to prove that \(\neg P\) is false (proof by contradiction).
Instead of proving \(P \implies Q\) it might be easier (by Theorem 2.8 ) to prove \(\neg Q \implies \neg P\) (proof by contrapositive).
We will expand on these two points later. We already know how to negate most simple statements, for example:
the negation of \(x = 5\) is \(x\neq 5\).
the negation of \(x > 5\) is \(x\leq 5\) (notice the strict inequality became unstrict).
the negation of \(x \in X\) is \(x\notin X\).
To negate simple statements that have been strung together, we use the following theorem.
Suppose \(P,Q\) are two statements. Then
\(\neg(P\wedge Q) \iff ((\neg P) \vee (\neg Q)).\)
\(\neg(P\vee Q) \iff ((\neg P) \wedge (\neg Q)).\)
\(\neg(P\implies Q)\iff (P\wedge (\neg Q)).\)
We will prove part a. and leave part b. and c. as exercises. We have the following truth table.
| \(P\) | \(Q\) | \(\neg P\) | \(\neg Q\) | \(P\wedge Q\) | \(\neg(P\wedge Q)\) | \((\neg P)\vee (\neg Q)\) |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| F | F | T | T | F | T | T |
□
If \(x\) is not between \(5\) and \(10\), then \(x\) is either less than \(5\) or more than \(10\). Formally speaking \(\neg(5\leq x\leq 10)\) if and only if \(\neg(5\leq x)\) or \(\neg(x\leq 10)\) if and only if \(x<5\) or \(10<x\).
For statements that involves quantifiers (i.e., \(\forall, \exists\)), we use the following theorem.
Let \(X\) be a set, and suppose that \(P(x)\) is a statement involving \(x\in X\). Then
\[\neg(\forall\ x\in X,\ P(x) )\quad \iff\quad \exists \ x\in X \text{ such that } \neg P(x).\]
We also have
\[\neg(\exists\ x\in X \text{ such that } P(x) )\quad \iff \quad \forall\ x\in X,\ \neg P(x).\]
Suppose that \(\forall\ x\in X, P(x)\) is a false statement. Then there must be at least one \(x\in X\) such that \(P(x)\) does not hold. That is, \[\begin{equation} \neg(\forall\ x\in X,\ P(x)) \quad \implies\quad \exists\ x\in X \text{ such that } \neg P(x). \tag{2.1} \end{equation}\]
Conversely, suppose that \(\exists\ x\in X \text{ such that } \neg P(x)\) is a true statement. Then it is not the case that \(P(x)\) holds for all \(x\in X\), that is \[\begin{equation} \exists\ x\in X \text{ such that } \neg P(x) \quad \implies\quad \neg(\forall\ x\in X,\ P(x)). \tag{2.2} \end{equation}\]
By (2.1) and (2.2), it follows that \[\neg(\forall\ x\in X,\ P(x) \quad \iff\quad \exists \ x\in X \text{ such that } \neg P(x).\]
Equivalently, we have \[\begin{align*} \neg(\neg(\forall\ x\in X,\ P(x)))\quad &\iff \quad\neg (\exists\ x\in X \text{ such that } \neg P(x))\\ &\iff \quad\forall\ x\in X,\ P(x). \end{align*}\] Setting \(Q(x)=\neg P(x)\), we have \[ \neg(\exists\ x\in X \text{ such that } Q(x) )\quad \iff \quad \forall\ x\in X,\ \neg Q(x). \]□
Let \(X\) be a set and let us negate the statement “\(\forall x \in X, P(x)\implies Q(x)\)”, by writing equivalent statements using Theorem 2.18 and Theorem 2.19.
\[\begin{align*} \neg(\forall x \in X, P(x)\implies Q(x)) &\ \iff &\ \exists x \in X \text{such that} \neg(P(x) \implies Q(x)) \\ &\ \iff &\ \exists x \in X \text{such that } (P(x) \wedge \neg Q(x)). \end{align*}\]
To make this more concrete, let \(P(x)\) be the statement \(x \in 2\mathbb{Z}\) and \(Q(x)\) the statement \(x \in 4\mathbb{Z}\). We have already shown that \(2\mathbb{Z} \nsubseteq 4\mathbb{Z}\), i.e. \(\forall x \in \mathbb{Z}, P(x) \implies Q(x)\) is false. We did this by showing when \(x=10\), \(P(x)\) is false while \(Q(x)\) is true, i.e., \(\exists x \in \mathbb{Z}\) such that \(P(x)\) is true and \(Q(x)\) is false.Negating statements is also very useful to see when an object does not satisfy a definition. We will see more examples of this later in the course, but for the moment here is an example.
Using (O2) as an example, a set \(X\) satisfies transitivity (with respect to \(<\) ) if for all \(x,y,z\in X\) if \(x<y\) and \(y<z\) then \(x<z\). Let us see what it means for \(X\) not to satisfy (O2). First we turn the definition into symbolic language \(\forall x,y,z \in X, (x<y)\wedge(y<z)\implies (x<z)\). We then negate this
\[\begin{align*} &\neg(\forall x,y,z \in X, (x<y)\wedge(y<z)\implies (x<z)) \\ \iff & \exists x,y,z \in X \text{ such that } \neg((x<y)\wedge(y<z) \implies (x<z)) \\ \iff & \exists x,y,z \in X \text{ such that } ((x<y)\wedge(y<z))\wedge \neg(x<z)) \\ \iff & \exists x,y,z \in X \text{ such that } (x<y)\wedge(y<z)\wedge (x\geq z). \end{align*}\]
□
To negate a statement with the quantifier \(\exists!\), it is useful to first translate this notation to not include “!”.
Suppose \(X\) is a set, and \(P(x)\) is a proposition dependent on \(x\in X\). When we say there is a unique \(x\in X\) so that \(P(x)\) holds we mean first that:
there is some \(x\in X\) so that \(P(x)\) is true, and
if we have \(x_1,x_2\in X\) with \(P(x_1)\) and \(P(x_2)\) are true, then \(x_1=x_2\).
More symbolically, we have \[\left[\exists!x\in X, P(x)\right] \iff \left[(\exists x\in X,\ P(x))\wedge(\forall x_1,x_2\in X,\ (P(x_1)\wedge P(x_2))\implies x_1=x_2)\right].\] So negating, we get: \[\begin{align*} &\neg\left[\exists!x\in X, P(x)\right]\\ &\iff \neg\left[(\exists x\in X,\ P(x))\wedge(\forall x_1,x_2\in X,\ (P(x_1)\wedge P(x_2))\implies x_1=x_2)\right]\\ &\iff \left[\neg(\exists x\in X,\ P(x))\vee\neg[(\forall x_1,x_2\in X,\ (P(x_1)\wedge P(x_2)\implies x_1=x_2)]\right]\\ &\iff \left[(\forall x\in X,\ \neg P(x))\vee[\exists x_1,x_2\in X,\ \neg(P(x_1)\wedge P(x_2)\implies x_1=x_2)]\right]\\ &\iff \left[(\forall x\in X,\ \neg P(x))\vee[\exists x_1,x_2\in X,\ (P(x_1)\wedge P(x_2)\wedge x_1\not=x_2)]\right]. \end{align*}\]
Thus the negation of exactly one \(x\) such that \(P(x)\) holds is “either there exists no \(x\) such that \(P(x)\) holds or there exists more than one \(x\) such that \(P(x)\) holds”