What Is Proof By Contradiction? (3 Examples)

Proof by contradiction is useful for proving statements by assuming the opposite.  This assumption gives us an equation, inequality, or statement to work with to derive the contradiction.

So, what is proof by contradiction?  Proof by contradiction has 3 steps: 1. Write out your assumptions in the problem, 2. Make a claim that is the opposite of what you want to prove, and 3. Use this claim to derive a contradiction to your original assumptions (a contradiction is something that cannot be true, given what we assumed).

Of course, we don’t need to use proof by contradiction (an indirect method of proof) for every theorem.  For some statements, we can use a direct proof, such as proof by induction.

In this article, we’ll talk about proof by contradiction, what it is, and how it works.  We’ll also look at some examples to make the concept clear.

Let’s get started.

What Is Proof By Contradiction?

Proof by contradiction is an indirect method of proof.  With a proof by contradiction, we assume the opposite of what we want to prove.

In turn, this assumption leads to a statement that contradicts what we already know to be true.

For example, your friend is either at home or not at home.  If you assume that he is at home, this might lead you to go to his house.

If you find nobody there, then you know that your initial assumption was incorrect.  So, your friend is not at home.

Why Does Proof By Contradiction Work?

Proof by contradiction works because we are splitting a situation into two possible cases: 1. the one we want to prove, and 2. the alternative.  In other words, if the only two possibilities are A or B, and we disprove A, then we know B must be true.

For example, for any natural number N, we know that N is either even or odd.  This is because:

• the even numbers are integer multiples of 2 (such as 2, 4, 6, 8, etc.), and
• the odd number are the rest of the whole numbers (such as 1, 3, 5, 7, etc.)

So, if you can prove that a whole number is not even, then you know it is odd.  Likewise, if you can prove that a whole number is not odd, then you know it is even.

When To Use Proof By Contradiction

Proof by contradiction is useful when direct methods (such as mathematical induction) will not work.

Proof by contradiction is useful because it can give you an equation, inequality, or statement that you can use to help you prove something (by deriving a contradiction).

We will see some examples in the proofs by contradiction that follow.

What Is An Example Of Proof By Contradiction?

Some examples of statements where we can use proof by contradiction include:

• N Is Odd If N² Is Odd
• There Are Infinitely Many Prime Numbers
• √2 Is Irrational

Example 1: Proof By Contradiction That N Is Odd If N² Is Odd

Remember that every whole number is either even or odd.  So, if we can show that a whole number is not even, then it must be odd.

If we can prove that N cannot be even when N² is odd, then we know it falls into the second category: the set of odd numbers.

To show this, use proof by contradiction to assume the opposite: that N is even if N² is odd.

In that case, we can write:

• N = 2K  [our assumption, which we want to prove false]

where K is a whole number.

Now that we have an equation to work with, let’s begin to derive a contradiction:

• N = 2K  [our assumption]
• N² = (2K)²  [square both sides of the equation]
• N² = 4K²
• N² = 2(2K²)  [4 = 2*2]

From the equation in this last line, we can see that N² is even (K is an integer, so K² is also an integer, as is 2K² and 2 times an integer is an even number).

However, this contradicts our initial statement that N² was odd.

So, it cannot be true that N is even when N² is odd.

Thus, N is even whenever N² is even.

Example 2: Proof By Contradiction That √2 Is Irrational

Remember that every real number is either rational or irrational.  Since √2 is a real number, it must either be rational or irrational.

If we can prove that √2 is not a rational number, then we know it falls into the second category: the set of irrational numbers.

To show this, use proof by contradiction to assume the opposite: that √2 is rational.

In that case, we can write:

• √2 = p / q  [our assumption, which we want to prove false]

Where p and q are integers, with q nonzero and p / q reduced as much as possible.  That is, gcd(p, q) = 1 (p and q share no common factors).

Now that we have an equation to work with, let’s begin to derive a contradiction:

• √2 = p / q  [our assumption]
• (√2)² = (p / q)²  [square both sides of the equation]
• 2 = p² / q²
• 2q² = p²  [multiply by q² on both sides to clear the denominator]

From the equation in this last line, we can see that p² is even (q is an integer, so q² is also an integer, and 2 times an integer is an even number).

Since p² is even, this also means that p is even (remember: if p² is odd, then p is odd, which we proved in Example 1 above).

 Now that we know that p is even, we can write the equation:

• p = 2m

for some integer m.

Substituting this equation for p into our equation relating p and q gives us:

• 2q² = p²  [the equation we derived above]
• 2q² = (2m)²  [since p = 2m]
• 2q² = 4m²
• q² = 2m²  [divide by 2 on both sides]

From the equation in this last line, we can see that q² is even (m is an integer, so m² is also an integer, and 2 times an integer is an even number).

Since q² is even, this also means that q is even (remember: if q² is odd, then q is odd, which we proved in Example 1 above).

 Now that we know that q is even, we can write the equation:

• q = 2n

for some integer n.

However, this contradicts our initial statement that p / q was reduced as much as possible.  In particular, p and q share a common factor of 2 (since they are both even):

• p / q = 2m / 2n = m / n

So, it cannot be true that √2 is rational.

Thus, √2 is irrational.

Example 3: Proof By Contradiction That There Are Infinitely Many Prime Numbers

There are infinitely many prime numbers.  That is, no matter how many prime numbers we write out in a list, we can always find more to add to the list.

To show this, we will use proof by contradiction.  First, assume that there are only finitely many prime numbers (let’s say there are N of them), and write them in a list, labeling them with subscripts from 1 to N:

• p₁, p₂, … , p_N  [this is the list of all prime numbers]

Then, take the product P of all of the prime numbers on our list (all N of them):

• P = p₁ x p₂ x … x p_N

Finally, add 1 to this number to get a total of P + 1 (which is just another positive integer).

Since P is a product of every prime number in our list, then P + 1 is larger than any number on the list.

Thus, P + 1 is not on the list, and so it is not prime.  Since P + 1 is not prime, it must be composite.

Therefore, P + 1 is the product of some of the prime numbers from our list.  This means that there must be some prime number p_i in our list so that P + 1 divided by p_i has a zero remainder.

However, P + 1 divided by any prime in our list will have a remainder of 1, since:

• (P + 1) / p₁ = (p₁ x p₂ x … x p_N + 1) / p₁ = p₂ x … x p_N + 1 / p₁
• (P + 1) / p₂ = (p₁ x p₂ x … x p_N + 1) / p₂ = p₁ x p₃ x … x p_N + 1 / p₂
• …
• (P + 1) / p_N = (p₁ x p₂ x … x p_N + 1) / p_N = p₁ x p₂ x … x p_N-1 + 1 / p_N

No matter which prime p_i we divide by, we always get a remainder of 1.  So, P + 1 is not divisible by any prime number p_i on our list.

This implies that either:

• P + 1 is prime, which is a contradiction (we said P + 1 is not prime, since it is not on the list), or
• P + 1 is composite and is a product of other primes that were not on our list, which is also a contradiction (we said our list contained all of the possible prime numbers).

Due to this contradiction, we conclude that there is no such finite list of prime numbers.  So, there must be infinitely many prime numbers.  Thus, we can never run out of primes.

Note: due to the Fundamental Theorem of Arithmetic, it is also true that every integer greater than 1 is either prime or has a unique prime factorization.  That means that there is only one combination of prime numbers (raised to the proper powers) that will result in a given integer product.

Conclusion

Now you know a little more about proof by contradiction, what it means, and how it works.  You also have some examples to work with so that you can try writing some proofs of your own.

I hope you found this article helpful.  If so, please share it with someone who can use the information.

Don’t forget to subscribe to my YouTube channel & get updates on new math videos!

~Jonathon