[FOM] Is Godel's Theorem surprising?
joeshipman@aol.com
joeshipman at aol.com
Sun Dec 10 02:19:30 EST 2006
-----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.
More information about the FOM
mailing list