The structural complexity of models of arithmetic

2022/08/02 by Antonio Montalbán, Montalbán, Antonio, Dino Rossegger +1 · 1 citation
Computer Science · #03C62 #03E15 #03H15 #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.48550/arxiv.2208.01697

openalex publication_date 2022/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Δⁱⁿ₁ bi-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.

Cited by

• Classifying the complexity of models of arithmetic

Related

• Classifying the complexity of models of arithmetic
• Scott ranks of models of a theory
• Model Theoretic Complexity of Automatic Structures
• On highly equivalent non-isomorphic countable models of arithmetic and set theory
• Some new computable structures of high rank