Archive for the ‘Homework’ Category

116b- Homework 9

March 11, 2008

Homework 9

Due Tuesday March 18 at 1pm.

Advertisements

116b- Homework 8

March 5, 2008

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. 

116b- Homework 7

February 25, 2008

Homework 7

Due Tuesday March 4 at the beginning of lecture.

116b- Homework 6

February 20, 2008

Homework 6

Due Tuesday February 26 at the beginning of lecture.

116b- Homework 5

February 13, 2008

Homework 5

Due Tuesday February 19 at the beginning of lecture.

116b- Homework 4

February 4, 2008

Homework 4

Due Tuesday February 12 at the beginning of lecture.

116b- Homework 3

January 29, 2008

Homework 3

Due Tuesday February 5 at the beginning of lecture.

116b- Homework 2

January 22, 2008

Homework 2

Due Tuesday January 29 at the beginning of lecture.

 Update:  There is a typo in problem 2, it must be z<y.

116b- Homework 1

January 15, 2008

Homework 1

Due Tuesday January 22 at the beginning of lecture.

117b – Homework 8

March 1, 2007

Due Tuesday, March 13 at noon.

Homework 8