[FOM] Simple historical question

[Bob Wolf]

      Michael,

      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.

                Bob Wolf

    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.

Many thanks,
Michael Sheard

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom


       
---------------------------------
Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/fom/attachments/20070720/704c3d55/attachment.html