Proof by Contradiction

A contradiction is where two statements can't both be true at the same time.

Alex: "You were at the beach yesterday."

Sam: "I was not at the beach yesterday!"

Alex and Sam can't both be right. Their statements contradict each other.

Proof by Contradiction

In this type of proof, we start by assuming the exact opposite of what we want to prove.

Then we use logical steps until we hit a roadblock where things makes no sense ... so our starting assumption must be wrong!

Example: Prove you can't always win at chess

Chess board with pieces set up in starting positions

Let's assume the opposite: you can always win at chess.

Now imagine you play a game against yourself:

You make the first move for White
Then you turn the board around and play for Black

. . . both sides can't win, but you are playing both sides! This makes no sense.

Our assumption is broken. So, we have proven that you can't always win.

Note: in a formal proof we would need to use better clearer logical steps.

It sounds a bit tricky, but it is a powerful trick. Let's look at numbers.

Example: Prove there's no largest integer

Let's assume the opposite: there is a largest integer called N.

Largest integer:

Now let's add 1 to it:

N + 1

But:

N + 1 is also an integer

Our assumption that N is the largest integer must be false.

So there's no largest integer.

Small dog looking up through a magnifying glass

Example: Proving There's No Smallest Positive Rational Number:

Let's assume there exists a smallest positive rational number.

We'll call it r.

Start with:

Divide it by 2:

But:

r2 is also a positive rational number

And it is smaller!

So no such smallest positive rational number exists.

A proof by contradiction is also known as "reductio ad absurdum" which is the Latin phrase for reducing something to an absurd (silly or foolish) conclusion.

Proof That √2 is an Irrational Number

Euclid proved that √2 (the square root of 2) is an irrational number by first assuming the opposite.

This is one of the most famous proofs by contradiction. Let's take a look at the steps.

First Euclid assumed √2 was a rational number.

A rational number is a number that can be written as a fraction p/q, where p and q are integers with no common factors other than 1, and q isn't zero.

He then showed that such a fraction could always be simplified further:

If √2 = p/q (in simplest form), then squaring both sides gives
2 = p²/q², or
p² = 2q²
This means p² is an even number, so p itself must be even
If p is even, then p² is divisible by 4, which forces q² (and thus q) to be even too
But if both p and q are even, the fraction p/q can be simplified further (by dividing by 2)

This contradiction proves √2 can't be written as a fraction, so it is irrational.

Discover more at Euclid's Proof that √2 is Irrational.

Real Numbers

Another famous proof by contradiction was given by Georg Cantor when he showed the Real Numbers are not countable.