4
$\begingroup$

This is a question that I really think about. I wanted to develop my mind, and started trying to prove the Pythagorean theorem of a triangle, trying each day, and now its been a week. I wonder if theorems can be proved in infinite ways, or just a finite number of ways. I think the first one is correct, because each theorem has so many implications, and maybe we can use those implications in reverse order to prove the original theorem. But still, I need an answer from you all, the professionals.

$\endgroup$
  • 2
    $\begingroup$ If you have any proof, a new proof can be formed adding to the original one unuseful statements. So, basically a theorem can have infinitely many proofs. $\endgroup$ – Crostul Feb 2 '16 at 16:15
  • 6
    $\begingroup$ Well, first you need a well-defined meaning of proofs being different. $\endgroup$ – forallepsilon Feb 2 '16 at 16:16
  • 1
    $\begingroup$ In a trivial sense, yes: you can always overcomplicate a proof by adding irrelevant digressions, and there are infinitely many of those. Of course, that's not really what you're asking. But first, you'll have to come up with a sharper definition of what different "ways" of proof are. (I'm not suggesting that's impossible, but certainly it's not trivial.) $\endgroup$ – BrianO Feb 2 '16 at 16:17
  • 1
    $\begingroup$ You probably want to read into this post first, before trying to answer this question $\endgroup$ – vrugtehagel Feb 2 '16 at 16:23
  • 2
    $\begingroup$ @vrugtehagel Thanks for that link, a good discussion and intro to current approaches. These are tricky questions. One of the answers there remarks "And while the syntactic notions of equivalence capture quite well the formal operations by which one can relate different proofs, the real challenge is (imho) to give a formal definition of semantic equivalence and recognize it syntactically!" Because of Rice's Theorem, I expect it won't be possible to meet that "real challenge". $\endgroup$ – BrianO Feb 2 '16 at 16:30
5
$\begingroup$

There are many proofs, in fact, I have seen a book with a title like "100 Proofs of the Pythagorean Theorem." One of the proofs listed there was developed by a President of the United States (Grover Cleveland).

Here is a site with many proofs: http://www.cut-the-knot.org/pythagoras/

The first proof I did (and I am obviously not the first one to find this proof) involves dropping a perpendicular from the right angle vertex to the hypotenuse. You then have three similar triangles, and using the fact that the ratios of corresponding sides are equal, plus a bit of simple algebra, you can derive the theorem.

But your question runs deeper: What makes two proofs "different"?

Let's define a proof of proposition $A$ from starting point $B$ as a sequence of steps, each obeying some defined set of rules of logic, that ends at $A$ and that are free to assume $B$. Well, at any step in a proof, I could insert some proof of a completely unrelated theorem, and the new longer proof is still a proof of the original. But would you consider that a "different" proof of the original?

Similarly, if in my proof I label the foot of the altitude $D$ and you present the same logic but label the foot of the altitude $E$, are those two different proofs?

In the field of automated theorem proving, one might study "irreducible" proofs in the sense that each step in the proof is essential. If you have that, you can say that two proofs are equivalent if there is a mapping of the symbols used in proof 1 to those used in proof 2, such that the resulting mapped proof is identical to proof 2. But it turns out to be hard to define what an irreducible proof means.

So I think you can't cleanly answer the question of whether there are a finite number of different proofs, because you can't come up with a useful meaning to the word "different" in that sense.

$\endgroup$
  • 1
    $\begingroup$ I believe the book you're thinking of is The Pythagorean Proposition, by Elisha Loomis. It contains 367 proofs. (Note the "new book" price, a bargain at $6.57 per proof!) $\endgroup$ – Barry Cipra Feb 2 '16 at 16:42
3
$\begingroup$

If you take a purely mechanical notion of "proof" as suggested in some of the comments, then yes, there are lots of "different" proofs for any given theorem. If a "proof" is just a sequence of statements, starting with assumptions/axioms, where each subsequent statement logically follows from those before it, and the last statement is the conclusion of the proof, then you can make a "different" sequence of statements by randomly placing a tautology anywhere in the middle. In this sense, there are certainly infinitely many "different" proofs for any theorem.

"But wait," I can already hear you saying, "that's just fluffing up an existing proof -- are there many fundamentally different proofs for a theorem?" Well, what do you mean by "fundamentally different"? When I teach introduction to proofs, I often give examples where I prove the same statement twice, for example once by contradiction and once by contrapositive. If you look closely at the proofs, they are doing the same work with the same tools and assumptions, but the proofs are structurally different. Does that make them "fundamentally different"? Many students might be inclined to say "yes," but many working professional mathematicians would disagree -- they are "the same proof, just written differently."

I had this come up in an article based on my thesis -- a reviewer suggested a "simpler" approach to a proof believing it would be shorter, but it turned out to be a purely structural difference and didn't even have a significant effect on the length of the proof. I rewrote it that way anyway, of course.

This higher-level view of the theorem ignores the structural details, but how do you use this for a strict definition of "fundamentally different"? I think the "syntactic equivalence" mentioned in the post link from @vrugtehagel is really trying to formalize this notion of "same proof but structurally different" as an equivalence relation between proofs. It is still unclear if non-equivalence in this sense will actually capture the semantic concept of proofs being "fundamentally different," though, as @BrianO points out.

My point here is that these notions of "the same proof" or "fundamentally different" are ill-defined at best, and people may even disagree about their meanings. The only good answer to your question is the mechanical one above, perhaps with the suggested overlay of "syntactic equivalence." Anything else gets into squishy matters of personal preference and interpretation. Even so, I think most working professional mathematicians (myself included) would be inclined to answer "yes," but then they would have a hard time explaining what they mean when they give that answer -- they would either revert to the mechanical definition of "proof" or start waving their hands around a lot.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.