We 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 show 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 *0*¢ with no c.e. branches.

We show that if j is S^{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 use this to prove *Craig’s trick* showing that a theory admits a c.e. axiomatization iff it admits a primitive recursive axiomatization.

We define *(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.

### Like this:

Like Loading...

*Related*

This entry was posted on February 13, 2007 at 2:51 pm and is filed under 117b, Undecidability and incompleteness. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply