Proof by Contradiction

In this section, we will learn about using contradiction for mathematical proofs. Proof by contradiction is a method of proof where you first assume the claim you wish to prove is false, and then prove through a series of logical deductions that this assumption results in a contradictory claim. If this happens, and we have made no errors, this assumption that the claim was false must have been incorrect. Thus, the claim must be true.

While this idea may make sense abstractly and we see the proof method is confirmed by formal logic, the authors believe the method is best demonstrated by examples if you hope to build some intuitive understanding of the approach, learn when it is likely to be effective, and construct your own mathematical proofs.

First, let's review some ideas we all probably learned in primary school. Recall a real number x is called rational if it can be written as a ratio:

Here, a and b ≠ 0 are relatively prime integers—that is, numbers who share no common factors or only a common factor of 1—a and b may be negative or positive whole numbers, and a could be 0. For example, the following numbers are rational:

Of these rational numbers, note that only one of these numbers, five-sevenths, is actually written as a ratio of two relatively prime numbers. The keywords in the definition of rational numbers are that they can be written in this way. Note that all the numbers listed can be written this way, meaning they are in fact rational numbers:

Figure 2.10 – Each of the rational numbers can be written as a ratio of two relatively prime integers

It would not be unexpected if your first question is "Are there any numbers that cannot be written as a fraction?" The answer is certainly yes, but the great ancient Greek mathematicians such as Pythagoras and Euclid debated this question for centuries before it was settled that, in fact, there are numbers that cannot be written as such a ratio. So, this is a good question, and you are in good company if you thought to ask it!

Let's see a couple of examples related to rational numbers.

Example – is there a smallest positive rational number?

The problem here is simple to state: is there a smallest positive rational number? But how can we tackle this? It seems unlikely that we could create a tiny number and somehow claim it is the smallest possible one, although it is also not clear that we can say there isn't such a number. Since no direct path to a proof seems obvious, let's try to prove there is no such number by proof by contradiction.

Suppose x is the smallest positive rational number. Since it is rational, we can write the following:

Here, a and b are relatively prime integers, both of which have the same sign since x is positive. If we divide x by 2, we get a smaller number:

This number is still positive as no signs have changed. b is a nonzero integer, so 2b is also a nonzero integer of the same sign. Therefore, y is a positive rational number that is less than x. This contradicts the assumption that x is the smallest integer. Thus, if you give me any rational number, I can always give you a smaller one by dividing it by 2, so there is no smallest positive rational number.

This was a nice, simple example of proof by contradiction, but let's try another one that is pretty simple in principle, but probably not at all obvious.

Example – Prove is an Irrational Number

In this example, we will prove the square root of 2 is irrational, which should put this question to rest. In other words, we will prove the square root of 2 is not rational. We will set up a proof by contradiction.

First, assume the square root of 2 is rational. Therefore, by definition, there exist relatively prime numbers a and b where we have the following:

But if we square both sides of the equation, we find the following:

Since b is an integer, so is b2, so a2 is two times an integer, which means a2 is a multiple of 2—in other words, a2 is an even number. As we have proven previously, this means a must be an even number, so there is an integer n where a = 2n, so we can rewrite the preceding equation as follows:

Therefore, b2 is an even number, which we have shown implies b is an even number.

We have shown both a and b are even numbers, so they share a factor of 2, meaning they are not relatively prime integers. We previously assumed the square root of 2 was rational and could be written as the ratio of relatively prime integers a and b. Then, the assumption that the square root of 2 is irrational leads to a contradiction that a and b both are and are not relatively prime integers.

Next is a famous example of proof by contradiction regarding prime numbers used by Euclid in approximately 300 BCE. It is actually one of the first known uses of proof by contradiction.

Example – How Many Prime Numbers Are There?

A prime number is a positive integer greater than 1 that is only divisible by 1 and itself. The first few prime numbers are 2, 3, 5, 7, and 11. Note that the numbers we skipped have divisors other than 1 and the number itself. Clearly, 4, 6, 8, and 10 are divisible by 2 and, indeed, all even numbers except 2 will be prime. 9 is an odd number, but it is not prime since it is divisible by 3.

The prime numbers are sometimes called the building blocks of the positive integers because all positive integers can be written as a product of a unique set of prime numbers, called its prime factorization. Take the following example:

Indeed, no matter how large the initial number, this can be done! Another example is the following:

Once again, this is made up entirely of prime factors. In each case, the numbers cannot be broken down into smaller factors, so these factorizations are unique.

The result is now called the fundamental theorem of arithmetic. But interest in primes goes back to at least ancient Egypt. The Rhind Mathematical Papyrus is an Egyptian artifact dating to 1500 BCE with some computations with primes! But we know much more about the work of ancient Greeks mathematicians with primes. They were quite intrigued by prime numbers. In fact, Euclid proved prime factorizations are unique for all numbers in approximately 300 BCE. A question that arose millennia ago was: "How many prime numbers are there?" According to Euclid, there are infinitely many. But how could he know that? Dealing with infinity can be subtle, so it seems impractical to attempt to prove this directly. In such a situation, where a direct path to a proof seems difficult, proof by contradiction is one of the tools in the toolbox of a seasoned mathematician. Let's try it!

Assume there are finitely many prime numbers. Without loss of generality, suppose the number of primes is a finite positive integer m and let's name all primes p1, p2, …, pm. Let n be a number equal to the product of all the primes plus 1:

This means n – 1 is divisible by p1, p2, …, pm—that is, all of the primes. Each prime number is greater than 1 by definition. Therefore, dividing n by any prime number would have a remainder of 1. Therefore, n is not divisible by any of these prime numbers.

By Euclid's fundamental theorem of arithmetic, all positive integers have a unique prime factorization, so there must be another prime number not in our set. This contradicts the assumption that there are m primes, which was an arbitrary choice of number, so the assumption that there are finitely many primes leads to this contradiction. Hence, the opposite must be true: there are infinitely many primes.

Now, this has completed the proof, but let's zoom in on one point. We said m was an arbitrary choice, which led to the conclusion we made previously. However, this point is not too obvious to the uninitiated.

Let's think about this. If we assumed there were m primes, we concluded there are at least m + 1 prime numbers. Say we repeat this argument with the following:

We will conclude there are at least m + 2 primes, and this could go on forever! No matter how many primes there are, we have proven there is at least one more!

In this section, we learned about proving by contraction and applied this idea to a few examples.

In the next section, we will learn about proving by induction.