December 10
Leszek Kołodziejczyk,
University of Warsaw
Models of fragments of PA with low Scott rank
The infinitary logic $L_{\omega_1, \omega}$ extends first-order logic by allowing countable disjunctions and conjunctions of formulas. Every countable structure can be described up to isomorphism (within the class of countable structures) by an $L_{\omega_1, \omega}$ sentence. This gives rise to a particular way of measuring the complexity of countable structures: there is a natural alternation hierarchy $(\Pi^{\text{in}}_\alpha: \alpha \lt \omega_1)$ of $L_{\omega_1, \omega}$ formulas, and the Scott rank of a structure $A$ is the smallest ordinal $\alpha$ such that $A$ can be described up to isomorphism by a $\Pi^{\text{in}}_{\alpha+1}$ sentence.
In recent years, beginning with a paper by Montalban and Rossegger, the Scott rank of models of arithmetic has attracted some attention. We now know, for instance, that every nonstandard pointwise definable model of ${\rm PA}$ has Scott rank at least omega, that all other nonstandard models of ${\rm PA}$ must have rank at least $\omega+1$, and that recursively saturated models of ${\rm PA}$ have rank exactly $\omega+1$. This naturally leads one to ask about possible Scott ranks of models of subtheories of ${\rm PA}$. In particular: what is the lowest possible Scott rank of a structure satisfying $I\Sigma_n + \lnot B\Sigma_{n+1}$? What about $B\Sigma_n + \lnot I\Sigma_n$?
We prove that every nonstandard model of $B\Sigma_n$ must have Scott rank at least $n+1$. Moreover, this lower bound is tight: it is realized both by the most familiar models of $I\Sigma_n + \lnot B\Sigma_{n+1}$, namely pointwise $\Sigma_{n+1}$-definable substructures of models of $I\Sigma_{n+1}$, and by the most familiar models of $B\Sigma_n + \lnot I\Sigma_n$, namely initial segments generated by the $\Sigma_n$-definables of models of $I\Sigma_n$. Time permitting, we also hope to mention a few other facts about Scott ranks of models of fragments of ${\rm PA}$.
This is joint work in progress with Mateusz Łełyk and Patryk Szlufik.