Due Tuesday February 5 at the beginning of lecture.

## 116b- Homework 3

January 29, 2008## 116- Lecture 7

January 29, 2008We showed that recursive functions and recursive sets are -representable in . We also defined *Gödel numberings* and exhibited an example of one. This allowed us to define when a theory is *recursive*. Finally, we proved Gödel’s **diagonal lemma**.

## 116b- Lecture 6

January 24, 2008We proved that a set is recursive iff it is -definable.

We showed some elementary properties of the theory , defined end-extensions, and verified that is -complete.

We also defined what it means for a function, or a set, to be *represented* in a theory.

## 116b- Homework 2

January 22, 2008Due Tuesday January 29 at the beginning of lecture.

**Update:** There is a typo in problem 2, it must be .

## 116b- Lecture 5

January 22, 2008We showed that a function is in iff it has a -graph. It follows that a set is r.e. iff it is -definable.

## 116b- Lecture 4

January 18, 2008We defined the notion of *r.e.* sets and proved Gödel’s lemma stating that there is a coding of finite sequences by numbers.