## 116b- Homework 8

Homework 8

Due Tuesday March 11 at the beginning of lecture.

Important update: In problem 4.(a), recall that $U^1$ is a universal $\Sigma_1$ predicate for unary formulas, so if $x$ is the Gödel number of a $\Sigma_1$ formula $\psi(v)$ in one free variable $v$, then $U^1_x(y)$ holds iff $\psi(y)$ holds. Hence, asking that $U^1_x$ is finite is the same as asking that $\{n:{\mathbb N}\models \psi(n)\}$ is finite.  Actually, this is a serious typo:

$\{x:U^1_x\ \mbox{is finite}\}$ is $\Sigma_{\bf 2}$-complete. The set $\{x\colon U^1_x\ \mbox{is cofinite}\}$ is $\Sigma_3$-complete.

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