[FOM] Recursion Theory and Goedel's theorems
hbe at math.ucla.edu
Thu Aug 2 15:15:42 EDT 2007
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.
More information about the FOM