How We Know What We Know 3: Proof By Contradiction
Before we start, I’d just like to apologise for the lack of replies to comments recently, especially on part 2 of this series. My life recently has been… not bad, but full of incident, and it’s taken all my spare energy to get even the few posts I’ve managed up. Those of you who’ve followed my blog for a while will know that I go through phases of productivity and phases where getting words out is like pulling teeth. I’m in the latter at the moment but hope to be in the former again soon. That said, let’s move on…
So after parts one and two, we’re going to move away from the scientific method for a little while, and talk about mathematics. This jump between subjects is the biggest one we’re going to see in this series of posts, and it might seem that we’ve gone completely off-topic. In fact, this is the necessary background we need in order to put the topics of the first two posts into a more formal context. By post twelve in this series, we will have the outlines of a formal proof of the efficacy of the scientific method.
(Don’t worry, I’m not going to throw a huge set of equations or diagrams at anyone – it’s all going to be much the same kind of thing as the posts so far have been).
So we’re going to go back to very basic maths, of the kind that used to be taught as a matter of course in schools (it may still be, but as an adult I am legally obliged to assume that no child educated after the day I left school was taught anything). If you’ve studied anything about mathematical proofs at all, you can ignore this post – it’s aimed at those with little or no maths who want to understand what’s coming up.
This is a technique of proof that dates back at least to Euclid, and is referred to as reductio ad absurdum or proof by contradiction. It’s a very simple technique, but it’s very powerful. To prove a statement must be true, assume its opposite and then see what follows. If you can get a contradiction then that proves the opposite of the statement must be false, so the statement must be true.
As an example, here’s how Euclid used it to prove there is no highest prime number:
Assume there is a highest prime number – say, for argument’s sake, we choose 37. Now, by definition, a prime number is a number that has no divisors except itself and one. So if 37 is the highest prime number, all numbers over 37 must be divisible by a number between two and thirty-seven inclusive, by definition.
But what about the number (2x3x…35x36x37)+1?
It’s not divisible by two, because if you try you’re left with a remainder of one. It’s not divisible by three, because if you try you’re left with a remainder of one…
So that leaves two alternatives. Either (2x3x…35x36x37)+1 is itself a prime, or there is some number higher than 37 but lower than that high number which is a divisor of (2x3x…35x36x37)+1 but isn’t itself divisible by any number under 37.
In other words, if 37 is the highest prime number, then there has to be a prime number higher than 37. This is a contradiction, so we’re left with 37 *not* being the highest prime. But this can work for *any* number – you can just stick n in there and have (2x3x…n-1xn)+1, for any value of n you choose.
So no number can be the highest prime number, so there must be an infinite number of primes, ever higher.
Once we know Pythagoras’ theorem (that given a right angle triangle with sides a, b and c, where c is the hypotenuse, c^2 = a^2 + b^2), we can prove that the hypotenuse is always shorter than the sum of the other two sides (c < a+b).
So assume that a+b is less than or equal to c, the opposite of what we've assumed:
Square both sides
a^2 + 2ab + b^2 <= c^2
We know that c^2 = a^ + b^2, from the Pythagorean theorem, so we can substitute that in for c^2:
a^2 + 2ab + b^2 <= a^ + b^2
Take a^ + b^2 from both sides:
But we're talking about a triangle, so all the sides must have positive lengths, so the multiple of a and b can't be less than or equal to zero. So a+b can't be less than or equal to c. So c must be less than a+b .
Despite its simplicity, this technique is quite a beautiful one, mathematically. Partly, this is because it's so audacious and almost arrogant – "OK, we'll try it your way, and assume that there's a highest prime… oh look, we've proved there isn't a highest prime! Why are you hitting yourself?"
But also because, while mathematics isn't a science (though as we shall see, it may be rather more than 'a science' and may include all the sciences within it), it shows an admirably scientific attitude – start off assuming you’re wrong, because nobody ever learned anything new by thinking they already knew everything.
And finally, because it’s brave, because it exposes the fatal weakness with logical systems. If you can prove a contradiction, if you can actually show that a contradiction must be true within your system, then the whole system becomes worse than useless. If you can prove that A *and* not-A are true, then you can prove literally anything with your system. With something like mathematics, which started out as an attempt to find absolute truths, the idea that you could prove a contradiction was, for a lot of the subject’s history, very, very scary to a lot of people. Proof *by* contradiction comes quite close to this, mentally.
In fact, one of the main mathematical projects of the early part of the last century, one that took the work of some of the best mathematicians and logicians of their – or any – generation, was an attempt to prove that mathematics could not possibly have any contradictions in it, and ensure that no-one would ever find any. They failed, but to see why we’ll have to first go back to the nineteenth century, to Georg Cantor, and take a closer look at infinity…