Some thoughts on how people come up with mathematical proofs

Everyone who has studied mathematics and tried to prove things themselves will have realised that the process is quite different from what you might imagine from the proofs given in textbooks. In textbooks, proofs are made up of a sequence of statements which are, roughly, ordered by implication: the proof begins with the hypotheses of the theorem, and the statements derive conclusions from these hypotheses and from the conclusions of previous statements until finally the statement that is to be proved is concluded. But when you are coming up with a proof yourself, you can’t just derive things from the hypotheses without bearing in mind what conclusion you’re aiming for. After all, there are infinitely many statements that could be derived from the hypothesis and only some of these will help lead you towards the inclusion. Instead, you often have to work backwards, trying to find hypotheses that imply the desired conclusion, so that you can aim to conclude the statements of these hypotheses from your original hypotheses, rather than aiming for the desired conclusion directly. Of course, you have to bear in mind what the original hypotheses are while doing this. So you end up constantly alternating between working forwards and working backwards until finally everything links up somewhere in the middle. Deduction can be thought of, in metaphorical terms, as a kind of journey. In the textbooks, you have a group of people, corresponding to the hypotheses, travelling towards their destination, which corresponds to the conclusion. But deduction as a mental process is more like a meeting between two parties.

I thought it might be interesting, therefore, to try and write down how I came up with a proof, to show you how the process works. The thing I’m going to prove is the following statement.

Theorem 1. There is a rational number between every pair of distinct real numbers.

The proof will be different, of course, depending on how you define the real numbers. My proof will use the axiomatic definition of the real numbers. In case you are not familiar with this, the axiomatic definition is the one where we don’t really worry about what the real numbers are; we just list some of the most essential properties of the real numbers, and see what we can prove if we assume that these properties hold. These assumed properties are called our axioms. Although this might seem philosophically dubious, if we can prove something from the axioms, then we can be quite sure that it is a true fact about the real numbers, regardless of how we define them, because we can always be sure that the axioms hold. After all, the axioms are the most essential properties of the real numbers. If we were to define the ‘real numbers’ in such a way that not all of the axioms held, it could be reasonably argued that these objects were not, in fact, real real numbers. (This is kind of like what I was talking about in the above paragraph. Rather than going directly from a more concrete definition of the real numbers to the Theorem 1, we are just going to prove that certain hypotheses—the axioms—imply Theorem 1, and we can be satisfied with that since we can assume that given any concrete definition, we will be able to derive the axioms.)

The axioms we will use mostly consist of elementary algebraic facts that you learn in school, such as the fact that adding 0 to a number doesn’t change it, or the fact that the product of two positive numbers is positive. I assume the reader is familiar with these facts. The only axiom which will be new to you, unless you’ve taken a course in real analysis, is the axiom of completeness. The axiom of completeness is a bit complicated, so I won’t tell you what it is here; instead, I’ll just assume a weaker form of the axiom called the axiom of Archimedes. The axiom of Archimedes is simply the statement that no real number is greater than every integer. The axiom of completeness implies the axiom of Archimedes, but the axiom of Archimedes does not imply the axiom of completeness. However, the axiom of Archimedes is all we need to prove Theorem 1; we won’t need to use the full axiom of completeness.

Now we know, more or less, exactly what we’re trying to prove. It’s always very important to make sure you know this before trying to make a proof, otherwise the attempt will be hopeless. Let’s finally make a start on the proof itself. The statement to be proven is that there is a rational number between every pair of distinct real numbers. The natural way to carry out the proof of a statement like this is to show how, given two distinct real numbers a and b, we can find a rational number r between a and b. For example, we might be able to find a formula for r in terms of a and b. It’s not immediately obvious how we might find such a formula, though. It’s easy to give a formula for a real number between a and b; for example, (a + b) / 2 is a real number between a and b. The problem is in making sure that the number is rational. There aren’t any ways of combining arbitrary real numbers using simple arithmetic operations that will ensure that the result is rational.

Let’s think about what it means for a number to be rational. It means that it can be expressed as a fraction with an integral numerator and an integral denominator. In other words, r is rational if and only if there are two integers m and n such that r = m / n. In fact, because we can cancel out the common factors of m and n if they have any, and we can transfer a minus sign in n up to m, we can express every rational number as a fraction whose numerator and denominator have no common factors and whose denominator is positive. So what we’re looking for is a number of the form m / n, where m and n are integers with no common factors and n is positive, which is between a and b.

As a and b are distinct, one of them must be greater than the other. Let’s assume that b is the greater one. This assumption does not limit us in any way; if b is actually the smaller one, then we can just swap the names of a and b. Then, if m / n is to be between a and b, that means that a < m / n < b. Now, it’s always convenient to get rid of divisions if we can help it. And since n is positive, we can multiply the parts of any inequality by n, and the inequality will still hold; in fact, it will also imply the old one. So, the inequality a < m / n < b is equivalent to the inequality n a < m < n b. Hence, in order to prove Theorem 1, we can prove the following equivalent theorem (which we’ll call a lemma, actually, since that’s the usual term for theorems you are only interested in so that you can prove other theorems with them).

Lemma 1. For every pair of distinct real numbers a and b, there is an integer between n a and n b for some positive integer n.

The difference between Theorem 1 and Lemma 1 is minor; the two are completely logically equivalent statements; and yet Lemma 1 a lot easier to think about, visually. If you had never been told that there is a rational number between every pair of distinct real numbers before, you’d probably be somewhat unsure if it was true. But if you think about what Lemma 1 means, it isn’t too difficult to see that it’s true. Think about the distance between n a and n b on the number line, given an arbitrary positive integer n. This is n b - n a (using the fact that b is greater than a). But this can also be written as n (b - a). So it’s the distance between a and b, enlarged by a factor of n. Now, all the statement requires is that there is an integer somewhere in the n (b - a)-width interval between n a and n b for some positive integer n. In particular, it doesn’t matter how big n needs to be. So the question becomes: is it possible to enlarge the gap between a and b so much that there is at least one integer within the enlarged gap, if we restrict ourselves to integral scale factors, but allow the scale factor to be as large as we like? Well, if the distance between n a and n b (where n is the scale factor) is greater than 1, there will have to be an integer in the interval between n a and n b. And the distance between n a and n b is proportional to n. So, if we can make n as large as we like, we can make the distance between n a and n b as large as we like; in particular we can make it greater than to 1. And then we’re done! (Note that I’ve tacitly relied on the axiom of Archimedes here—can you see why? If not, I’ll explain how shortly.)

At this point, I’m pretty much convinced that Theorem 1 can be proven, but what I said above wasn’t really up to the usual standards for a proof, it was more of an intuitive justification. We need to state precisely how Theorem 1 follows from the axioms. The chief weak point in the reasoning above is the statement that as long as the distance between n a and n b is greater than to 1, there is an integer in the interval between n a and n b. It probably seems pretty obvious that this is true; in general, for every pair of real numbers x and y such that x < y and y - x > 1, there is an integer k such that x < k < y, or so you would think based on intuition. But I can’t immediately see how it follows from the axioms. So let’s try and prove it. The first thing that occurs to me is that we can easily find an integer k such that x < k. Because the existence of such an integer is more or less exactly what the axiom of Archimedes asserts. If there was no such integer, then x would be greater or equal to every integer, and hence x + 1 would be greater than every integer, but the axiom of Archimedes states that no real number is greater than every integer. So the question is, of these integers k such that x < k, how can we find one which is less than y? Well, we’re pretty sure that what we’re trying to prove is true, so there must be at least one integer k' which is greater than x but less than y. Therefore, the least integer k such that x < k must also be less than y, because it is less than k'. So, if we let k' be this least integer, we should be able to prove that k' < y, somehow. But how? A useful thing to do in this kind of situation is to remember what assumptions we have made. If the statement you’re trying to prove can be false if one your assumptions does not hold, you’re going to have to make use of that assumption in the proof; otherwise, your proof would work just as well at proving the statement without making that assumption, yet the statement is not true without that assumption. So we’re necessarily going to have to use the fact that k' is the least integer k such that x < k, because there are integers k such that x < k but y \le k (since the axiom of Archimedes ensures that there are integers greater than y, and y is greater than x). And we’re going to have to use the fact that y - x > 1 at some point, of course. Any ideas? Here’s something: we can rearrange the inequality y - x > 1 to get y > x + 1. Now, let’s suppose that, counter to what we suspect is true, y \le k. Then, since x + 1 is less than y, we have x < k as well. Rearranging this, we have x < k - 1. But if x < k - 1, then k is not the least integer k such that x < k. So our supposition that y \le k leads to an inevitable contradiction. We can therefore conclude that, in fact, k < y, which is what we needed to prove.

So, now let’s return to Lemma 1 and prove it with greater rigour. Remember, we need to find a positive integer n such that there is an integer between n a and n b. The first thing we need to do is to decide what value of n to use. We want the distance between n a and n b, n (b - a), to be greater than 1, i.e. n (b - a) > 1. Dividing both sides of this inequality by b - a (which we can do because a < b, so b - a is positive) we get n > 1 / (b - a). Can we find a positive integer n greater than 1 / (b - a)? Yes, of course we can, by the axiom of Archimedes. The axiom of Archimedes ensures that there is an integer greater than 1 / (b - a); it doesn’t say anything about whether it’s positive; but since 1 / (b - a) is positive, it has to be positive. So we have our value of n. Of course we don’t know exactly what it is, but we know that a value which will work exists. Now, since the distance between n a and n b is greater than 1, we can immediately conclude that there is an integer between n a and n b by what we proved above. This completes the proof of Lemma 1, and thereby Theorem 1.

Just to be totally sure, let’s write the proof out, textbook style.

Theorem. For every pair of distinct real numbers a and b, there is a rational number r such that a < r < b.

Proof. Suppose a and b are real numbers and a < b. Since b - a is positive, 1 / (b - a) exists, and in fact is positive, and by the axiom of Archimedes there is an integer n such that 1 / (b - a) < n. Since 1 / (b - a) is positive, n has to be positive. Also, since b - a is positive, we can multiply both sides of the inequality by b - a to get 1 < n (b - a) = n b - n a. It follows that there is an integer m such that n a < m < n b. Since n is positive, we can divide each part of this inequality by n to get a < m / n < b. As m and n are both integers, m / n is rational.

So, in the end, the proof is just 7 sentences. If you followed this through to the end, you can probably see what I mean about the textbook proofs making things look a lot simpler. And even the description I’ve given in this post has omitted some of the messier details of the process. For example, as I wrote it I made occasional minor errors, mainly to do with strict and non-strict inequalities (for example, I originally only proved that there was an integer between any two real numbers separated by a distance greater than or equal to to 1, which is true, but not sufficient to imply Theorem 1 as the integer might be equal to one of the two real numbers). I opted to correct those rather than leaving them in and making things more confusing. So, hopefully, this has given you some insight into how mathematicians come up with proofs, if you didn’t know much about it already. Bear in mind, though, that this is a pretty straightforward undergraduate-level theorem. Professional mathematicians have to deal with proofs that are much, much, harder and more complicated.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s