[FOM] Is Godel's Theorem surprising?

[ignacio]

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