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 $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⁴⁴ 4 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.

⁵⁵ 5 This proof also works for other values, for example

\sqrt{3}

\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

\frac{p}{q}

(6.14)

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

\sqrt[]{2}=\frac{p}{q}

(6.15)

Which implies that

2p^{2}=q^{2}

(6.16)

As if the square of any integer is even, the integer itself must be even ⁶⁶ 6 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

\sqrt[]{2}=\frac{2a}{q}

(6.17)

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

	$\displaystyle\sqrt[]{2}=\frac{2a}{q}$		(6.18)
	$\displaystyle 2=\frac{4a^{2}}{q^{2}}$		(6.19)
	$\displaystyle q^{2}=2a^{2}$		(6.20)

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.

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, $\left\{p_{1},p_{2},p_{3},...,p_{n}\right\}$ (where $p_{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:=\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 $\left\{p_{1},p_{2},p_{3},...,p_{n}\right\}$ . This means that this number must divide both $\left\{p_{1}\right\}\cdot\left\{p_{2}\right\}\cdot\left\{p_{3}\right\}\cdot...% \cdot\left\{p_{n}\right\}$ and $P$ , so it must also divide the difference (i.e. it must divide $1$ ), however, the smallest prime is $2$ which does not divide $1$ . 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.

$\Box$

6.4 Proof by contradiction

6.4.1 Proof that 2\sqrt{2} is irrational

Example 6.4.1

6.4.2 Proof that there are infinitely many primes

Example 6.4.2

6.4.1 Proof that $\sqrt{2}$ is irrational