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