[FOM] Is Godel's Theorem surprising?

[joeshipman@aol.com]

-----Original Message-----
From: rda at lemma-one.com
>>...
>>   I'm also wondering, though this is a separate point, whether today
>> the theorem is not only not surprising, but perhaps even intuitively
>> obvious.

>But then there must be some intuitively obvious difference between a 
complete
>system like the first-order theory of the reals and an incomplete 
system like
>PA or ZF. What would that intuition be?



The intuition is simply that the first-order theory of the reals is 
"only about the reals', while it is easy to frame any question of 
mathematical interest in ZF, and easy to frame any "finitary' question 
using PA, so these theories are about mathematics in general.

That just explains why we can have an intuition about the truth of 
Godel's First Incompleteness Theorem; we can still be surprised that it 
is provable.

Of course, nowadays we all have an intuition about the possibility of 
coding in PA which was not intuitive in Godel's day, but if Godel had 
originally stated his theorems about the theory of integers with 
addition, multiplication, and exponentiation, when it is MUCH easier to 
code things, I think people would still have been almost as impressed. 
Presburger had just shown that the theory of addition was decidable, so 
the result that exponentiation is not necessary, while very 
interesting, is of technical not philosophical interest as showing 
where the demarcation is between complete and incomplete theories.

The real surprise of Godel's work, in my view, comes from the gulf it 
reveals between first-order and second-order logic -- the theory of the 
integers is obviously decided implicitly in second-order logic because 
the structure is categorical, but there is no way of capturing it in 
our proof systems, because all our formal systems for deriving 
validities of second-order logic can be mirrored in first-order logic. 
The full set of second-order validities is inaccessible to us (though 
not until the work of Turing was it clear exactly what this meant, 
before then one could imagine that Godel's class of formal systems 
could be "effectively" transcended just as Hilbert's primitive 
recursive systems had been).

(Godel's earlier Completeness Theorem increases the surprise factor 
quite a bit, because it shows that the principles of first-order 
reasoning are completely understood, which tends to increase one's 
confidence in the possibility of identifying all the principles of 
second-order reasoning.)

-- JS
________________________________________________________________________
Check out the new AOL.  Most comprehensive set of free safety and 
security tools, free access to millions of high-quality videos from 
across the web, free AOL Mail and more.