116b- Homework 3

January 29, 2008

Homework 3

Due Tuesday February 5 at the beginning of lecture.


116- Lecture 7

January 29, 2008

We showed that recursive functions and recursive sets are \Sigma_1-representable in \mathsf{Q}. 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, 2008

We proved that a set is recursive iff it is \Delta_1-definable.

We showed some elementary properties of the theory \mathsf{Q}, defined end-extensions, and verified that \mathsf{Q} is \Sigma_1-complete.

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


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.


116b- Lecture 4

January 18, 2008

We defined the notion of r.e. sets and proved Gödel’s lemma stating that there is a \Delta_0 coding of finite sequences by numbers. 


116b- Homework 1

January 15, 2008

Homework 1

Due Tuesday January 22 at the beginning of lecture.