Proof by Contradiction (with Examples)

Written by

Malcolm McKinsey

January 11, 2023

Fact-checked by

Paul Mazzola

Proof by contradiction

One of the most powerful types of proof in mathematics is proof by contradiction or an indirect proof. It is powerful because it can be used to prove any statement, in several fields of mathematics. The structure is simple: assume the statement to be proven is false, and work to show its falsity until the result of that assumption is a contradiction.

Proof by contradiction definition

Proof by contradiction in logic and mathematics is a proof that determines the truth of a statement by assuming the proposition is false, then working to show its falsity until the result of that assumption is a contradiction.

The mathematician's toolbox

The metaphor of a toolbox only takes you so far in mathematics; what you really have is a powerful mind, and one of the best strategies you can store in that wonderful brain of yours is proof by contradiction.

Suppose you want very much to believe in the truth of a mathematical statement, like this one:

• No integers y and z exist for which $24y+12z=1$

With proof by contradiction, you set out to prove the statement is false, which is often easier than proving it to be true.

You continue along with your proof until (predictably) you run into something that does not make sense. That moment when your proof of falsity falls apart is actually your goal; your "failure" is your success! You showed that the statement must be true since you cannot prove it to be false.

Proof by contradiction steps

Lets break it down into steps to clarify the process of proof by contradiction. We follow these steps when using proof by contradiction:

1. Assume your statement to be false.

2. Proceed as you would with a direct proof.

3. Come across a contradiction.

4. State that because of the contradiction, it can't be the case that the statement is false, so it must be true.

No two ways

Truth and falsity are opposites. If one exists, then the other cannot. This is a basic rule of logic, and proof by contradiction depends upon it. Truth and falsity are mutually exclusive, so that:

1. A statement cannot be true and false at the same time

2. If the statement can be proven true, then it cannot be false

3. If the statement can be proven false, then it cannot be true

4. If the statement cannot be proven true, then it is false

5. If the statement cannot be proven false, then it is true

It is that last condition of truth and falsity that is exploited, powerfully and universally, by proof by contradiction.

Proof by contradiction examples

Remember this statement from earlier?

• No integers y and z exist for which $24y+12z=1$

You could spend days, weeks, years stumbling around with specific numbers to show that every integer you try works in the statement.

For example, try $y=-5$ and $z=7$

Well, those integers didn't work; care to keep doing that for a few hours with a few hundred other integers?

Probably not. Using proof by contradiction, though, we can try to prove the statement false.

To prove this false, we take the position that we can find integers y and z to make the equation work out:

We start with the original equation and divide both sides by 12, the greatest common factor:

Immediately we are struck by the nonsense created by dividing both sides by the greatest common factor of the two integers. The sum of the integers is a fraction!

That is a contradiction: two integers cannot add together to yield a non-integer (a fraction).

The two integers will, by the closure property of addition, produce another member of the set of integers. This contradiction means the statement cannot be proven false. It must therefore be true!

A famous contradiction example

Perhaps the most famous example of proof by contradiction is this:

• $\sqrt{2}$ is irrational

Our proof will attempt to show that this is false. We will attempt to show that $\sqrt{2}$ is rational.

A polite signal to any reader of a proof by contradiction is to provide an introductory sentence, like this:

That alerts the reader that you are using proof by contradiction and will plug away at the proof until it collapses logically. You work until you find the contradiction.

A rational number can be written as a ratio, or a fraction (numerator over denominator). Any fraction can be simplified to its irreducible form, so $\frac{2}{6}$ can simplify to $\frac{1}{3}$ but can be simplified no further. Notice in its simplified form at least one term of the fraction is odd.

An irrational number cannot be expressed as a fraction or ratio. Numbers like π and Euler's number e are irrational, having no fractional equivalent.

So we are saying that $\sqrt{2}$ is some irreducible fraction $\frac{a}{b}$, such that a or b is odd, or both a and b are odd:

Now we square both sides:

Lastly, we multiply both sides by ${b}^{2}$:

Here we can see that ${a}^{2}$ has to be an even number, because the square of every even number is even, and the square of every odd number is odd. Recall that a and b cannot both be even, so b must be odd.

If a is an even number, some number exists for a = 2c, and we can replace a with 2c everywhere we had aa in our equation:

The contradiction emerges: ${b}^{2}$is even, so b is even, but we just got through showing it was odd.

It is also contradicted because if a is even and b is even, the fraction is not in simplest form, but we started by saying it was irreducible.

The $\sqrt{2}$ cannot be rational, so it must be irrational.

At the contradiction, you should stop your work. You have proven the truth of the statement by showing that a claim that it is false cannot hold up to logic.

Lesson summary

This was a challenging lesson. You may well benefit from rereading it several times, but once you do, you should feel more confident in your understanding of proof by contradiction.

Now you are able to recognize and apply proof by contradiction in proofs, develop a logical case to show that the premise is false, until your argument fails by contradiction, and recognize the contradiction in your argument that demonstrates the validity of the original premise.