[FOM] Fwd: Recursion Theory and Goedel's theorems

[Peter Michael Gerdes]

On Aug 1, 2007, at 2:17 AM, Arnon Avron wrote:

> On Tue, Jul 24, 2007 at 10:42:20AM -0700, H. Enderton wrote:
>
>> Maybe it's not clear that this undecidable sentence is Pi^0_1.
>> But  I still advance the claim that the heart of the
>> first incompleteness  theorem lies in recursion theory.
>>

[snip]

>  Does recursion theory provide such a procedure too?

While it's an interesting question whether the first incompleteness  
theorem is most naturally presented in the context of classical  
recursion theory (using the methods mentioned on this list) even if  
not I think the original claim still stands because Godel's proof of  
the first incompleteness theorem is a recursion theoretic proof.

Ultimately the proof of the first incompleteness theorem is just a  
certain special kind of construction.  One can view the proof as  
building a machine with a special sort of property (provably halts  
iff it doesn't halt) from an index of a machine that enumerates  
provable statements in the theory.

The heart of the proof is really just the following recursion  
theoretic argument:  Given a machine M_i enumerating provable  
statements of an r.e. extension of PA define f(e) to be a recursive  
function so that M_f(e) halts iff M_i enumerates the statement saying  
M_e doesn't halt.  Now use the fixed point lemma to find e such that  
M_e = M_f(e) and now we have a machine M_e which halts iff our  
extension of PA proves it doesn't halt.  The sentence asserting that  
M_e does not halt is then the Godel sentence for the given r.e. system.

Godel may not have worded it this way but I think the methods used  
place the theorem clearly inside the domain of recursion theory.

Peter Gerdes