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 \saycontradiction (i.e. that a statement which is definitely false is true). This relies upon the fact that if we have two statements AA and BB, where AA is what we wish to prove is true, and BB is definitely false, then if AA were to be false would imply BB must be true, because BB must be false, AA must be true44 4 This is easier to prove using logic: we can write the statement as (¬AB)¬B(\lnot A\rightarrow B)\land\lnot B, of which AA is a logical consequence.

6.4.1 Proof that 2\sqrt{2} is irrational

Example 6.4.1

Prove that 2\sqrt{2} is irrational.

55 5 This proof also works for other values, for example 3\sqrt{3} or 5\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

pq\frac{p}{q} (6.14)

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

2=pq\sqrt[]{2}=\frac{p}{q} (6.15)

Which implies that

2p2=q22p^{2}=q^{2} (6.16)

As if the square of any integer is even, the integer itself must be even 66 6 This is because if the integer was odd - i.e. we could write it in the form 2k+12k+1, then the square would also be odd because (2k+1)2=4k2+4k+1=2(2k2+2k)+1(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=2aq=2a (for some suitable value of aa). Therefore, we can write

2=2aq\sqrt[]{2}=\frac{2a}{q} (6.17)

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

2=2aq\displaystyle\sqrt[]{2}=\frac{2a}{q} (6.18)
2=4a2q2\displaystyle 2=\frac{4a^{2}}{q^{2}} (6.19)
q2=2a2\displaystyle q^{2}=2a^{2} (6.20)

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

6.4.2 Proof that there are infinitely many primes

Example 6.4.2

Prove that there is an infinite number of prime numbers.

Let us assume that there are not infinitely many primes. In that case, we can state that there is an ordered set (i.e. every element in the set is less than the previous element in the set) with a finite number of elements, {p1,p2,p3,,pn}\left\{p_{1},p_{2},p_{3},...,p_{n}\right\} (where pkp_{k} is the kth prime). If we multiply all the prime numbers together and add one to them, then we end up with a new number P:={p1}{p2}{p3}{pn}+1P:=\left\{p_{1}\right\}\cdot\left\{p_{2}\right\}\cdot\left\{p_{3}\right\}\cdot% ...\cdot\left\{p_{n}\right\}+1. This number must have a prime factor (as every number does - this is an assumption we make, which can be proved separately), which must be one of {p1,p2,p3,,pn}\left\{p_{1},p_{2},p_{3},...,p_{n}\right\}. This means that this number must divide both {p1}{p2}{p3}{pn}\left\{p_{1}\right\}\cdot\left\{p_{2}\right\}\cdot\left\{p_{3}\right\}\cdot...% \cdot\left\{p_{n}\right\} and PP, so it must also divide the difference (i.e. it must divide 11), however, the smallest prime is 22 which does not divide 11. Therefore, we have found a number which does not have prime factors (which is impossible!) This means we have found an absurdity, and there must be infinitely many primes.