4.5 Proof by contradiction

Consider the conditional statement ‘ $P\Rightarrow Q$ ’ and suppose we know that statement $Q$ is false. This situation can be represented by the Euler diagram in Figure 4.2. (See Section 3.2.4 if you need to remind yourself about this.)

Figure 4.2: Euler diagram showing ‘

P\Rightarrow Q

’ with

Q

false

We can deduce that statement $P$ must also be false, because it is not possible to place a dot outside $Q$ but inside $P$ . This is the key to the idea of a proof by contradiction: it is impossible to start with a true statement and deduce a false statement using valid logical deduction.

This means that we can prove a statement $P$ is true by showing that ‘not $P\Rightarrow F$ ’ for some statement $F$ that we know is false. As $F$ is false, ‘not $P$ ’ must also be false and so $P$ must be true. Such a proof of $P$ is called a proof by contradiction.

Example 4.23.

Let’s prove by contradiction that there is no integer that is both odd and even. This means that we should assume the negation is true and use that to deduce a statement that we know is false.

So, assume that there is some integer $a$ that is both even and odd. [Convince yourself that this is indeed the negation.] By definition (see Definition 2.6) this means we can write $a=2k$ and $a=2l+1$ for some integers $k$ and $l$ . This means that

	$\displaystyle a$	$\displaystyle=a$
$\displaystyle\Leftrightarrow$	$\displaystyle 2k$	$\displaystyle=2l+1$	(replacing $a$ )
$\displaystyle\Leftrightarrow$	$\displaystyle 2k-2l$	$\displaystyle=1$	(rearranging)
$\displaystyle\Leftrightarrow$	$\displaystyle\quad 2(k-l)$	$\displaystyle=1$	(factorising)
$\displaystyle\Leftrightarrow$	$\displaystyle k-l$	$\displaystyle=\tfrac{1}{2}$	(dividing both sides by $2$ ).

The statement $k-l=\tfrac{1}{2}$ must be false because $k$ and $l$ are integers and so $k-l$ must also be an integer. Every step of the argument is a valid logical deduction, and so the only statement involved that could be false (and must be false!) is the statement that there is some integer $a$ that is both even and odd.

Example 4.24.

We shall prove that there is no integer $n$ such that $n^{2}=2$ .

For a contradiction, assume that there is an integer $n$ with $n^{2}=2$ . Because $n^{2}$ is even then, by Exercise 4.21, $n$ must be even too. This means that there is an integer $k$ such that $n=2k$ . Therefore $n^{2}=(2k)^{2}=4k^{2}$ and so

		$\displaystyle 4k^{2}$	$\displaystyle=2$		(since $n^{2}=2$ )
	$\displaystyle\Leftrightarrow$	$\displaystyle\quad 2k^{2}$	$\displaystyle=1$		(dividing both sides by $2$ ).

Because $k^{2}$ is an integer, this last equation implies that $1$ is even (since it can be written as $2$ times an integer). This contradicts the fact that $1$ is not even (as discussed after Definition 2.6) and so our assumption that such an integer $n$ exists must be false.

Note that in these examples, we clearly stated what we were assuming and that these assumptions were ‘for a contradiction’. You should do this too – it will help the reader to understand the structure of your proof.

Exercise 4.25.

Prove that if $a$ and $b$ are positive integers then $a^{2}-b^{2}\neq 1$ .

Solution.For a contradiction, assume that $a$ and $b$ are positive integers and that $a^{2}-b^{2}=1$ . Then, by factorising the left-hand side, we have

$(a-b)(a+b)=1.$

As $a$ and $b$ are integers, so are $(a-b)$ and $(a+b)$ . Moreover, as $a$ and $b$ are positive, $(a+b)$ must also be positive. The only way two integers, one of which is positive, can multiply to give $1$ is if both are equal to $1$ , thus $a$ and $b$ must solve these equations simultaneously:

$\left\{\begin{array}[]{lr}a-b=1\\ a+b=1.\end{array}\right.$

Adding the two equations gives $2a=2$ and so $a=1$ . Putting $a=1$ in either equation gives $b=0$ . This contradicts our assumption that $b$ was a positive integer and so our assumption that $a^{2}-b^{2}=1$ must be false.