[FOM] Recursion Theory and Goedel's theorems

[David Auerbach]

I think the best way to express the relationship between the Gödel  
theorems and recursion theory while at the same time keeping the  
connection with formalized theories that give the results their  
philosophical oomph is via Post Canonical Systems as in Smullyan's  
original Theory of Formal Systems (or his Oxford update of my  
crumbling orange Princeton orginal).  And Jersoslow had some  
wonderful extensions of that work that are useful in proving the  
Second Theorem in ways that make the restrictions on Prov not ad hoc.  
(It's sort of one level of analysis finer than Feferman's.)



David Auerbach
Department of Philosophy & Religion
Box 8103
NCSU
Raleigh, NC  27695-8103


On Jul 20, at 2:09 PM, H. Enderton wrote:

> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom