[FOM] Simple historical question
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.
More information about the FOM