A couple of years ago I spoke at a conference about mathematics that brought together philosophers, psychologists and mathematicians. The proceedings of the conference will appear fairly soon—I will give details when they do. My own article ended up rather too long, because I found myself considering the question of “essential equality” of proofs. Eventually, I cut that section, which was part of a more general discussion of what we mean when we attribute properties to proofs, using informal (but somehow quite precise) words and phrases like “neat”, “genuinely explanatory”, “the correct” (as opposed to merely “a correct”), and so on. It is an interesting challenge to try to be as precise as possible about these words, but I found that even the seemingly more basic question, “When are two proofs the same?” was pretty hard to answer satisfactorily. Since it is also a question on which we all have views (since we all have experience of the phenomenon), it seems ideal for a post. You may have general comments to make, but I’d also be very interested to hear of your favourite examples of different-seeming proofs that turn out, on closer examination, to be based on the same underlying idea (whatever that means).
A general remark that becomes clear quickly when one thinks about this is that there are fairly standard methods for converting one proof into another, and when we apply such a method then we tend to regard the two proofs as not interestingly different. For example, it is often possible to convert a standard inductive proof into a proof by contradiction that starts with the assumption that is a minimal counterexample. In fact, to set the ball rolling, let me give an example of this kind: the proof that every number can be factorized into primes.
The usual approach is the minimal-counterexample one: if there is a positive integer that cannot be factorized, let be a minimal one; is not prime, so it can be written as with both and greater than 1; by minimality and can be factorized; easy contradiction.
Now let’s give the inductive version. We need the “strong” principle of induction. Suppose, then, that we have proved that every integer up to can be factorized and are trying to factorize . If is already prime, then we are done. Otherwise, we can write with both and greater than 1. But then and are less than , so by induction they can be factorized. Putting together those factorizations gives a factorization for and the inductive step is complete.
(I missed out the proof that the induction starts, just as I did not check in the first proof that there exists a number that can be factorized.)
That’s a rather boring example of sameness of proofs—boring because they are so obviously the same, and one can even point to a mechanical procedure that converted one into the other (which can be applied to many other proofs). More interesting are examples where the sameness becomes apparent only after a more complicated process of transformation. At this point, I’d like to mention the theorem that I discussed in great detail in the bit that I removed from my article: the irrationality of .
Very briefly, here’s the standard proof. If is rational, then we can write it as . Let us do so in such a way that and are not both even. We know that , so is even, so is even, so for some integer . This gives us , so , so is even, so is even, which is a contradiction.
Now, equally briefly, here is another proof. Suppose again that and let be written in its lowest terms. Now . Substituting for and tidying up, this gives us that . But , so the denominator of the right-hand side is less than , which contradicts the minimality of (and hence too, since their ratio is determined).
Now there are some similarities between those two arguments: both assume that and aim for a contradiction, assuming that is in its lowest terms. But there are also definite differences. For example, the first proof doesn’t actually care whether and are minimized: it just wants them not both to be even. The second proof doesn’t care at all about the factorizations of and but does care about their sizes. So I’d maintain that they are different proofs. Having said that, I once put that to Terence Tao in a conversation and he immediately adopted a more general perspective from which one could regard the two arguments as different ways of carrying out the same essential programme. It had something to do with if I remember correctly. Terry, if you felt like reminding me of exactly what you said, that would be a perfect illustration of “non-obvious equivalence” between proofs.
Here, though, is a third argument for the irrationality of . You just work out the continued-fraction expansion. It comes out to be . Since the continued-fraction expansion of any rational number terminates, is irrational.
Here’s a fourth. Let and be coprime and suppose that does not equal . Then and are also coprime. We also find that . From this observation we can build a succession of fractions , each in their lowest terms, with tending to infinity and with all equal. From that we find that has order of magnitude , and from that it is easy to verify that has order of magnitude as well. But it is impossible to find a sequence of rationals with denominators tending to infinity that approach a rational this quickly. Indeed, , which for fixed has order of magnitude . (For large and coprime and , the difference cannot be zero.)
I won’t demonstrate it here, but it’s not too hard an exercise to see that the second, third and fourth proofs are all essentially the same. (At some point, perhaps I’ll put a link to a more detailed account of exactly why, at least for the second and third. The fourth has only just occurred to me.) For instance, the construction of the sequence in the fourth proof is the same as the construction of the continued-fraction expansion of (as lovers of Pell’s equation will know). Also, the way that we produced from is just the reverse of the way that we produced a smaller fraction from in the second proof. The fourth proof is perhaps very slightly different, in that it involved inequalities, but that was not a fundamental difference. (It would be interesting to be precise about why not—this is what I haven’t got round to thinking about yet.)
To repeat: for the time being I am interested in responses of two kinds. First, I’d like to see lots of examples of proofs that turn out to be essentially the same when they might not initially seem that way. Secondly, I’m keen to see examples of “conversion techniques”—that is, methods for transforming a proof into another that is not interestingly different. See this comment for some interesting links, though here I am not so much looking for a formal theory right down at the level of logical formulae. Rather, I would like as good a picture as possible of high-level equivalence of proofs.
Some general questions are quite interesting. For instance, if two proofs are essentially the same, must there always be some more general perspective from which one can see that the only differences between them consist in arbitrary choices that do not affect the argument in an important way? (A simple example of what I mean is something like replacing “Let ” by “Let ” in an argument in real analysis. But there are much more interesting examples of this.) Also, is “essential equivalence” really an equivalence relation, or could one morph in several stages from one proof to another that was “genuinely different”? (My own feeling, by the way, is that the morph would itself be a demonstration of essential equivalence, but perhaps a really good example might change my mind on that.) Is it ever possible to give a completely compelling argument that two proofs are genuinely different? How would one go about such a task? Could one attach an invariant to a proof, perhaps?