A calculus of the absurd

6.4 Proof by contradiction

The key idea behind proof by contradiction (also known in Latin as reductio ad absurdum) is that we assume the opposite of what we’re trying to prove is true, and then show that this causes a “contradiction” (i.e. that a statement which is definitely false is true). This relies upon the fact that if we have two statements \(A\) and \(B\), where \(A\) is what we wish to prove is true, and \(B\) is definitely false, then if \(A\) were to be false would imply \(B\) must be true, because \(B\) must be false, \(A\) must be true⁴⁵⁴⁵ This is easier to prove using logic: we can write the statement as \((\lnot A \rightarrow B) \land \lnot B\), of which \(A\) is a logical consequence.

6.4.1 Proof that \(\sqrt {2}\) is irrational

Example 6.4.1 Prove that \(\sqrt {2}\) is irrational.

This proof also works for other values, for example \(\sqrt {3}\) or \(\sqrt {5}\).

To prove this, we start by writing down the definition of the rational numbers, which is that for any rational number we can write it in the form

\begin{equation} \frac {p}{q} \end{equation}

where both \(p\) and \(q\) are integers and the greatest common divisor of \(p\) and \(q\) is 1. To prove this we assume that \(\sqrt {2}\) is rational, and thus we can write that

\begin{equation} \sqrt []{2} = \frac {p} {q} \end{equation}

Which implies that

\begin{equation} 2p^2 = q^2 \end{equation}

As if the square of any integer is even, the integer itself must be even ⁴⁶⁴⁶ This is because if the integer was odd - i.e. we could write it in the form \(2k+1\), then the square would also be odd because \((2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\) which is one more than an even number and thus also odd. As the square is even, the integer must therefore also be even. we can write \(q=2a\) (for some suitable value of \(a\)). Therefore, we can write

\begin{equation} \sqrt []{2} = \frac {2a} {q} \end{equation}

Then we can square both sides and manipulate them a bit.

\begin{align} & \sqrt []{2} = \frac {2a} {q} \\ & 2 = \frac {4a^2} {q^2} \\ & q^2 = 2a^2 \end{align}

Therefore, \(q\) is also even! However, for a number to be rational, the greatest common divisor must be \(1\) - here the greatest common divisor is \(2\): we have derived a contradiction and \(\sqrt []{2}\) must be irrational.