116b- Lecture 8

(Covered by Clinton Conley.)

We proved the Gödel-Rosser incompleteness theorem, as a consequence of the diagonal lemma. This is a stronger version of the first incompleteness theorem than originally proved by Gödel, who needed to assume more than just consistency of the underlying theory T. Several corollaries follow: \mathsf{Q} is essentially undecidable, there are r.e. sets that are not recursive, and truth is undefinable, a result due to Tarski.

We closed with some observations about r.e. sets, to which we will return at some later point. Namely, there are universal \Sigma_1-relations, which provides us with a new proof that there are r.e. sets that are not recursive. Then, we proved the \Sigma_1 enumeration theorem of Kleene.

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: