[FOM] Is Godel's Theorem surprising?
Harvey Friedman
friedman at math.ohio-state.edu
Fri Dec 8 05:58:14 EST 2006
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
More information about the FOM
mailing list