# The structural complexity of models of arithmetic

Antonio Montalbán  Department of Mathematics, University of California,
Berkeley<EMAIL_ADDRESS>and  Dino Rossegger  Department of
Mathematics, University of California, Berkeley and Institute of Discrete
Mathematics and Geometry, Technische Universität Wien<EMAIL_ADDRESS>
###### 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 $\omega$ and
that non-standard models of true arithmetic must have Scott rank greater than
$\omega$. Other than that there are no restrictions. By giving a reduction via
$\Delta^{\mathrm{in}}_{1}$ bi-interpretability from the class of linear
orderings to the canonical structural $\omega$-jump of models of an arbitrary
completion $T$ of $\mathrm{PA}$ we show that every countable ordinal
$\alpha>\omega$ is realized as the Scott rank of a model of $T$.

###### 1991 Mathematics Subject Classification:

03E15, 03C62, 03H15

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

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 [16] 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 [18] on the Lopez-Escobar theorem [10] one gets a
connection with descriptive set theory. Vaught showed that the sets of models
of $\Pi^{\mathrm{in}}_{\alpha}$ formulas are precisely the
$\boldsymbol{\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 structures 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
$\boldsymbol{\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 [2]
that a structure is uniformly $\boldsymbol{\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
[12] 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 ([12]).

The following are equivalent for countable $\mathcal{A}$ and
$\alpha<\omega_{1}$.

  1. (1)

Every automorphism orbit of $\mathcal{A}$ is
$\Sigma^{\mathrm{in}}_{\alpha}$-definable without parameters.

  2. (2)

$\mathcal{A}$ has a $\Pi^{\mathrm{in}}_{\alpha+1}$ Scott sentence.

  3. (3)

$\mathcal{A}$ is uniformly $\boldsymbol{\Delta}^{0}_{\alpha}$-categorical.

  4. (4)

The set of presentations of $\mathcal{A}$ is $\boldsymbol{\Pi}^{0}_{\alpha+1}$
in the Borel hierarchy.

  5. (5)

No tuple in $\mathcal{A}$ is $\alpha$-free.

The least $\alpha$ satisfying the above is the _(parameterless) Scott rank_ of
$\mathcal{A}$.

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 back-and-forth relations. Let us define these
formally. Our definitions follow Montalbán’s upcoming book [13] and we refer
to it for a thorough treatment of the back-and-forth relations and other
notions used here.

######  Definition 1.

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.

$(\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})$

For the base case let $(\mathcal{A},\bar{a})\leq_{0}(\mathcal{B},\bar{b})$ if
$\bar{a}$ and $\bar{b}\operatorname{\upharpoonright}|\bar{a}|$ satisfy the
same quantifier-free $\tau_{|\bar{a}|}$-formulas.

Karp [8] 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 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

$\forall(\beta<\alpha)\forall\bar{b}\exists\bar{a}^{\prime}\bar{b}^{\prime}(\bar{a}\bar{b}\leq_{\beta}\bar{a}^{\prime}\bar{b}^{\prime}\land\bar{a}\not\leq_{\alpha}\bar{a}^{\prime}).$

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 [11] defined the
following.

######  Definition 3.

Let $T$ be an $L_{\omega_{1}\omega}$-sentence. The _Scott spectrum_ of $T$ is
the set

$SS(T)=\\{\alpha<\omega_{1}:\alpha\text{ is the Scott rank of a countable
model of T}\\}.$

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. (1)

If $T=Th(\mathbb{N})$, then
$SS(T)=\\{1\\}\cup\\{\alpha<\omega_{1}:\alpha>\omega\\}$.

  2. (2)

If $T\neq Th(\mathbb{N})$, then $SS(T)=\\{\alpha<\omega_{1}:\alpha>\omega\\}$.

Thus, $SS(\mathrm{PA})=\\{1\\}\cup\\{\alpha<\omega_{1}:\alpha\geq\omega\\}$.

In Section 1 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 3 we analyze results by Gaifman [6] 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 2. At last we combine
all of our results to obtain a proof of Theorem 2.

##  1\. 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 [17] for formal
definitions.

Let $Tr_{\Delta^{0}_{1}}$ be the truth predicate for bounded formulas, i.e., a
predicate satisfying for all bounded formulas $\varphi(\overline{x})$

$PA\vdash\forall\overline{x}\
(Tr_{\Delta^{0}_{1}}(\ulcorner\varphi\urcorner,\overline{x})\leftrightarrow\varphi(\overline{x})).$

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:

$\displaystyle\bar{u}\leq^{a}_{0}\bar{v}$
$\displaystyle\Leftrightarrow\forall(x\leq|\bar{u}|)(Tr_{\Delta^{0}_{1}}(x,\bar{u})\to
Tr_{\Delta^{0}_{1}}(x,\bar{v}))$
$\displaystyle\mathllap{\bar{u}\leq_{n+1}^{a}\bar{v}}\Leftrightarrow\forall\bar{x}\exists\bar{y}\Big{(}|\bar{x}|\leq
a\to\bar{v}\bar{x}\leq_{n}^{a}\bar{u}\bar{y}\Big{)}$

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. (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. (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

$\displaystyle\bar{u}\leq_{n+1}^{b}\bar{v}$ $\displaystyle\iff$
$\displaystyle\forall\bar{x}\exists\bar{y}\Big{(}|\bar{x}|\leq
b\to\bar{v}\bar{x}\leq_{n}^{b}\bar{u}\bar{y}\Big{)}$ $\displaystyle\implies$
$\displaystyle\forall\bar{x}\exists\bar{y}\Big{(}|\bar{x}|\leq
a\to\bar{v}\bar{x}\leq_{n}^{b}\bar{u}\bar{y}\Big{)}$ $\displaystyle\implies$
$\displaystyle\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},$

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 by an easy induction on the definition. ∎

######  Proposition 4.

Let $\overline{a},\overline{b}\in M$. Then

$\overline{a}\leq_{n}\overline{b}\Leftrightarrow(\forall
m\in\omega)\mathcal{M}\models\overline{a}\leq_{n}^{\dot{m}}\overline{b}.$

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 $\forall_{2n}$ first-order 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. ∎

###  1.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\varphi(x,y_{1},\dots,y_{n})$, a model $\mathcal{M}$ and
$a_{1},\dots,a_{n}\in M$ recall that a Skolem term
$s_{\varphi}(a_{1},\dots,a_{n})$ is the least element $b\in M$ satisfying
$\varphi(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_{\varphi}$. Consider the
subset

$N=\\{m_{\varphi}:\varphi\text{ an }L\text{-formula}\\}.$

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},...,y_{k}),\varphi_{1}(x),...,\varphi_{k}(x)$, we have
that $T$ decides whether $\psi(m_{\varphi_{1}},...,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 $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$,

$\mathcal{M}\models\exists\bar{x}_{0},\bar{x}_{1}\
\bar{x}_{0}\neq\bar{x}_{1}\land\bar{x}_{0}\leq_{n}^{\dot{m}}\bar{x}_{1}$

and by elementarity $\mathcal{N}\models\exists\bar{x}_{0},\bar{x}_{1}\
\bar{x}_{0}\neq\bar{x}_{1}\land\bar{x}_{0}\leq_{n}^{\dot{m}}\bar{x}_{1}$.
Consider the set

$X_{n}=\\{b\in\mathcal{N}:\mathcal{N}\models\exists\bar{x}_{0}\bar{x}_{1}\
\bar{x}_{0}\neq\bar{x}_{1}\ \land\bar{x}_{0}\leq_{n}^{b}\bar{x}_{1}\\}$

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$. We then have that every automorphism orbit of
$\mathcal{M}$ is $\Sigma^{\mathrm{in}}_{n}$ definable, and therefore whenever
we have $\bar{u}\leq_{n}\bar{a}$, we have 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

$X_{{\bar{a}}}=\\{c\in
M:\mathcal{M}\models\forall\bar{u}(\bar{u}\leq_{n}^{c}\bar{a}\to\bar{a}=\bar{u})\\}.$

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}^{\prime}(\forall
x(\bar{a}\leq_{1}^{x}\bar{a}^{\prime})\leftrightarrow\forall
x(\bar{a}\leq_{n}^{x}\bar{a}^{\prime}))$. 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}^{\prime}\bar{b}^{\prime}\exists
x\left(\bar{a}\bar{b}\leq_{0}^{x}\bar{a}^{\prime}\bar{b}^{\prime}\to\forall
y(\bar{a}\leq_{1}^{y}\bar{a}^{\prime})\right)$. Combining these two
observations we get that $\mathbb{N}$ satisfies the following form of non-
freeness:

(1)
$\forall\bar{a}\exists\bar{b}\forall\bar{a}^{\prime}\bar{b}^{\prime}\exists
x\left(\bar{a}\bar{b}\leq_{0}^{x}\bar{a}^{\prime}\bar{b}^{\prime}\to\forall
y(\bar{a}\leq_{n}^{y}\bar{a}^{\prime})\right)$

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 [13, 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}^{\prime}\bar{b}^{\prime}(\bar{a}\bar{b}\leq_{0}\bar{a}^{\prime}\bar{b}^{\prime}\land\bar{a}\not\leq_{1}\bar{a}^{\prime})$
and
$(\exists\beta<n)\exists\bar{b}\forall\bar{a}^{\prime}\bar{b}^{\prime}(\bar{a}\bar{b}\leq_{\beta}\bar{a}^{\prime}\bar{b}^{\prime}\to\bar{a}\leq_{n}\bar{a}^{\prime}).$
In particular, by the nestedness of the back-and-forth relations $\mathcal{M}$
does not satisfy
$\exists\bar{b}\forall\bar{a}^{\prime}\bar{b}^{\prime}(\bar{a}\bar{b}\leq_{0}\bar{a}^{\prime}\bar{b}^{\prime}\to\bar{a}\leq_{n}\bar{a}^{\prime})$.
This implies that $\mathcal{M}$ does not satisfy Eq. 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 $\varphi$. Then by elementarity there is
$n\in\omega$ such that $\dot{n}$ satisfies one of the disjuncts of $\varphi$
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$.

######  Question 1.

Is there a non-atomic homogeneous model $\mathcal{M}$ with
$SR(\mathcal{M})=\omega$?

##  2\. 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 [2] that
$SS(\mathrm{LO})=\\{\alpha<\omega_{1}\\}$. Theorem 8 shows that we can not
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 3. Before that we need to discuss infinitary bi-
interpretability and canonical structural $\omega$-jumps.

###  2.1. Reductions via infinitary bi-interpretability

Infinitary bi-interpretability between structures, studied by Harrison-
Trainor, Miller, and Montalbán [7], is a weakening of the model-theoretic
notion of bi-interpretability. Let us recall these notions.

######  Definition 4 ([7]).

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. (1)

$Dom_{\mathcal{A}}^{\mathcal{B}}\subseteq\mathcal{B}^{<\omega}$,

  2. (2)

$\sim$ is an equivalence relation on $Dom^{\mathcal{B}}_{\mathcal{A}}$,

  3. (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:

$f_{\mathcal{A}}^{\mathcal{B}}:\mathcal{A}^{\mathcal{B}}=(Dom_{\mathcal{A}}^{\mathcal{B}},R_{0},R_{1},...){/}{\sim}\cong\mathcal{A}.$

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 ([7]).

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

$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}$

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 [14] 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 ([7]).

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}$.

###  2.2. The canonical structural $\alpha$-jump

The canonical structural $\alpha$-jump is an extension of the ideas developed
by Montalbán [15], see [14] 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

$\bar{b}\in
R_{i}^{\mathcal{A}_{(\alpha)}}\iff\bar{a}_{i}\leq_{\alpha}\bar{b}.$

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 $\varphi$ be a
$\Sigma^{\mathrm{in}}_{\alpha+1}$ $\tau$-formula. Then there is a
$\Sigma^{\mathrm{in}}_{1}$ $\tau_{(\alpha)}$-formula $\psi$ such that

$\mathcal{A}_{(\alpha)}\models\forall\bar{x}\
(\varphi(\bar{x})\leftrightarrow\psi(\bar{x})).$

###### 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 $\varphi$ let
$I_{\varphi}=\\{i:\mathcal{A}\models\varphi(\bar{a}_{i})\\}$. We claim that
$\psi=\mathop{\mathchoice{\bigvee\mkern-15.0mu\bigvee}{\bigvee\mkern-12.5mu\bigvee}{\bigvee\mkern-12.5mu\bigvee}{\bigvee\mkern-11.0mu\bigvee}}_{i\in
I_{\varphi}}R_{i}$ is as required.

The proof of the claim follows easily from the definition of $\psi$. Suppose
first that $\mathcal{A}\models\varphi(\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 $\varphi$ such that

$\mathcal{A}\models\exists\bar{x}\varphi(\bar{x})\land\forall\bar{x}\left(\varphi(\bar{x})\to\mathop{\mathchoice{\bigwedge\mkern-15.0mu\bigwedge}{\bigwedge\mkern-12.5mu\bigwedge}{\bigwedge\mkern-12.5mu\bigwedge}{\bigwedge\mkern-11.0mu\bigwedge}}_{\gamma\in\Gamma}\gamma(\bar{x})\right).$

A proof of the following fact appeared in [13].

######  Proposition 12 ([13, 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 $\varphi$ 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\varphi(\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 $\varphi$ 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}$

$\mathcal{A}\models\psi(\bar{a})\iff\mathcal{A}_{(\alpha)}\models\varphi(\bar{a}).$

###### Proof.

To obtain $\psi$ from $\varphi$ simply replace each occurence 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\varphi(\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 3.

######  Corollary 15.

For all countable ordinals $\alpha$ and $\beta$, the following are equivalent.

  1. (1)

$\mathcal{A}_{(\gamma)}$ is $\Delta^{\mathrm{in}}_{1}$ bi-interpretable with
$\mathcal{B}_{(\alpha)}$.

  2. (2)

$\mathcal{A}$ is infinitary bi-interpretable with $\mathcal{B}$ such that

    1. (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}$,

    2. (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}$,

    3. (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}$,

    4. (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 2b 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$

$\forall\bar{b}\exists\bar{a}^{\prime}\bar{b}^{\prime}\left(\bar{a}\bar{b}\leq_{\alpha+\gamma}\bar{a}^{\prime}\bar{b}^{\prime}\land\bar{a}\not\leq_{\alpha+\beta}\bar{a}^{\prime}\right)$

and hence by Proposition 17,

$(\forall\gamma<\beta)\forall\bar{b}\bar{b}\exists\bar{a}^{\prime}\bar{b}^{\prime}\left((\mathcal{A}_{(\alpha)},\bar{a}\bar{b})\leq_{\gamma}(\mathcal{A}_{(\alpha)},\bar{a}^{\prime}\bar{b}^{\prime})\land(\mathcal{A}_{(\alpha)},\bar{a})\not\leq_{\beta}(\mathcal{A}_{(\alpha)},\bar{a}^{\prime})\right).$

So, $\bar{a}$ is $\beta$-free in $\mathcal{A}_{(\alpha)}$. That $\bar{a}$
being $\beta$-free in $\mathcal{A}_{(\alpha)}$ implies that $\bar{b}$ is
$(\alpha+\beta)$-free in $\mathcal{A}$ follows from the nestedness of the
back-and-forth relations. That is, 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 the following from Item 5 in
Theorem 1.

######  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$.

##  3\. 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 [6]. The
following result is a special case of one of his results, see [9, Section 3.3]
for more details.

######  Theorem 20 (cf. [6]).

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 [5] 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}}$.

###  3.1. Gaifman’s $\mathcal{L}$-canonical extension

This section follows Gaifman’s construction. We will outline his proof and
refer the reader to [9, 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. (1)

_unbounded_ : $(t<x)\in p(x)$ for every Skolem constant, and

  2. (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 [9, 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 $\varphi(u,v)$, there is a
formula $\sigma_{\varphi}(u)$ such that for all Skolem constants,
$\varphi(t,v)\in p(x)\Leftrightarrow T\vdash\sigma_{\varphi}(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 [9, 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$ [9, 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 $\varphi(x,y)\in r(x,y)$ if and
only if $\exists x\varphi(x,y)\in q(y)$ and $\sigma_{\varphi}(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 less than $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 so obtained
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}}$.

###  3.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\varphi^{j}_{i}(\bar{a}_{1},\dots,\bar{a}_{j})\\}$
where $\varphi_{i}^{j}$ is the $i$th 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 the generators under the equivalence $\sim$ given by

$s_{m}(\bar{x})\sim
s_{n}(\bar{x}^{\prime})\iff\left(\prod_{i<|\bar{x}|+|\bar{x}^{\prime}|}p(\lambda(\bar{x}^{\smallfrown}\bar{x}^{\prime})_{i})\right)\models
s_{m}(\bar{x})=s_{n}(\bar{x}^{\prime}).$

For any first order formula $\varphi$ and elements
$s_{1}(\bar{x}_{1}),\dots,s_{m}(\bar{x}_{m})$ in $\mathcal{N}_{\mathcal{L}}$
we have that

$\mathcal{N}_{\mathcal{L}}\models\varphi(s_{1}(\bar{x}_{1}),\dots,s_{m}(\bar{x}_{m}))\\\
\iff\left(\prod_{i<|\bar{x}_{1}|+\dots+|\bar{x}_{m}|}p(\lambda({\bar{x}_{1}}^{\smallfrown}\dots{}^{\smallfrown}\bar{x}_{m})_{i})\right)\models\varphi(s_{1}(\bar{x}_{1}),\dots,s_{m}(\bar{x}_{m})).$

We will interpret this canonical presentation of $\mathcal{N}_{\mathcal{L}}$
in $\mathcal{L}$ using relations in
$\omega\times\mathcal{N}_{\mathcal{L}}^{<\omega}$.111We 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^{\prime}\subseteq\mathcal{N}_{\mathcal{L}}^{<\omega}$
and vice versa by letting $R^{\prime}=\\{\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 [3], and, independently, Chisholm [4]. A proof
for the version that we are using can be found in [14].

######  Lemma 21.

[[14], cf. [3, 4]] 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. (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. (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}$,
$\\{\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})=\prod_{i<n}p(x_{i})$
and the elements satisfying this type is 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 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

$y\in
tp(a)\Leftrightarrow\mathop{\mathchoice{\bigvee\mkern-15.0mu\bigvee}{\bigvee\mkern-12.5mu\bigvee}{\bigvee\mkern-12.5mu\bigvee}{\bigvee\mkern-11.0mu\bigvee}}_{i\in\omega}\exists
x_{1},\dots,x_{m(i)}\ y=s_{i}(x_{1},\dots,x_{m(i)})$

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 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\in 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}$.

###  3.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})$ [9, 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 [9,
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$ [9, 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)$ can not 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,
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
$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)\\}$ and

$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}}}}\mathbin{\&}b=s_{n}(a_{1},\dots,a_{m})\\}$

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 [2]:
$SR(\omega^{\alpha})=2\alpha$, $SR(\omega^{\alpha}\cdot 2)=2\alpha+1$. For
detailed calculations see [1, 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. ∎

## References

  * [1] Rachael Alvir and Dino Rossegger  “The Complexity of Scott Sentences of Scattered Linear Orders”  In _The Journal of Symbolic Logic_ 85.3 Cambridge University Press, 2020, pp. 1079–1101  arXiv:1810.11423
  * [2] C.. Ash  “Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees”  In _Transactions of the American Mathematical Society_ 298.2, 1986, pp. 497–514
  * [3] Chris Ash, Julia Knight, Mark Manasse and Theodore Slaman  “Generic Copies of Countable Structures”  In _Annals of Pure and Applied Logic_ 42.3, 1989, pp. 195–205  DOI: 10.1016/0168-0072(89)90015-8
  * [4] John Chisholm  “Effective Model Theory vs. Recursive Model Theory”  In _The Journal of Symbolic Logic_ 55.03, 1990, pp. 1168–1191  DOI: 10.2307/2274481
  * [5] Samuel Coskey and Roman Kossak  “The Complexity of Classification Problems for Models of Arithmetic”  In _Bulletin of Symbolic Logic_ 16.3 Cambridge University Press, 2010, pp. 345–358
  * [6] Haim Gaifman  “Models and Types of Peano’s Arithmetic”  In _Annals of Mathematical Logic_ 9.3 North-Holland, 1976, pp. 223–306
  * [7] Matthew Harrison-Trainor, Russell Miller and Antonio Montalbán  “Borel Functors and Infinitary Interpretations”  In _The Journal of Symbolic Logic_ 83.4 Cambridge University Press, 2018, pp. 1434–1456
  * [8] Carol R. Karp  “Finite-Quantifier Equivalence”  In _The Theory of Models_ North-Holland, Amsterdam, 1965, pp. 407–412
  * [9] Roman Kossak and James Schmerl  “The Structure of Models of Peano Arithmetic”  Oxford University Press on Demand, 2006
  * [10] E… Lopez-Escobar  “An Interpolation Theorem for Denumerably Long Formulas”  In _Journal of Symbolic Logic_ 34.2, 1969
  * [11] Michael Makkai  “An Example Concerning Scott Heights”  In _The Journal of Symbolic Logic_ 46.2 Cambridge University Press, 1981, pp. 301–318
  * [12] Antonio Montalbán  “A Robuster Scott Rank”  In _Proceedings of the American Mathematical Society_ 143.12, 2015, pp. 5427–5436  URL: http://www.ams.org/journals/proc/0000-000-00/S0002-9939-2015-12669-X
  * [13] Antonio Montalbán  “Computable Structure Theory: Beyond the Arithmetic”  draft, 2021  URL: https://math.berkeley.edu/~antonio/CSTpart2_DRAFT.pdf
  * [14] Antonio Montalbán  “Computable Structure Theory: Within the Arithmetic”, Perspectives in Logic  Cambridge: Cambridge University Press, 2021  DOI: 10.1017/9781108525749
  * [15] Antonio Montalbán  “Notes on the Jump of a Structure”  In _Conference on Computability in Europe_ Springer, 2009, pp. 372–378
  * [16] Dana Scott  “Logic with Denumerably Long Formulas and Finite Strings of Quantifiers”  In _The Theory of Models_ Elsevier, 1963, pp. 329–341
  * [17] Stephen G. Simpson  “Subsystems of Second Order Arithmetic”  Cambridge University Press, 2009
  * [18] Robert Vaught  “Invariant Sets in Topology and Logic”  In _Fund. Math_ 82.269-294, 1974, pp. 75


# ChemVise: Maximizing Out-of-Distribution Chemical Detection with the Novel
Application of Zero-Shot Learning

Alexander M. Moore  Randy C. Paffenroth  Ken T. Ngo  Joshua R. Uzarski

###### Abstract

Accurate chemical sensors are vital in medical, military, and home safety
applications. Training machine learning models to be accurate on real world
chemical sensor data requires performing many diverse, costly experiments in
controlled laboratory settings to create a data set. In practice even
expensive, large data sets may be insufficient for generalization of a trained
model to a real-world testing distribution. Rather than perform greater
numbers of experiments requiring exhaustive mixtures of chemical analytes,
this research proposes learning approximations of complex exposures from
training sets of simple ones by using single-analyte exposure signals as
building blocks of a multiple-analyte space. We demonstrate this approach to
synthetic sensor responses surprisingly improves the detection of out-of-
distribution obscured chemical analytes. Further, we pair these synthetic
signals to targets in an information-dense representation space utilizing a
large corpus of chemistry knowledge. Through utilization of a semantically
meaningful analyte representation spaces along with synthetic targets we
achieve rapid analyte classification in the presence of obscurants without
corresponding obscured-analyte training data. Transfer learning for supervised
learning with molecular representations makes assumptions about the input
data. Instead, we borrow from the natural language and natural image
processing literature for a novel approach to chemical sensor signal
classification using molecular semantics for arbitrary chemical sensor
hardware designs.

##  1 Introduction

Figure 1: ChemVise utilizes activations from a pretrained supervised molecular
property model to represent analytes of interest with geometric
interpretation. The utilization of arithmetic means between points in analyte
space creates improved, tunable decision boundaries for chemical sensor
classifiers. We find that semantic chemistry representations outperforms non-
chemical embeddings and leads to greater discriminability of obscured chemical
analytes.

Classifying chemical vapors is vital to military, industrial, and safety
applications. Hazardous chemical detection becomes challenging in the presence
of obscurants and environmental factors as sensor responses change. This paper
addresses the generalizability of data mining applied to challenging chemical
vapor mixtures with novel deep learning approaches. We take inspiration from
embedding-translation models in calling our approach “ChemVise”, a portmanteau
of the constituent Chemception [10] molecular attribute prediction model and
DeViSE [8] visual-semantic embeddings. Rather than natural image and sentence
semantics, we utilize deep representations of SMILES molecular images paired
with chemiresistive sensor signals to learn improved representations for
downstream predictors (Figure 1). Improved chemical representations for
chemical sensing allows even challenging double-analyte samples to be encoded
such that they are linearly separable with simple classifiers. We find our
approach significantly outperforms competitive models for the detection of
obscured chemical analytes with only unobscured analytes as training data.

In the domain of chemical sensing, gathering data sufficient for complex
chemical detection tasks is highly laborious and expensive [31, 18]. The
ability to import significant domain knowledge in the form of transfer
learning is vital to the rapid development of diverse and accurate sensors.
Promising results in chemistry-applied deep learning indicate that well-tuned
models shorten the development cycle of new tools and in some cases can
replace repetitive laboratory experiments [27].

(a)

(b)

Figure 2: Visualization of the shortcomings of linear decomposition with
linear classifiers for mixture data. Left: Under a 2-dimensional PCA
transformation, signal data of single-analyte exposures may be well-separated
by a linear classifier. Right: Under a PCA embedding of signal data, the same
model fails to accurately discriminate between samples containing Analyte A.
Samples marked with x contain Analyte A and are intermixed with non-Analyte A
single-analyte exposures, leading to poor classification results from this
linear classifier.

For our chemiresistive sensor signal classification task, an example machine
learning approach to the discrimination of chemical Analyte A from chemical
Analytes B, C, and D succeeds when one analyte is present at a time (Figure
2a). For the more complex detection test of obscured signals given by analyte
mixtures, this approach performs poorly (Figure 2b). The ability to
discriminate Analyte A signals from other analyte exposures even when obscured
by a secondary analyte is a vital task for chemical sensors, and one which
demands changes to standard data mining practice.

In order to classify more challenging analyte mixtures which do not appear in
the training set, we borrow from zero-shot, transfer, and multi-modal learning
approaches in deep natural image and language learning [13, 8, 20]. We
contribute the following to the challenging task of obscured analyte detection
for one chemical detection paradigm, with generalizations available for any
sensing hardware design:

  1. 1.

We introduce the novel ChemVise approach which modifies transfer learning to
utilize chemistry domain knowledge for any chemiresistive sensor data (Section
4).

  2. 2.

We apply linear interpolation between single analyte exposures for analyte
mixture representations to improve the detection of obscured analytes (Section
5). The utilization of linear interpolation for chemistry representations as
well as sensor response approximations to mixture data is yet unexplored in
the literature.

  3. 3.

We demonstrate that transfer learning of ChemVise outperforms other machine
and deep learning approaches to chemical sensing as well as alternative non
molecular-semantic representations (Section 6).

  4. 4.

We provide an outline for the generalization of this approach to arbitrary
sensing hardware. Whereas most transfer learning techniques would be domain
specific, this approach can adapt the training of the deep encoder for
arbitrary input data to the same latent representation space (Section 7).

Figure 3: The corresponding number of experimental trials to be performed
given four analytes (A, B, C, D) at four possible exposure magnitudes (12.5%,
15%, 20%, 25%).

The data considered here are drawn from two types. Single-analyte exposures
are created by exposing one chemical analyte of a given concentration to the
multi-array sensor comprising eight polymer and graphene nanoplatelet
composites for a defined time period. For this work we trim chemical sensing
trials (Figure 5) to exposure windows from 2.4 to 4.0 seconds which includes
the moment the chemical analyte first meets the sensor array (Figure 4). The
second, more challenging data are the double-analyte exposures: a two-analyte
mixture is exposed to the sensor array for a time period. Mixtures containing
Analyte A are labelled the positive class for classification. These double-
analyte exposures are substantially more difficult to classify as the desired
information (the presence of Analyte A) is obscured by an additional analyte
which alters the sensor response profiles (Figures 4, 8).

In addition to being harder to classify, mixture data are substantially harder
to exhaustively gather. The experimental cost of datasets even with limited
numbers of analytes and concentrations quickly becomes intractable as trials
require expert supervision, experimental design, hardware setup, and data
verification processes. Given a number of chemical analytes of interest
$x_{1},...,x_{n}$ at various concentrations $c_{1},...,c_{k}$, the number of
experiments necessary to perform experimentation of all mixtures at all
concentrations is given by

$\sum_{p=1}^{n}\binom{n}{p}k^{p}$ (1)

where $p$ represents the number of analytes in the mixture. Figure 3
visualizes the complexity of gathering representative data sets for even a
limited number of analytes and concentrations: in this case, simultaneous
exposure of one, two, three, or four chemical analytes each at one of four
potential vapor concentrations. By utilizing single-analyte exposures
canonical dimensions of multi-analyte mixture space and incorporating external
chemistry knowledge, supervised learning outcomes are improved and constraints
to experimental hardware, budget, and time limit may be mitigated.

(a)  (b)

Figure 4: Two example single-analyte exposures. Left: A 5-second window
including the moment a mixture of 12.5% Analyte A is exposed to the array of
eight sensors. Right: A 5-second window including the moment a mixture of
12.5% Analyte B is exposed to the array of eight sensors. Machine learning
classifiers use discrepancies in sensor resistances responses to discriminate
between analytes.

##  2 Relevant Work.

Partially due to the meteoric rise of deep learning approaches for natural
image and natural language processing, many practitioners are more intensely
researching the application of machine and deep learning to applied chemistry
which was originally met with skepticism by chemists practicing hand-coded
heuristics such as the Morgan Fingerprint [14, 16]. Researchers have seen
rising application of machine learning to the physical sciences, with “many
demonstrating significant improvements in predictive accuracy and ability to
replicate human decision making” [14, 3]. For an excellent review of deep
learning applications to chemistry and the reception history of chemical
applications, please refer to [14] as well as [25] for an excellent survey of
surface chemistry. For an introduction to machine learning and its
applications for chemists we recommend [17].

A primary concern of computation for applied chemistry is the representation
of chemical analytes in machine-readable format. This topic has been relevant
to chemical researchers for over 160 years - long before even the advent of
electronic computation [6, 32]. In the deep learning field as in chemistry,
representations must serve the purpose of encoding meaningful elements of the
object they represent and for machine and deep learning must be processable
with vector mathematics. The question of representation poses as many
challenges to the encoding of molecules and compounds as it does to images and
written text. No singular representation will be appropriate for every task,
so countless molecular descriptors, embeddings, and encoding techniques have
been proposed.

One such chemical representation is SMILES [28], which encodes molecular
structure to ASCII strings given by depth-first traversal over molecular
bonds. While the SMILES approach does represent molecules in a machine-
readable manner, deep learning researchers have recently relied on the
implicit representation learning that occurs in multi-layer networks as the
source of information density in vector representations [1]. The feedforward
deep neural network outlined in Chemception [10] was trained on a set of
molecular images derived from SMILES strings to predict the toxicity,
activity, and solvation properties of the input. As a consequence of implicit
representation learning in deep neural networks, the penultimate activations
of this model may be used to represent molecular analytes in dense real-valued
vector embeddings. The Chemception embeddings encode semantically meaningful
distances between points which facilitate vector mathematics and downstream
learners for fine-tuned tasks (Figure 6). Chemception and Mol2vec [11] use
modern deep learning practice to outperform the earlier Morgan Fingerprints
representation [16] using pattern recognition on a massive corpus of chemistry
data.

Contemporary research utilizes deep learning for chemistry, and in particular
compound representations for supervised learning such as drug interaction [24,
2], new material discovery [27, 25], and drug design [33, 9, 7, 22]. These
approaches utilize pretrained or novel deep learning embedding models to
encode an unseen set of chemical analytes. The encodings are used as
information-dense representations of training data for an external task
outside of the initial scope of the embedding model. This process is called
fine-tuning or transfer learning in the deep learning literature [29, 35].

Our surveying efforts above report many other techniques utilizing molecular
and compound embeddings for downstream supervised learning. However, to our
knowledge our ChemVise approach (Section 4) utilizing transfer learning
representations as targets to train embedding models for arbitrary input data
remains unexplored in chemical sensing and materials science. Natural image
and natural language researchers [8, 26, 20] have emphasized semantically
meaningful target spaces for supervised and generative deep learning.
Sentence-to-image generation and image-to-sentence captioning are a promising
recent breakthrough which large language transformers have had incredible
recent successes [21]. Multi-modal deep representation learners use paired
encoder-decoder models which operate in the same meaningful embedding space,
and learn to link the two embeddings with a translation model. Rather than
natural image and sentence semantics, however, our ChemVise approach utilizes
deep representations of molecular SMILES images encodings paired with
chemiresistive sensor signals to learn improved latent representations for
downstream predictors (Figure 6).

##  3 Data.

Chemical sensors utilize resistance changes of electrodes with unique
coatings. Different vapor analytes have different adsorption affinities to the
different coatings, resulting in differential resistance changes. Figure 5
visualizes the temporal regions of a full analyte exposure experiment. Analyte
exposure experiments utilizing chemiresistive sensors contain three exposure
periods [19]:

  1. 1.

Controlled flux of analyte and adsorption to the active surface or substrate.

  2. 2.

Change in electrical resistance due to interaction of sensor coating with
adsorbed and/or absorbed analyte molecules.

  3. 3.

Cessation of analyte flux followed by flux of zero gas. Desorption of analyte
from sensors which reverses resistance change.

Figure 5: One experimental sample including baseline, absorption, and
desorption for an exposure of Analyte B. The sensor resistances rapidly
increase during the analyte exposure period as chemical analytes adsorb onto
sensor coatings before returning to baseline levels during desorption as
analytes diffuse from the surface.

In our research, we utilize an 8-sensor chemiresistive array with chemically
diverse polymer and graphene composites to maximize analyte discriminability
as in [18, 31, 30]. The data and results here are one set of experiments
performed with this array, but the deep learning methodology for transferring
analyte representations and supervised classification of multiple analytes may
be extended to any chemical sensor array.

Each of the eight sensors utilizes some baseline resistance of electric
current through the sensor coating. Different adsorption of analytes leads to
the discriminability based on sensor responses seen in the resistances changes
between an exposure to Analyte A and Analyte B in Figure 4. These resistance
responses are preprocessed from the data collection step with only z-scoring.

In addition to single-analyte exposures of one analyte to the sensor array,
multiple analytes may be exposed simultaneously. Here we refer to a two-
analyte mixture exposed to the sensor device as a double-analyte exposure, and
may be a combination of any two analytes with any relative magnitude. In our
binary classification results 6, a mixture containing any amount of Analyte A
is treated as a positive sample and all other mixture pairs are treated as
negative samples.

##  4 ChemVise Method.

Our proposed ChemVise 111Further detail on the implementation and training of
ChemVise along with a PyTorch-style pseudocode is available in the extended
materials section. approach to chemical sensing borrows from the deep learning
literature on zero-shot learning [13], transfer learning [29], and domain
transfer [21] to utilize a transformed target space given by an expert model
(Figure 1). DeVise [8] used a pretrained skip-gram language embedding model
and a pretrained deep convolutional neural network to embed images and their
text labels as high-dimensional real-valued vectors in two distinct
representation spaces. A translation model is then trained to map between an
image-representation space to a label-representation space, thereby linking
the spaces and allowing zero-shot semantic prediction of input images.

Figure 6: Embeddings of four analytes of interest as well as six comparison
analytes and compounds. The penultimate activations of the Chemception model
are used as embeddings and reduced to two dimensions with PCA for inspection.
Chemception provides representations of analytes used as targets for the
ChemVise embedder.

There exist many pretrained deep representation models trained on large
chemistry corpi mentioned in Section 2. In this work we utilize penultimate
activations of the pretrained Chemception [10] supervised model which was
trained to predict toxicity, activity, and solvation of a large dataset of
chemicals. The inherent representation learning of deep neural networks
provides representations of analytes we use to create a more meaningful target
space for the ChemVise embedding model which trained from scratch for our
novel chemical sensing hardware.

ChemVise uses targets represented by embeddings rather than traditional labels
for a chemiresistive sensor signal input. Using representations of analytes as
a target rather than typical one-hot classification or multiple regression
targets leads to improved decision boundaries and signal representations and
can be adapted to arbitrary sensing hardware. Figure 6 shows 2D visualizations
of embeddings of analytes given by Chemception [10] encodings of analytes
represented as images of SMILES strings match our intuition about similarity
of analytes in a high-dimensional space. Representation spaces replace the
label space as the target for a high-dimensional output.

A deep fully-connected neural network is trained to map from the input data
space of sensor signals to this molecular-semantics representation space. Any
supervised learning algorithm with a multidimensional real-valued output may
be used. The ChemVise process provides a trained embedder which encodes any
sensor response input in the information-dense space with improved
separability between classes. Subsequently any classifier can be used in the
chemistry space for improved classification outcomes (Figure 7) compared to
non-embedded samples (Figure 2).

(a)  (b)

Figure 7: This visualization shows the validation singles and testing doubles
(black) embedded by the ChemVise model then classified with a linear SVC. This
image is for visual illustration only as ChemVise utilizes a 512-dimensional
representation space, which is more accurate than the same model under a
2-dimensional PCA decomposition. Left: ChemVise embeddings given training the
deep learning model to map signal samples to their corresponding target given
by the matching color “+”. The tunable decision boundary linearly separates
the positive and negative samples. Right: Double-analyte samples under this
trained embedding model fall in line with the correct classification given by
the SVC trained with only single-analytes. This embedding outperforms simple
decomposition embeddings by incorporating molecular semantics into the
embedded representations, and allows even double-analyte samples to be
linearly separated.

Each point of an analyte representation space encodes a similarity and
dissimilarity to other molecule and compound points. ChemVise must provide a
faithful embedding to the properties of chemical compounds as well as multi-
analyte mixture signals. For this reason we implement linear interpolation
between single-analyte exposures with synthetic targets given by the geodesic
center of the two canonical elements.

PyTorch-style pseudocode for the implementation of ChemVise is provided. Since
the implementation of the sensor hardware and capture devices may change, this
algorithm paired with any pretrained chemical representation model for analyte
targets is compatible with arbitrary input signals.

##  5 Linear Combinations of Chemiresistive Signals.

(a)  (b)

Figure 8: Left: Sensor experiment exposing eight chemiresistive sensors with
unique polymer and graphene coatings to a mixture of 12.5% Analyte A and 12.5%
Analyte B. Right: The summation of 12.5% Analyte A and Analyte B signals
approximates the simultaneous double-analyte exposure to Analyte A and Analyte
B. The synthesized double-analyte target in the analyte representation space
is taken to be the weighted sum of the two single-analyte representation
vectors according to the linear combination weight (Section 5)

We utilize linear combinations of single-analyte exposures as approximations
to multi-analyte signals which are harder to gather. Linear combinations are
sometimes utilized in natural image data augmentation designed to promote
simple linear behavior in-between training examples for deep neural networks
[34]. The data-agnostic linear combination augmentation synthesizes samples
given by linear interpolations between random examples and their training
labels:

$\bar{x}=\lambda x_{i}+(1-\lambda)x_{j}\\\ \bar{y}=\lambda
y_{i}+(1-\lambda)y_{j}$

Where $y_{i},y_{j}$ are analyte exposure embedding vectors corresponding to
sensor response vectors $x_{i},x_{j}$.

Linear combinations as applied to chemical sensing approximates real double-
analyte chemical sensor exposures using only single-analyte exposures as
training data. We modify the typical probability density function from a Beta
distribution for ImageNet optimization [34, 12] to a tunable uniform
distribution between $a$ and $b$. The maximum and minimum of the distribution
may be tuned to account for what level of mixture sensitivity should be
classified as a positive sample. Here, we utilize $(a,b)=(0.3,0.7)$ as the
bounds for mixtures. Otherwise, utilization remains the same as in the natural
image paradigm wherein samples are linearly interpolated during training using
linear combinations of training pairs.

##  6 Results.

We provide results for a training paradigm given by training on single-analyte
exposures and testing on challenging out-of-distribution obscured double-
analyte exposures. We demonstrate the importance of representation selection
(Section 6.1) as well as optimized models for the rapid detection of obscured
Analyte A given variable-length exposure windows (Section 6.2). Results within
follow a consistent algorithm (K-fold validation hyperparameter gridsearch)
for the selection of hyperparameters prior to observation of the holdout
testing data using the following from [15]:

  1. 1.

ChemVise

     * •

Model width: 128, 512, 1024, 2048, 4096, 8192

     * •

Learning rate: 1e-7, 5e-7, 1e-6, 5e-6, 1e-5

     * •

Training epochs: 1000, 2000, 4000

     * •

Batch size: 4, 8, 16, 32

  2. 2.

Feedforward Neural Networks [23]

     * •

Model width: 128, 512, 1024, 2048, 4096, 8192

     * •

Learning rate: 1e-7, 5e-7, 1e-6, 5e-6, 1e-5

     * •

Training epochs: 1000, 2000, 4000

     * •

Batch size: 4, 8, 16, 32

  3. 3.

Baseline models:

    1. (a)

Support Vector Machine [5]

       * •

“C” Penalty: uniform(1e-4, 8e-3)

       * •

Kernel: “Linear”

       * •

Kernel Degree: random(0, 8)

       * •

Class Weight (Negative:Positive): 1:1, 1:2, 1:4

    2. (b)

XGBoost222Tree boosting [4]

       * •

Column Ratio: random(1,8)

       * •

Gamma: uniform(0,0.5)

       * •

Learning Rate: uniform(0.03, 0.3)

       * •

Max Depth: random(1,8)

       * •

N Estimators: random(50,800)

###  6.1 Representation Matters.

Figure 9: Classification metric on double-analyte exposures as a function of
embedding model and downstream classifier. Downstream classifiers include a
K-Neighbors classifier in the representation space, or a Support Vector
Classifier in the representation or 2-dimensional projection of the
representation space. The choice of Chemception, one-hot, or equidistant
spherical targets modifies the training of the embedding deep learning model
prior to classification by the classifier head.

Though our design utilizes the pretrained Chemception [10] to represent
analyte SMILES images as meaningful vectors in a target space, in theory any
space could be used to represent analyte labels for embedder training. Here we
compare the Chemception representation space with two alternative analyte
representation spaces to use as targets for the embedding prior to SVC
classification. “One-hot” denotes utilizing 512-dimensional (matching the
Chemception embedding dimension) representations for analytes where signals
containing Analyte $i$ are represented as $e_{i}$, where $e_{i}$ is the zero-
vector with $1$ at index $i$. “Equidistant spherical” denotes utilizing
equidistant points from the 512-dimensional unit hypersphere as
representations for the chemical analytes.

Figure 9 demonstrates the importance of the semantically meaningful space for
the ChemVise embedding. Whereas one-hot and equidistant spherical
representation spaces struggle to provide meaningful representation spaces for
downstream SVC classification, Chemception consistently provides a high-
quality representation space for three candidate classifiers. Semantic meaning
implemented as intra-analyte distances dramatically improves the decision
boundary outcomes over two approaches which do not incorporate external
chemistry knowledge.

###  6.2 Variable Exposure Times.

Figure 10: Matthews Correlation Coefficient score given the prediction of
Analyte A in a holdout set of 39 real double-analyte experiments after
training on only single-analyte exposures. Given five hyperparameter
optimizations over five 5-fold cross validation experiments, model
performances for 7 different exposure window lengths from 2.4 to 4.0 seconds.

In Figure 10 we demonstrate results on the rapid classification of Analyte A
in the presence of obscurant analytes with no corresponding obscured-analyte
training data. Though multiple machine and deep learning approaches show a
positive scaling behavior in the response metric as a function of exposure
time, the ChemVise approach substantially and consistently outperforms the
alternative models for the out-of-distribution detection task.

##  7 Conclusion.

ChemVise representation learning outperformed linear decomposition embeddings
as well as standard machine and deep learning supervised models by
incorporating molecular semantics into the embedded representations. We
demonstrated how improved chemical representations incorporating domain
knowledge on molecular semantics for chemical sensing allow double-analyte
samples to be encoded such that they are linearly separable with simple
classifiers when only single-analyte real experiments are available. This
approach may benefit researchers performing chemical detection with arbitrary
hardware designs, and does not require pretrained models in the input domain.
Rather, chemical classification may utilize sensor data from any sensors
provided a corresponding target domain exists and is sufficiently studied.

Though transfer learning may be appropriate when the input data lies in a
well-studied domain with learnable representations, relying on both transfer
learning and ChemVise-style target adaptation dramatically increases the
number of tasks which may incorporate exterior data corpi. The ChemVise
approach may extend the toolbox of a machine learning engineer performing
supervised learning on a more diverse set of tasks with diverse inputs. The
implementation would retain the deep embedding model and replace the target
space with an appropriate pretrained model capable of representing the targets
of the data set with some meaningful distance encoding. The generalizable
approaches to supervised learning discussed here may dramatically improve
sensor machine learning results and move away from complex, hand-tuned
representations of domain knowledge.

## References

  * [1] Y. Bengio, A. Courville, and P. Vincent.  Representation learning: A review and new perspectives, 2012.
  * [2] C. Cai, P. Guo, Y. Zhou, J. Zhou, Q. Wang, F. Zhang, J. Fang, and F. Cheng.  Deep learning-based prediction of drug-induced cardiotoxicity.  Journal of chemical information and modeling, 59(3):1073–1084, 2019\.
  * [3] H. Chen, O. Engkvist, Y. Wang, M. Olivecrona, and T. Blaschke.  The rise of deep learning in drug discovery.  Drug discovery today, 23(6):1241–1250, 2018.
  * [4] T. Chen and C. Guestrin.  XGBoost.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, aug 2016.
  * [5] C. Cortes and V. Vapnik.  Support-vector networks.  Machine learning, 20(3):273–297, 1995.
  * [6] L. David, A. Thakkar, R. Mercado, and O. Engkvist.  Molecular representations in ai-driven drug discovery: a review and practical guide.  Journal of Cheminformatics, 12(1):56, Sep 2020.
  * [7] D. C. Elton, Z. Boukouvalas, M. D. Fuge, and P. W. Chung.  Deep learning for molecular generation and optimization - a review of the state of the art.  CoRR, abs/1903.04388, 2019.
  * [8] A. Frome, G. S. Corrado, J. Shlens, S. Bengio, J. Dean, M. A. Ranzato, and T. Mikolov.  Devise: A deep visual-semantic embedding model.  In C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
  * [9] N. W. A. Gebauer, M. Gastegger, S. S. P. Hessmann, K.-R. Müller, and K. T. Schütt.  Inverse design of 3d molecular structures with conditional generative neural networks.  Nature Communications, 13(1), feb 2022.
  * [10] G. B. Goh, C. Siegel, A. Vishnu, N. O. Hodas, and N. Baker.  Chemception: A deep neural network with minimal chemistry knowledge matches the performance of expert-developed qsar/qspr models, 2017.
  * [11] S. Jaeger, S. Fulle, and S. Turk.  Mol2vec: Unsupervised machine learning approach with chemical intuition.  ChemRxiv, 2017.
  * [12] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [13] H. Larochelle, D. Erhan, and Y. Bengio.  Zero-data learning of new tasks.  In Zero-data Learning of New Tasks., volume 2, pages 646–651, 01 2008.
  * [14] A. C. Mater and M. L. Coote.  Deep learning in chemistry.  Journal of Chemical Information and Modeling, 59(6):2545–2559, 2019\.
  * [15] A. M. Moore, R. C. Paffenroth, K. T. Ngo, and J. R. Uzarski.  Cycles improve conditional generators: Synthesis and augmentation for data mining.  In Advanced Data Mining and Applications: 18th International Conference, ADMA 2022, Brisbane, QLD, Australia, November 28–30, 2022, Proceedings, Part II, pages 352–364. Springer, 2022.
  * [16] H. L. Morgan.  The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service.  Journal of chemical documentation, 5(2):107–113, 1965.
  * [17] T. Mueller, A. G. Kusne, and R. Ramprasad.  Machine Learning in Materials Science, chapter 4, pages 186–273.  John Wiley and Sons, Ltd, 2016.
  * [18] E. C. Nallon, V. P. Schnee, C. J. Bright, M. P. Polcha, and Q. Li.  Discrimination enhancement with transient feature analysis of a graphene chemical sensor.  Analytical chemistry, 88(2):1401–1406, 2016.
  * [19] R. Nix.  Surface Science (Nix), chapter 1.  Queen Mary, University of London, 2022.
  * [20] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, G. Krueger, and I. Sutskever.  Learning transferable visual models from natural language supervision, 2021.
  * [21] A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen.  Hierarchical text-conditional image generation with clip latents, 2022\.
  * [22] A. S. Rifaioglu, E. Nalbat, V. Atalay, M. J. Martin, R. Cetin-Atalay, and T. Doğan.  Deepscreen: high performance drug–target interaction prediction with convolutional neural networks using 2-d structural compound representations.  Chem. Sci., 11:2531–2557, 2020.
  * [23] D. E. Rumelhart, G. E. Hinton, and R. J. Williams.  Learning representations by back-propagating errors.  nature, 323(6088):533–536, 1986.
  * [24] J. Y. Ryu, H. U. Kim, and S. Y. Lee.  Deep learning improves prediction of drug–drug and drug–food interactions.  Proceedings of the National Academy of Sciences, 115(18):E4304–E4311, 2018.
  * [25] J. Schmidt, M. R. G. Marques, S. Botti, and M. A. L. Marques.  Recent advances and applications of machine learning in solid-state materials science.  npj Computational Materials, 5(1):83, Aug 2019.
  * [26] R. Socher, M. Ganjoo, H. Sridhar, O. Bastani, C. D. Manning, and A. Y. Ng.  Zero-shot learning through cross-modal transfer, 2013.
  * [27] J. Wei, X. Chu, X.-Y. Sun, K. Xu, H.-X. Deng, J. Chen, Z. Wei, and M. Lei.  Machine learning in materials science.  InfoMat, 1(3):338–358, 2019.
  * [28] D. Weininger.  Smiles, a chemical language and information system. 1. introduction to methodology and encoding rules.  J. Chem. Inf. Comput. Sci., 28(1):31–36, feb 1988.
  * [29] K. Weiss, T. M. Khoshgoftaar, and D. Wang.  A survey of transfer learning.  Journal of Big data, 3(1):1–40, 2016.
  * [30] M. Weiss, M. S. Wiederoder, R. C. Paffenroth, E. C. Nallon, C. J. Bright, V. P. Schnee, S. McGraw, M. Polcha, and J. R. Uzarski.  Applications of the kalman filter to chemical sensors for downstream machine learning.  IEEE Sensors Journal, 18(13):5455–5463, 2018.
  * [31] M. S. Wiederoder, E. C. Nallon, M. Weiss, S. K. McGraw, V. P. Schnee, C. J. Bright, M. P. Polcha, R. Paffenroth, and J. R. Uzarski.  Graphene nanoplatelet-polymer chemiresistive sensor arrays for the detection and discrimination of chemical warfare agent simulants.  ACS sensors, 2(11):1669–1678, 2017.
  * [32] W. J. Wiswesser.  107 years of line-formula notations (1861-1968).  Journal of Chemical Documentation, 8(3):146–150, 1968.
  * [33] M. Yang, B. Tao, C. Chen, W. Jia, S. Sun, T. Zhang, and X. Wang.  Machine learning models based on molecular fingerprints and an extreme gradient boosting method lead to the discovery of jak2 inhibitors.  Journal of Chemical Information and Modeling, 59(12):5002–5012, Dec 2019.
  * [34] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz.  mixup: Beyond empirical risk minimization, 2017.
  * [35] F. Zhuang, Z. Qi, K. Duan, D. Xi, Y. Zhu, H. Zhu, H. Xiong, and Q. He.  A comprehensive survey on transfer learning.  Proceedings of the IEEE, 109(1):43–76, 2020.