Proof by contradiction

Proof by contradiction is a popular proof technique. If we want to prove that some statement is true, we negate it, assume that its negation is true and try to reach a contradiction. The aim is to show that the assumption we chose leads to something absurd.

A trivial example

Take the statement “there is no smallest positive rational number”. We prove this by contradiction by first negating the statement: “there is a smallest positive rational number”, and we call this number q. If q is the smallest positive rational number, then we cannot find a smaller positive rational number, because then q would not be the smallest.

We use this when looking for the contradiction. If we do manage to find a number smaller than q, which we can choose freely, then we have reached a contradiction and the negated statement is false. If we choose, say, 0.1 as the smallest number, we see that 0.01 is smaller. Then 0.001 is smaller still, 0.0001 is smaller again, and so on. We only need to divide q by ten to get a smaller number. In fact we can divide it by any number greater than one, such as two: half of q is certainly smaller than q itself.

So the number q/2 is certainly smaller than q, and it is also a positive rational number. This contradicts the negated statement, so the negated statement is false, and therefore the original, un-negated statement is true.

Interesting numbers

A classic joke proof that illustrates the principle of contradiction is the following example. Suppose that there are positive integers that are interesting in some way. For example, the number 2 is interesting because 2 · 2 = 2 + 2, which is quite an unusual property. The number 42 is interesting because it is the answer to everything. And so on. The question is: are there infinitely many interesting numbers?

Suppose the opposite, that is, that there are only finitely many interesting numbers and some numbers are uninteresting. We collect these uninteresting positive integers into a set of uninteresting numbers. Now we pick the smallest uninteresting number. Wait, the smallest uninteresting number? That sounds rather interesting, doesn’t it? :-)

That is a contradiction, because the smallest uninteresting number is in fact quite interesting, so there cannot be a smallest uninteresting number, and therefore the set of uninteresting numbers must be empty.

This is of course nonsense, since we have not properly defined what an interesting number is, but the method of proof itself is sound.

Proof that there are infinitely many primes

In this example we will use a similar approach to the previous section, but this time it will be correct in every respect.

A prime number is a number divisible by only two different numbers: itself and one. Note that one does not satisfy the definition and two does.

Prime factorisation is the decomposition of a positive integer, other than one, into a product of prime numbers. It is quite an interesting property of the positive integers. Whichever positive integer you take (apart from that one), it can be written as a product of several (possibly equal) primes. Examples:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

The statement about prime factorisation is called the fundamental theorem of arithmetic. Among other things, it tells us that such a factorisation is unique, that is, we will not find two different prime factorisations of one positive integer. It also says that only primes have a prime factorisation consisting of a single number, namely themselves. So the prime factorisation of seven would be the number seven. We will use these facts when constructing the proof of the following statement.

Now we prove the statement “there are infinitely many primes”. Again we negate the statement: “there are finitely many primes”. Suppose that the sequence of numbers

$$a_1,a_2,a_3,\dots ,a_n$$

represents all the primes that exist. If this sequence contains all the primes, then we certainly will not be able to find a number that is prime and is not in this sequence. All the primes are in the sequence, and no prime may occur outside it.

If we want to reach a contradiction, we therefore have to construct a prime that is not in this sequence. The number q will help us with this. We construct it by multiplying all the primes in the sequence together and adding one:

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

Now we have to show that this number either is a prime or somehow generates a prime. We know that q is a positive integer and that every positive integer can be expressed as a product of primes. However, no prime a_i divides q exactly; there is always a remainder of one. If we tried to divide q by, say, the prime a₂, it would go like this:

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

First we split the fraction into two. In the first fraction we cancel a₂ and are left with some product of primes, which is just some other, unimportant integer. In the second fraction there is nothing to cancel, and this fraction will always be a non-integer (because the denominator cannot be one, as one is not a prime). The sum is therefore a number that is not an integer, so the prime a₂ does not divide q.

So we have proved that none of the primes in the sequence a_n divides q. (Note: we showed this only for a₂, but it is easy to generalise by replacing a₂ with a general a_i.) But since every positive integer can be factorised into a product of primes, there must be other primes, not in the sequence a_n, that make up the factorisation of q. The number q itself may well be a prime, in which case the prime factorisation consists of q alone. So here is the final train of thought once more:

1. Every positive integer can be expressed as some product of primes.
2. By assumption, the sequence a_n contains all the primes that exist.
3. We rephrase the first statement: every positive integer can be expressed as a product of selected terms of the sequence a_n, because it contains all the primes.
4. We have proved that no number from the sequence a_n divides q.
5. This contradicts the assumption → if we must be able to factorise every positive integer into a product of primes, and the sequence a_n contains no number that divides q, then there must be other primes that divide q and make up the prime factorisation of q.

This is the contradiction. The prime factorisation of q includes primes that are not contained in the sequence that we assumed to contain all the primes. So the negated statement is false, and the original statement is true. There are infinitely many primes.