The standard model of arithmetic is the structure of the natural numbers with operations of addition and multiplication. By the compactness theorem, the first-order theory of this structure has countable models that are non-standard, i.e. not isomorphic to the standard one. The study of such models sheds light on issues of (un)provability of arithmetical statements, leads to consistency and conservativity results for various arithmetical theories, and so on.

Investigations of Peano arithmetic and its natural subsystems by means of model-theoretic methods is one of the most developed areas of mathematical logic. The present course offers an introduction to this area. In particular, we shall prove Tennenbaum's theorem, which asserts that Peano arithmetic has no computable non-standard models, and the Paris–Harrington theorem, which gives an impressive example of a combinatorial statement that can neither be proved nor refuted in $\mathsf{PA}$.

Program:

1. Non-standard models of arithmetic: their existence and basic properties. Describing orderings in non-standard models of arithmetic.
2. An excursion into formal arithmetic.
3. Initial segments of non-standard models of $\mathsf{PA}$. Parikh's theorem on $\Pi_2$-consequences for the system $I \Delta_0$.
4. The subsystem $\mathsf{PA}^-$ and its models. The theorem that each decidable theory has a computable model, and its relativizations.
5. Tennenbaum's theorem and variations on it.
6. Definable elements in models of $\mathsf{PA}$. Prime models for extensions of $\mathsf{PA}$.
7. Collection axioms. The subsystems $I \Sigma_n$ and $I \Pi_n$.
8. $\Sigma_n$-definable elements and $\Sigma_n$-elementary initial segments. Conservativity and independence results for subsystems of $\mathsf{PA}$.
9. The Paris–Harrington and Kanamori–McAloon theorems.

Lecturers
Beklemishev Lev Dmitrievich
Speranski Stanislav Olegovich

Organizations
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
Steklov International Mathematical Center