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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: