High school mathematics education focuses on calculation. It’s all about getting the right answer to some problem, like finding the x such that x² + 3x = 18. This almost entirely excludes the notion of a mathematical proof, to the point that there are highly educated people who have never even heard of the concept.
This is sad. It is sad, first, because proofs are often more fun and more beautiful than calculations. And, second, because you can’t really understand what mathematics is if you don’t know about proofs. It’s like having had physics classes and being able to use Ohm’s Law and the Ideal Gas Law and so on to calculate things… and yet having no idea what an experiment is and how physicists find out about laws. For proofs stand to mathematics as experiments stand to the physical sciences: they are how we know that our statements are true.
The mathematics text book gives us the Pythagorean theorem: “In every right triangle with right sides a and b and hypotenuse c, it is true that a² + b² = c².” Nice. But how do we know this is true? What we could do, is this: draw a variety of right triangles, measure their sides, perform the calculation, and see whether the outcomes are approximately correct. We could do that, but if we did, we would not be doing mathematics. The Pythagorean theorem is not something that holds approximately. It is also not something that we happen to have some good evidence for, but which could be proved false by new evidence (the discovery of a right triangle that doesn’t fit the formula). On the contrary. We can prove the theorem. That is, we can show that it’s true, for absolutely every right triangle, and in a way that can withstand all criticism and that leaves no room for further doubt or further ‘experimentation’.
In this way, it must be said, mathematical proof is very different from, say, Sherlock Holmes ‘proving’ that the butler did it. There could always be new evidence showing that the butler was innocent. Mathematical proof is not like that.
So how does mathematical proof work? There are many different types of proof and I want to look at some examples. But first, four bits of terminology about numbers. Mathematicians love careful use of terminology, because they allow us to see that our proofs are valid.
- The natural numbers are just the ‘whole’ numbers starting from zero: 0, 1, 2, 3, 4, 5, 6, … (So neither -2 nor 0.5 are natural numbers.)
- A natural number is a square if you can get it by multiplying some natural number by itself. So 4 is the square of 2 (since 2 times 2 is 4), 9 is the square of 3, and so on.
- We say that one number, a, can be divided by another number, b, just in case a/b is a natural number. So 12 can be divided by 3, because 12/3 = 4. It can’t be divided by 5, because 12/5=2.4, which is not a natural number. Another way of thinking about this is that a can be divided by b just in case you could equally divide a cookies over b children without having to break any. (Of the cookies.)
- A prime number (or simply a prime) is a natural number unequal to 1 that can only be divided by 1 and by itself. So 5 is a prime, because you can only divide it by 1 and by 5.
Given this bit of terminology, we can make the following claim:
All natural numbers smaller than 6 are either prime or square.
How do we prove this? That’s easy! We just look at all the natural numbers smaller than 6. Let’s go. 0 is the square of 0. 1 is the square of 1. 2 is prime. 3 is prime. 4 is the square of 2. And 5 is prime. So the mathematical claim we made was true. We’ve proven it beyond a doubt.
It was possible to do so because (1) we could easily check the truth for each of the numbers, and (2) there was just a limited amount of numbers to check. And of course we can be sure that we didn’t forget any numbers. We know what the natural numbers smaller than 6 are; it’s impossible that somebody makes the surprising discovery of a new natural number between 2 and 3! (Why this is impossible is a difficult question for the philosophy of mathematics. We will not go into it.)
To be honest, though, this proof is pretty disappointing. It’s an example of what mathematicians call a proof by exhaustion, or what we might also call a brute-force proof. We just tried every case. There was no real insight involved, and the resulting proof lacks what mathematicians like to call elegance. So let’s move on to something better!
(I did have a reason for talking about this particular mathematical claim, though you might not think it a good reason. See, I really hate the kind of test where you are given a list of numbers and have to give the next number. “0, 1, 2, 3, 4, 5″… what’s the next number? Of course you’re supposed to think that these are the natural numbers and the next number is 6. But it could just as well be a list of all the squares and primes, in which case the next number is 7. With sufficient ingenuity, you can make the case for any number being the next number. So these tests don’t test whether you can do maths, or whether you are smart. They test your ability to conform to expectations. Okay, that was my rant. Back to proofs.)
Let’s look at the following mathematical claim:
8 is not a square
This may look trivial, but it is actually a claim about all the natural numbers, telling us that for any natural number n, the number n² is not 8. How can we know that this is true? Surely we can’t exhaust all the natural numbers? No, we can’t. But let’s see what happens if we try.
0² = 0, 1² = 1, 2² = 4, 3² = 9, 4²=16…
At this point something dawns on us. If we go on, the numbers will just get bigger and bigger. And since we have already passed our target number of 8, we can be sure that every number we haven’t checked yet will yield a square that is bigger than 8. Hence, we have done enough; we can be sure that there is indeed no number that squares to 8.
I’m willing to call this a proof. But it’s pretty informal. I claim that the numbers will just keep getting bigger, and it’s kind of obvious… but do I really know that the numbers will keep getting bigger? Surely, if we are to be mathematicians, we can do better than this. We can redo the proof in a slightly more formal, slightly more careful, and therefore more robust way. How do we do that? If we think about it, the idea of our proof is the following: we show that 0, 1 and 2 don’t square to 8; then we point at that 3 squared is already too big; and then we claim that this means that for all the bigger numbers, the square will also be to big. In formulas:
- STEP 1: we show that 8 is not the square of 0, 1 or 2.
- STEP 2: we show that 3² > 8.
- STEP 3: we show that if 3² > 8, then n² > 8 for all n > 3.
The first step is a very small proof by exhaustion. Step 2 and 3 together constitute what mathematicians call a proof by induction. A proof by induction works like this: you show that something is true for a particular number a [STEP 2 above], and then you show that if it’s true for some number n, then it is also true for n+1. Together, this shows that it’s true for a and every number bigger than a [STEP 3 above].
How does that work in this example? Showing that 3² > 8 is easy, since it’s clear that 9 > 8. But now we also want to show that if n² > 8, then (n+1)² > 8. How do we do that? Well, we first assume that n² > 8. Then we calculate that (n+1)² = n² + 2n + 1. But 2n + 1 is always bigger than 0. So (n+1)² > n² > 8. This completes our proof by induction.
This may have been a bit more interesting than our first proof, but we’re still not really doing anything amazing, are we? I mean, we kind of already knew that 8 wasn’t a square. It’s sort of obvious. What the proof does, though, is clarify why it’s obvious. And indeed it often turns out, when we try to prove something, that the obvious isn’t that obvious. Suppose somebody had said: “Clearly 8 isn’t a square. The square root of 8 is 2.8284…, which is not a natural number. So 8 is not the square of a natural number.” Sounds good. But there’s an unspoken assumption there, which is that no two numbers can have the same square. And this assumption has not been proven and may not be true. In fact, it’s false: 8 has another square root, which is -2.8284… Clearly, mathematicians have to be very careful about stating their assumptions, because things can go wrong if they don’t.
Still — we want to prove something a bit more interesting. Something that is not obvious. Maybe we would like to prove that there infinitely many prime numbers? That’s not obvious! It seems like there could also be 50 of them, or 5000, or maybe 10⁵⁰. But no, there are in fact infinitely many, and you and I are going to prove so in this very blog post.
But before we’re there, let’s mess around a bit and think about dividing one number by another. In fact, I’ll give you a problem to solve… quick, give me a number that is bigger than 2, but that can’t be divided by 2.
Maybe you said… 3? Good choice! 3 = 2 + 1, and that means that if you try to divide it by 2, you’re going to be left with that nasty + 1 that can’t be divided by 3. In school, you may have called that 1 the “remainder” of the division. Thinking about remainders is actually going to help us solving some other problems… quick, give me number that is bigger than 346, but that can’t be divided by 346!
What about… 347? Yes, brilliant! Clearly, 347 can’t be divided by 346. Because it is 346 + 1, and if you try to divide it by 346 you’re going to end up with a remainder of 1. In other words, 347/346 = 1 + 1/346, and the nasty fraction at the end ensures that this is not a natural number.
In fact, it’s clear that for every number n (with n > 1), the number n + 1 cannot be divided by n. There will always be that remainder of 1.
Now we’re going to make things a bit more interesting. I now want a number that is bigger than 2 and bigger than 3 and that cannot be divided by either 2 or 3. How do I construct such a number? Well, here’s an option: multiply 2 and 3, then add 1. So we do (2 * 3) + 1, and of course that means we end up with 7.
It is clear from how we wrote the number (2 * 3) + 1 that you cannot divide it by 2 and cannot divide it by 3. Dividing by 2 gives 3… and a remainder of 1. Dividing by 3 gives 2… and a remainder of 1. And this is true in general. If I have two numbers a and b, and I want to construct a bigger number that is not divisible by either a or b, then the number (a * b) + 1 will do the job. Because divide it by a or divide it by b, and you’ll always have that remainder of 1.
In fact, we can generalise this insight even further. (Mathematicians love to generalise: take an insight about something specific, and show that it applies more generally.) Give me any amount of numbers bigger than 1, let’s call them a, b, c, …, z. Then we can construct a bigger number that cannot be divided by any of those numbers; it is the number (a * b * c * … * z) + 1. There will always be that pesky remained of 1. But this is nice! Without really meaning to, we have given a proof of the following theorem:
Let a, b, c, …, z be any list of natural numbers bigger than 1. Then there exists at least one number bigger than any of them that cannot be divided by any of them.
The proof we have given of this theorem is what mathematicians call a constructive proof: we have actually given a recipe to construct (we could also say “find”) a number that has the sought-for property. And what’s also great is that our proof is completely general. It works for any list of natural numbers, no matter how many, no matter which numbers they are.
We now have almost all the ingredients we need to give a famous proof of that very important mathematical claim:
There is no biggest prime number.
At first sight, this may seem really hard to prove. We can of course make a list of prime numbers: 2, 3, 5, 7, 11, 13, … So far so easy. We can even write a computer programme that will keep calculating more. But how can we prove that this list will never end? How can we show that there is always a bigger prime to be found, that our computer programme will never stop coming up with new primes?
Here’s what we’re going to do. We’re going to give a proof by contradiction. How does that work? Well, we are going to assume that there IS a biggest prime number. And then we are going to show that this leads to a contradiction. If the assumption leads to a contradiction, it must be false; and so we can conclude that there is in fact no largest prime.
Sounds hard? With the work we’ve already done, it’s actually not that difficult. But we need to lay just a little more groundwork. To be precise, we need to prove this:
Any number n > 1 is divisible by at least one prime.
To prove this, we start by considering two cases. Either n is prime, or n is not prime. (Clearly, these are the only two cases. We call them “jointly exhaustive”, because together they exhaust all possibilities.) And now we will prove the theorem first for the one case, and then for the other. This is often a good way of approaching a proof.
Suppose that n is prime. This is the easy case! Every number is divisible by itself; you can always divide n cookies over n children, simply by giving 1 cookie to each child. So if n is prime, it is automatically divisible by a prime number, namely, itself.
Second case. Suppose that n is not prime. If n is not prime, we can write it as a * b, with a and b natural numbers bigger than 1. (That is what it is to be not prime: it means you are divisible by a number different from 1 and yourself. And so you can be written as a multiplication of two different numbers. For instance, 20 = 4 * 5.)
Now again we will distinguish between two cases. First case: a or b is prime. Second case: neither a nor b is prime. Take the first case first, so a or b is prime. Well, n is divisible by a and by b, so it’s divisible by a prime, and our job is done.
Second case. Suppose that a and b are both not prime. Then they themselves can be written as a product of two smaller numbers; so, for instance, we can write a as c * d and we can write b as e * f. So we now have n = a * b = c * d * e * f. And you can see how we proceed! One of c, d, e, f may be prime, in which case we know that n is divisible by a prime. Or none of them is prime, in which case we can go on writing n as a product of even smaller numbers. We can keep doing this; at every stage we either reach a prime or we keep going. And since the numbers become smaller and smaller, this process must stop at some point; it can’t go into infinite. And that is the point at which we must have reached primes. So, any non-prime number can be written as the product of primes; and therefore, any non-prime number is divisible by at least one prime.
That’s a good proof, but we can perhaps make things clearer by giving a concrete example. Take the number 72. It can be written as 72 = 6 * 12. Neither of those are prime. But 6 can be written as 2 * 3, and 12 can be written as 3 * 4. So 72 = 2 * 3 * 3 * 4. We could stop there, because some primes have appeared; but maybe we notice that 4 can be written as 2 * 2 and we take it one step further: 72 = 2 * 3 * 3 * 2 * 2. It can be written as a product of only primes. Clearly, this is a process we can perform for any non-prime number, and we always up with a bunch of primes.
Now we can give the famous proof that there is no biggest prime number. We’ll do it as a proof by contradiction: we start from the assumption that there is a biggest prime and we show that this assumption leads to a contradiction. So the assumption has to be false.
Suppose that there is a biggest prime number, which we’ll call N. Then we can make a list of all the prime numbers from small to large, and it will look like this: 2, 3, 5, 7, …, N. Now we construct the number P as follows:
P = (2 * 3 * 5 * 7 * … * N) + 1
In other words, P, is one plus the product of all the primes. Now P must be divisible by at least one prime. (We proved above that all numbers bigger than 1 are divisible by at least one prime.) But we have also already seen that the number P cannot be divided by any of the numbers 2, 3, 5, 7, …, N, since there will always be a remainder of 1. However, our assumption is precisely that those are all the primes, so it follows that P is not divisible by any prime. But it has to be divisible by a prime. Contradiction! Since the assumption that there is a biggest prime number leads to a contradiction, the assumption must be false. There is no biggest prime number. There are infinitely many prime numbers.
To be clear, this proof by contradiction does not tell us how to find a prime number bigger than N. It only tells us that there must be one. (In fact, that there must be infinitely many.) If we look at the number P, we see that either it must be a prime, or some number between N and P must be a prime. So we know a range in which to search, but we don’t know where the prime can be found. (In practice, there will usually be many primes between N and P.)
Is there something strange about this? That we can know that there is a prime bigger than N without knowing which number it is? Maybe; but on the other hand, we may also know that someone murdered Mr. Black without knowing who it was. So perhaps it’s not so strange after all.
This completes my overview of proofs. But you may wonder whether mathematicians can always find the proofs they want. And the answer is no. There are situations where we just don’t know whether and how a certain mathematical claim can be proved. For instance, there is Goldbach’s conjecture:
Every even number greater than 2 is the sum of two primes.
It’s easy to find positive instances for this claim. 4 = 2 +2; 6 = 3 + 3; 8 = 3 + 5; 10 = 5 + 5; 12 = 5 + 7; and so on. In fact, Goldbach’s conjecture has been shown to be true for all the numbers up to 4 × 1018. But we have no proof of it, though many mathematicians have tried; and so we don’t know whether it holds for all numbers or not. In fact, we can’t be sure that we’ll ever be able to know; it could be the case that there is no possible proof that Goldbach’s conjecture is true and also not possible proof that it is false. Maybe it can be neither proved nor disproved.
Indeed, strange as it may sound, there are mathematical claims that can be proved to be unprovable: we can prove that there is no possible proof that the claim is true and no possible proof that the claim is false. An example is the continuum hypothesis. But talking about that would be taking us too far afield.
That was it: a primer on mathematical proofs. I hope you enjoyed it!