Montalbán, A., & Rossegger, D. (2023). The structural complexity of models of arithmetic. Journal of Symbolic Logic. https://doi.org/10.1017/jsl.2023.43
arithmetic; Scott rank; Peano arithmetic; nonstandard models
en
Abstract:
We calculate the possible Scott ranks of countable models of Peano arithmetic. We show that no non-standard model can have Scott rank less than ω and that non-standard models of true arithmetic must have Scott rank greater than ω. Other than that there are no restrictions. By giving a reduction via Δin1bi-interpretability from the class of linear orderings to the canonical structural ω-jump of models of an arbitrary completion T of PA we show that every countable ordinal α > ω is realized as the Scott rank of a model of T.
en
Project title:
Algorithmische Komplexität von Strukturen und deren Äquivalenzrelationen: 101026834 (European Commission)
