Pythagorean Proofs

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

nevskey1
Posts: 257
Joined: Sat Oct 27, 2007 2:12 am UTC

Pythagorean Proofs

Postby nevskey1 » Thu Nov 08, 2007 4:02 pm UTC

I'm reading The Golden Ratio right now and in it Livio writes the following: "In his 1940 book The Pythagorean Proposition, mathemetician Elisha Scvott Loomis presented 367 proofs of the Pythagorean theorem...."

This lead me to wonder how many proofs there are. Is it possible to determing an exact number? Could there be an infinite amount of proofs? If so, could that be proven? Or is this an NP-hard (I think that's the term) issue, that we can't know the number of proofs until we've got them all, but if we think we got them all, we can't know that there's not another?

I mean for this question to be specifically about the Pythagorean theorem, not just a general discussion of the computability issue. Has there been any work done on this?

Thanks
-nev
"Personally, I'd never want to be a member of any group where you either have to wear a hat or you can't wear a hat." --George Carlin.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Pythagorean Proofs

Postby quintopia » Thu Nov 08, 2007 4:08 pm UTC

Well, the Pythagorean theorem should fall into the category of many other things, in that I wouldn't expect it to be possible to prove that there are no other ways to prove it. Even if you define equivalence classes among the proofs, what's to stop another class of proofs from being discovered?

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Thu Nov 08, 2007 4:17 pm UTC

You can always take a proof, throw in unnecessary steps, such as stating that 2=1+1 in the middle of it, to get a new one. Sometimes it's also possible to change the order of steps. If you say those are the same, then think about how you would define two proofs to be equal. Most of those proofs probably use the same actual steps to arrive at the conclusion, but use different high-level ways of stating them. What usually makes proofs different is using different theorems, but if you dive into the proofs of those theorems, and remove all unnecessary steps, you'll probably wind up with something very similar.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Pythagorean Proofs

Postby quintopia » Thu Nov 08, 2007 4:41 pm UTC

True, it could be argued that any given theorem has only one proof: the simplest one.

If you take any proof, and expand it until you have atomic operations, and then remove the ones that cancel, you get that proof, no matter the proof you start with. I'd like to think this is true.

Unfortunately, it's possible, on occasion, to prove the same result starting from two different sets of axioms, and I don't think that such things could ever be expanded to the same form.

This may or may not be true for the thm at hand.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Thu Nov 08, 2007 5:06 pm UTC

I definitely think there are different shortest proofs (if we use the string-of-symbols kind of pure logic proofs) for some theorems, but many "macroscopic" proofs that seem different on the surface will probably boil down to essentially the same thing.

To compare proofs, they have to use the same axioms, so if you use different ones, you have to prove them first, and I think most Pythagoras's theorem proofs will be essentially the same if reduce them to the same axiom set and remove unnecessary steps.

nevskey1
Posts: 257
Joined: Sat Oct 27, 2007 2:12 am UTC

Re: Pythagorean Proofs

Postby nevskey1 » Thu Nov 08, 2007 5:30 pm UTC

Very interesting points, thanks for the input.

So would you say that there's an infinite array of possibilities at the "macroscopic" leve, but a finite set of "microscopic" axiom sets from which that macroscopic array can be reached? Or will the macroscopic array also start to wear down eventually (become finite) to the point that nothing more can be added that has something to do with the proof? (Of course new strings can always be introduced that have nothing to do with anything.)

And can any of this be proven?
"Personally, I'd never want to be a member of any group where you either have to wear a hat or you can't wear a hat." --George Carlin.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Thu Nov 08, 2007 9:32 pm UTC

Infinitely many "high-level" proofs. This is because you can make arbitrarily complicated structures and build a theory around it, and subsequently prove theorems which have the Pythagorean theorem as a special case.

If you just consider formal logic proofs (which are just strings of symbols, like this: http://us.metamath.org/mpegif/equid.html ), then there's a shortest one (if there is one at all), but there may be many (but finitely many) of that length. I'd guess there's only finitely many sensible ones, but I'm not sure. With finitely many axioms, there should only be finitely many tricks you can use, which should occur more than once in a silly proof which has been made unnecessarily long. I don't know how you could detect if a proof is unnecessarily long. That is probably NP-hard, or maybe even undecidable.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Pythagorean Proofs

Postby antonfire » Thu Nov 08, 2007 9:53 pm UTC

quintopia wrote:If you take any proof, and expand it until you have atomic operations, and then remove the ones that cancel, you get that proof, no matter the proof you start with. I'd like to think this is true.

I really doubt it. There are lots of very different proofs of quadratic reciprocity, and even of the infinitude of primes. There's Euclid's argument, there's the topology one, which does essentially reduce to Euclids' argument, but then there's using the Riemann Zeta function to show that Sum 1/p doesn't converge. I think that even if you expand that into atomic operations and start "cancelling" like crazy, you won't end up with Euclid's argument.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Thu Nov 08, 2007 10:18 pm UTC

An explicit counterexample to quintopia's hypothesis: show that there exists a set with one member from each set in the set {{0,1},{2,3}}. You can either give an example, say {0,2}, or invoke the axiom of choice. Neither proof can be reduced to the other.

User avatar
Lamil_Lerran
Posts: 9
Joined: Tue Oct 30, 2007 8:33 pm UTC

Re: Pythagorean Proofs

Postby Lamil_Lerran » Thu Nov 08, 2007 10:30 pm UTC

I think for most reasonable definitions of "proof A is equivalent to proof B" there will be either infinitely many classes of proofs of a statement or exactly one class of proofs of a statement. I have a set of definitions and a proof under the spoiler.

Spoiler:
Here's how I'll define my terms: Let a "Proof of S" be a finite sequence P of statements P1, P2, ..., Pp such that each statement is either an axiom or can be deduced from the previous statements (e.g. via first order logic) and such that S is one of the statements Pn.

Suppose we define two proofs P and Q to be equivalent if and only if their corresponding statements are equal, i.e., Pi=Qi for all i. Then clearly there are infinitely many non-equivalent proofs of any statement S just by adding useless statements, as Torn Apart By Dingos noted.

Similarly if we define two proofs P and Q to be equivalent if and only if the sets {Pi} and {Qi} are equal (i.e. allowing rearrangement) we will get infinitely many non-equivalent proofs of any statement by the same logic.

Therefore, we need to somehow account for adding useless statements. So we will call proofs P and Q equivalent if we can construct Q by adding a single statement X to the sequence P1, P2, ..., Pp (we can add it anywhere). We certainly want our notion of equivalence to be an equivalence relation, so we need symmetry. Thus, we will also call P and Q equivalent if we can construct P by adding a single statement X to the sequence Q1, Q2, ..., Qq (or equivalently, if we can construct Q by removing some statement from P). We also need transitivity, so we will call P and Q equivalent if we can construct one from the other by performing this adding/removing operation some finite number of times.

Now suppose P and Q are both proofs of S. Construct a proof P' = Q1, Q2, ..., Qq, P1, P2, ..., Pp by adding the Qi to the front of the proof in order starting with 1 (i.e., start with Q1, P1, P2, ..., Pp then Q1, Q2, P1, P2, ..., Pp and so on). Clearly each of these intermediate proofs is valid a valid proof of S, and so P' is equivalent to P.

Remove the statements Pi in order starting with Pp, until only the statements Qi remain. This results in a sequence of valid proofs of S, and so Q is equivalent to P'. Then by transitivity P is equivalent to Q. Thus, any two proofs of S must be equivalent.


In short, I've shown that if we want the two proofs P and [P plus useless statement X] to be equivalent, and if we want our notion of "equivalence" to be an equivalence relation, then there is only one equivalence class of proofs of any statement. (Well, and if we use my definition of "proof," which I think is similar to but weaker than what Godel's incompleteness theorem requires of theories -- I think it's analogous to a completely enumerable theory.)

I'll admit that I don't have enough experience with this sort of thing to feel confident about my proof, but I'm sure someone who knows more than me will step in if I said something terribly stupid.

P.S. There have been some replies since I started writing this, so I have a further point: Note that the key notion in my proof is that adding/removing statements leaves equivalent proofs. In particular, this means that you need to be able to add statements -- not just "cancel out" statements as in the version we reduced to atomic operators. Also, note that you can add axioms, allowing you to switch between e.g. the axiom of choice and just choosing something.

[edit: grammar]
Last edited by Lamil_Lerran on Sat Nov 10, 2007 10:55 pm UTC, edited 1 time in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Pythagorean Proofs

Postby quintopia » Thu Nov 08, 2007 11:33 pm UTC

antonfire wrote:
quintopia wrote:If you take any proof, and expand it until you have atomic operations, and then remove the ones that cancel, you get that proof, no matter the proof you start with. I'd like to think this is true.

I really doubt it. There are lots of very different proofs of quadratic reciprocity, and even of the infinitude of primes. There's Euclid's argument, there's the topology one, which does essentially reduce to Euclids' argument, but then there's using the Riemann Zeta function to show that Sum 1/p doesn't converge. I think that even if you expand that into atomic operations and start "cancelling" like crazy, you won't end up with Euclid's argument.


As I said, I doubt it too.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Pythagorean Proofs

Postby btilly » Fri Nov 09, 2007 10:04 pm UTC

Torn Apart By Dingos wrote:I definitely think there are different shortest proofs (if we use the string-of-symbols kind of pure logic proofs) for some theorems, but many "macroscopic" proofs that seem different on the surface will probably boil down to essentially the same thing.

To compare proofs, they have to use the same axioms, so if you use different ones, you have to prove them first, and I think most Pythagoras's theorem proofs will be essentially the same if reduce them to the same axiom set and remove unnecessary steps.


I can't speak for "most proofs", but I can say that the several proofs of the Pythagorean theorem that I have learned bear no relationship to each other. And as far as I can tell, the ones that I have seen have no unnecessary steps in them.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
el sjaako
Posts: 45
Joined: Sun Feb 11, 2007 3:52 pm UTC
Location: Netherlands
Contact:

Re: Pythagorean Proofs

Postby el sjaako » Fri Nov 09, 2007 11:43 pm UTC

I think a better equivalance relation between proofs (than Lamil_Lerran's) would be one where you can reorder or remove P's or Q's, as long as the whole statement remains true. They are equivelent if you can then get Pn = Qn for all n (and P and Q need te be equally large). This allows for proofs that are different, yet still seems intuitively correct. But if you can add elements also you can construct completely new proofs.

Something else that I noticed from Lamil_Lerran's story: a finite number of elements in a proof. I'm not sure I agree, isn't a proof by induction basicly an infinite number of statements?

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Sat Nov 10, 2007 12:19 am UTC

btilly wrote:
Torn Apart By Dingos wrote:I definitely think there are different shortest proofs (if we use the string-of-symbols kind of pure logic proofs) for some theorems, but many "macroscopic" proofs that seem different on the surface will probably boil down to essentially the same thing.

To compare proofs, they have to use the same axioms, so if you use different ones, you have to prove them first, and I think most Pythagoras's theorem proofs will be essentially the same if reduce them to the same axiom set and remove unnecessary steps.


I can't speak for "most proofs", but I can say that the several proofs of the Pythagorean theorem that I have learned bear no relationship to each other. And as far as I can tell, the ones that I have seen have no unnecessary steps in them.

I don't think you've seen any of them expressed in formal logic. Reduced to that, there will certainly be unnecessary steps (in a proof, you might use that addition is commutative, but you actually only need that a^2+b^2=b^2+a^2).

But I'd like to detract what I said. Even for simple theorems in logic, there are different routes to take, so one large proof could have many different appearances reduced to formal logic. And as Lamil_Lerran showed, there seems to be no useful way to declare two proofs to be equal (my example using AoC earlier was a clear example of two proofs being obviously different, but if we define equality as before, they must be the same). Possibly you could require that a valid proof should have no unnecessary steps in it, but I think you could embed unnecessary steps into necessary steps somehow.

The proofs in my example above are obviously different because they use different axioms, so maybe you could define two proofs to be equal if they use the same assumptions ("same" meaning you could derive the assumptions of either proof from the other's assumptions).

A problem then, however, would be that one valid proof would be one that just assumes the theorem, and states it in a single step to prove it. It's true, after all, and it's the weakest set of axioms needed to prove it.

It would maybe make more sense to define two proofs to be equal if they use the same axioms. I'm not sure how useful that would be though. Most proofs of high-level theorems probably use all axioms in intermediate steps.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Sat Nov 10, 2007 12:32 am UTC

el sjaako wrote:I think a better equivalance relation between proofs (than Lamil_Lerran's) would be one where you can reorder or remove P's or Q's, as long as the whole statement remains true. They are equivelent if you can then get Pn = Qn for all n (and P and Q need te be equally large). This allows for proofs that are different, yet still seems intuitively correct. But if you can add elements also you can construct completely new proofs.

Something else that I noticed from Lamil_Lerran's story: a finite number of elements in a proof. I'm not sure I agree, isn't a proof by induction basicly an infinite number of statements?

That wouldn't be an equivalence relation. P would be equal to P Q which would be equal to Q, but P and Q wouldn't be equal.

If you use the Peano axioms, there is the axiom of induction, which is then used in a single step. I think I've read about there being infinite proofs, but I don't think they manifest themselves in any of the proofs one usually sees.

User avatar
Lamil_Lerran
Posts: 9
Joined: Tue Oct 30, 2007 8:33 pm UTC

Re: Pythagorean Proofs

Postby Lamil_Lerran » Sat Nov 10, 2007 10:54 pm UTC

Torn Apart By Dingos wrote:
el sjaako wrote:Something else that I noticed from Lamil_Lerran's story: a finite number of elements in a proof. I'm not sure I agree, isn't a proof by induction basicly an infinite number of statements?


If you use the Peano axioms, there is the axiom of induction, which is then used in a single step. I think I've read about there being infinite proofs, but I don't think they manifest themselves in any of the proofs one usually sees.


I restricted my proofs to being finite for convenience and because it doesn't gain us much to allow infinite proofs. Note that since the statement S that we want to prove must appear somewhere in the proof, and by the well-ordering of the naturals, we can find a minimal n such that the statement Pn is the first appearance of S in the proof P. Thus, every infinite proof contains a finite subproof, and any statements after Pn will be "useless."

This also gives a method for constructing an infinite proof Q from an infinite proof P. Adjoin a finite subproof of Q to the front of P, remove all the statements of P (by induction), add all the remaining statements of Q (by induction).

Infinite proofs might be more interesting if we indexed their statements with uncountable sets. Unfortunately, they also become much harder to deal with (certainly beyond my abilities).

[edit: you probably don't even need to go to uncountable sets to get interesting infinite proofs, just to unusual orders. For instance, the well-ordering 1, 2, 3, ... , 0 would eliminate my "every infinite proof has a finite subproof" lemma (for S=P0), and so is potentially interesting.]

User avatar
MartianInvader
Posts: 809
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Pythagorean Proofs

Postby MartianInvader » Sun Nov 11, 2007 4:44 pm UTC

I think you probably could define a good equivalence (or something similar) so that there might be a finite number of proofs. For example, the first thing I would do is say that if we have a statement in a proof that is never used later (e.g. an unneccessary '1+1=2'), then we can delete that statement to obtain a new proof. We can define two proofs to be equivalent if one can be reached from the other by a sequence of adding and removing useless steps in this way. Maybe toss in another legal type of step or two, and then prove that there's only finitely many proofs of the Pythagorean Theorem: sounds like a reasonable graduate thesis!
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Pythagorean Proofs

Postby Owehn » Sun Nov 11, 2007 7:56 pm UTC

Previously in this thread it was pointed out that any equivalence relation, so long as P is equivalent to P' if you add or remove a useless step, requires any two proofs of the same theorem to be equivalent. The reason is that if you have two proofs, P and Q, you can adjoin the lines of Q one at a time (starting at the beginning) and then remove the lines of P (starting at the end) to get from P to Q.
[This space intentionally left blank.]

User avatar
MartianInvader
Posts: 809
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Pythagorean Proofs

Postby MartianInvader » Mon Nov 12, 2007 4:59 am UTC

Ok, sorry, misread that proof. Nonetheless, I still think you could approach this problem... how about a partial order? P <= P' if P can be obtained from P' by successive removals of useless steps (maybe allow some other types of one-way changes as well). Then you'd turn the set of all proofs into a partially ordered set, and you could look for minimal elements and try to prove only finitely many exist.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Mon Nov 12, 2007 4:30 pm UTC

It would be silly to define two proofs to be equal iff one of them has the same steps in the same order, but with added useless steps. No actual proofs have useless steps.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Pythagorean Proofs

Postby btilly » Mon Nov 12, 2007 5:56 pm UTC

Torn Apart By Dingos wrote:It would be silly to define two proofs to be equal iff one of them has the same steps in the same order, but with added useless steps. No actual proofs have useless steps.


I take it from this comment that you've never had to grade math homework.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Pythagorean Proofs

Postby antonfire » Mon Nov 12, 2007 10:31 pm UTC

Torn Apart By Dingos wrote:It would be silly to define two proofs to be equal iff one of them has the same steps in the same order, but with added useless steps. No actual proofs have useless steps.

We're wandering to the realm of relevant logic here, which is not the sort of logic that underpins mathematics. Classical logic is, and under that, a proof with useless steps is still a perfectly good proof.

MartianInvader wrote:Ok, sorry, misread that proof. Nonetheless, I still think you could approach this problem... how about a partial order? P <= P' if P can be obtained from P' by successive removals of useless steps (maybe allow some other types of one-way changes as well). Then you'd turn the set of all proofs into a partially ordered set, and you could look for minimal elements and try to prove only finitely many exist.

At this point, you need to precisely define what you mean by "useless". I imagine it's not too hard to construct steps that are useless, but in a way that makes them hard to remove, or to even tell that they're useless. I really think that under just about any definition, you'd end up with either one proof or infinitely many.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pythagorean Proofs

Postby Torn Apart By Dingos » Mon Nov 12, 2007 11:23 pm UTC

btilly wrote:
Torn Apart By Dingos wrote:It would be silly to define two proofs to be equal iff one of them has the same steps in the same order, but with added useless steps. No actual proofs have useless steps.


I take it from this comment that you've never had to grade math homework.
I have. Today, actually. Hence the qualification "actual" proofs. :) A collection of well-written Pythagoras proofs won't have useless steps in them.

antonfire wrote:
Torn Apart By Dingos wrote:It would be silly to define two proofs to be equal iff one of them has the same steps in the same order, but with added useless steps. No actual proofs have useless steps.

We're wandering to the realm of relevant logic here, which is not the sort of logic that underpins mathematics. Classical logic is, and under that, a proof with useless steps is still a perfectly good proof.
Valid, but silly. What I'm striving for is a definition that will have non-trivial consequences. The silly definition isn't interesting. Then we might as well just have defined proofs to be equal if they are exactly the same strings of symbols. I'd like to deduce from it that it can be shown that two proofs boil down to the same "idea" somehow.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Pythagorean Proofs

Postby antonfire » Mon Nov 12, 2007 11:40 pm UTC

Yes, I'd guessed. The problem is that that's very hard to quantify, and I'm quite sure that there's no algorithm that will tell you, given two proofs, whether or not they boil down to the same thing.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Pythagorean Proofs

Postby jestingrabbit » Tue Nov 13, 2007 5:30 pm UTC

I keep thinking about Euler's formula and proofs which start with different definitions for ez. It can be defined using a power series, as solving a particular IVP, as being lim (1 + z/n)n and probably several other things as well. In some proofs you make certain assumptions, in other proofs you make other assumptions (ie you might assume that |zw|=|z||w| or that certain IVPs have unique solutions with certain forms or that certain functions are conformal etc).

Some of these definitions are easy to translate between (the first two for instance) and the assumptions are the sorts of things that can be proven "within the approach" of a given proof. Differentiating wrt a complex variable should probably be defined as part of several of the more popular proofs. But these differences/problems aren't substantial imo and so it seems like a lot of differences can be reduced to showing that what we assume in one context can be proven in another.

So, perhaps if each initial assumption and step of a given proof (A) can be proven using the initial assumptions of some other proof (B) we should say that "B groks A". Groks is clearly transitive and reflexive, and not entirely well defined.

Just some thoughts.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 15 guests