[FOM] Simple historical question

H. Enderton hbe at math.ucla.edu
Fri Jul 20 14:09:29 EDT 2007

Credit for showing the undecidability of true arithmetic surely goes
to Alonzo Church, "An unsolvable problem of elementary number theory,"
Amer. J. of Math., vol. 58 (1936), 345-363.  This is the same paper that
presents Church's Thesis for the first time, so it would have been hard
for anyone (Goedel, Post, Turing, ...) to have formulated the result
before then.

As for your pedagogical point, I quite agree.  Now that we have a robust
theory of computability, I think we can say that the heart of Goedel's
first incompleteness theorem lies in the fact that true arithmetic is
not computably enumerable.  Of course, in 1931 the computability concepts
were unavailable.

--Herb Enderton

On Thu, 19 Jul 2007, Michael Sheard wrote:

> ...
> To whom should we rightly give first credit for the result/observation 
> that Th(N,0,S,+,*,<) is undecidable?
> ...
> This question arose in a pedagogical context.  In a survey of 
> undecidability results, I find it much simpler and more effective to 
> mention the undecidability of Th(N,...) rather than of PA, or any other 
> axiomatized theory, especially for a general audience.
> Many thanks,
> Michael Sheard

More information about the FOM mailing list