Homework 8

Due Tuesday March 11 **at the beginning of lecture**.

**Important update:** In problem 4.(a), recall that is a universal predicate for unary formulas, so if is the Gödel number of a formula in one free variable , then holds iff holds. Hence, asking that is finite is the same as asking that is finite. Actually, this is a serious typo:

is -complete. The set is -complete.

Sorry about this. Either ignore 4.(a), or try to show (for extra credit) that the set is -complete, or (for a much more challenging problem) that the corresponding set with “cofinite” is -complete.

### Like this:

Like Loading...

*Related*

This entry was posted on March 5, 2008 at 8:48 am and is filed under 116b, Homework. 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