### Messages

### Timetable

### Material

The material for the course are the "famous" notes of Craig Smorynski. We will also rely on Richard Kaye's text "Models of Arithmetic".

## Lecture material

### Tasks

#### Homework for example class meeting 24.01

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.

#### Homework for example class 31.012

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.

#### Homework for example class 07.02

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

#### Homework for example class 21.02

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.

#### Homework for example class 28.02

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.

#### Homework for March 21

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.

### Description

Optional course.

Master's Programme in Mathematics and Statistics is responsible for the course.

The course belongs to the Mathematics and Applied mathematics module.

The course is available to students from other degree programmes.

Model theory of arithmetic including arithmetized completeness and Scott's Theorem, saturated models

Recommended time/stage of studies for completion: 1. or 2. year

Term/teaching period when the course will be offered: varying

Basic theory of models of arithmetic including the arithmetized completeness theorem; Scott sets

Exam and excercises, Course will be graded with grades 1-5

Exam, other methods will be described later