1 Introduction
The structural complexity of countable structures has been an active and deep area of research at the intersection of model theory, descriptive set theory, and computability theory for more than half a century. One of the early results responsible for the interest in this area is Scott’s theorem [Reference Scott20] that every countable structure has a sentence defining it up to isomorphism among countable structures in the infinitary logic
$L_{\omega _1\omega }$
. Combining this with Vaught’s work [Reference Vaught22] on the Lopez-Escobar theorem [Reference Lopez-Escobar14] one gets a connection with descriptive set theory. Vaught showed that the sets of models of
$\Pi ^{\mathrm {in}}_{\alpha }$
formulas (we refer the reader to [Reference Ash and Knight3, Section 6.4] for a definition of quantifier complexity in
$L_{\omega _1\omega }$
) are precisely the
${\pmb {\Pi }}^{0}_{\alpha }$
isomorphism-invariant sets in the Borel hierarchy on the space of structures. Thus, not only is every isomorphism class of a countable structure Borel, but calculating the quantifier complexity of a structure’s Scott sentence gives a measure of the complexity of its isomorphism class in the Borel hierarchy.
Computability theorists use another approach to measure the complexity of countable structures. Say a structure
$\mathcal {A}$
is uniformly
${\pmb {\Delta }}^0_\alpha $
-categorical if there is a Turing operator
$\Phi $
and an oracle
$X\subseteq \omega $
such that for all
$\mathcal {B},\mathcal {C}$
isomorphic to
$\mathcal {A}$
,
${\Phi }^{(X\oplus \mathcal {B}\oplus \mathcal {C})^{(\alpha )}}$
is an isomorphism between
$\mathcal {B}$
and
$\mathcal {C}$
. It follows from results of Ash [Reference Ash5] that a structure is uniformly
${\pmb {\Delta }}^0_\alpha $
-categorical if and only if its automorphism orbits are definable by
$\Sigma ^{\mathrm {in}}_{\alpha }$
formulas. The usual proof of Scott’s theorem builds a Scott sentence for a structure out of the defining formulas of its automorphism orbits. This shows that such a structure must have a
$\Pi ^{\mathrm {in}}_{\alpha +1}$
Scott sentence. On the other hand, Montalbán [Reference Montalbán17] showed that a structure with a
$\Pi ^{\mathrm {in}}_{\alpha +1}$
Scott sentence must have all automorphism orbits
$\Sigma ^{\mathrm {in}}_{\alpha }$
definable. This unifies the two approaches and gives a robust notion of Scott rank.
Theorem 1 [Reference Montalbán17].
The following are equivalent for countable
$\mathcal {A}$
and
$\alpha <\omega _1$
.
-
(1) Every automorphism orbit of
$\mathcal {A}$
is
$\Sigma ^{\mathrm {in}}_{\alpha }$
-definable without parameters. -
(2)
$\mathcal {A}$
has a
$\Pi ^{\mathrm {in}}_{\alpha +1}$
Scott sentence. -
(3)
$\mathcal {A}$
is uniformly
${\pmb {\Delta }}^0_\alpha $
-categorical. -
(4) The set of copies of
$\mathcal {A}$
is
${\pmb {\Pi }}^0_{\alpha +1}$
in the Borel hierarchy. -
(5) No tuple in
$\mathcal {A}$
is
$\alpha $
-free.
The least
$\alpha $
satisfying the above is the (parameterless) Scott rank of
$\mathcal {A}$
.
Apart from the parameterless Scott rank several other notions of Scott rank can be found in the literature. Scott [Reference Scott20] used a notion of rank based on symmetric back-and-forth relations, Ash and Knight [Reference Ash and Knight3] defined two notions of rank based on infinitary equivalence of tuples, and Montalbán [Reference Montalbán17] also proposed a parameterized version of the above rank. All of these ranks differ by a small ordinal constant. While Montalbán’s parameterized Scott rank shares the robustness of the parameterless Scott rank, we focus on the latter in this article as it allows for a slightly finer complexity analysis.
We already gave a quick introduction to all of the notions appearing in Theorem 1 except Item 5. This is a combinatorial condition that is useful in arguments. It is based on the asymmetric back-and-forth relations, a variation of the back-and-forth relations first introduced by Barwise [Reference Barwise6] and often used in computable structure theory. See [Reference Ash and Knight3, Chapter 15] for a development of their theory and applications. Let us define the asymmetric back-and-forth relations formally. Our definitions follow Montalbán’s upcoming book [Reference Montalbán18] and we refer to it for a thorough treatment of the back-and-forth relations and other notions used here.
Definition 1. Fix a relational vocabulary
$\tau $
. Given an ordinal
$\alpha $
,
$\tau $
-structures
$\mathcal {A}$
and
$\mathcal {B}$
and tuples
$\bar a\in A^{<\omega }$
,
$\bar b\in B^{<\omega }$
define the
$\leq _\alpha $
back-and-forth relations inductively as follows:
$$\begin{align*}(\mathcal{A},\bar a)\leq_\alpha (\mathcal{B},\bar b)\iff (\forall \beta<\alpha) \forall \bar d\in B^{<\omega} \exists \bar c\in A^{<\omega} (\mathcal{B},\bar b\bar d )\leq_\beta (\mathcal{A},\bar a\bar c).\end{align*}$$
For the base case let
$(\mathcal {A},\bar a)\leq _0(\mathcal {B},\bar b)$
if
$\bar a$
and
$\bar b\operatorname {\mathrm {\upharpoonright }} |\bar a|$
satisfy the same quantifier-free
$\tau _{|\bar a|}$
-formulas.
Karp [Reference Karp12] showed that, for
$\alpha>0$
,
$(\mathcal {A},\bar a)\leq _\alpha (\mathcal {B},\bar b)$
if and only if every
$\Pi ^{\mathrm {in}}_{\alpha }$
-formula that is true of
${\bar {a}}$
in
$\mathcal {A}$
is true of
${\bar {b}}$
in
$\mathcal {B}$
.
In this article we will mostly look at the case in the above definition when
$\mathcal {A}=\mathcal {B}$
. In this case we will write the shorthand
$\bar a\leq _\alpha \bar b$
for
$(\mathcal {A},\bar a)\leq _\alpha (\mathcal {A},\bar b)$
.
Definition 2. A tuple
$\bar a$
in
${\mathcal {A}}$
is
$\alpha $
-free if
$$\begin{align*}(\forall \beta<\alpha) \forall \bar b \exists \bar a'\bar b' (\bar a\bar b \leq_\beta \bar a'\bar b'\land \bar a \not\leq_\alpha \bar a').\end{align*}$$
One of the main questions about structural complexities is how complicated structures in natural classes can be. More formally, we want to calculate the possible Scott ranks in natural classes of structures. Makkai [Reference Makkai15] defined the following.
Definition 3. Let T be an
$L_{\omega _1\omega }$
-sentence. The Scott spectrum of T is the set
$$\begin{align*}ScottSp(T)=\{\alpha<\omega_1: \alpha\text{ is the Scott rank of a countable model of } T\}.\end{align*}$$
While this definition is about models of
$L_{\omega _1\omega }$
-sentences we can also use it for measuring the complexity of structures in elementary classes, as every first-order theory can be viewed as a sentence of
$L_{\omega _1\omega }$
by taking the conjunction of all the sentences in the theory.
The purpose of this article is to study the complexity of models of Peano arithmetic (
$\mathrm {PA}$
) where, as usual:
$\mathrm {PA}$
is the theory consisting of the axioms for discrete ordered semirings and the induction scheme. An easy argument shows that the Scott rank of the standard model
$\mathbb N$
is
$1$
. We show that
$\mathbb N$
is the only model of
$\mathrm {PA}$
that has Scott rank
$1$
and that all other models must have Scott rank at least
$\omega $
. In particular, the non-standard prime models of
$\mathrm {PA}$
have Scott rank
$\omega $
and non-homogeneous models of
$\mathrm {PA}$
must have Scott rank greater than
$\omega $
. For non-standard models of the theory of the natural numbers, true arithmetic, we obtain a stronger lower bound. Every such model must have Scott rank greater than
$\omega $
. Giving a reduction from the class of linear orderings via
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretability to the structural
$\omega $
-jump of models of an arbitrary completion of
$\mathrm {PA}$
we obtain that every Scott rank greater than
$\omega $
is realized by a model of
$\mathrm {PA}$
and thus the following.
Theorem 2. Let T be a completion of
$\mathrm {PA}$
.
-
(1) If
$T=Th(\mathbb N)$
, then
$ScottSp(T)=\{1\}\cup \{\alpha <\omega _1: \alpha> \omega \}$
. -
(2) If
$T\neq Th(\mathbb N)$
, then
$ScottSp(T)=\{\alpha <\omega _1: \alpha \geq \omega \}$
.
Thus,
$ScottSp(\mathrm {PA})=\{1\}\cup \{\alpha <\omega _1: \alpha \geq \omega \}$
.
In Section 2 we formalize the back-and-forth relations in
$\mathrm {PA}$
to obtain the aforementioned lower bounds for the Scott ranks of non-standard models. In Section 4 we analyze results by Gaifman [Reference Gaifman9] to recover a reduction from linear orderings to models of
$\mathrm {PA}$
. It turns out that this reduction actually provides a reduction from linear orderings to the structural
$\omega $
-jumps of models of
$\mathrm {PA}$
. This and the properties of the structural
$\alpha $
-jump are reviewed in Section 3. At last we combine all of our results to obtain a proof of Theorem 2 and state some open problems.
2 Back-and-forth relations and Peano arithmetic
Throughout this article we assume that
$\mathcal {M}$
and
$\mathcal {N}$
are non-standard models of
$PA$
, and M and N are their respective universes. We will write
$\mathbb N$
for the set of standard natural numbers in a given model and
$\dot m$
for the formal term representing the natural number m in
$PA$
. We can code bounded subsets of a model
$\mathcal {M}$
,
$\mathcal {M}$
-finite sets, using elements of
$\mathcal {M}$
. Informally we let
$\dot 0$
be the code for the empty set and given an
$\mathcal {M}$
-finite set A,
$\sum _{a\in A} 2^a$
is its code. Using this and Cantor’s pairing function
$\langle x,y\rangle =\frac {1}{2} ((x+y)^2 +3x+y)$
we can code sequences
$\bar a\in M^{<\omega }$
by the
$\mathcal {M}$
-finite set
$\{ \langle i, a_i\rangle : i<|\bar a|\}$
. The length of sequences and concatenation can be defined in the obvious way. We refer the reader to [Reference Simpson21] for formal definitions.
Let
$Tr_{\Delta ^0_1}$
be the truth predicate for bounded formulas, i.e., a predicate satisfying for all bounded formulas
$\phi (\overline x)$
$$\begin{align*}PA\vdash \forall \overline x\ (Tr_{\Delta^0_1}(\ulcorner \phi\urcorner,\overline x) \leftrightarrow \phi(\overline x)).\end{align*}$$
We define a version of the standard asymmetric back-and-forth relations where we bound the length of the tuples involved. The idea is that we want to be able to talk about the back-and-forth relations within models of PA, and the problem is that we don’t want to have to consider tuples of non-standard length. Inductively define bounded asymmetric n-back-and-forth relations with bound a, denoted
$\leq _n^a$
, for all
$n\in \omega $
as follows:
We view
$\bar u\leq _n^a \bar v$
as a formula on three variables
$\bar u$
,
$\bar v$
, and a that refer to elements of the model, and an outside parameter
$n\in \omega $
that is just part of the notation. Note that the a parameter in the definition of
$\leq _0^a$
is technically superfluous. We just use it to emphasize that
$\leq _0^a$
is a relation in the language of
$\mathrm {PA}$
. Thanks to the availability of codes for strings we regard the above formulas as ternary predicates that are false if for some elements
$\bar u,\bar v,a\in M$
,
$\bar u$
and
$\bar v$
are not codes for sequences. Defined like this, the bounded back-and-forth relations behave as expected.
Proposition 3. The bounded back-and-forth relations
$\leq _n^x$
satisfy the following properties for all
$n\in \omega $
:
-
(1)
$PA\vdash \forall \bar u, \bar v, a, b (( a\leq b \land \bar u\leq _n^b \bar v )\to \bar u\leq _n^a \bar v)$
. -
(2)
$PA\vdash \forall \bar u, \bar v, a ( \bar u\leq _{n+1}^a \bar v \to \bar u \leq _{n}^a \bar v)$
.
Proof Item 1 can be shown using induction on
$n\in \omega $
. The case
$n=0$
follows easily. For the
$n+1$
case, take
$a\leq b$
, and
$\bar u$
and
$\bar v$
in the model. Then
$$ \begin{align*} \bar u\leq_{n+1}^b \bar v &\iff \forall \bar x\exists \bar y \Big(|\bar x|\leq b \to \bar v\bar x \leq_n^{b} \bar u\bar y\Big) \\ &\implies \forall \bar x\exists \bar y \Big(|\bar x|\leq a \to \bar v\bar x \leq_n^{b} \bar u\bar y\Big) \\ &\implies \forall \bar x\exists \bar y \Big(|\bar x|\leq a \to \bar v\bar x \leq_n^{a} \bar u\bar y\Big) \iff \bar u\leq_{n+1}^a \bar v, \end{align*} $$
where the second line uses that
$|\bar x|\leq a\implies |\bar x|\leq b$
, and the third line uses the induction hypothesis.
Item 2 follows from the definition by an easy induction.
Proposition 4. Let
$\overline a, \overline b\in M$
. Then
$$\begin{align*}\overline a\leq_n \overline b \iff (\forall m\in\omega) \mathcal{M}\models \overline a\leq_n^{\dot m }\overline b.\end{align*}$$
Furthermore, if there is
$c\in M\setminus \mathbb N$
such that
$\mathcal {M}\models \overline a\leq _n^c\overline b$
, then
$\overline a\leq _n\overline b$
.
Proof That
$\overline a\leq _n \overline b \implies \mathcal {M}\models \overline a\leq _n^{\dot m }\overline b$
for
$m\in \omega $
follows by the same argument as in the previous proposition using
$|\bar x|< \omega $
instead of
$|\bar x|\leq b$
.
That
$\mathcal {M}\models \overline a\leq _n^c\overline b\implies \overline a\leq _n\overline b$
for
$c\in M\setminus \mathbb N$
also follows by the same argument as in the previous proposition now using
$|\bar x|< c$
instead of
$|\bar x|\leq b$
, and
$|\bar x|< \omega $
instead of
$|\bar x|\leq a$
.
Finally, suppose that
$ (\forall m\in \omega ) \mathcal {M}\models \overline a\leq _n^{\dot m }\overline b$
. The set of all
$m\in M$
for which
$\mathcal {M}\models \overline a\leq _n^{m }\overline b$
is definable in
$\mathcal {M}$
(by a finitary
$\Pi ^0_{2n}$
formula), and it contains all
$m\in \omega $
. Since M satisfies induction, this set must overspill and contain some
$c\in M\setminus \mathbb N$
. So we have
$\overline a\leq _n^{c}\overline b$
. It follows from the previous paragraph that we then have
$\overline a\leq _n \overline b$
.
Lemma 5. For every
$\bar {a}, \bar {b}\in M^{<\omega }$
,
$\bar {a}\leq _\omega \bar {b}$
if and only if
$tp(\bar {a})=tp(\bar {b})$
.
Proof The left to right direction follows since
$\bar {a}\leq _\omega \bar {b}$
implies that every
$\Pi ^{\mathrm {in}}_{\omega }$
sentence true of
$\bar {a}$
is true of
$\bar {b}$
. To see the other direction assume that
$tp(\bar {a})=tp(\bar {b})$
. Then there is
$\mathcal {N}\succ \mathcal {M}$
and
$\sigma $
an automorphism of
$\mathcal {N}$
with
$\sigma (\bar {a})=\bar {b}$
, so in particular
$(\mathcal {N},\bar {a})\leq _\omega (\mathcal {N},\bar {b})$
. For every
$n,m\in \omega $
we have that
$\mathcal {N}\models \bar {a} \leq _n^{\dot m} \bar {b}$
and thus also
$\mathcal {M}\models \bar {a} \leq _n^{\dot m}\bar {b}$
. Thus, by Proposition 4, for every
$n\in \omega $
,
$(\mathcal {M},\bar {a}) \leq _n (\mathcal {M},\bar {b})$
and
$(\mathcal {M},\bar {a})\leq _\omega (\mathcal {M},\bar {b})$
as required.
2.1 Homogeneous models
Recall that a model
$\mathcal {M}$
is homogeneous if every partial elementary map
$M\to M$
extends to an automorphism. This implies that the automorphism orbits of elements in homogeneous models are equal to their types. Some of the best known examples of homogeneous models are atomic and recursively saturated models.
Lemma 5 already implies that models of
$PA$
that are not homogeneous must have Scott rank larger than
$\omega $
. To see this recall that if
$\mathcal {M}$
is not homogeneous, then there are
$\bar {a},\bar {b}\in M^{<\omega }$
such that
$tp(\bar {a})=tp(\bar {b})$
and
$\bar {a}$
and
$\bar {b}$
are not automorphic. If
$SR(\mathcal {M})\leq \omega $
, then the automorphism orbit of
$\bar {b}$
is
$\Sigma ^{\mathrm {in}}_\omega $
definable and thus
$\bar {a}\not \leq _\omega \bar {b}$
, a contradiction with Lemma 5.
Lemma 6. If
$\mathcal {M}$
is not homogeneous, then
$SR(\mathcal {M})>\omega $
.
Given a formula
$\psi (y_1,\dots ,y_n)=\exists x \phi (x,y_1,\dots ,y_n)$
, a model
$\mathcal {M}$
, and
$a_1,\dots , a_n\in M$
recall that a Skolem term
$s_\phi (a_1,\dots ,a_n)$
is the least element
$b\in M$
satisfying
$\phi (b,a_1,\dots , a_n)$
. If
$\mathcal {M}$
is a model of
$\mathrm {PA}$
, then b is uniquely determined if
$\mathcal {M}\models \psi (a_1,\dots a_n)$
. If
$\mathcal {M}\not \models \psi (a_1,\dots ,a_n)$
we use the convention that
$b=0$
. In the special case where
$\psi $
is parameter-free we refer to b as Skolem constant and denote it by
$m_\phi $
. Consider the subset
$$\begin{align*}N=\{ m_\phi:\phi \text{ an }L\text{-formula} \}. \end{align*}$$
One can prove, using the Tarski–Vaught test, that
$\mathcal {N}$
is an elementary substructure of
$\mathcal {M}$
. Furthermore
$\mathcal {N}$
is unique up to isomorphism among models of
$T=Th(\mathcal {M})$
: This is because for all formulas
$\psi (y_1,\ldots ,y_k)$
, we have that T decides whether
$\psi (m_{\varphi _1},\ldots ,m_{\varphi _k})$
holds or not. Since
$\mathcal {N}$
is a sub-model of all models of T, it is the prime model of T. Furthermore, for any
$\mathcal {M}\succeq \mathcal {N}$
if
$n\in N$
, then the automorphism orbit of n in
$\mathcal {M}$
,
$aut_{\mathcal {M}}(n)$
, is a singleton as every element of
$\mathcal {N}$
is definable in
$\mathcal {M}$
.
Theorem 7. Let
$\mathcal {N}$
be a non-standard prime model of
$PA$
, then
$SR(\mathcal {N})=\omega $
.
Proof Every prime model is atomic and thus has Scott rank at most
$\omega $
, as the defining formulas of the automorphism orbits are given by the isolating formulas of the types. To see that
$SR(\mathcal {N})\geq \omega $
consider any non-homogeneous model
$\mathcal {M}\succ \mathcal {N}$
. Then by Lemma 6,
$SR(\mathcal {M})> \omega $
. Thus, for every n there are
$\bar a_0, \bar a_1\in \mathcal {M}^{<\omega }$
such that,
$\bar a_0\leq _n \bar a_1$
but
$\bar a_0\not \in aut_{\mathcal {M}}(\bar a_1)$
. Fix n. For every
$m\in \omega $
,
$$\begin{align*}\mathcal{M}\models\exists \bar x_0,\bar x_1\left(\bar x_0\neq \bar x_1 \land \bar x_0\leq_n^{\dot m} \bar x_1\right) \end{align*}$$
and by elementarity
$\mathcal {N}\models \exists \bar x_0,\bar x_1\left (\bar x_0\neq \bar x_1 \land \bar x_0\leq _n^{\dot m} \bar x_1\right )$
. Consider the set
$$\begin{align*}X_n=\{ b\in \mathcal{N} : \mathcal{N}\models \exists \bar x_0\bar x_1\left( \bar x_0\neq \bar x_1\ \land \bar x_0 \leq_n^b \bar x_1\right)\}\end{align*}$$
which is a definable subset of
$\mathcal {N}$
containing all of
$\mathbb N$
. Therefore, as
$\mathcal {N}$
is non-standard, it must overspill and contain an element
$b^*\in \mathcal {N}\setminus \mathbb N$
. Consider
$\bar a_0,\bar a_1\in N^{<\omega }$
such that
$\bar a_0\leq ^{b^*}_n \bar a_1$
. Then, by Proposition 4,
$\bar a_0\leq _n \bar a_1$
but
$\bar a_0\neq \bar a_1$
. Since all the elements of
$\mathcal {N}$
are definable, all automorphism orbits are singletons. It follows that the automorphism orbit of
$a_1$
is not
$\Sigma ^{\mathrm {in}}_{n}$
definable (as every
$\Sigma ^{\mathrm {in}}_{n}$
formula true of
$a_1$
is also true of
$a_0$
). Hence
$SR(\mathcal {N})> n$
. Thus,
$\mathcal {N}$
does not have Scott rank less than
$\omega $
.
Theorem 8. Let
$\mathcal {M}$
be a model of
$\mathrm {PA}$
such that
$\mathcal {M}\not \models Th(\mathbb N)$
, then
$SR(\mathcal {M})\geq \omega $
.
Proof Let
$\mathcal {N}$
be the elementary sub-model of
$\mathcal {M}$
consisting of all Skolem constants in
$\mathcal {M}$
. In particular,
$\mathcal {N}$
is the prime model of
$Th(\mathcal {M})$
. Towards a contradiction, suppose that
$SR(\mathcal {M})=n<\omega $
. Then every automorphism orbit of
$\mathcal {M}$
is
$\Sigma ^{\mathrm {in}}_{n}$
definable, and therefore whenever
$\bar u \leq _n \bar a$
, we get that
$\bar u\in aut(\bar a)$
. Fix
$\bar a\in N^{<\omega }$
. Since
$\bar a$
is definable in
$\mathcal {M}$
, whenever we have
$\bar u \leq _n \bar a$
, we have
$\bar u=\bar a$
.
Consider the set
$$\begin{align*}X_{{\bar{a}}}=\{ c \in M: \mathcal{M}\models \forall \bar u (\bar u \leq_n^c \bar a\to \bar a=\bar u)\}. \end{align*}$$
This definable set contains all
$c\in M\setminus \mathbb N$
, and hence it must contain some
$k\in \mathbb N$
. By elementarity, we get that
$\mathcal {N}\models \forall \bar u (\bar u \leq _n^{\dot {k}} \bar a\to \bar a=\bar u)$
, and in particular whenever we have
$(\mathcal {N},\bar u) \leq _n (\mathcal {N},\bar a)$
, we have
$\bar u=\bar a$
. This is true for all
$\bar a\in N^{<\omega }$
, contradicting Theorem 7.
For non-standard models of true arithmetic we get an even better lower bound.
Theorem 9. Let
$\mathcal {M}\models Th(\mathbb N)$
be non-standard. Then
$SR(\mathcal {M})>\omega $
.
Proof Assume that
$\mathcal {M}\models Th(\mathbb N)$
. Then the elementary submodel
$\mathcal {N}\preccurlyeq \mathcal {M}$
consisting of all Skolem constants in
$\mathcal {M}$
is isomorphic to
$\mathbb N$
. Because
$\mathbb N$
is standard and
$SR(\mathbb N)=1$
it satisfies
$\forall \bar a \bar a'( \forall x(\bar a\leq _1^x\bar a') \leftrightarrow \forall x(\bar a\leq _n^x\bar a'))$
. Furthermore, no tuple in
$\mathbb N$
is
$1$
-free. In particular,
$\mathbb N$
satisfies the following version of
$1$
-freeness for the bounded back-and-forth relations:
$\forall \bar a \exists \bar b\forall \bar a'\bar b' \exists x\left (\bar a \bar b\leq _0^x\bar a'\bar b' \to \forall y(\bar a \leq _1^y\bar a')\right )$
. Combining these two observations we get that
$\mathbb N$
satisfies the following form of non-freeness:
$$ \begin{align} \forall \bar a \exists \bar b\forall \bar a'\bar b' \exists x\left(\bar a \bar b \leq_0^x \bar a'\bar b' \to \forall y (\bar a\leq_n^y \bar a')\right).\end{align} $$
Say
$SR(\mathcal {M})=\alpha $
with
$1<\alpha \leq \omega $
. In the case where
$\alpha =\omega $
we have that all automorphism orbits are
$\Sigma ^{\mathrm {in}}_{\omega }$
definable. Notice that this implies that for every automorphism orbit there is
$n\in \omega $
such that the orbit is
$\Sigma ^{\mathrm {in}}_{n}$
definable and that the complexity of the defining formulas of the automorphism orbits is cofinal in
$\omega $
. Furthermore, recall that a tuple has
$\Sigma ^{\mathrm {in}}_{n}$
definable automorphism orbit if and only if it is not n-free [Reference Montalbán18, Lemma II.65]. In any case, since
$\alpha>1$
and
$\alpha $
is the least such that no tuple is
$\alpha $
-free we get that there is a tuple
$\bar a$
that is
$1$
-free but not n-free for some
$n<\omega $
. So,
$\mathcal {M}$
satisfies
$\forall b \exists \bar a' \bar b' ( \bar a\bar b \leq _0\bar a'\bar b' \land \bar a\not \leq _1\bar a')$
and
$(\exists \beta <n) \exists \bar b\forall \bar a' \bar b' (\bar a \bar b \leq _\beta \bar a'\bar b'\to \bar a \leq _n\bar a').$
In particular, by the nestedness of the back-and-forth relations
$\mathcal {M}$
does not satisfy
$\exists \bar b \forall \bar a'\bar b' (\bar a\bar b \leq _0 \bar a'\bar b'\to \bar a\leq _n \bar a')$
. This implies that
$\mathcal {M}$
does not satisfy Equation (1), contradicting that
$\mathcal {M}\models Th(\mathbb N)$
.
It remains to show that
$SR(\mathcal {M})\neq 1$
. Assume the contrary and let
$a\in M\setminus \mathbb N$
with automorphism orbit defined by the
$\Sigma ^{\mathrm {in}}_{1}$
formula
$\phi $
. Then by elementarity there is
$n\in \omega $
such that
$\dot n$
satisfies one of the disjuncts of
$\phi $
and thus
$\dot n$
is in the automorphism orbit of a. But this is a contradiction, since
$\dot n$
’s automorphism orbit is a singleton.
It is easy to see that every homogeneous model has Scott rank at most
$\omega +1$
, as every automorphism orbit is definable by the infinitary conjunction over the formulas in its type. In the case where T is not true arithmetic we do not know whether there are non-atomic homogeneous models of T with Scott rank
$\omega $
.
3 The canonical structural
$\alpha $
-jump and bi-interpretability
One way to obtain a characterization of the Scott Spectrum of
$\mathrm {PA}$
is to find a reduction from a well-understood class of structures to models of
$\mathrm {PA}$
. One particularly well-understood class is the class of linear orderings. It follows from results of Ash [Reference Ash5] that
$ScottSp(\mathrm {LO})=\{\alpha <\omega _1\}$
. Theorem 8 shows that we cannot find a reduction from linear orderings that preserves Scott ranks. Instead we need a reduction that preserves Scott ranks up to an additive factor of
$\omega $
. We will do this by giving a reduction via
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretability from the class of linear orderings to the class of canonical structural
$\omega $
jumps of models of a given completion of
$\mathrm {PA}$
in Section 4. Before that we need to discuss infinitary bi-interpretability and canonical structural
$\omega $
-jumps.
3.1 Reductions via infinitary bi-interpretability
Infinitary bi-interpretability between structures, studied by Harrison-Trainor, Miller, and Montalbán [Reference Harrison-Trainor, Miller and Montalbán11], is a weakening of the model-theoretic notion of bi-interpretability. Let us recall these notions.
Definition 4 ([Reference Harrison-Trainor, Miller and Montalbán11]).
A structure
$\mathcal {A}=(A,P_0^{\mathcal {A}},\dots )$
(where
$P_i^{\mathcal {A}}\subseteq A^{a(i)}$
) is infinitarily interpretable in
$\mathcal {B}$
if there are relations
$Dom^{\mathcal {A}}_{\mathcal {B}},\sim ,R_0,R_1,\dots $
, each
$L_{\omega _1\omega }$
definable without parameters in the language of
$\mathcal {B}$
such that:
-
(1)
$Dom_{\mathcal {A}}^{\mathcal {B}}\subseteq \mathcal {B}^{<\omega }$
, -
(2)
$\sim $
is an equivalence relation on
$Dom^{\mathcal {B}}_{\mathcal {A}}$
, -
(3)
$R_i\subseteq (Dom^{\mathcal {B}}_{\mathcal {A}})^{a(i)}$
is closed under
$\sim $
,
and there exists a function
$f_{\mathcal {A}}^{\mathcal {B}}: Dom_{\mathcal {A}}^{\mathcal {B}}\to \mathcal {A}$
which induces an isomorphism:
$$\begin{align*}f_{\mathcal{A}}^{\mathcal{B}}: \mathcal{A}^{\mathcal{B}}=(Dom_{\mathcal{A}}^{\mathcal{B}}, R_0,R_1,\ldots){/}{\sim}\cong \mathcal{A}.\end{align*}$$
We say that
$\mathcal {A}$
is
$\Delta ^{\mathrm {in}}_{\alpha }$
interpretable in
$\mathcal {B}$
if the above relations are both
$\Sigma ^{\mathrm {in}}_{\alpha }$
and
$\Pi ^{\mathrm {in}}_{\alpha }$
definable in
$\mathcal {B}$
.
Definition 5 ([Reference Harrison-Trainor, Miller and Montalbán11]).
Two structures
$\mathcal {A}$
and
$\mathcal {B}$
are infinitarily bi-interpretable if there are interpretations of each structure in the other such that the compositions
$$\begin{align*}f_{\mathcal{B}}^{\mathcal{A}}\circ \tilde f_{\mathcal{A}}^{\mathcal{B}}: Dom_{\mathcal{B}}^{(Dom^{\mathcal{B}}_{\mathcal{A}})} \to \mathcal{B} \text{ and } f_{\mathcal{A}}^{\mathcal{B}}\circ \tilde f_{\mathcal{B}}^{\mathcal{A}}: Dom_{\mathcal{A}}^{(Dom^{\mathcal{A}}_{\mathcal{B}})} \to \mathcal{A}\end{align*}$$
are
$L_{\omega _1\omega }$
definable in
$\mathcal {B}$
, respectively,
$\mathcal {A}$
. If
$\mathcal {A}$
and
$\mathcal {B}$
are
$\Delta ^{\mathrm {in}}_{\alpha }$
interpretable in each other and the associated compositions are
$\Delta ^{\mathrm {in}}_{\alpha }$
definable, then we say that
$\mathcal {A}$
and
$\mathcal {B}$
are
$\Delta ^{\mathrm {in}}_{\alpha }$
bi-interpretable.
The following definition is a generalization of reducibility via effective bi-interpretability. See [Reference Montalbán19] for a thorough treatment of effective bi-interpretability.
Definition 6. A class of structures
$\mathfrak C$
is reducible via infinitary bi-interpretability to a class of structures
$\mathfrak D$
if there are infinitary formulas defining domains, relations, and isomorphisms of an infinitary bi-interpretation so that every structure in
$\mathfrak C$
is bi-interpretable with a structure in
$\mathfrak D$
using this bi-interpretation. If all the formulas are
$\Delta ^{\mathrm {in}}_{\alpha }$
then we say that
$\mathfrak C$
is reducible via
$\Delta ^{\mathrm {in}}_{\alpha }$
bi-interpretability to
$\mathfrak D$
.
Two structures that are infinitary bi-interpretable behave in the same way. A particularly striking testimony of this is the following result.
Theorem 10 ([Reference Harrison-Trainor, Miller and Montalbán11]).
Two structures are infinitary bi-interpretable if and only if their automorphism groups are Baire-measurably isomorphic.
It is easy to see that two
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable structures have the same Scott sentence complexity and thus also the same Scott rank. However, this observation is not true for infinitary bi-interpretability in general. Furthermore, Theorem 8 shows that there is no hope in having a reduction from linear orderings to Peano arithmetic that preserves the Scott rank. Instead, our goal is that given a linear ordering
${\mathcal {L}}$
we produce a model
$\mathcal {N}_{\mathcal {L}}$
such that
${\mathcal {L}}$
and
$\mathcal {N}_{\mathcal {L}}$
are bi-interpretable and
$SR(\mathcal {N}_{\mathcal {L}})=\omega +SR({\mathcal {L}})$
. Infinitary bi-interpretations of two structures
$\mathcal {A}$
and
$\mathcal {B}$
such that
$SR(\mathcal {A})$
is equal to
$\alpha +SR(\mathcal {B})$
have some interesting properties. As we will see in Corollary 15 they give
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretations between
$\mathcal {A}$
and
$\mathcal {B}_{(\alpha )}$
, the structural
$\alpha $
-jump of
$\mathcal {B}$
.
3.2 The canonical structural
$\alpha $
-jump
The canonical structural
$\alpha $
-jump is an extension of the ideas developed by Montalbán [Reference Montalbán16] (see [Reference Montalbán19] for a more up-to-date exhibition including recent developments). The canonical structural jump of a structure
$\mathcal {A}$
is obtained by adding relation symbols for the
$\Pi ^{\mathrm {in}}_{1}$
types of tuples in A to its vocabulary. It is
$\Pi ^{\mathrm {in}}_{1}$
definable in
$\mathcal {A}$
and
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable with the jump of
$\mathcal {A}$
. When trying to generalize to the
$\alpha $
-jump, it is not immediately clear how these definability properties carry over. After all, for
$\alpha>1$
, there might be continuum many formulas in the
$\Pi ^{\mathrm {in}}_{\alpha }$
-type of a tuple. However, surprisingly we will see that these properties do carry over.
Definition 7. Given a
$\tau $
-structure
$\mathcal {A}$
and a countable ordinal
$\alpha>0$
fix an injective enumeration
$(\bar a_i)_{i\in \omega }$
of representatives of the
$\alpha $
-back-and-forth equivalence classes in
$\mathcal {A}$
. The canonical structural
$\alpha $
-jump
$\mathcal {A}_{(\alpha )}$
of
$\mathcal {A}$
is the structure in the vocabulary
$\tau _{(\alpha )}$
obtained by adding to
$\tau $
relation symbols
$R_i$
interpreted as
$$\begin{align*}\bar b\in R_i^{\mathcal{A}_{(\alpha)}}\iff \bar a_i\leq_\alpha \bar b.\end{align*}$$
We will use the convention that
$\mathcal {A}_{(0)}=\mathcal {A}$
.
Notice that the canonical structural
$\alpha $
-jump of a structure is only unique up to choice of enumeration of all the
$\Pi ^{\mathrm {in}}_{\alpha }$
types. When working with the jump we always have a fixed enumeration in mind. This does not impose a strong restriction as for two enumerations the two resulting candidates for the canonical structural
$\alpha $
-jump are
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable.
Proposition 11. Let
$\mathcal {A}$
be a
$\tau $
-structure and
$\phi $
be a
$\Sigma ^{\mathrm {in}}_{\alpha +1}\ \tau $
-formula. Then there is a
$\Sigma ^{\mathrm {in}}_{1}\ \tau _{(\alpha )}$
-formula
$\psi $
such that
$$\begin{align*}\mathcal{A}_{(\alpha)} \models \forall \bar x \ (\phi(\bar x) \leftrightarrow \psi(\bar x)). \end{align*}$$
Proof Since a
$\Sigma _{\alpha +1}^{\mathrm {in}}\ \tau $
-formula is a disjunction of existentially quantified
$\Pi _{\alpha }^{\mathrm {in}} \tau $
-formulas, it is enough to prove that every
$\Pi _{\alpha }^{\mathrm {in}}\ \tau $
-formula
$\varphi $
is equivalent to a
$\Sigma _1^{\mathrm {in}} \tau _{(\alpha )}$
-formula
$\psi $
. Let
$(\bar a_i)_{i\in \omega }$
be the enumeration of representatives of
$\alpha $
-back-and-forth classes used to generate
$\mathcal {A}_{(\alpha )}$
. Given
$\phi $
let
$I_{\phi }=\{i: \mathcal {A}\models \phi (\bar a_i)\}$
. We claim that
is as required.
The proof of the claim follows easily from the definition of
$\psi $
. Suppose first that
$\mathcal {A}\models \phi (\bar a)$
. Then
${\bar {a}}\equiv _\alpha {\bar {a}}_i$
for some
$i\in I$
. It follows that
$\mathcal {A}_{(\alpha )}\models R_i(\bar a)$
and so
$\mathcal {A}_{(\alpha )}\models \psi (\bar a)$
. Conversely, if
$\mathcal {A}_{(\alpha )}\models \psi (\bar a)$
, then
$\mathcal {A}_{(\alpha )}\models R_i(\bar a)$
for some
$i\in I$
. It follows that
${\bar {a}}_i\leq _\alpha {\bar {a}}$
. Since
$\mathcal {A}\models \varphi ({\bar {a}}_i)$
and
$\varphi $
is
$\Pi _{\alpha }^{\mathrm {in}}$
, we have that
$\mathcal {A}\models \varphi ({\bar {a}})$
too.
Let
$\Gamma $
be a set of formulas. Then
$\Gamma $
is
$\Pi ^{\mathrm {in}}_{\alpha }$
-supported in
$\mathcal {A}$
if there is a
$\Pi ^{\mathrm {in}}_{\alpha }$
formula
$\phi $
such that
A proof of the following fact appeared in [Reference Montalbán18].
Proposition 12 ([Reference Montalbán18, Lemma II.62]).
For every ordinal, every structure
$\mathcal {A}$
, and every tuple
$\bar a\in A^{<\omega }$
,
$\Pi ^{\mathrm {in}}_{\alpha }\text {-} tp^{\mathcal {A}}(\bar a)$
is
$\Pi ^{\mathrm {in}}_{\alpha }$
-supported in
$\mathcal {A}$
.
Note that in Proposition 12 the supporting formula
$\phi $
is indeed equivalent to the
$\Pi ^{\mathrm {in}}_{\alpha }\text {-} tp^{\mathcal {A}}(\bar a)$
as it is itself
$\Pi ^{\mathrm {in}}_{\alpha }$
. In other words,
$\mathcal {A}\models \phi (\bar b)\iff \bar a\leq _\alpha \bar b$
. As a consequence we get a syntactic definition for the canonical structural
$\alpha $
-jump, similarly to the structural
$1$
-jump.
Corollary 13. For any structure
$\mathcal {A}$
and non-zero ordinal
$\alpha $
,
$\mathcal {A}_{(\alpha )}$
is
$\Delta ^{\mathrm {in}}_{\alpha +1}$
interpretable in
$\mathcal {A}$
.
Proof All the relations
$R_i^{\mathcal {A}_{(\alpha )}}$
are
$\Pi ^{\mathrm {in}}_{\alpha }$
definable in
$\mathcal {A}$
. These definitions together with
$Dom_{\mathcal {A}_{(\alpha )}}^{\mathcal {A}}=A$
and
$\sim $
the graph of the identity function yield a
$\Delta ^{\mathrm {in}}_{\alpha +1}$
interpretation of
$\mathcal {A}_{(\alpha )}$
in
$\mathcal {A}$
.
Proposition 12 also lets us proof the dual of Proposition 11.
Proposition 14. Let
$\mathcal {A}$
be a
$\tau $
-structure and let
$\phi $
be a
$\Sigma ^{\mathrm {in}}_{1}$
$\tau _{(\alpha )}$
-formula. Then there is a
$\Sigma ^{\mathrm {in}}_{\alpha +1}\ \tau $
-formula
$\psi $
such that for all
$\bar a\in A^{<\omega }$
$$\begin{align*}\mathcal{A}\models \psi(\bar a) \iff \mathcal{A}_{(\alpha)}\models \phi(\bar a).\end{align*}$$
Proof To obtain
$\psi $
from
$\phi $
simply replace each occurrence of the relation
$R_i$
with the supporting formula of the
$\Pi ^{\mathrm {in}}_{\alpha }$
type of
$\bar a_i$
. Clearly the resulting formula is
$\Sigma ^{\mathrm {in}}_{\alpha +1}$
and
$\mathcal {A}_{(\alpha )}\models \phi (\bar a)$
if and only if
$\mathcal {A}\models \psi (\bar a)$
.
Combining everything we have proven about the structural
$\alpha $
-jump so far, the following corollary may not be very surprising. It is, however, quite useful as we will see in Section 4.
Corollary 15. For all countable ordinals
$\alpha $
and
$\gamma $
, the following are equivalent.
-
(1)
$\mathcal {A}_{(\gamma )}$
is
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable with
$\mathcal {B}_{(\alpha )}$
. -
(2)
$\mathcal {A}$
is infinitary bi-interpretable with
$\mathcal {B}$
such that
$:$
-
(a) the interpretation of
$\mathcal {A}$
in
$\mathcal {B}$
and
$f_{\mathcal {B}}^{\mathcal {A}}\circ \tilde f_{\mathcal {A}}^{\mathcal {B}}$
are
$\Delta ^{\mathrm {in}}_{\alpha +1}$
in
$\mathcal {B}$
, -
(b) the interpretation of
$\mathcal {B}$
in
$\mathcal {A}$
and
$f_{\mathcal {A}}^{\mathcal {B}}\circ \tilde f_{\mathcal {B}}^{\mathcal {A}}$
are
$\Delta ^{\mathrm {in}}_{\gamma +1}$
in
$\mathcal {A}$
, -
(c) for every
$\bar a \in Dom_{\mathcal {A}}^{\mathcal {B}}$
,
$\{\bar c: (\mathcal {A}^{\mathcal {B}},\bar c)\models \Pi ^{\mathrm {in}}_{\gamma }\text {-} tp^{\mathcal {A}^{\mathcal {B}}}(\bar a)\}$
is
$\Delta ^{\mathrm {in}}_{\alpha +1}$
definable in
$\mathcal {B}$
, -
(d) for every
$\bar b \in Dom_{\mathcal {B}}^{\mathcal {A}}$
,
$\{\bar c: (\mathcal {B}^{\mathcal {A}},\bar c)\models \Pi ^{\mathrm {in}}_{\alpha }\text {-} tp^{\mathcal {B}^{\mathcal {A}}}(\bar b)\}$
is
$\Delta ^{\mathrm {in}}_{\gamma +1}$
definable in
$\mathcal {A}$
.
-
Proof Assume that
$\mathcal {A}_{(\gamma )}$
is
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable with
$\mathcal {B}_{(\alpha )}$
. From Corollary 13 we get that
$\mathcal {B}_{(\alpha )}$
is
$\Delta ^{\mathrm {in}}_{\alpha +1}$
interpretable in
$\mathcal {B}$
and hence if
$\mathcal {A}_{(\gamma )}$
is
$\Delta ^{\mathrm {in}}_{1}$
interpretable in
$\mathcal {B}_{(\alpha )}$
, then it is
$\Delta ^{\mathrm {in}}_{\alpha +1}$
interpretable in
$\mathcal {B}$
. In particular,
$\mathcal {A}$
is
$\Delta ^{\mathrm {in}}_{\alpha +1}$
interpretable in
$\mathcal {B}$
. Similarly, as
$f_{\mathcal {B}}^{\mathcal {A}}\circ \tilde {f}^{\mathcal {B}}_{\mathcal {A}}$
is
$\Delta ^{\mathrm {in}}_{1}$
definable in
$\mathcal {B}_{(\alpha )}$
, it is
$\Delta ^{\mathrm {in}}_{\alpha +1}$
in
$\mathcal {B}$
. Thus, we get Item 2a and Item 2c. Item 2d and Item 2d follow by a symmetric argument.
Assuming all the items in Item 2 we get that
$\mathcal {A}_{(\gamma )}$
is
$\Delta ^{\mathrm {in}}_{\alpha }$
interpretable in
$\mathcal {B}$
and
$\mathcal {B}_{(\alpha )}$
is
$\Delta ^{\mathrm {in}}_{\gamma }$
interpretable in
$\mathcal {A}$
. By Proposition 11 we get that
$\mathcal {A}_{(\gamma )}$
is
$\Delta ^{\mathrm {in}}_{1}$
interpretable in
$\mathcal {B}_{(\alpha )}$
and vice versa, that
$f_{\mathcal {B}}^{\mathcal {A}}\circ \tilde {f}^{\mathcal {B}}_{\mathcal {A}}$
is
$\Delta ^{\mathrm {in}}_{1}$
definable in
$\mathcal {B}_{(\alpha )}$
, and that
$f_{\mathcal {A}}^{\mathcal {B}}\circ \tilde {f}_{\mathcal {B}}^{\mathcal {A}}$
is
$\Delta ^{\mathrm {in}}_{1}$
definable in
$\mathcal {A}_{(\gamma )}$
. Thus,
$\mathcal {A}_{(\gamma )}$
and
$\mathcal {B}_{(\alpha )}$
are
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable.
Using Lemma 5 we get that the canonical structural
$\omega $
-jump of models of Peano arithmetic has a model theoretic flavor.
Proposition 16. For
$\mathcal {N} \models \mathrm {PA}$
, the structure
$(\mathcal {N}, (S_n)_{n\in \omega })$
, where
$(S_n)_{n\in \omega }$
is a listing of the types realized in
$\mathcal {N}$
, is the canonical structural
$\omega $
-jump of
$\mathcal {N}$
.
At last we need to relate the Scott rank of a structure with the Scott rank of its jump. For this we need to study how the back-and-forth relations interact.
Proposition 17. Let
$\mathcal {A}$
be a structure and
$\alpha ,\beta <\omega _1$
where
$\beta>0$
. Then
$(\mathcal {A}_{(\alpha )},\bar a)\leq _{\beta } (\mathcal {A}_{(\alpha )},\bar b)\iff (\mathcal {A},\bar a)\leq _{\alpha +\beta } (\mathcal {A},\bar b)$
.
Proof The proposition is proven by transfinite induction on
$\beta $
. The successor and limit cases are actually trivial, and the only case that matters is the base case
$\beta =1$
.
Say
$(\mathcal {A},\bar a)\leq _{\alpha +1}(\mathcal {A},\bar b)$
, then
$\Sigma ^{\mathrm {in}}_{\alpha +1}\text {-} tp^{\mathcal {A}}(\bar b)\subseteq \Sigma ^{\mathrm {in}}_{\alpha +1}\text {-} tp^{\mathcal {A}}(\bar a)$
. By Propositions 11 and 14,
$\Sigma ^{\mathrm {in}}_{1}\text {-} tp^{\mathcal {A}_{(\alpha )}}(\bar b)\subseteq \Sigma ^{\mathrm {in}}_{1}\text {-} tp^{\mathcal {A}_{(\alpha )}}(\bar a)$
and thus
$(\mathcal {A}_{(\alpha )},\bar a)\leq _1 (\mathcal {A}_{(\alpha )},\bar b)$
.
On the other hand assume that
$(\mathcal {A}_{(\alpha )},\bar a)\leq _1(\mathcal {A}_{(\alpha )},\bar b)$
. We have that
$(\mathcal {A},\bar a)\leq _{\alpha +1} (\mathcal {A},\bar b)$
if and only if for all
$\bar d$
there is
$\bar c$
such that
$(\mathcal {A},\bar b\bar d)\leq _\alpha (\mathcal {A},\bar a\bar c)$
. Fix a tuple
$\bar d$
and let
$\bar a_i$
be such that
$\bar b\bar d\equiv _\alpha \bar a_i$
. Then
$(\mathcal {A}_{(\alpha )},\bar b\bar d)\models R_i(\bar b\bar d)$
, and in particular
$(\mathcal {A}_{(\alpha )},\bar b)\models \exists \bar x R_i(\bar b\bar x)$
. By assumption that
$(\mathcal {A}_{(\alpha )},\bar a)\leq _1(\mathcal {A}_{(\alpha )},\bar b)$
, also
$(\mathcal {A}_{(\alpha )},\bar a)\models \exists \bar x R_i(\bar a\bar x)$
. Pick a witness
$\bar c_0$
for
$\bar x$
. Then
$\Pi ^{\mathrm {in}}_{\alpha }\text {-} tp^{\mathcal {A}}(\bar a\bar c_0)\supseteq \Pi ^{\mathrm {in}}_{\alpha }\text {-} tp^{\mathcal {A}}(\bar b\bar d)$
and thus
$(\mathcal {A},\bar b\bar d)\leq _\alpha (\mathcal {A},\bar a \bar c_0)$
as required.
Assume that a tuple
$\bar a$
from
$\mathcal {A}$
is
$(\alpha +\beta )$
-free where
$\beta \geq 1$
. Then in particular for all
$\gamma <\beta $
$$\begin{align*}\forall \bar b \exists \bar a'\bar b' \left((\mathcal{A},\bar a\bar b)\leq_{\alpha+\gamma} (\mathcal{A},\bar a'\bar b')\land (\mathcal{A},\bar a)\not\leq_{\alpha+\beta}(\mathcal{A},\bar a')\right)\end{align*}$$
and hence by Proposition 17,
$$\begin{align*}(\forall \gamma<\beta )\forall \bar b\exists\bar a'\bar b' \left((\mathcal{A}_{(\alpha)},\bar a\bar b)\leq_{\gamma} (\mathcal{A}_{(\alpha)},\bar a'\bar b') \land (\mathcal{A}_{(\alpha)},\bar a)\not\leq_\beta (\mathcal{A}_{(\alpha)},\bar a')\right).\end{align*}$$
So,
$\bar a$
is
$\beta $
-free in
$\mathcal {A}_{(\alpha )}$
. On the other hand if
$\bar a$
is
$\beta $
-free in
$\mathcal {A}_{(\alpha )}$
we get by Proposition 17 that
$$\begin{align*}(\forall \gamma<\beta) \forall \bar b \exists \bar a'\bar b'\left( (\mathcal{A},\bar a\bar b)\leq_{\alpha+\gamma} (\mathcal{A},\bar a'\bar b') \land (\mathcal{A},\bar a)\not\leq_\beta (\mathcal{A},\bar a')\right). \end{align*}$$
Recall that the back-and-forth relations are nested, i.e., if for some
$\bar a, \bar b$
, and
$\beta $
,
$\bar a\leq _\beta \bar b$
, then for all
$\gamma <\beta $
,
$\bar a\leq _\gamma \bar b$
. Hence we get that the above equation holds for all
$\gamma <\alpha +\beta $
and thus
$\bar a$
is
$(\alpha +\beta )$
-free in
$\mathcal {A}$
. Using Item 5 in Theorem 1 we obtain the following.
Corollary 18. For any structure
$\mathcal {A}$
and non-zero
$\alpha ,\beta <\omega _1$
,
$SR(\mathcal {A})=\alpha +\beta $
if and only if
$SR(\mathcal {A}_{(\alpha )})=\beta $
.
4 Reducing linear orderings to models of
$\mathrm {PA}$
The goal of this section is to complete the proof of Theorem 2 by showing that for every completion T of
$\mathrm {PA}$
and every countable ordinal
$\alpha $
bigger than
$\omega $
,
$\alpha $
is the Scott rank of a model of T. The main missing part is the following theorem which is the main result of this section.
Theorem 19. For any completion T of
$\mathrm {PA}$
, the class of linear orderings is reducible via
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretability to the canonical structural
$\omega $
-jumps of models of T.
To prove Theorem 19 we use a classical construction of Gaifman [Reference Gaifman9]. The following result is a special case of one of his results (see [Reference Kossak and Schmerl13, Section 3.3] for more details).
Theorem 20 (cf. [Reference Gaifman9]).
For every completion T of
$\mathrm {PA}$
and every linear order
${\mathcal {L}}$
, there is a model
$\mathcal {N}_{\mathcal {L}}\models T$
such that the automorphism groups of
${\mathcal {L}}$
and
$\mathcal {N}_{\mathcal {L}}$
are isomorphic.
In light of Theorem 10 this result suggests that there is an infinitary bi-interpretation between
${\mathcal {L}}$
and
$\mathcal {N}_{\mathcal {L}}$
. Coskey and Kossak [Reference Coskey and Kossak8] used Gaifman’s construction to obtain a Borel reduction from linear orderings to models of T and thus obtained that the isomorphism relation on the models of T is Borel complete. Analyzing Gaifman’s construction we will see that this
${\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable with the canonical structural
$\omega $
-jump of
$\mathcal {N}_{\mathcal {L}}$
.
4.1 Gaifman’s
${\mathcal {L}}$
-canonical extension
This section follows Gaifman’s construction. We will outline his proof and refer the reader to [Reference Kossak and Schmerl13, Section 3.3] for details. We will work with a fixed completion T of
$\mathrm {PA}$
. The main ingredient of Gaifman’s construction are minimal types. A type
$p(x)$
is minimal if and only if
$p(x)$
is:
-
(1) unbounded:
$(t<x)\in p(x)$
for every Skolem constant, and -
(2) indiscernible: for every model
$\mathcal {M}$
, and all increasing sequences of elements
$\bar a, \bar b$
in M of the same length with each element realizing
$p(x)$
,
$tp^{\mathcal {M}}(\bar a)=tp^{\mathcal {M}}(\bar b)$
.
This is not Gaifman’s original definition, rather a convenient characterization. The original definition was that a type
$p(x)$
is minimal if it is unbounded and whenever
$\mathcal {M}\models T$
and
$\mathcal {M}(a)$
is a
$p(x)$
-extension of
$\mathcal {M}$
, then there is no
$\mathcal {N}$
such that
$\mathcal {M}\prec \mathcal {N}\prec \mathcal {M}(a)$
. See [Reference Kossak and Schmerl13, Section 3.2] for this and other characterizations of minimal types.
One other property of minimal types is that they are definable in the sense of stable model theory. That is, for every formula
$\phi (u,v)$
, there is a formula
$\sigma _\phi (u)$
such that for all Skolem constants t,
$\phi (t,v)\in p(x) \Leftrightarrow T\vdash \sigma _\phi (t)$
. Gaifman used these types to build
${\mathcal {L}}$
-canonical extensions of models
$\mathcal {M}$
given a linear order
${\mathcal {L}}$
. We will build the
${\mathcal {L}}$
-canonical extension of the prime model
$\mathcal {N}$
, denoted by
$\mathcal {N}_{\mathcal {L}}$
. We will fix a minimal type
$p(x)$
not realized in
$\mathcal {N}$
. Gaifman [Reference Kossak and Schmerl13, Theorem 3.1.4] used Ramsey’s theorem to show that minimal types exist. Let us point out though that one can find a minimal type recursive in T [Reference Kossak and Schmerl13, Remark below Theorem 3.1.4].
Let
$p(x), q(y)$
be two definable types. Then we can define the product
$p(x)\times q(y)$
to be the type
$r(x,y)$
of
$(a,b)$
in
$\mathcal {M}(a)(b)$
where
$\mathcal {M}(a)$
is a
$p(x)$
-extension of
$\mathcal {M}$
and
$\mathcal {M}(a)(b)$
is a
$q(y)$
-extension of
$\mathcal {M}(a)$
. Definability of
$q(x)$
guarantees uniqueness of
$r(x,y)$
, as
$\phi (x,y)\in r(x,y)$
if and only if
$\exists x \phi (x,y)\in q(y)$
and
$\sigma _\phi (x)\in p(x)$
. Furthermore, if
$\mathcal {M}(a_1,\dots ,a_n)$
is a
$p_1(x_1)\times \dots \times p_n(x_n)$
-extension and
$\mathcal {M}(b_1,\dots , b_k)$
is a
$p_{i_1}(x_{i_1})\times \dots \times p_{i_k}(x_{i_k})$
-extension with all
$i_k$
disjoint and between
$1$
and n, then there is a unique elementary embedding that is the identity on
$\mathcal {M}$
and takes
$b_j$
to
$a_{i_j}$
. This allows us to iterate
$p(x)$
-extensions. Given a linear ordering
${\mathcal {L}}$
, associate with every
$l\in L$
a variable
$x_l$
and a minimal type
$p(x_l)$
(where
$p(x_{l_1})$
and
$p(x_{l_2})$
only differ in the free variable). Fix the prime model
$\mathcal {N}$
of T and let
$\mathcal {N}_{\mathcal {L}}$
be the structure obtained by taking the direct limit of all
$p(x_{l_1})\times \dots \times p(x_{l_k})$
-extensions of
$\mathcal {N}$
for every ascending sequence
$l_1<\dots <l_k$
in
${\mathcal {L}}$
. The structure
$\mathcal {N}_{\mathcal {L}}$
is commonly referred to as an
${\mathcal {L}}$
-canonical extension of
$\mathcal {N}$
. We will refer to the elements of
${\mathcal {L}}$
and their corresponding elements in
$\mathcal {N}_{\mathcal {L}}$
as the generators of
$\mathcal {N}_{\mathcal {L}}$
.
4.2 Interpreting
${\mathcal {L}}$
in
$\mathcal {N}_{\mathcal {L}}$
The prime model
$\mathcal {N}$
of any completion T of
$\mathrm {PA}$
has a copy whose elementary diagram—the set
$\bigoplus _{i,j\in \omega } \{\langle a_1,\dots ,a_j \rangle : \mathcal {N}\models \phi ^j_i(\bar a_1,\dots ,\bar a_j) \}$
where
$\phi _i^j$
is the ith formula in the language of arithmetic with j free variables—is T-computable. We say that such
$\mathcal {N}$
is T-decidable.
Something similar can be observed for the models
$\mathcal {N}_{\mathcal {L}}$
. Fix an enumeration
$(s_i)_{i\in \omega }$
of the Skolem terms of T. Let
$Var=\{x_i:i\in L\}$
, and, given
${\mathcal {L}}$
, let
$\lambda :Var^{<\omega } \to Var^{<\omega }$
be the function taking tuples of variables and outputting them such that their indices form an
${\mathcal {L}}$
-ascending sequence. The canonical copy of
$\mathcal {N}_{\mathcal {L}}$
is given by the quotient of the Skolem terms with parameters being the generators under the equivalence
$\sim $
given by
$$\begin{align*}s_m(\bar x)\sim s_n(\bar x') \iff \left(\bigwedge_{i<|\bar x|+|\bar x'|}p(\lambda(\bar x^\smallfrown\bar x')_{i}) \right)\models s_m(\bar x)=s_n(\bar x'). \end{align*}$$
For any first-order formula
$\phi $
and elements
$s_1(\bar x_1),\dots , s_m(\bar x_m)$
in
$\mathcal {N}_{\mathcal {L}}$
we have that
$$ \begin{align*} \mathcal{N}_{\mathcal{L}} \models & \phi(s_1(\bar x_1),\dots, s_m(\bar x_m)) \\ & \iff \left(\bigwedge_{i<|\bar x_1|+\dots+ |\bar x_m|} p(\lambda({\bar x_1}^\smallfrown\dots^\smallfrown \bar x_m)_i)\right)\models \phi(s_1(\bar x_1),\dots , s_m(\bar x_m)). \end{align*} $$
We will interpret this canonical presentation of
$\mathcal {N}_{\mathcal {L}}$
in
${\mathcal {L}}$
using relations in
$\omega \times \mathcal {N}_{\mathcal {L}}^{<\omega }$
. We use
$\omega \times \mathcal {N}_{\mathcal {L}}^{<\omega }$
instead of
$\mathcal {N}_{\mathcal {L}}^{<\omega }$
for conceptual reasons. Given
$R\subseteq \omega \times \mathcal {N}_{\mathcal {L}}^{<\omega }$
we can effectively pass to a relation
$R'\subseteq \mathcal {N}_{\mathcal {L}}^{<\omega }$
and vice versa by letting
$R'=\{\underbrace {a \dots a}_{n \text { times}} b\bar c: a,b\in \mathcal {N}_{\mathcal {L}}, (n,\bar c)\in R\}$
. We let
$Dom_{\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}=L\cup \{\langle n,l_1,\dots l_m\rangle : s_n(x_{l_1},\dots ,x_{l_m})\in \mathcal {N}_{\mathcal {L}}\}$
and the relation symbols and
$\sim $
to be interpreted in the obvious way from
$\mathcal {N}_{\mathcal {L}}$
. It is not immediate that the so defined relations are
$\Delta ^{\mathrm {in}}_{1}$
-definable in
${\mathcal {L}}$
. We will use the relativization of a result obtained by Ash, Knight, Manasse, Slaman [Reference Ash, Knight, Manasse and Slaman4], and, independently, Chisholm [Reference Chisholm7]. A proof for the version that we are using can be found in [Reference Montalbán19].
Lemma 21 ([Reference Montalbán19], cf. [Reference Ash, Knight, Manasse and Slaman4, Reference Chisholm7]).
Let
$\mathcal {A}$
be a structure,
$R\leq \omega \times A^{<\omega }$
a relation on
$\mathcal {A}$
, and
$X\subseteq \omega $
. The following are equivalent
$:$
-
(1) R is uniformly relatively intrinsically X-c.e., that is in every copy
$\hat {\mathcal {A}}\cong \mathcal {A}$
, the relation
$R^{\hat {\mathcal {A}}}$
is X-c.e. in
$\hat {\mathcal {A}}$
, uniformly in the copies. -
(2) R is definable by an X-computable
$\Sigma ^{\mathrm {in}}_{1}$
formula in the language of
$\mathcal {A}$
.
Using this lemma one easily sees that the elementary diagram of
$\mathcal {N}_{\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{1}$
interpretable in
${\mathcal {L}}$
.
In order to prove Theorem 19 we want to use Item 2 of Corollary 15. Towards that we show that the
$\Pi ^{\mathrm {in}}_{\omega }$
types of tuples in
$\mathcal {N}_{\mathcal {L}}$
are
$\Delta ^{\mathrm {in}}_{1}$
definable in
${\mathcal {L}}$
. By Lemma 5 it is sufficient to show that all first-order types realized in
$\mathcal {N}_{\mathcal {L}}$
are
$\Delta ^{\mathrm {in}}_{1}$
definable in
${\mathcal {L}}$
. Since the full first-order structure of
$\mathcal {N}_{\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{1}$
interpretable in
${\mathcal {L}}$
, the sets
$\{ \bar b: \bar b\models tp^{{\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}}( \bar a)\}$
for
$\bar a\in \mathcal {N}_{\mathcal {L}}$
are clearly
$\Pi ^{\mathrm {in}}_{1}$
definable in
${\mathcal {L}}$
. We will show that they are also
$\Sigma ^{\mathrm {in}}_{1}$
definable.
Lemma 22. For every
$\bar a\in (Dom_{\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}})^{<\omega }$
, the set
$\{ \bar b: \bar b\models tp^{{\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}}( \bar a)\}$
is
$\Sigma ^{\mathrm {in}}_{1}$
-definable in
${\mathcal {L}}$
.
Proof First note that if
$\bar a$
is an n-tuple of generators of
$\mathcal {N}_{\mathcal {L}}$
, then
$tp^{{\mathcal {N}_{\mathcal {L}}}^{{\mathcal {L}}}}(\bar a)=\bigwedge _{i<n} p(x_i)$
and the elements satisfying this type are all in the
$\sim $
-closure of the generators of length n from
${\mathcal {L}}$
. It is therefore trivially
$\Sigma ^{\mathrm {in}}_{1}$
definable in
${\mathcal {L}}$
. Every other element is a Skolem term with generators as parameters. We will view these elements as such. Recall that in a model of
$\mathrm {PA}$
we can represent every finite sequence of elements by a single element, its code. Given
$\bar a$
, recall that its code is the element
$c(\bar a)=\sum _{i<|a|} 2^{\langle i,a_i\rangle }$
. It is then not hard to see that
$\bar b\models tp(\bar a)$
if and only if
$c(\bar b)\models tp(c(\bar a))$
. Thus, it is sufficient to establish the lemma for
$1$
-types.
Claim 22.1. Let s be a Skolem term and
$a=s(l_1,\dots , l_n)$
where
$l_1<\dots <l_n\in L$
. If
$b=s(k_1,\dots ,k_n)$
for some
$k_1<\dots <k_n\in L$
, then
$b\models tp(a)$
.
Assuming the claim, we have that every type in
${\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}$
is a countable union of Skolem terms with parameters being all ordered L-tuples. Let
$(s_i)_{i\in \omega }$
be an enumeration of these Skolem terms. Then it is definable by a
$\Sigma ^{\mathrm {in}}_{1}$
formula of the form
where the
$s_i$
can be viewed as a formula in the language of
$\mathrm {PA}$
and thus are
$\Delta ^{\mathrm {in}}_{1}$
interpretable in
${\mathcal {L}}$
.
Proof of Claim 22.1
Note that
$(k_1,\dots ,k_n)\models tp(l_1,\dots ,l_n)$
. Say
$b=s(k_1,\dots ,k_n)$
and that
$b\not \models tp(a)$
, then there is
$\psi $
such that
${\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}\models \psi (b)$
and
${\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}\not \models \psi (a)$
. So
${\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}\models \exists x ( x=s(l_1,\dots ,l_n) \land \neg \psi (x) )$
and
${\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}\models \exists x ( x=s(k_1,\dots ,k_n) \land \psi (x) )$
, a contradiction as
$(k_1,\dots ,k_n)\models tp(l_1,\dots ,l_n)$
.
We have thus shown the following.
Lemma 23. For every linear ordering
${\mathcal {L}}$
,
$(\mathcal {N}_{\mathcal {L}})_{(\alpha )}$
is
$\Delta ^{\mathrm {in}}_{1}$
interpretable in
${\mathcal {L}}$
.
4.3 Interpreting
${\mathcal {L}}$
in
$\mathcal {N}_{\mathcal {L}}$
Our goal is to show that
${\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{\omega +1}$
interpretable in
$\mathcal {N}_{\mathcal {L}}$
. This follows from the following lemma which can be extracted from various results of Gaifman.
Lemma 24. For any
${\mathcal {L}}$
,
$\{a: tp^{\mathcal {N}_{\mathcal {L}}}(a)=p(x)\}=L$
. In particular,
$(\{a: tp^{\mathcal {N}_{\mathcal {L}}}(a))=p(x)\}, \leq ^{\mathcal {N}_{\mathcal {L}}})\cong {\mathcal {L}}$
.
Proof sketch
To obtain a proof of this lemma we need the definition of the gap of an element. For fixed
$\mathcal {M}\models PA$
, let
$\mathcal F$
be the set of first-order definable functions
$f: M\to M$
for which
$x\leq f(x)\leq f(y)$
whenever
$x\leq y$
. Then for any
$a\in M$
let
$gap(a)$
be the smallest set S with
$a\in S$
and if
$b\in S$
,
$f\in \mathcal {F}$
, and
$b\leq x\leq f(b)$
or
$x\leq b\leq f(x)$
, then
$x\in S$
. Notice that the gaps of
$\mathcal {M}$
partition
$\mathcal {M}$
into
$\leq ^{\mathcal {M}}$
-intervals. We can thus obtain an equivalence relation
$a\sim b \iff gap(a)=gap(b)$
and study the order type
$(\mathcal {M}{/}{\sim }, \leq ^{\mathcal {M}})$
, the order type of the gaps of
$\mathcal {M}$
. Notice, that if
$\mathcal {M}$
is the prime model of T, then the order type of its gaps is
$1$
and unsurprisingly, the order type of the gaps of
$\mathcal {N}_{\mathcal {L}}$
is
$1+o({\mathcal {L}})$
[Reference Kossak and Schmerl13, Corollary 3.3.6].
Minimal types and gaps interact in interesting ways. Minimal types are rare, that is no two elements in the same gap can realize the same minimal type [Reference Kossak and Schmerl13, Lemma 3.1.15]. A different characterization of a rare type
$p(x)$
is that if a is an element realizing it and
$b\in gap(a)$
, then a is in the Skolem closure of b [Reference Kossak and Schmerl13, Theorem 3.1.16]. So, in particular, if the type
$p(x)$
is non-principal, then in the first gap, the gap of
$0$
,
$p(x)$
cannot be realized. Thus, we get that
${\mathcal {L}}$
and the ordering of the elements of type
$p(x)$
in
$\mathcal {N}^{\mathcal {L}}$
are isomorphic.
It remains to show that the elements of type
$p(x)$
are precisely the generators. Clearly the type of every generator is
$p(x)$
by construction. To see that
$L\supseteq \{a:tp^{\mathcal {N}_{\mathcal {L}}}(a)=p(x)\}$
, note that every
$b\in \mathcal {N}_{\mathcal {L}}$
is of the form
$s(l_1,\dots ,l_m)$
where s is a Skolem term and
$l_1,\dots ,l_m$
is a sequence of generators. Then
$b\in \mathcal {N}(l_1,\dots ,l_m)$
and thus by rarity, if b had type
$p(x)$
, then
$gap(b)\neq gap(l_i)$
for
$i<m$
and
$gap(b)\neq gap(0)$
. But the order type of the gaps in
$\mathcal {N}(l_1,\dots ,l_m)$
is
$1+m$
and every
$l_i$
and
$0$
sit in their own gap, so this is impossible.
Lemma 24 yields a natural interpretation of
${\mathcal {L}}$
in
$\mathcal {N}_{\mathcal {L}}$
given by
$Dom_{\mathcal {L}}^{\mathcal {N}_{\mathcal {L}}}=\{ a: a\models p(x)\}$
,
$\sim =id$
, and
$\leq ^{{\mathcal {L}}^{\mathcal {N}_{\mathcal {L}}}}=\leq ^{\mathcal {N}_{\mathcal {L}}}$
. The only complicated relation is
$Dom_{{\mathcal {L}}}^{\mathcal {N}_{\mathcal {L}}}$
which has a
$\Pi ^{\mathrm {in}}_{\omega }$
definition given by the conjunction of all formulas in
$p(x)$
. We thus obtain the required interpretation.
Lemma 25. Every linear ordering
${\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{\omega +1}$
interpretable in
$\mathcal {N}_{\mathcal {L}}$
.
To finish the proof of Theorem 19 it remains to show that
$\mathcal {N}_{\mathcal {L}}$
and
${\mathcal {L}}$
are infinitary bi-interpretable, i.e., that the function
$f_{{\mathcal {L}}}^{\mathcal {N}_{\mathcal {L}}}\circ \tilde f_{\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}: {{\mathcal {L}}^{(\mathcal {N}_{\mathcal {L}})}}^{\mathcal {L}}\to {\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{1}$
definable in
${\mathcal {L}}$
and that
$f^{\mathcal {L}}_{\mathcal {N}_{\mathcal {L}}}\circ \tilde f^{\mathcal {N}_{\mathcal {L}}}_{\mathcal {L}}: {(\mathcal {N}_{\mathcal {L}})^{\mathcal {L}}}^{(\mathcal {N}_{\mathcal {L}})}\to \mathcal {N}_{\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{\omega +1}$
definable in
$\mathcal {N}_{\mathcal {L}}$
. We have that
$Dom_{\mathcal {L}}^{Dom_{\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}}=\{ \bar a\in L^{<\omega }: tp^{(\mathcal {N}_{\mathcal {L}})^{\mathcal {L}}}(\bar a)=p(x)\}=L$
. Thus, by Lemma 24,
$f_{{\mathcal {L}}}^{\mathcal {N}_{\mathcal {L}}}\circ \tilde f_{\mathcal {N}_{\mathcal {L}}}^{\mathcal {L}}=id_{\mathcal {L}}$
and so trivially
$\Delta ^{\mathrm {in}}_{1}$
definable in
${\mathcal {L}}$
.
On the other hand
$$\begin{align*}Dom_{\mathcal{N}_{\mathcal{L}}}^{Dom_{\mathcal{L}}^{\mathcal{N}_{\mathcal{L}}}}=\{\langle n, a_1,\dots, a_m\rangle: n\in\omega, (\forall i<m) tp^{\mathcal{N}_{\mathcal{L}}}(a_i)=p(x)\}\end{align*}$$
and
$$ \begin{align*} Graph_{f^{{\mathcal{L}}_{\mathcal{N}_{\mathcal{L}}} \circ \tilde{f}^{{\mathcal{N}}_{\mathcal{L}}}_{\mathcal{L}}}} &= \\ &\! \!\{ (\langle n, a_{1}\dots a_{m}\rangle ,b): \langle n, a_{1}\dots a_{m}\rangle\in Dom_{\mathcal{N}_{\mathcal{L}}}^{Dom_{\mathcal{L}}^{\mathcal{N}_{\mathcal{L}}}} \& b=s_{n}(a_{1},\dots,a_{m}) \} \end{align*} $$
which is easily seen to be
$\Delta ^{\mathrm {in}}_{\omega +1}$
definable in
$\mathcal {N}_{\mathcal {L}}$
. We have thus shown that the interpretations
${\mathcal {L}}^{\mathcal {N}_{\mathcal {L}}}$
and
$(\mathcal {N}_{\mathcal {L}})^{{\mathcal {L}}}$
satisfy all the conditions of Item 2 in Corollary 15. Hence, we obtain Theorem 19 and can close by finishing the proof of Theorem 2.
Proof of Theorem 2
First, recall that by Theorem 8 no model of
$\mathrm {PA}$
except the standard model has Scott rank
$n<\omega $
. By Theorem 7 non-standard prime models have Scott rank
$\omega $
and thus
$\omega $
is the least element of the Scott spectrum of any completion of
$\mathrm {PA}$
that is not true arithmetic. Similarly, for true arithmetic, by Theorem 9 the only element of the Scott spectrum below
$\omega +1$
is
$1$
.
To obtain models of Scott rank
$\alpha $
for
$\alpha>\omega $
we use Theorem 19 that says that for every completion T of
$\mathrm {PA}$
and every linear order
${\mathcal {L}}$
there is a model
$\mathcal {N}_{\mathcal {L}}$
of T such that
${\mathcal {L}}$
is
$\Delta ^{\mathrm {in}}_{1}$
bi-interpretable with
${\mathcal {N}_{\mathcal {L}}}_{(\omega )}$
. Hence,
$SR({\mathcal {N}_{\mathcal {L}}}_{(\omega )})=SR({\mathcal {L}})$
and thus, by Corollary 18,
$SR(\mathcal {N}_{\mathcal {L}})=\omega +SR({\mathcal {L}})$
. It remains to show that there are linear orderings of every Scott rank. This follows from Ash’s characterization of the back-and-forth relations [Reference Ash5]:
$SR(\omega ^\alpha )=2\alpha $
,
$SR(\omega ^\alpha \cdot 2)=2\alpha +1$
. For detailed calculations, see [Reference Alvir and Rossegger2, Proposition 19]. To obtain a linear ordering of Scott rank
$1$
one can either consider finite linear orderings or
$\eta $
, the order type of the rationals. Both are uniformly
$\Delta ^{\mathrm {in}}_{1}$
categorical.
5 Questions
While Theorem 2 completely characterizes the possible Scott ranks of models of Peano arithmetic, there are possibilities to push this research further. One question which we alluded to at the end of Section 2 concerns homogeneous models.
Question 1. Is there a non-atomic homogeneous model
$\mathcal {M}$
of Peano arithmetic with
$SR(\mathcal {M})=\omega $
?
The Scott rank is a robust measure of complexity but a structure having parameterless Scott rank
$\alpha $
for
$\alpha $
a success ordinal only tells us that it has a
$\Pi ^{\mathrm {in}}_{\alpha +1}$
Scott sentence and no Scott sentence of complexity
$\Pi ^{\mathrm {in}}_{\alpha }$
. It is possible that it has Scott rank
$\alpha $
and, for example, a
$\Sigma ^{\mathrm {in}}_{\alpha }$
Scott sentence. Thus, one could ask what is the minimal complexity of a structure’s Scott sentence, its Scott sentence complexity. The formal study of this notion was recently initiated by Alvir, Greenberg, Harrison-Trainor, and Turetsky [Reference Alvir, Greenberg, Harrison-Trainor and Turetsky1].
Question 2. Which Scott sentence complexities can be realized by models of Peano arithmetic?
Our results in this article show that no Scott sentence complexities below
$\Pi ^{\mathrm {in}}_{\omega }$
can be realized by non-standard models of
$\mathrm {PA}$
and that for every successor ordinal
$\alpha>\omega $
, there is a model of
$\mathrm {PA}$
with Scott sentence complexity
$\Pi ^{\mathrm {in}}_{\alpha +1}$
. A thorough study of our reduction from linear orderings to models of
$\mathrm {PA}$
should yield an answer to the above question, once one understands the possible Scott sentence complexities of linear orderings. In recent work, Gonzalez and Rossegger [Reference Gonzalez and Rossegger10] obtained a partial characterization of the possible Scott sentence complexities in that class.
If the parameterless Scott rank of a structure is a limit ordinal
$\lambda $
, then it can either have Scott sentence complexity
$\Pi ^{\mathrm {in}}_{\lambda }$
or
$\Pi ^{\mathrm {in}}_{\lambda +1}$
. For
$\lambda =\omega $
the only models that could potentially have either of these two complexities are homogeneous models by Lemma 6. What about the atomic models?
Question 3. Let
$\mathcal {M}$
be an atomic model of Peano arithmetic. Does
$\mathcal {M}$
have a
$\Pi ^{\mathrm {in}}_{\omega }$
Scott sentence?
Funding
The first author was supported by NSF grant DMS-1363310. The work of the second author was supported by the European Union’s Horizon 2020 Research and Innovation Programme under the Marie Skłodowska-Curie grant agreement No. 101026834—ACOSE.
