Prove the compactness theorem for first order logic. Prove the validity of "Vaught's Criterion" for elementarily of a submodel, i.e. M is an elementary submodel of N if it is a submodel and if any existential formula which is true in N can be witnessed by an element of M. Prove the consistency of the theory T^C_\omega as in notes. Time permitting we will go through some basics of computability theory.

Prove theorem 1.6 (ii) from chapter 1 of our notes, a version of overspill.
Prove the compactness theorem using ultraprodcuts. See attached notes.
Write down a Turing machine for 1. multiplication 2. exponentiation.

1. Prove that if you add names to the language of a model M of arithmetic (so the language of M is the language of PA), then take a model M' of the extended language, then M' is a conservative extension of M, i.e. every set which is definable (with parameters) in M' is already definable (with parameters) in M.
2. Prove that the Cantor pairing function has a unique inverse.
3. Compactness for f.o. logic
4. Every set coded in the "D_d" sense is coded in the "F_x" sense

Prove theorems 1.20 and 1.21 from the notes, as indicated in class. Finish coding problem, that every set coded in the "D" sense, has a code in the "F" sense.

Read theorem 2.7 and corollary 2.9 in Kaye's Models of Peano Arithmetic and present it in class. Read section 3.1, prove theorem 3.3. Start reading chapter 9 (Satisfaction) up to theorem 9.15.

Prove the existence of a recursive, non-primitive recursive function.

In E. Mendelson's text Introduction to Mathematical Logic, 3rd edition, this is problem 3.33 on page 146.