Proof by contradiction

Proof by contradiction is a popular proof technique. If we want to prove that a statement is true, we assume that it is true, then we negate it and try to arrive at a disagreement. The goal is to prove that our chosen assumption leads to some nonsense.

A trivial example

Consider the statement "there is no smallest positive rational number". We can prove this statement by disputation by first negating the statement "there is a smallest positive number" and labeling this number q. If q is the smallest positive rational number, then we are unable to find a smaller positive rational number - because then q would not be the smallest.

We will use this to find a contradiction. If we do find a number that is smaller than q, which we can choose arbitrarily, then we have reached a contradiction and the original statement is not valid. If we choose, for example, 0.1 as the smallest number, we see that 0.01 is smaller. Next, 0.001 is even smaller, 0.0001 is smaller again, and so on. Just divide the given number q by ten and we get a smaller number. In fact, just divide it by any number that is greater than one, such as two - half of the number q will certainly be smaller than the whole number q.

Thus, the number q/2 is certainly smaller than q, and it is also a positive number. This brings us to a conflict with the negated statement, i.e. the negated statement is not valid and hence the original non-negated statement is valid.

Interesting numbers

A classic funny proof that illustrates the principle of contradiction is the following example. Suppose there are natural numbers that are interesting in some way. For example, the number 2 is interesting because it is true that 2 · 2 = 2 + 2, this is a rather untypical 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?

Let's assume the opposite, i.e. that there are only finitely many interesting numbers and some numbers are uninteresting. We arrange these uninteresting natural numbers into a set of uninteresting numbers. Now we choose the smallest uninteresting number. Wait, the smallest uninteresting number? That sounds pretty interesting, doesn't it? :-)

This brings us to a contradiction, because the smallest uninteresting number is actually quite interesting, so there can't be a smallest uninteresting number, thus the set of uninteresting numbers must necessarily be empty.

Of course this is nonsense, we don't have a proper definition of what an interesting number is, but the proof procedure itself is fine.

The proof of the infinity of prime numbers

In this example, we will show a similar procedure to the previous section, but this time it will be correct on all counts.

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

Prime number decomposition, or factorization, is the decomposition of a natural number, other than one, into a product of primes. It's quite an interesting property of natural numbers. Whatever natural number you take (except the one), it is true that it can be decomposed into the product of several (even the same) prime numbers. Examples:

$$\begin{eqnarray} 8&=&2\cdot2\cdot2\\15&=&3\cdot5\\26&=&2\cdot13\\1800&=&2^3\cdot3^2\cdot5^2 \end{eqnarray}$$

The statement about prime number decomposition is called the Fundamental Theorem of Arithmetic. Among other things, it tells us that such a decomposition is unique, i.e., we cannot find two different prime decompositions of a single natural number. Further, only prime numbers have a prime decomposition consisting of only one number - themselves. Thus, the prime decomposition of seven would be the number seven. We will use these facts in constructing the proof of the following statement.

We will now prove the statement that "there are infinitely many prime numbers". We will again invalidate the claim: "there are a finite number of prime numbers". Suppose that a sequence of numbers

$$a_1, a_2, a_3,,\ldots,a_n$$

represents all the primes in existence. If all the primes are in this sequence, then surely we will not be able to find a number that is both a prime and not in the sequence. We have all the primes in the sequence, no primes can be outside the sequence.

So if we want to reach a contradiction, we have to construct a prime number that is not in the sequence. The number q helps us to do this. We build this by multiplying all the primes in the sequence and adding one:

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

Now we need to show that this number either is a prime or somehow generates a prime. We know that q is a natural number and that every natural number can be expressed as a product of primes. However, no prime number a_i divides the number q without remainder, always leaving one after division. If we tried to divide the number q by, for example, the prime number a₂, we would end up with the following:

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

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

We first divide the fraction into two. In the first fraction, we truncate a₂ and are left with some product of primes, which is simply some other irrelevant integer. In the second fraction there is nothing to truncate, this fraction will always be some non-integer (because the denominator cannot be one, one is not a prime number). So in the sum we get a number that is not an integer, i.e. the prime a₂ does not divide the number q.

This proves that none of the primes in the sequence a_n divide the number q. (Note: we have shown this only for a₂, but it can be easily generalized if we replace a₂ with the general a_i) But since every natural number can be decomposed into a product of primes, there must be other primes that are not in the sequence a_n, but are factorizations of q. Yet the number q itself may well be a prime number, and the prime decomposition will thus involve only the number q. So one last train of thought:

1. Every natural number can be expressed as some product of prime numbers.
2. By assumption, the sequence a_n contains all existing primes.
3. Let's modify the first statement to say that every natural number can be expressed as the product of selected members of the sequence a_n, since it contains all primes.
4. We have proved that no number in the sequence a_n divides the number q.
5. This raised a dispute with the assumption $\rightarrow$ if we must be able to decompose every natural number 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 are prime decompositions of q.

This brings us to a contradiction. The prime decomposition of q includes primes that are not contained in the sequence we have assumed contains all primes. Thus, the negated assertion does not hold, the unnegated original assertion does. There are infinitely many prime numbers.