3.3 Proof by contraposition

We saw in Example 2.3.7 that the statement ‘‘$p\Rightarrow q$’’ is equivalent to its contrapositive ‘‘$(\neg q)\Rightarrow(\neg p)$’’. Thus, to deduce $q$ from $p$, we may suppose that $q$ is false and then deduce from this that $p$ is false.

Proof. This follows because the contrapositive statement,

$$\neg(x<3)\Rightarrow\neg(x^{2}<9),\qquad\text{that is,}\qquad(x\geqslant 3)\Rightarrow(x^{2}\geqslant 9),$$

is clearly true, as we see by squaring both sides of the inequality $x\geqslant 3.$ $\Box$

Proof. In symbols, the statement is

$$(x+y\notin\mathbb{Q})\Rightarrow\bigl((x\notin\mathbb{Q})\ \text{or}\ (y\notin\mathbb{Q})\bigr).$$

Therefore the contrapositive statement is

$$\neg\bigl((x\notin\mathbb{Q})\ \text{or}\ (y\notin\mathbb{Q})\bigr)\Rightarrow\neg(x+y\notin\mathbb{Q})$$

which is logically equivalent to

$$\bigl((x\in\mathbb{Q})\ \&\ (y\in\mathbb{Q})\bigr)\Rightarrow(x+y\in\mathbb{Q}).$$

(3.3.1)

To prove (3.3.1), suppose that $x\in\mathbb{Q}$ and $y\in\mathbb{Q}$. Then we can write

$$x=\frac{a}{b}\qquad\text{and}\qquad y=\frac{c}{d}$$

for some $a,\,b,\,c,\,d\in\mathbb{Z}$ with $b,\,d\neq 0$, and consequently we have

$$x+y=\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}\in\mathbb{Q},$$

where $bd\neq 0$. Hence the statement on the right-hand side of (3.3.1) is true, as required. $\Box$

Proof. ‘‘$\Rightarrow$’’. Suppose that $n$ is a multiple of $3$, say $n=3m$, where $m\in\mathbb{Z}$. Then

$$n^{2}=(3m)^{2}=9m^{2}=3(3m^{2}),$$

so that $n^{2}$ is a multiple of $3$ because $3m^{2}\in\mathbb{Z}$.

‘‘$\Leftarrow$’’. We seek to prove that

$$(n^{2}\ \text{is a multiple of}\ 3)\ \Rightarrow\ (n\ \text{is a multiple of}\ 3)$$

which by contraposition can be rewritten as

$$(n\ \text{is not a multiple of}\ 3)\ \Rightarrow\ (n^{2}\ \text{is not a multiple of}\ 3).$$

To verify this, suppose that $n$ is not a multiple of $3$. Then either $n=3m+1$ or $n=3m+2$ for some $m\in\mathbb{Z}$. In the first case

$$n^{2}=(3m+1)^{2}=9m^{2}+6m+1=3(3m^{2}+2m)+1,$$

so $n^{2}$ is not a multiple of $3$. Similarly, in the second case,

$$n^{2}=(3m+2)^{2}=9m^{2}+12m+4=3(3m^{2}+4m+1)+1,$$

so again $n^{2}$ is not a multiple of $3$. $\Box$