117b – Undecidability and incompleteness – Lecture 7

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

We showed that if is then its characteristic function is primitive recursive and that if 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.

Advertisement