## 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.

## 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.