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 and , where is what we wish to prove is true, and is definitely false, then if were to be false would imply must be true, because must be false, must be true44 4 This is easier to prove using logic: we can write the statement as , of which is a logical consequence.
6.4.1 Proof that is irrational
Prove that is irrational.
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
where both and are integers and the greatest common divisor of and is 1. To prove this we assume that is rational, and thus we can write that
Which implies that
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 , then the square would also be odd because 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 (for some suitable value of ). Therefore, we can write
Then we can square both sides and manipulate them a bit.
Therefore, is also even! However, for a number to be rational, the greatest common divisor must be - here the greatest common divisor is : we have derived a contradiction and must be irrational.
6.4.2 Proof that there are infinitely many primes
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, (where 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 . 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 . This means that this number must divide both and , so it must also divide the difference (i.e. it must divide ), however, the smallest prime is which does not divide . 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.