Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If there are two different proofs for one theorem, at some level are the two proofs the same, or can they be fundamentally different?

In other words, if you have two proofs of a theorem, can one show that the two proofs are expressing the same thing in different ways, and then remove the redundancies and generate a "shorter" proof?

share|improve this question
    
It depends. For example the Prime Number Theorem has a Elementary proof as well as an Analytic proof and these two proofs are completely different. –  anonymous Jan 24 '11 at 16:02
3  
can you explain what you mean by "completely different"? –  picakhu Jan 24 '11 at 16:03
5  
There was a long discussion of this at mathoverflow.net/questions/3776/… . –  Qiaochu Yuan Jan 24 '11 at 16:31
    
@QY: Thanks, that was exactly what I was looking for. –  picakhu Jan 24 '11 at 16:39
    
See mathoverflow.net/questions/3776/… –  Kaveh May 27 '11 at 7:57
add comment

2 Answers

up vote 7 down vote accepted

They can be "completely different".

For example, some existence results have both indirect proofs and constructive proofs. There is often no way to interpret the "indirect proof" as "essentially the same" as the constructive proof.

Or you have the many different proofs of Quadratic Reciprocity. Gauss's first proof, in the Disquisitiones Arithmeticae, is very constructive; it is done by recursion, and for example it shows exactly how to transform a solution of $x^2\equiv p\pmod{q}$ into a solution of $x^2\equiv q\pmod{p}$ when $p$ and $q$ are not both congruent to $3$ modulo $4$; whereas his third proof was purely combinatorial, counting certain objects, and his sixth used Gauss sums, again an essentially different approach. Eisenstein used infinite products for his fifth proof, Kummer used quadratic forms, Zolotarev used permutations; Auslander and Tolimieri used the Fourier transform, Weil used theta functions. These are truly essentially different approaches, with no easy way to pare them down to the same thing (unless you "pare them down" to the statement of Quadratic Reciprocity itself).

share|improve this answer
    
Thanks, this is insightful, however, I was thinking about an algorithmic mathematical systems, where computers can generate proofs. If there are fundamentally different methods to prove something, doesn't that seem a bit weird? For example I was thinking was can a computer generate a Synthetic proof for a geometric question ? –  picakhu Jan 24 '11 at 16:22
    
@picakhu: I see not reason why "fundamentally different methods to prove something" would be "a bit weird". Unless your system happens to be rather poor, I would expect a lot of paths leading to the same points in the landscape. –  Arturo Magidin Jan 24 '11 at 16:28
    
I never thought about it that way! Thanks! –  picakhu Jan 24 '11 at 16:29
add comment

They can come as "completely different". Consider proofs in logic. A classical logician CL can prove some theorem T used a reductio type argument. A constructivist logician CO proving T proves T in a very different way. Were it the case that the proofs of CO and CL were fundamentally the same at some level, then (at least it seems so) that the proof theory of CO and CL should match exactly. But, of course, they don't, so the proofs of CO and CL are not fundamentally the same, and thus different. So, no to the second question also.

share|improve this answer
    
This is the second time you start an answer with a "paragraph indent". Compare how it looks now, after I removed it, to how it used to. Please don't do it again. –  Yuval Filmus May 24 '11 at 14:06
    
CL extends CO so a constructive proof is also a "normal" proof, though usually more complicated than one can be done classically. –  Yuval Filmus May 24 '11 at 14:07
    
Sorry Yuval, I ddin't understand how that works! –  Doug Spoonwood May 27 '11 at 15:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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