[FOM] Simple historical question
robertswolf at yahoo.com
Fri Jul 20 22:01:26 EDT 2007
I figured someone would provide an immediate answer to your question that would be more thorough than anything I could provide, but since no one has so far, I'll hop in.
For sure, this result follows easily from the work of Godel and/or Church, and I guess one could throw Tarski and Turing into this mix. But in terms of who first explicitly stated it, Church is usually given the credit. As you mentioned, it follows immediately from "Church's theorem" - more of a particular case than a corollary.
To be sure, Godel must have KNOWN this fact earlier, but the terminology to state it explicitly didn't exist yet at that point.
P.S. For "pedagogical smoothness," you might want to check out the exposition of this material in my "Tour through Mathematical Logic" (MAA Carus Monograph #30).
Michael Sheard <msheard at stlawu.edu> wrote: 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.
FOM mailing list
FOM at cs.nyu.edu
Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the FOM