## 116b- Homework 7

February 25, 2008

Homework 7

Due Tuesday March 4 at the beginning of lecture.

## 116b- Lecture 14

February 21, 2008

We 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- Homework 6

February 20, 2008

Homework 6

Due Tuesday February 26 at the beginning of lecture.

## 116b- Lecture 13

February 19, 2008

We 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 $\mathsf{PA}$.

## 116b- Lecture 12

February 15, 2008

We sketched the method of indicators and the hierarchy of fast-growing functions as techniques to prove independence in $\mathsf{PA}$. 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 $\mathsf{PA}$.

## 116b- Lecture 11

February 14, 2008

We 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 $\mathsf{PA}$.

## 116b- Homework 5

February 13, 2008

Homework 5

Due Tuesday February 19 at the beginning of lecture.

## 116b- Lecture 10

February 13, 2008

We showed that $\mathsf{ACA}_0$ proves the completeness theorem. We then proved the second incompleteness theorem using the result on completeness, the fact that if a model of $\mathsf{ACA}_0$ thinks that it contains a model of $\mathsf{ACA}_0$ then we can really see this latter model, and the diagonal lemma.

## Francisco Bem

February 8, 2008

Born December 27, 2007. In the picture here, he is about a month old.

## Cardinal preserving elementary embeddings

February 8, 2008

For a while now I have been thinking about structural restrictions that elementary embeddings must satisfy in set theory. Some of my findings were reported in Oaxaca during the XIII SLALM. An updated version of these results has been accepted for publication in the Proceedings of the Logic Coloquium 2007.  You can find it in my papers page.