Proof by Contradiction
Another approach is proof by contradiction. Here is the idea:
- Assume the statement is false or true.
- Derive a contradiction, a paradox, something that doesn’t make sense. This will mean that the statement cannot possibly be what we assumed it to be, therefore it’s the opposite.
When I first saw this formal technique, it puzzled me. It didn’t seem to be valid: alright, assuming something is false leads to a paradox, so what? We haven’t proven that assuming it’s true doesn’t lead to another paradox! Or even the same paradox, for that matter. What I failed to understand conceptually is that a statement is a binary thing: it’s either true or untrue. Nothing in between. So, if one can definitely declare “X is not false”, then no other options are left: “X must be true”.
Theorem 3. n is a positive integer. If n^2 is even, then n is even.
We may try to construct another direct proof, but creating paradoxes is much more fun!
Proof. Let’s assume that n^2 is even, but n is odd. This is the opposite of what we want, and we will show that this scenario is impossible.
n is odd, then, according to Theorem 1 (which is already proven), n^2 must be odd. This doesn’t make sense! Our assumption and our conclusion are the opposite. This is a paradox, so the assumption was wrong. Meaning, the idea “n^2 is even, but n is odd” is false. Therefore, the idea “n^2 is even, n is even” is true. \blacksquare
Let’s look at one rather famous proof of irrationality of \sqrt{2}.
Theorem 4. \sqrt{2} is irrational.
Woah, this is… different. Prior theorems were formulas, something to play with, something physical. But here is just an idea, so how would we even start? Let’s start with a definition:
In mathematics, the irrational numbers are all real numbers which are not rational numbers.1
Doesn’t seem helpful, but let’s continue. What are rational numbers then? Are they some reasonable beings who make optimal decisions all the time?
A rational number is any number that can be expressed as the fraction \frac{p}{q} of two integers.2
Oh! They are rational because they are ratios! Just to make things super clear, let’s dig one more step and make sure we understand integers.
An integer (from the Latin integer meaning “whole”) is a number that can be written without a fractional component. For example, 21, 4, 0, and -2048 are integers, while 9.75, 5\frac{1}{2} and \sqrt{2} are not.3
Combining these things, we can construct a comprehensive definition of the irrational number: it’s a number that cannot be expressed as the fraction of two whole numbers. Now, let’s apply this to Theorem 3 so that it has some meat:
Theorem 4, re-framed. \sqrt{2} cannot be expressed as \frac{p}{q}, where p and q are integers.
Alright, now there is something to play with!
Proof. Start by assuming the opposite: \sqrt{2} is rational. This means it can be written as a fraction of two integers:
\sqrt{2} = \frac{p}{q}
We can assume that p and q are not both even, because if they are, we can reduce them by dividing both by a common factor (like, for example, \frac{8}{10} should be reduced to \frac{4}{5}). In other words, if they are both even, reduce them until at least one is odd and no further reductions are possible. Now, let’s square the square root:
(\sqrt{2})^2 = \frac{p^2}{q^2} 2 = \frac{p^2}{q^2} p^2 = 2q^2
Remember, something like 2k + 1 is odd, and 2k is even. Here we see this pattern: p^2 = 2q^2, which means that p^2 is even (it consists of two things). Then, using Theorem 3, we can say that p is even as well, which means we can write p as p = 2k. So:
2q^2 = p^2 = (2k)^2 2q^2 = 4k^2
Divide both by two:
q^2 = 2k^2
So, q^2 is even. According to the same Theorem 3 it follows that q is even. Let’s summarize the two conclusions:
- p is even.
- q is even.
Wait… We made sure that not both p and q are even before starting this whole thing! We made sure to reduce them until at least one is odd, but then, by applying Theorem 3, we ended up with two even numbers. This is impossible, so the idea that “\sqrt{2} is rational” is not true. Therefore, \sqrt{2} is irrational. \blacksquare.