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.