[FOM] Recursion Theory and Goedel's theorems

[Bill Taylor]

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

Quite right.

Delta^0_1 are both provable (if true) and refutable (if false),
by routine methods.  So, fully "testable" statements, or "facts".

Pi^0_1 are merely refutable (if false) - I like to call them "scientific".

Sigma^0_1 are merely provable (if true) - I like to call them "religious".

Those higher up, with mixed quantifiers, are neither provable nor refutable
(by routine methods).  They could be called "philosophical" or "meaningless".

These four-fold categories are a great example of a "bi-dichotomy",
a concept that I am particularly fond of.

The Pi^0_1 nature of Godel statements is particularly significant,
as it can be for any other such statement.  Because if they are found to be
undecidable (in some basic theory, such as Q), then they are AUTOMATICALLY
true in the natural numbers.  This is enormously significant.

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

Well, yes, isn't it?  It is within recursion theory that "creative sets"
are fully defined and examined; these are precisely the sets of the type
you describe.

-- Bill Taylor