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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: