From: jbrock@panix.com (John Brock) Newsgroups: sci.math Subject: A question about truth values in Godel's theorem (Was: Need help with help with Penrose' "Shadows of the Mind") Date: 4 Jan 1998 02:31:00 -0500 In article , Henry Baker wrote: >Where Penrose goes completely wrong is in bringing logic and Goedel into >his arguments. The Goedel theorem is really quite _unremarkable_, once >you really understand it. It simply says that if you try to list all the >(true) theorems by producing all proofs, there will be some statements that >won't show up in either the positive or the negative form. This is no >different than showing that there are numbers that don't show up if you try >to list all numbers by showing their decimal expansions. That's it! All >of this 'mystery' is due to popular science writers, who don't understand >Goedel either, trying to make something 'magic' about this. This is a very interesting way of looking at Goedel's theorem, and it does indeed make the result more comprehensible to me. I have a question though. Does Goedel's theorem state that any sufficiently elaborate axiomatic system has statements which are in fact true (or false) but cannot be proven true or false, or does it simply say that there are syntactically valid statements which cannot be proven true or false, without commenting on whether such statements have a truth value. The second interpretation seems most compatible with your description of Goedel's theorem, since then the truth value of a statement can simply be *defined* by the way it shows up in the list of all possible proofs. The first interpretation -- which is the way I had thought it went -- is more "mysterious", since it's not clear to me what it means for a statement with no proof to be either true of false. As an example, it was asserted in one of the recent books on Fermat's Last Theorem that until the theorem was actually proven people worried that it might be undecidable, like the Continuum Hypothesis, in which case it would have to be *true*, since if it were false there would have to be a counterexample, which would make the it decidable. This would imply that the first interpretation above is the correct one, which means that the mystery is still there (at least for me). -- John Brock jbrock@panix.com ============================================================================== From: feldmann@bsi.fr Subject: Re: A question about truth values in Godel's theorem (Was: Need help with help with Penrose' "Shadows of the Mind") Date: Sun, 04 Jan 1998 06:51:10 -0600 Newsgroups: sci.math In article <68ndrk$ek0@panix.com>, jbrock@panix.com (John Brock) wrote: > > In article , > Henry Baker wrote: > > >Where Penrose goes completely wrong is in bringing logic and Goedel into > >his arguments. The Goedel theorem is really quite _unremarkable_, once > >you really understand it. It simply says that if you try to list all the > >(true) theorems by producing all proofs, there will be some statements that > >won't show up in either the positive or the negative form. This is no > >different than showing that there are numbers that don't show up if you try > >to list all numbers by showing their decimal expansions. Well, there is a strong analogy (same syntactic argument), but the semantic meaning is quite different, as proofs are finite (this is in fact the difference between recursive and recursively enumerable) Of course, this doesnt change much to the value of your argument >> That's it! All > >of this 'mystery' is due to popular science writers, who don't understand > >Goedel either, trying to make something 'magic' about this. > I agree : its almost as if human mind was supposed to be "magically" able to see truth without proof in those cases... > This is a very interesting way of looking at Goedel's theorem, and it > does indeed make the result more comprehensible to me. I have a > question though. Does Goedel's theorem state that any sufficiently > elaborate axiomatic system has statements which are in fact true (or > false) but cannot be proven true or false, or does it simply say that > there are syntactically valid statements which cannot be proven true or > false, without commenting on whether such statements have a truth > value. The second interpretation seems most compatible with your > description of Goedel's theorem, since then the truth value of a > statement can simply be *defined* by the way it shows up in the list of > all possible proofs. The first interpretation -- which is the way I > had thought it went -- is more "mysterious", since it's not clear to me > what it means for a statement with no proof to be either true of > false. > Well, again, a statement can be "true" from the outside (arithmetic (the system PA following from Peano axioms) is consistent by hypothesis in Godel theorem, so Consis (PA) has to be true, and yet this statement is precisely the one with no proof in the demonstration (the "second" Godel theorem)). Mostly, in the above analogy, this is similar to say that the real obtained by Cantor diagonalisation is a "true" real, but not in the list > As an example, it was asserted in one of the recent books on Fermat's > Last Theorem that until the theorem was actually proven people worried > that it might be undecidable, like the Continuum Hypothesis, in which > case it would have to be *true*, since if it were false there would > have to be a counterexample, which would make the it decidable. This is another classical misinterpretation: let's suppose it is undecidable. We can then add a counterexample ((x,y,z,n) such that...) without getting any contradiction (by hypothesis). Of course, one of the x,y,z,n (at least) will have to be "non-standard", ie not expressible in finite terms (or we would have a proof of falsehood), so if you don't believe in non-standard integers, you have to say that (in this case) undecidable implies true. But the existence (or absence of) those integers is only a matter of faith from the inside of PA (or ZF); from the outside, it's a perfectly ordinary consequence of the Lowenheim-Skolem theorem... > This > would imply that the first interpretation above is the correct one, > which means that the mystery is still there (at least for me). > -- Hope I have contributed to deepen it :-) -------------------==== Posted via Deja News ====----------------------- http://www.dejanews.com/ Search, Read, Post to Usenet