Home page for accesible maths 3 Mathematical proofs 3.3 Proof by contraposition 3.5 Counterexamples

Style control - access keys in brackets

Font (2 3) - + Letter spacing (4 5) - + Word spacing (6 7) - + Line spacing (8 9) - +

3.4 Proof by contradiction

The final proof technique which we shall cover — proof by contradiction — is the least intuitive. It is based on the conclusion of Example 2.3.8: for any statement variables $p$ and $q$ , the statements ‘‘ $\neg(p\Rightarrow q)$ ’’ and ‘‘ $p\ \&\ (\neg q)$ ’’ are logically equivalent. In other words, negating both statements, we see that ‘‘ $p\Rightarrow q$ ’’ is logically equivalent to ‘‘ $\neg\bigl(p\ \&\ (\neg q)\bigr)$ ’’. Thus, to prove ‘‘ $p\Rightarrow q$ ’’, we may instead show that the statement ‘‘ $p\ \&\ (\neg q)$ ’’ is false. We achieve this by showing that the assumption that $p$ and $\neg q$ are both true leads to a contradiction (that is, a statement which is clearly false). Some examples will (hopefully) clarify this; further examples will be given later in the course.

Example 3.4.1

We saw in Example 2.4.4(iv) that the statement ‘‘there is a rational number which is greater than every natural number’’ can be written $(\exists\,r\in\mathbb{Q})(\forall n\in\mathbb{N})(r>n),$ and we claimed that this statement is false. To verify our claim, we must show that its negation is true. Now $\neg\bigl((\exists\,r\in\mathbb{Q})(\forall n\in\mathbb{N})(r>n)\bigr)$ is logically equivalent to $(\forall r\in\mathbb{Q})\bigl(\neg\bigl((\forall n\in\mathbb{N})(r>n)\bigr)\bigr)$ which can be written ‘‘ $p\Rightarrow q$ ’’, where $p$ represents the statement $r\in\mathbb{Q}$ , while $q$ stands for $\neg\bigl((\forall n\in\mathbb{N})(r>n)\bigr).$

We prove this by contradiction; that is, we assume that $p$ and $\neg q$ are both true and seek a contradiction. Our assumptions state that $r\in\mathbb{Q}$ and $(\forall n\in\mathbb{N})(r>n)$ after cancellation of the double negation. We see that $r>1$ , so that $r=k/m$ for some integers $k>m\geqslant 1$ . Let $n=k+1\in\mathbb{N}$ . Then

n>k\geqslant k/m=r

which contradicts our assumption that $r>n.$ Thus $p$ and $\neg q$ cannot both be true, so if $p$ is true, then $\neg q$ must be false, that is, $q$ is true. Hence the implication ‘‘ $p\Rightarrow q$ ’’ is always true, as required. $\Box$

Example 3.4.2

The number $\sqrt{2}$ is irrational.

Proof. Recall that, by definition, $x=\sqrt{2}$ is the unique positive real number such that $x^{2}=2$ . Therefore, what we seek to prove can be rephrased as

\bigl(\bigl(x\in(0,\infty)\bigr)\ \ \&\ \ (x^{2}=2)\bigr)\ \ \Rightarrow\ \ (x% \notin\mathbb{Q}).

To give a proof by contradiction of this statement, we assume that

\bigl(x\in(0,\infty)\bigr)\ \ \&\ \ (x^{2}=2)\ \ \&\ \ \neg(x\notin\mathbb{Q}),

that is, $(x\in(0,\infty))$ & $(x^{2}=2)$ & $(x\in\mathbb{Q})$ . We can then write $x=a/b$ , where $a,\,b\in\mathbb{N}$ . After cancellation of any factors that $a$ and $b$ have in common, we may suppose that $a$ and $b$ have no common factors (except $\pm 1$ ). Squaring both sides of the equation $x=a/b$ , we obtain $2=x^{2}=a^{2}/b^{2}$ , so that $a^{2}=2b^{2}$ . This shows that $a^{2}$ is even (since $2b^{2}$ is clearly even), but then $a$ must be even (since odd times odd is odd), say $a=2c$ for some $c\in\mathbb{N}$ . Thus, we have

2b^{2}=a^{2}=(2c)^{2}=4c^{2}.

Dividing both sides of this equation by $2$ , we obtain $b^{2}=2c^{2}$ , so that $b^{2}$ is even (since $2c^{2}$ is clearly even), and thus $b$ is even as before. In conclusion, we see that $a$ and $b$ are both even, so $2$ is a common factor of $a$ and $b$ , contradicting the assumption that they have no common factors. This contradiction proves that $x\notin\mathbb{Q}.$ $\Box$