The nature of mathematical proof is a fascinating subject, particularly when we delve into the question of equivalence. When do we consider two proofs to be fundamentally the same, even if they appear different on the surface? This question was the crux of a presentation I gave at a mathematics conference alongside philosophers and psychologists. While preparing my contribution for the conference proceedings, I found myself grappling with the concept of “essential equality” in proofs. This led me to ponder the seemingly simple yet surprisingly complex question: “When are two proofs the same?”
This question, rooted in our shared experience with mathematical reasoning, is ripe for exploration. We often use informal yet insightful terms to describe proofs – “elegant,” “genuinely insightful,” “the correct approach.” Trying to define these terms precisely is a challenge, but even defining the sameness of proofs presents significant hurdles. I am eager to hear your perspectives and, in particular, examples of proofs that initially appear distinct but, upon closer inspection, reveal a shared underlying concept.
A common observation is that there are standard techniques to transform one proof into another. When we apply such transformations, the resulting proofs often feel like mere variations of the same core argument. For instance, an inductive proof can frequently be converted into a proof by contradiction using a minimal counterexample. Let’s illustrate this with the fundamental theorem of arithmetic: the proof that every number greater than one can be factorized into primes.
Consider the proof by minimal counterexample. Assume there exists a positive integer that cannot be factorized into primes. Let be the smallest such integer. is not prime, so it can be expressed as a product where both and are greater than 1. Since was the minimal counterexample, both and must be factorizable into primes. Combining the prime factorizations of and gives a prime factorization for , contradicting our initial assumption.
Image alt text: Diagram illustrating the structure of a proof by minimal counterexample, showing the initial assumption leading to a contradiction.
Now, let’s examine the inductive proof. We employ the principle of strong induction. Assume that every integer less than can be factorized into primes. We aim to show that can also be factorized. If is prime, we are done. If not, then where and . By our inductive hypothesis, both and can be factorized into primes. Therefore, their product, , can also be factorized into primes, completing the inductive step.
Image alt text: Diagram illustrating the structure of an inductive proof, highlighting the base case, inductive hypothesis, and inductive step.
This example, while illustrating the convertibility of proofs, is somewhat unexciting because the two proofs are clearly very similar. The transformation from one to the other is almost mechanical. More intriguing are cases where the underlying sameness is revealed only through a more complex analysis. One such example, which I explored in detail in the section omitted from my conference article, is the proof of the irrationality of .
Let’s briefly revisit the standard proof by contradiction. Assume is rational, so it can be written as and are integers with no common factors (lowest terms). Squaring both sides yields , or . This means is even, which implies that must also be even. If is even, we can write for some integer . Substituting this back into our equation gives , which simplifies to , and further to . This shows that is also even, and therefore is even. But this contradicts our initial assumption that and have no common factors, as we have now shown they are both even (divisible by 2).
Here is another proof, also by contradiction, but seemingly different. Again, assume in lowest terms. Consider the algebraic manipulation . Wait, there was a mistake in the original equation provided in the source. Let’s correct it to . Substituting for , we get . Thus, . Since , we know that , so and . Also, since , we have and so . The denominator of the fraction , which is , is less than . This contradicts the assumption that was in lowest terms, as we have found another representation of as a fraction with a smaller denominator (though this needs more rigorous justification about maintaining integer ratios, which is implicit but should be clarified for a fully formal proof). More precisely, if is in lowest terms and , then would imply that is also a representation of was in lowest terms with the smallest possible denominator, and we showed that (which holds as ), then we would have a contradiction.
While both proofs utilize contradiction and start by assuming in lowest terms, their paths diverge significantly. The first proof focuses on the parity (evenness or oddness) of and based on factorization by 2, whereas the second proof relies on algebraic manipulation to derive a contradiction based on the size of the denominator. One could argue they are distinct proofs. However, in a conversation with Terence Tao, he suggested a broader perspective from which these two proofs could be seen as different manifestations of the same fundamental idea, possibly related to . Terry, if you happen to read this, reminding me of your exact insight would be a perfect illustration of “non-obvious equivalence” between proofs.
Here’s a third proof of the irrationality of , using continued fractions. The continued fraction expansion of is infinite and repeating: . Since the continued fraction expansion of any rational number must terminate, must be irrational.
Image alt text: Visual representation of the continued fraction expansion of the square root of 2, showing the repeating pattern of 2s in the denominator.
Finally, a fourth argument involves coprime numbers and sequences. Let and be coprime, and assume . Consider the transformation to new numbers and . It can be shown that if and are coprime, then and are also coprime. Furthermore, . Starting with any coprime , we can generate a sequence of fractions , each in lowest terms, where tends to infinity, and the absolute difference remains constant. This leads to showing that is of the order of magnitude , and consequently, is also of the order of magnitude . However, rational numbers cannot be approximated this quickly by other rationals with increasing denominators. If and are distinct rationals, then (if and assuming integers are involved). For a fixed denominator , the approximation order cannot be better than .
Intriguingly, the second, third, and fourth proofs, despite their apparent differences, are essentially the same when viewed from a certain perspective. The sequence construction in the fourth proof is directly related to the continued fraction expansion in the third proof, and the reduction of fraction size in the second proof is the inverse operation. While the fourth proof introduces inequalities, this is not a fundamental distinction. Precisely articulating why these proofs are equivalent is a further interesting challenge.
Returning to our initial question of “what is comparing two essentially unalike things to one another?” in the context of proofs, we see that proofs that appear vastly different in their approach – parity arguments, algebraic manipulation, continued fractions, sequence constructions – can, in fact, be deeply connected. Comparing these seemingly disparate methods reveals underlying common structures and highlights the multifaceted nature of mathematical truth.
I am keen to gather more examples of proofs that, despite initial appearances of dissimilarity, turn out to be fundamentally the same. Furthermore, I am interested in “conversion techniques” – methods for transforming one proof into another while preserving its essential core. While formal logical theories are relevant, I am more interested in a high-level understanding of proof equivalence.
Several general questions emerge from this exploration. If two proofs are essentially the same, is there always a more general framework that reveals their shared essence, where the differences are merely superficial choices? Is “essential equivalence” a true equivalence relation, or can we transition through a series of “essentially equivalent” proofs to reach one that is “genuinely different” from the starting point? And perhaps most challenging: Can we ever definitively prove that two proofs are genuinely different? How would one even approach such a task? Could we define an “invariant” of a proof to help distinguish genuinely different proofs?
These questions invite further reflection on the nature of mathematical understanding and the criteria we use to judge the “sameness” or “difference” of mathematical arguments. Your insights and examples are highly welcome as we continue to explore this fascinating aspect of mathematical reasoning.
