How to Write a Proof by Contradiction

There are many different methods one can use when trying to prove a mathematical statement, such as induction, using the contrapositive, or other direct proof methods. Today we discuss is known as a proof by contradiction and is an incredible tool to have in your tool kit. But you know what we are going to discuss since you clicked on the link to get here!

What is a Proof by Contradiction?

The basic idea is the following: When writing proofs,

If your starting assumptions are true and your logic is sound, then your conclusion must be correct.

If, on the other hand, information that you used in your proof happened to be false (even if you thought it was true), then your conclusion could be right or could be wrong. It’s like Schrödinger’s proof! Now say you did all the research and have a firm foundation of truth as your starting point, but then your logic is false or you make some logical leaps. You end up in the same place: your conclusion could be right or could be wrong.

This probably makes intuitive sense. There doesn’t seem to be anyway around this statement when regarding writing valid mathematical proofs.

The idea behind using a proof by contradiction is to exploit what we have just discussed.

Say you want to prove some statement using the method of a proof by contradiction, what you do first is to assume what you are trying to prove is false (this goes into our “assumptions are true” part of what we already discussed). Next, you use all your mathematical know how to find out what your assumption implies (this goes into our “logic is sound” part of what we already discussed). Finally, if you are able to prove something that you know to be incorrect, then something is amiss. As we already said: assumptions are true + logic is sound = correct conclusion. So if your conclusion was incorrect, then either your assumption was false, or your logic was flawed. But, since we made sure that our logic was still airtight, the only option is that our step: assume what you are trying to prove is false, was false. I.e. the statement we want to prove is not false, and hence true. Try saying that three times fast!

Let’s take this for a test drive:

Theorem: There are infinitely many positive integers.¹

Recall that the positive integers are the counting numbers like 1, 2, 3, …

I know what you’re thinking! You cannot get more obvious than saying there are infinitely many counting numbers! True, but the point was not to learn some new theorem, it’s to show you how to write a proof by contradiction.

Our recipe is to first assume that what we want to show is false. So, we will assume:

FALSE: There are infinitely many positive integers

TRUE: There are a finite number of positive integers

Now we want to use airtight logic to prove something incorrect. What might this be and how do we know where to start? This is where your creativity can shine! Math is a creative endeavor, and that makes it challenging to everyone, but it also is what makes it fun! What you will find is that you will need to try a lot of different things in order to find some contradiction. And this is great! It’s like a good video game level that you need to play a few times to win.

Ok, back to the proof at hand. Our starting point is that there are only a finite number of positive integers. If that’s true, what else must be true? Here are somethings that I came up with regarding the positive integers:

All the integers are spaced one apart.
To go from one counting number to the next, you only need to add 1 to it.
The positive integers have a smallest number in them and it’s 1 (this is called the principle of well-ordering)
If there are only finitely many positive integers, then there is also a largest number.

Could you think of anything else? Can you use what we wrote to find a contradiction? Let’s walk through it together. Have you ever been in a situation where you, or a classmate got into the argument:

kid #1: “I’m a million times better at this game than you!”

kid #2 “No I’m 1,000,001 times better than you!”

kid #1: “I’m 1,000,002 times better at this game than you!”

kid #2 “No I’m 1,000,003 times better than you!”

kid #1: “No, I’m infinity times better than you are!”

kid #2: “Oh yah! Well, I’m infinity plus 1 times better than you!”

etc.

Little did you know that you both were on the verge of using a proof by contradiction to demonstrate that the counting numbers go on forever!

But I want you to have a little fun, so see if you can use this to come up with a contradiction before you read on.

Proof: Let’s assume for the hope of a contradiction that there are only a finite number of positive integers. Then, there must be a largest integer, denoted by $N$ . Recall that $N+1$ is also a positive integer and that $N+1>N$ . This contradicts that we said $N$ was the largest integer! Thus, we have reached a contradiction since both of the following cannot be true:

$N$ is the largest integer and $N+1$ is an integer larger than $N$ .

Hence there are an infinite number of positive integers.

$\square$

Beautiful! But I bet you want to try to prove something deep in mathematics, not something as obvious as there being an infinite number of counting numbers! This is where the next theorem comes in.

A Beautiful Theorem due to Euclid

Theorem: There are infinitely many prime numbers.

This theorem was ranked 3^rd on the list of most beautiful math theorems, and we now have the tools to prove it as Euclid did back in 300 BC. His proof is considered to be one of the most beautiful in all of mathematics. But, since I’m not sure how much number theory you have under your belt, we will be relying on your intuition regarding prime numbers.

First, recall that a prime number $p$ is an integer whose factors are only $1$ and itself $p$ . For example, 2 and 3 are prime numbers but 10 is not prime since 10 has factors 2 and 5.

How might we prove that there are an infinite number of primes?

As you might guess, we will be assuming that there is only a finite number of primes. Let’s see if we can do something similar to what we did earlier when proving that there are an infinite number if counting numbers.

What helped us find a contradiction earlier? It was that we said we had a largest integer, $N$ , and we were able to find an integer, $N+1$ , that’s larger than $N$ . So, maybe if we can discover a way to generate primes from primes, we can reach a similar contradiction!

Since we are assuming that there are only a finite number of primes, let’s create a list of them. The key is that this list is finite. Our hope is to show that the list is incomplete somehow. Let’s consider some examples to help us discover what to do.

Imagine if the only prime numbers we knew of were:

“Complete” List of primes = 2, 3, 5, 7, and 11.

Our task is to use these primes to find a new prime not on our list. Let’s run through some of my initial thoughts.

What if we add all our primes together? Maybe we will land on a new prime number? Unfortunately, their sum is 28, and 28 is not a prime. Scratch this idea.

New idea, primes are connected to multiplication because they are defined in terms of what their factors are. Can we somehow use the primes on our list to make a new integer that doesn’t have the primes on our list as a factor? Consider what we’d get by multiplying all the primes on our list together.

$2\times 3\times 5\times 7 \times 11 = 2,310$

We know that $2,310$ is not prime since it has factors such as 2, 3, 5, 7, and 11 (actually 2,310 has 32 factors when you take into account all the pairs of prime factors you can make).² What happens if we shift 2,310 by 1 making 2,311?

What are 2,311’s factors?

First, can is it possible for 2, 3, 5, 7, or 11 to be a factor of 2,311? No! You can check this, and we will prove later a more general statement (can you guess what that statement is?). As it happens, 2,311 is a prime number!

Did we just find a way to generate new prime numbers?!?

Not so fast, we got lucky in this situation. Suppose we “knew of” the prime 13 so that our complete list would now be:

New “Complete” List of primes = 2, 3, 5, 7, 11 and 13.

Considering the product of all of these we get,

$2\times 3\times 5\times 7 \times 11 \times 13 = 30,030$

and then adding 1 to it gives 30,031. We can still check and see that 30,031 is not divisible by 2, 3, 5, 7, 11, or 13 (we’ll show why later, but can you see why?). However, 30031 is not prime since 30,031 factors as

$30,031 = 59 \times 509$ .

Gosh darn it! We thought we had a way to generate new primes but now it seems like we will also generate composite (non-prime) numbers. Back to the drawing board? Before we scrap our work, how did we know that 50 and 509 are prime numbers? We shouldn’t because they aren’t on our list of primes: 2, 3, 5, 7, 11, and 13. So, we did in fact find new prime numbers, they just didn’t end up being the product (30,031) but the products prime factors!

To write out our proof we must show that one of two things can happen: either our product plus one is a prime not on our list, or it’s divisible by new prime numbers not on our list. Either way we have found a new prime not on the list therefore reaching the contradiction:

Our list was a complete list pf prime numbers and we found a prime not on our list.

Proof: Assume for the hope of a contradiction that there are only a finite number of prime numbers. Let’s list all of them,

$p_1, p_2,\cdots, p_n$ .

Consider the product of all these primes plus 1,

$N = (p_1\times p_2 \times \cdots \times p_n) +1$

First, we claim that no primes on our list are a factor of $N$ . To see this, we will use a proof by contradiction. Assume that some prime $p_i$ on our list was a factor of $N$ (wow a proof by contradiction inside of a proof by contradiction). Since $p_i$ is a factor of $N$ we deduce that $N$ is equal to $p_i$ times some other number $k$ ,

$N = p_i \times k$

***This is the definition of what it means for a number to be a factor of another. For example, 7 is a factor of 14 because we can write $14 = 7\times 2$ .***

Let’s use the product form of $N$ ,

$N = p_i \times k = (p_1\times p_2 \times \cdots \times p_i \times \cdots \times p_n) +1 \\ \textit{ }\qquad\;\;\;\;\;\;\;\;\,= p_i \times (p_1\times p_2 \times \cdots \times p_n) +1$

Grouping all of the terms with $p_i$ together we deduce,

$p_i \Big(k - (p_1\times p_2 \times \cdots \times p_n )\Big) = 1$

But this makes no sense! Since the product on the left is between two positive integers it cannot equal 1, unless both of the integers equal to one. Which isn’t the case since $p_i$ is prime and hence is at least 2. Thus, it must be the case that none of our primes are a factor of $N$ .

*Almost done*

There are two cases to consider, either $N$ is prime or $N$ is not prime! When $N$ prime we’re done, since $N$ is not on our list contradicting that our list was supposed to have all the primes in it! (This was like when we were looking at 2,311.)

For case two, suppose that $N$ is not prime. Then by definition $N$ must have a prime factor (since it has to have factors other than 1 and $N$ ). But, as we’ve already shown, no primes on our list are those factors. Thus, our list is incomplete. (This was like when we were looking at 30,031.)

In either case we have shown that our list is incomplete and therefore reached a contradiction proving that there are infinitely many primes.

$\square$

The Square Root of 2

Theorem: There $\sqrt{2}$ is irrational.

This theorem was ranked 7 on the list of most beautiful math theorems! However, we will not give the proof here, so this is more of a demonstration of the utility of what a proof by contradiction can do. But, for those who really want to know how to prove that the $\sqrt{2}$ is irrational, here is a whole discussion going through everything you need in great detail: Newbie at Number Theory (Part 1.414…): Irrational Numbers.

Final Thoughts

Today was a short article day. But don’t take this to mean that proof by contradictions aren’t important. They are incredibly useful. Whenever you have a statement such as: for all blank blah blah blah. It’s usually a good idea to try a proof by contradiction. This is because the assumption gives you a starting point: there is a blank that blah blah blah. The great mathematician G. H. Hardy (yes, the same Hardy that worked alongside Srinivasa Ramanujan) said it best:

“[A proof by contradiction] is a far finer gambit than any chess gambit“

– G. H. Hardy

Let’s end on a word of warning though. Sometimes it’s so tempting to try to use a proof by contradiction when you aren’t sure where to start that you can end up in a situation where you didn’t end up using the assumption that the statement you want to prove was false. This would mean that you didn’t actually use a proof by contradiction, even though you wanted to. This is totally fine, there is no reason why you need to use one proof method over another (unless you’re in a proof class and your professor told you to use one method over another). When this happens, double check to see if you used all your assumptions, if not, then rewrite your proof without the unused assumptions. As Ernest Hemingway almost said, writing proofs is like any other form of writing. Well, he actually said, “The only kind of writing is rewriting”.

Here are a few resources that you might like to check out. The first is an amazing textbook, one that inspired me to pursue mathematics, and the other three are nice articles that go through either proof techniques in general, proofs using contradictions, or background knowledge you might find useful.

Resources

Proofs Home – Long(er)-Form Mathematics

Proof by Contradiction | Brilliant Math & Science Wiki

Proof Techniques by Jessica Su

Introduction to mathematical arguments (background handout for courses requiring proofs) by Michael Hutchings

Footnotes:

Note that I will take some liberty with the assumptions that we will make regarding the integers. However, this example still illustrated the steps. ↩︎
Whenever you see a power of 2, such as 32, it’s fun to see if you can justify why you’d get a power of 2. In this case, it’s because 2,310 has five prime factors. Any of 2,310’s factors must be of the form: $2^a\times 3^b\times 5^c\times 7^d \times 11^e$ where $a,b,c,d,e$ are 0 or 1 (why?) Then, by considering all possible choices for $a,b,c,d,e$ we get $2^5 = 32$ possible factors. ↩︎

A Kick in the Discovery