FOM: really basic questions

[Martin Davis]

At 04:42 PM 9/18/98 +0100, fxn at cambrabcn.es wrote:
> Dear FOMers,
> 
> I've just taken a degree in Mathematics from the University of Barcelona
> and, in spite of the high level of the usual posts, I'd like to explain
> some basic doubts concerning f.o.m. that I think I must have pretty clear:
> 
> 
> 1) I don't understand why I'm supposed to be surprised because of the
> incompleteness of PA.
> 
..........................................................................
> 
> G\"odel's first theorem says that PA is incomplete, and what? This is the
> fact, is a theorem, what is the surprise?

In fact people did expect PA to be complete because it incorporated all the
usual proof methods used by number theorists. But the surprise is that the
result holds not only for PA, but for any reasonable extension of PA. In its
current best form, the theorem (sometimes called the G\"odel-Rosser theorem)
is that any recursive consistent extension of PA is incomplete. That means
that (via Church's thesis) if one is to insist that it be computationally
testable whether a supposed proof really is one, there is no hope of
obtaining completeness by proceeding to more powerful proof methods. So (if
it is consistent) even ZFC will not suffice to prove all true sentences of
arithmetic.

> But, Th(N) is complete as far as is the theory of a model, and therefore
> I cannot see in what sense Goldbach's Conjecture, for instance, could be
> an undecidable theorem of Number Theory. Of course, GC might be an
> undecidable sentence of PA... where is the link?
>

There is no proof procedure possible for Th(N). Number theorists want to
know whether GC is true in Th(N) (as you correctly say), but not having the
ability to just look at every even number to see whether it is true, they
are forced to seek a proof, and for that they must, in effect, work in a
system like PA or ZFC.

Martin Davis