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