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

Peter Michael Gerdes gerdes at Math.Berkeley.EDU
Thu Aug 2 19:43:40 EDT 2007

```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

```