[FOM] Recursion Theory and Goedel's theorems

[H. Enderton]

Arnon Avron wrote (replying to my claim that the heart of the
first incompleteness theorem lies in recursion theory):

>I am not sure.  First, the fact that the undecidable sentence is Pi^0_1
>is very important - these are the sentences which are mechanically
>refutable in case they are false.  More important: Goedel's proof
>includes a procedure which given an r.e. true theory, provides a true
>sentence (which we know to be true if we know that the theory is true!)
>which is undecidable in that theory.  For me this is a positive part of
>the first incompleteness theorem which is no less important than the
>negative part.  Does recursion theory provide such a procedure too?

Yes, recursion theory does this -- once we know that recursive sets are
definable in arithmetic.  The unprovable true sentence given to us by
the productive function is a lot like the one Goedel's proof yields.
In fact, you and I may be looking a different parts of the same elephant.

--Herb Enderton