Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When are two proofs essentially the same? (2007)

gowers.wordpress.com

Post reply on HN
Print view View original

51–60 of 111 posts

Re: When are two proofs essentially the same? (2007)

#51

Post by ColinWright »

pkoird wrote: post #30
ColinWright wrote: post #5

Earlier quoted context omitted.

This is like saying that if I walk out of my house, turn right, and walk 10 minutes to the local food store, it's the same as coming out of the house, turning left, and walking 15 minutes around the block. The destination is the same, so surely these are "the same". I'd argue that this is not the case.

Not quite. If we consider that we are trying to prove "you can reach the local food store from your house" then starting from either side would consist of two proofs by example. And for sure these are different paths one is taking and should be different! But if you consider deeply, both of these proofs are implicitly encoding same information about the space between your house and the local store: 1) there is contin…

You are being too literal -- I was providing an analogy, not an example.

Also:

> ... all theorems about a certain statement being true must be reducible to a single irreducible logical chain of argument.

Citation needed ... I have no reason to believe this is true.

But here's an example of two proofs.

Proving sqrt(2) is irrational.

Proof 1: Every rational number has a finite Continued Fraction representation. But the normalised Continued Fraction representation of sqrt(2) is [1;2,2,2,...], which is infinite. Since this is infinite, sqrt(2) is irrational.

Proof 2: Consider integers a and b, and suppose 2(b²)=a². Consider the prime decompositions of a and b, and count how many times "2" turns up on each side. It's odd on the left, it's even on the right, so this cannot happen. Therefore we can never have integers a and b with 2(b²)=a². Therefore we can't have 2=(a²)/(b²)=(a/b)². So any fraction when squared cannot equal 2, so sqrt(2) is irrational.

Do these really feel "the same" to you?

Re: When are two proofs essentially the same? (2007)

#52

Post by lisper »

VikingCoder wrote: post #41

I was working with a friend writing a paper about the Ship of Theseus, but my friend kept replacing all of my arguments.

I had a similar experience, but my collaborator had a touch of OCD and just kept micro-editing my original draft, each time replacing exactly one word with a different word that had nearly the same meaning. By the end of the process, my collaborator had produced a word-for-word copy of William Shakespeare's "Julius Caesar". It is a remarkable coincidence that my original draft just happened to have the same number of words to begin with to make this transformation possible.

My collaborator then translated the original paper into Greek. Or maybe he translated "Julius Caesar" into Greek. I don't speak Greek so I have no way of knowing.

;-)

Re: When are two proofs essentially the same? (2007)

#53

Post by Twisol »

pkoird wrote: post #42
Twisol wrote: post #38

Earlier quoted context omitted.

Thanks for taking a stab at it! I think I understand the angle you're attempting to take. May I offer a relatively contrived counterexample to poke at this a little more deeply? Suppose I have a proposition that says, roughly, "if A and B and C then contradiction". Furthermore, suppose that A and B together are already contradictory, and B and C together are also already contradictory. Now I can construct two proofs,…

That is a really good question. I suppose you could reduce it further by saying that you want the proof of "A or B". Assuming both true, it suffices to either get a proof for A or for B (of course, this may not be true in general). Regardless, this is a really good counter-example that will force me to think some more about it. Thanks!

> I suppose you could reduce it further by saying that you want the proof of "A or B". Assuming both true, it suffices to either get a proof for A or for B

Yes, absolutely :) I thought about this framing too, but figured the one I gave above might be more immediately convincing.

Re: When are two proofs essentially the same? (2007)

#54

Post by seanhunter »

pkoird wrote: post #2

If I were allowed a small philosophical leeway, I'd argue that two correct proofs are always the same. For sure they may contain different words or make use of different "abstractions", but it just seems to me that these abstractions should be equivalent if one were willing to unravel it all to a certain degree. Essentially, all proof is, is a statement that says "this is true" and no matter which language you use to…

I don't think this is true because a proof does more than state a conclusion. It establishes a true path from some premises to that conclusion. Sometimes that path continues.

For example if you had a general constructive proof that there were infinitely many prime numbers it should be a simple matter to alter it a bit and prove the twin prime conjecture wouldn't it?

In general a constructive proof and a non-constructive proof of some fact (say proof by contradiction) are fundamentally different in terms of where you can go with the proof.

Re: When are two proofs essentially the same? (2007)

#55

Post by seanhunter »

pkoird wrote: post #30
ColinWright wrote: post #5

Earlier quoted context omitted.

This is like saying that if I walk out of my house, turn right, and walk 10 minutes to the local food store, it's the same as coming out of the house, turning left, and walking 15 minutes around the block. The destination is the same, so surely these are "the same". I'd argue that this is not the case.

Not quite. If we consider that we are trying to prove "you can reach the local food store from your house" then starting from either side would consist of two proofs by example. And for sure these are different paths one is taking and should be different! But if you consider deeply, both of these proofs are implicitly encoding same information about the space between your house and the local store: 1) there is contin…

> all theorems about a certain statement being true must be reducible to a single irreducible logical chain of argument.

Why is this necessarily true? We know that true statements in topology (for example) don't all reduce down to being equivalent (eg if I have a loop that goes through the ring of a donut/toroid it doesn't reduce the same as if I have a loop on the surface of the donut/toroid so establishing facts about one wouldn't tell me facts about the other). So how do we know that statements in logic reduce? Could the space of logical statements not have topological characteristics like that?

Re: When are two proofs essentially the same? (2007)

#56

Post by naniwaduni »

Jtsummers wrote: post #50
setopt wrote: post #47

Earlier quoted context omitted.

On the other hand, compiler tricks like tail call optimization can e.g. reduce an O(n) algorithm to an O(1) algorithm. Is it a “different program” if the same source code is compiled with a new compiler?

Tail call optimization does not turn O(n) algorithms into O(1) algorithms unless you're talking about the space used and not the runtime.

At a certain level of abstraction, that's easily an example of converting an O(n log n) algorithm into an O(n) one.

In practice, of course, the effect is far more dramatic with a MMU.

Re: When are two proofs essentially the same? (2007)

#57

Post by naniwaduni »

pkoird wrote: post #2

If I were allowed a small philosophical leeway, I'd argue that two correct proofs are always the same. For sure they may contain different words or make use of different "abstractions", but it just seems to me that these abstractions should be equivalent if one were willing to unravel it all to a certain degree. Essentially, all proof is, is a statement that says "this is true" and no matter which language you use to…

> I'd argue that two correct proofs are always the same

All correct inferences proceeding from the same axioms are the same.

Re: When are two proofs essentially the same? (2007)

#58

Post by Jtsummers »

naniwaduni wrote: post #56
Jtsummers wrote: post #50

Earlier quoted context omitted.

Tail call optimization does not turn O(n) algorithms into O(1) algorithms unless you're talking about the space used and not the runtime.

At a certain level of abstraction, that's easily an example of converting an O(n log n) algorithm into an O(n) one. In practice, of course, the effect is far more dramatic with a MMU.

Can you show a O(n log n) algorithm with tail calls but not TCO that's O(n) after being optimized with TCO?

Re: When are two proofs essentially the same? (2007)

#60

Post by naniwaduni »

Jtsummers wrote: post #58
naniwaduni wrote: post #56

Earlier quoted context omitted.

At a certain level of abstraction, that's easily an example of converting an O(n log n) algorithm into an O(n) one. In practice, of course, the effect is far more dramatic with a MMU.

Can you show a O(n log n) algorithm with tail calls but not TCO that's O(n) after being optimized with TCO?

Computing f(0)=0; f(n)=f(n-1) is O(n log n) without tail calls because you need O(log n) addresses to hold your stack frames.
Post reply on HN