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- Lecture 5

January 22, 2008

We showed that a function is in \mathsf{R} iff it has a \Sigma_1-graph. It follows that a set is r.e. iff it is \Sigma_1-definable.