117b – Undecidability and incompleteness – Lecture 7

February 13, 2007

Define essentially undecidable theories as those theories (of arithmetic) that are recursively axiomatizable but such that any recursive extension T is undecidable and therefore incomplete. We showed that if S is essentially undecidable then there are continuum many complete extensions of S, none of which are c.e. The argument gives an example of a complete binary tree recursive in {\bf 0}' with no c.e. branches.

We showed that if \varphi is \Sigma^0_0 then its characteristic function is primitive recursive and that if R is a c.e. relation, then it is the range of a primitive recursive function. We used this to prove Craig’s trick showing that a theory admits a c.e. axiomatization iff it admits a primitive recursive axiomatization.

We defined (numeralwise) representability and binumerability of a relation by a formula in a given theory. Next lecture we will show that there is an essentially undecidable finitely axiomatizable theory that represents all c.e. relations and binumerates all recursive relations. This will be the key to the proof of the incompleteness theorems.