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

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

## 116b- Lecture 3

January 15, 2008

We defined Ackermann’s function and showed it is not primitive recursive. We showed that $\Delta_0$-formulas have a primitive recursive characteristic function, and defined the class $\mathsf{R}$ of recursive functions.

## 116b- Lecture 2

January 15, 2008

We defined the class $\mathsf{PR}$ of Primitive Recursive functions and showed several examples of functions that belong to this class.

## 116b- Lecture 1

January 15, 2008

We introduced the course, stated the incompleteness theorems, defined $\mathsf{Q}$ (Robinson Arithmetic), $\mathsf{PA}$ (Peano or first-order Arithmetic), and $\mathsf{ACA}_0$ (the subsystem of second-order Arithmetic given by the arithmetic comprehension axiom).