[FOM] Is Godel's Theorem surprising?
Charles Silver
silver_1 at mindspring.com
Sun Dec 10 09:19:37 EST 2006
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
More information about the FOM
mailing list