[FOM] Simple historical question

H. Enderton hbe at math.ucla.edu
Tue Jul 24 13:42:20 EDT 2007


I wrote (July 20):
| Now that we have a robust theory of computability, I think we can
| say that the heart of Goedel's first incompleteness theorem lies
| in the fact that true arithmetic is not computably enumerable.

To which Bill Tait replied (July 23):
>The result you state follows from the definability of c.e. relations  
>in arithmetic and Tarski's theorem on non-definability of arithmetic  
>truth in arithmetic and  ignores the Pi^0_1 nature of the undecidable  
>sentence.

Better yet, we don't even need Tarski's theorem.  Once we know that
a complete c.e. set and its complement are definable in arithmetic,
we know that the set of true sentences is productive (in Dekker's
sense).  So we are handed an undecidable sentence.

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.

--Herb Enderton



More information about the FOM mailing list