(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 . Several corollaries follow: 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 -relations, which provides us with a new proof that there are r.e. sets that are not recursive. Then, we proved the enumeration theorem of Kleene.

### Like this:

Like Loading...

*Related*

This entry was posted on February 8, 2008 at 4:18 pm and is filed under 116b. 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