Due Tuesday March 4 at the beginning of lecture.

## 116b- Homework 7

February 25, 2008## 116b- Lecture 14

February 21, 2008We defined translations of a language in another and interpretations between theories. These notions allow us to state a more general version of the incompleteness results.

We then defined Turing machines.

## 116b- Lecture 13

February 19, 2008We proved the Kanamori-McAloon result on regressive functions as a corollary of Ramsey’s theorem, and proved, using the method of indicators, that it cannot be proven in .

## 116b- Lecture 12

February 15, 2008We sketched the method of *indicators* and the hierarchy of *fast-growing functions* as techniques to prove independence in . Then we proved Ramsey’s theorem. We will use the method of indicators to show the **Kanamori-McAloon theorem** that the version of Ramsey’s theorem for regressive functions is not provable in .

## 116b- Lecture 11

February 14, 2008We presented the *provability conditions* and showed how a theory with a provability predicate satisfies the second incompleteness theorem. We showed several remarks about the incompleteness results, including Rosser’s proof of the first incompleteness theorem, and Löb’s theorem on sentences asserting their own provability.

We closed with some examples of “mathematically meaningful” sentences independent of .