[FOM] Simple historical question

Michael Sheard msheard at stlawu.edu
Thu Jul 19 15:44:45 EDT 2007

A question which I suspect some of the historically knowledgeable 
members of the list may be able to answer easily:

To whom should we rightly give first credit for the result/observation 
that Th(N,0,S,+,*,<) is undecidable?

Of the logic textbooks on my shelf, about half derive it as an easy 
corollary of Godel's Incompleteness theorem; about half derive it as an 
even easier corollary of Church's Undecidability theorem.  Remarkably, 
one textbook apparently never states the result explicitly at all, but 
then later uses it to derive the corresponding result about Th(Z,...).   
None of the books supply a historical reference.  The best on-line 
resource I could fine simply described the result as "following from the 
work of Godel and Church."

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