The structural complexity of models of arithmetic

Abstract

The Scott rank of a countable structure is the least ordinal α such that all auto-morphism orbits of the structure are definable by infinitary Σα formulas. Montalb ́anshowed that the Scott rank of a structure is a robust measure of the structural andcomputational complexity of a structure showing that various different measures areequivalent. For example, a structure has Scott rank α if and only if it has a Πα+1 Scottsentence if and only if it is uniformly ∆∆∆0α categorical. One of the objectives of computable structure theory is to obtain measures of thecomplexity of structures in common classes. In this talk we present results on the Scottrank of non-standard models of Peano arithmetic. We show that non-standard modelsof PA have Scott rank at least ω, but, other than that, there are no limits to theircomplexity. Given a completion T of P A we give a reduction via bi-interpretability ofthe class of linear orders to the models of T . This allows us to exhibit models of T ofScott rank α for every ω ≤ α ≤ ω1. In particular, every completion of T has models ofhigh Scott rank.