CSUN Algebra, Number Theory, and Discrete Mathematics Seminar

Using Gödel’s completeness theorem one can show that the theory of true arithmetic, the first-order theory of the discrete semiring $\mathbb{N}$, has uncountably many non-isomorphic countable models, so called non-standard models. The standard model $\mathbb{N}$ is structurally quite simple as every natural number can be uniquely described by its distance from $0$. However, non-standard models have elements of infinite rank and appear to be structurally complicated. So, how complicated are they? In order to establish the structural complexity of a countable structure we calculate its Scott rank; the least ordinal such that we can describe the automorphism orbits of the structure by infinitary formulas of rank $\alpha$.

In this talk I will present results from joint work with Antonio Montalbán on the possible Scott ranks of models of arithmetic. The standard model $\mathbb{N}$, is the unique model of true arithmetic, even of Peano arithmetic, that has finite Scott rank; its Scott rank is $1$. For every other infinite countable ordinal $\alpha$ we construct a model of arithmetic of Scott rank $\alpha$. In particular, we construct such a model for any given completion of Peano arithmetic. This characterizes the possible Scott ranks of models of Peano arithmetic as $\left\{1\right\}\cup [\omega ,{\omega }_1)$ and shows that Peano arithmetic does not have Borel isomorphism problem. Its isomorphism problem is Borel complete among isomorphism problems of countable structures.