May 3
Dino Rossegger, UC Berkeley and TU Wien
The structural complexity of models of PA

The Scott rank of a countable structure is the least ordinal $\alpha$ such that all automorphism orbits of the structure are definable by infinitary $\Sigma_{\alpha}$ formulas. Montalbán showed that the Scott rank of a structure is a robust measure of the structural and computational complexity of a structure by showing that various different measures are equivalent. For example, a structure has Scott rank $\alpha$ if and only if it has a $\Pi_{\alpha+1}$ Scott sentence if and only if it is uniformly $\pmb \Delta_\alpha^0$ categorical if and only if all its automorphism orbits are $\Sigma_\alpha$ infinitary definable.

In this talk we present results on the Scott rank of non-standard models of Peano arithmetic. We show that non-standard models of PA have Scott rank at least $\omega$, but, other than that, there are no limits to their complexity. Given a completion $T$ of $PA$ we give a reduction via bi-interpretability of the class of linear orders to the models of $T$. This allows us to exhibit models of $T$ of Scott rank $\alpha$ for every $\omega\leq \alpha\leq \omega_1$. In particular, every completion of $T$ has models of high Scott rank.

This is joint work with Antonio Montalbán.

Video