[FOM] Is Godel's Theorem surprising?
ignacio
natochdag at elsitio.net.uy
Mon Dec 11 09:42:36 EST 2006
Charles silver wrote:
" First, thanks very much for all the interesting and enlightening
responses to my question. A couple of comments:
Diagonalization is not central to Godel's (first) theorem, as shown
by Kripke's proof of G's theorem that was published by Putnam, which
does not *require* diagonalization.
I believe this proof also shows--please correct me if I'm wrong--
that a specifically *mathematical* proposition (though an unusual
one) cannot be proved nor can its negation."
It is possible to prove Gödel's first theorem without using diagonalization,
that’s right: but any other technique you use to prove it is, from a formal
mathematical point of view, equivalent to diagonalization: see for instance
the method of concatenation developed by Quine and later on by Smullyan; the
heart of the question here seems to be that there is a "recursively
inseparable" center within any given formal system, no matter how simple or
trivial the system is: so if a system is complete it is inconsistent, and if
it is consistent it is incomplete, there is no way out, It seems.
See Smullyan: "Lanugages in which self reference is possible", JSL.
"Recursion theory for metamatematics" Oxford logic guides.
Regards,
I. Nattochdag
-----Mensaje original-----
De: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] En nombre de
Charles Silver
Enviado el: Domingo, 10 de Diciembre de 2006 11:20 a.m.
Para: Foundations of Mathematics
Asunto: Re: [FOM] Is Godel's Theorem surprising?
First, thanks very much for all the interesting and enlightening
responses to my question. A couple of comments:
Diagonalization is not central to Godel's (first) theorem, as shown
by Kripke's proof of G's theorem that was published by Putnam, which
does not *require* diagonalization.
I believe this proof also shows--please correct me if I'm wrong--
that a specifically *mathematical* proposition (though an unusual
one) cannot be proved nor can its negation.
Charlie
On Dec 8, 2006, at 4:58 AM, Harvey Friedman wrote:
> On 12/7/06 8:12 AM, "Charles Silver" <silver_1 at mindspring.com> wrote:
>
>> Why should it be so surprising that PA is incomplete, and even (in a
>> sense) incompletable?
>> Or put the other way, why should we have thought PA (or, for Godel,
>> the system of Principia Mathematica and related systems) would have
>> to be complete? It has been alleged, for example, that at the time
>> of Godel's proof John von Neumann had been working on proving
>> *completeness* for PM or some related system? Why would von Neumann
>> have thought *intuitively* that the system could be proved complete?
>> I'm not intending the above to be questions of mathematical fact.
>> I'm just wondering what accounts for the shock so to speak of Godel's
>> Theorem. One answer I've read is to the effect that everyone at
>> the time thought PM was complete. But for me, that's not
>> satisfactory. I'd like to know *why* they should have thought it was
>> complete. Did they have *intuitions* for thinking it had to be
>> complete?
>> I'm also wondering, though this is a separate point, whether today
>> the theorem is not only not surprising, but perhaps even intuitively
>> obvious. One unsatisfactory answer would be that incompleteness is
>> now not surprising because we now know it holds. But do we now have
>> distinctly different *intuitions*, aside from the proof itself
>> (though of course the proof can't entirely be discounted), that
>> establish, let's say the "obviousness" of the result?
>>
>
> I assume you are talking exclusively about Godel's First Theorem. Not
> Godel's Second Theorem.
>
> One reason it was regarded as surprising is that, up to that time,
> every
> single example of an arithmetic theorem was easily seen to be
> provable in
> PA. At that time, there was no idea that arbitrary arithmetic
> statements
> might differ fundamentally from the arithmetic statements that came
> up in
> the course of mathematics.
>
> Of course, it is still true that PA may be complete for all
> arithmetical
> sentences that obey certain intellectual criteria - criteria which are
> normally left informal. I have no doubt that a lot of people will
> be very
> surprised by examples of statements independent of PA that meet
> certain such
> informal criteria. Much more surprised if PA can be improved to ZFC.
>
> In fact, following a general line that I have discussed on the FOM
> fairly
> recently, one can simply ask if PA is complete for sentences that
> are not
> very long in primitive notation. This is of course a very difficult
> problem.
>
> ALSO: There are two senses of surprise for a theorem. One is that
> one is
> surprised by the fact that the theorem is true. The other is that
> one is
> surprised by the fact that anyone was able to prove that the
> theorem is
> true. There were probably many people who weren't too surprised
> that it is
> true, but who were shocked that anyone was able to prove such a thing.
>
> Harvey
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
--
No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.1.409 / Virus Database: 268.15.15/581 - Release Date: 09/12/2006
--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.409 / Virus Database: 268.15.15/581 - Release Date: 09/12/2006
--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.409 / Virus Database: 268.15.15/581 - Release Date: 09/12/2006
More information about the FOM
mailing list