Proof by Contradiction
A contradiction is where two statements cannot 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's statements contradict each other.
Proof by Contradiction
In a proof by contradiction, the contrary (opposite) is assumed to be true at the start of the proof.
After logical reasoning at each step, the assumption is shown not to be true.
Example: Prove that you can't always win at chess
Let's start with the contrary: you can always win at chess.
I now set up a board, let you take the first move, then turn the board around and let you take the opponent's move.
Both sides cannot win, and you are playing both sides!
So the idea that you can always win is absurd, and I have proven that you cannot always win.
Note: in a formal proof we would need to use better clearer logical steps.
OK, a little bit tricky, but you get the idea.
Example: Proving There Is No Smallest Positive Rational Number:
Let's assume there exists a smallest positive rational number.
We'll call it r.
Now, let's consider the number r2. This number is positive and rational because dividing one rational number by another (as long as it isn't zero) results in a rational number.
Importantly, r2 is smaller than r, which contradicts our assumption that r is the smallest.
Therefore, 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 is not zero.
He then showed that such a fraction could always be simplified further
- Squaring the fraction shows both numerator and denominator would be even
- This means the fraction is not in simplest form
Which is impossible.
This contradiction proves √2 cannot 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.