Rossegger, D. (2022, July 1). The structural complexity of models of arithmetic [Conference Presentation]. ASL Logic Colloquium 2022, Reykjavik, Iceland. https://doi.org/10.34726/3763
The Scott rank of a countable structure is the least ordinal α such that all automorphism orbits of the structure are definable by infinitary Σα formulas. Montalbán showed that the Scott rank of a structure is a robust measure of its structural and computational complexity by showing that various different measures are equivalent. For example, a structure has Scott rank α if and only if it has a Πα+1 Scott sentence if and only if it is uniformly Δ0α categorical. In this talk we present results on the Scott rank of models of Peano arithmetic. We show that non-standard models of PA have Scott rank at least ω and that the models of PA that have Scott rank ω are precisely the prime models. We also give reductions via bi-interpretability of the class of linear orders to completions T of PA . This allows us to exhibit models of T of Scott rank α for every ω≤α≤ω1.
en
Project title:
Algorithmische Komplexität von Strukturen und deren Äquivalenzrelationen: 101026834 (European Commission)