Re: [math-fun] Re: proofs
Apropos proof-checking by any means: In Fall, 2002, the Russian mathematician Grigori Perelman posted to the math ArXiv website some papers claiming to prove W. Thurston's geometrization conjecture (TGC) <http://en.wikipedia.org/wiki/Geometrization_conjecture>. If true, TGC would greatly advance the field of 3-manifolds, and would also imply the famous so-called Poincare conjecture (PC) as well (one of the seven Clay $10^6 prize problems). Since then Perelman has given detailed lecture series at a number of U.S. math departments, and undoubtedly many others around the world. Ever so slowly, the experts in this field seem to be concluding cautiously that at least the part of Perelman's work that purports to prove the PC is *probably true. They're less sure about the entire TGC. (I believe there is at least one piece of the TGC proof that Perelman has promised to post on the ArXiv, but has not yet done so.) In March, 2004, Scientific American published an article that stated that PC had been proved by Perelman. Everyone I asked who attended any of his lectures expressed cautious optimism for PC, but none would affirm that it had been proven. That October, John Morgan of Columbia published an article written in August, 2004 that discussed Perelman's work, but he dd not affirm that the proof was correct. Though the optimism is slowly increasing for PC, it still seems no one among the experts is ready to publicly affirm that PC has been proven. For me this is a bit like watching a drama of high suspense unfold in slow motion. Assuming the absence of reliable automated theorem-checkers for this kind of proof, how do we decide when Perelman's work is correct? (Incidentally, he has apparently never submitted it to a peer-reviewed journal, but some sources say it's already gotten much more careful scrutiny than most such submissions would.) --Dan _________________________________ * Poincare didn't actually phrase this as a conjecture; he asked whether or not it was true.
Re the threads on proofs, and sudoku uniqueness, I thought of a question relating the two threads. Before I ask my question, I'll quote the example from Huang's post : ----------------------- There are two concentric circles, A and B. There is a line segment which is a chord of A and tangent to B. This line has length 10. What is the area of the annulus between the two circles? There is a mathematical solution: Let the radius of A be a and the radius of B be b. Now, call one endpoint of the line segment X, and the tangent point of the line segment to B we will call Y. Call the centers of the two circles Z. Now, since X is on circle A, we know XZ = a. Since Y is on circle B, we know YZ = b. Since YZ is a radius of B and Y is a tangent point of segment XY, we know that angle XYZ is a right angle. Finally, since we know that the extended line going through YZ is a diameter of A and that if a diameter of a circle intersects a chord at right angles then it bisect the chord, XY must be half the length of the chord, to wit, 5. By the Pythagorean theorem on right triangle XYZ, we know that 25 + b^2 = a^2, or 25 = a^2 - b^2. Now, the area of the annulus is the area of A minus the area of B. To wit, the area is pi a^2 - pi b^2, which is equal to pi (a^2 - b^2) = 25 pi. Therefore the area is 25 pi. There is also a "meta"-solution: Since this puzzle must have a reasonable solution, the size of the circles are probably irrelevant. Then consider the case where circle B has radius 0. In that case, B becomes a point (the center), the chord becomes a diameter of A, and the annulus becomes the area of A. The question is then: Given that the diameter of a circle has length 10, what is its area? This is easily found to be 25 pi. ---------------------------------- The first proof is a valid proof. If we ran it through a proof-checker, we would get a positive answer "yes this is valid". My question is, is this second proof a valid proof? If we had a proof checking program, and we fed it this proof and asked if it is correct, would it say "yes" or "no" ? If the answer is no, then why do we accept such solutions in exams/puzzle competitions? If a student submitted something like this in a puzzle competition (e.g. Putnam or olympiad) or even on a homework, we would all jump up and down with delight at the ingenuity. Well I would. I would be glad to have a student who thinks outside the box. Should I turn around and tell such a student that the argument is not valid? Gary McGuire
I suppose it has been a few years since there was a math-fun discussion which turned on the difference between a proof based on ZF and a proof based on ZF+Consis(ZF) -- that is, a proof in which you need to assume the extra axiom that ZF is consistent. The answer to Gary's "is this a valid proof" question, and the sudoku question to which he's drawing the analogy, both boil down to asking what your set of axioms is. In calculating the area of the annulus, Gary's second proof is valid only if you assume that the answer is independent of the radii -- which is, perhaps, an application of the pseudo-axiom "there is something clever which makes this problem worth asking", a frequent domain in which to solve olympiad-style problems. If you came across a similar but "naturally-occurring" problem -- one where it hadn't already been subjected to a selection process to eliminate boring questions -- then you would likely use different techniques to solve it. Similarly, as Gary said, most sudoku enthusiasts seem to agree that the axioms you're working under are "Each row/column/box contains one of each number, and the solution is unique." If you handed such solvers a puzzle with multiple solutions, they might well "solve" it using their axiom set -- which, note, makes false assumptions -- and conclude that they had found "the unique" solution, while in fact they had only found one of several. (If you were lucky, maybe you could even get them to conclude that the puzzle has no solution at all, when in fact it has more than one.) Note that this question of axioms is related to, but not the same as, the question of legal deductive techniques -- that's a question of what steps may appear in a proof, not of what axioms you assume. In a sense, a sudoku's "difficulty rating" is an assertion that a certain set of techniques suffice to solve this puzzle. You could imagine expanding your bag of tricks by adding the difficulty of the puzzle as yet another axiom: "This puzzle is rated as `devious', but if this box here held a 3, then I'd be able to solve the whole thing using only `beginner'-level logic. Therefore this box must hold an 8!" I doubt that many sudokists would condone that line of reasoning. --Michael Kleber On 3/7/06, Gary McGuire <Gary.McGuire@nuim.ie> wrote:
Re the threads on proofs, and sudoku uniqueness, I thought of a question relating the two threads.
Before I ask my question, I'll quote the example from Huang's post :
-----------------------
There are two concentric circles, A and B. There is a line segment which is a chord of A and tangent to B. This line has length 10. What is the area of the annulus between the two circles?
There is a mathematical solution:
Let the radius of A be a and the radius of B be b. Now, call one endpoint of the line segment X, and the tangent point of the line segment to B we will call Y. Call the centers of the two circles Z. Now, since X is on circle A, we know XZ = a. Since Y is on circle B, we know YZ = b. Since YZ is a radius of B and Y is a tangent point of segment XY, we know that angle XYZ is a right angle.
Finally, since we know that the extended line going through YZ is a diameter of A and that if a diameter of a circle intersects a chord at right angles then it bisect the chord, XY must be half the length of the chord, to wit, 5. By the Pythagorean theorem on right triangle XYZ, we know that 25 + b^2 = a^2, or 25 = a^2 - b^2.
Now, the area of the annulus is the area of A minus the area of B. To wit, the area is pi a^2 - pi b^2, which is equal to pi (a^2 - b^2) = 25 pi. Therefore the area is 25 pi.
There is also a "meta"-solution:
Since this puzzle must have a reasonable solution, the size of the circles are probably irrelevant. Then consider the case where circle B has radius 0. In that case, B becomes a point (the center), the chord becomes a diameter of A, and the annulus becomes the area of A. The question is then: Given that the diameter of a circle has length 10, what is its area? This is easily found to be 25 pi.
----------------------------------
The first proof is a valid proof. If we ran it through a proof-checker, we would get a positive answer "yes this is valid".
My question is, is this second proof a valid proof? If we had a proof checking program, and we fed it this proof and asked if it is correct, would it say "yes" or "no" ?
If the answer is no, then why do we accept such solutions in exams/puzzle competitions? If a student submitted something like this in a puzzle competition (e.g. Putnam or olympiad) or even on a homework, we would all jump up and down with delight at the ingenuity. Well I would. I would be glad to have a student who thinks outside the box. Should I turn around and tell such a student that the argument is not valid?
Gary McGuire _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Michael Kleber wrote:
The answer to Gary's "is this a valid proof" question, and the sudoku question to which he's drawing the analogy, both boil down to asking what your set of axioms is. In calculating the area of the annulus, Gary's second proof is valid only if you assume that the answer is independent of the radii -- which is, perhaps, an application of the pseudo-axiom "there is something clever which makes this problem worth asking", a frequent domain in which to solve olympiad-style problems.
This clears it up. I assume that a proof checking program will only use ZF, so would declare the second proof invalid. Dan wrote:
Are you sure that such solutions *are* given full credit in Putnam exams and Olympiads? I don't know if that's the case.
No, I'm not sure. I thought there would be some readers of this group who know. I know this particular problem is easy to solve the other way, but I've seen tricky problems which are made much easier by reasoning "here I am sitting in a Putnam/whatever, therefore this problem has a nice solution, therefore....." Dan wrote:
Suppose a sudoku has *exactly* 2 solutions. Then what is the maximum number of boxes that can differ in the two solutions?
502008471040710203107000000300104607070000105010057300601002730720030014493871500 532968471849715263167243859385124697276389145914657382651492738728536914493871526 562398471948716253137425986359184627874263195216957348681542739725639814493871562 42 clues, 39 positions different in the two solutions. I'm sure one can do better. Gary McGuire
In order for the second solution to be a valid proof, we need to prove a lemma that the size of the circles doesn't matter. If there's a simple, "proof without words" way of seeing this, then this would be an outstanding solution for a competition or homework. As an aside, I've been musing for many years about the possibility of "automatically" generating "proof without words" types of proofs of certain math theorems. This isn't going to be easy, as Newton himself spent 20 years converting his calculus-style proofs in the Principia into geometric proofs because he knew that no one would be able to understand or verify his calculus style proofs. (Now, of course, most students would find his geometric style proofs _harder_ to follow than the calculus-style proofs!) The basic idea is to reverse the logic of Tarski's decision procedure for geometry, which converts geometry into analytic geometry. Since the mapping is obviously not 1-1, you need a clever way to map questions about polynomials back into questions about lines, planes, circles, etc. At 05:06 AM 3/7/2006, Gary McGuire wrote:
There are two concentric circles, A and B. There is a line segment which is a chord of A and tangent to B. This line has length 10. What is the area of the annulus between the two circles?
There is also a "meta"-solution:
Since this puzzle must have a reasonable solution, the size of the circles are probably irrelevant. Then consider the case where circle B has radius 0. In that case, B becomes a point (the center), the chord becomes a diameter of A, and the annulus becomes the area of A. The question is then: Given that the diameter of a circle has length 10, what is its area? This is easily found to be 25 pi. ---------------------------------- If a student submitted something like this in a puzzle competition (e.g. Putnam or olympiad) or even on a homework, we would all jump up and down with delight at the ingenuity. Well I would. I would be glad to have a student who thinks outside the box. Should I turn around and tell such a student that the argument is not valid? Gary McGuire
On 3/7/06, Henry Baker <hbaker1@pipeline.com> wrote:
The basic idea is to reverse the logic of Tarski's decision procedure for geometry, which converts geometry into analytic geometry. Since the mapping is obviously not 1-1, you need a clever way to map questions about polynomials back into questions about lines, planes, circles, etc.
I skimmed over Gary's proof (literally for 2 seconds) and was unable to follow it; then pictured the problem mentally, saw the solution immediately, skimmed the proof again and realised it was saying the same thing as I had pictured. Pondering this chain of events, I wondered how does one teach people to think geometrically like this in the first place? [And when that's out of the way, is there a decent way to get 2-D or 3-D geometrical diagrams into TeX yet?] Fred Lunnon
dasimov@earthlink.net wrote:
Assuming the absence of reliable automated theorem-checkers for this kind of proof, how do we decide when Perelman's work is correct? (Incidentally, he has apparently never submitted it to a peer-reviewed journal, but some sources say it's already gotten much more careful scrutiny than most such submissions would.)
I'm sure it has. This reminds me of a discussion of proofs in the book "What is mathematics, really" by Reuben Hersch. If I remember correctly, he talks about how over time, important proofs come to be accepted as correct, as people in the field examine them. It's a social thing. Did people accept the proof of the 4-colour conjecture when it came out in 1976? Do people believe it more now than in 1976? Probably yes, because it has been gone over and redone by people in the field. Hales' proof of the Kepler conjecture was published while at the same time it has not been 100% fully checked, according to this: http://www.newscientist.com/channel/fundamentals/dn8743.html In the end, it's down to the experts in the field to decide. For a long proof, it takes time. It took a while for Wiles' proof to be examined and accepted. For Perelman's proof, eventually the people in that field will come to a consensus, and the rest of us just believe them. It's interesting right now, we are in the middle of the procedure. Not everyone is convinced: http://www.theaustralian.news.com.au/common/story_page/0,5744,18204052%255E3... Gary McGuire
participants (5)
-
dasimov＠earthlink.net -
Fred lunnon -
Gary McGuire -
Henry Baker -
Michael Kleber