Proof. We start by proving Item 1. To start suppose that $\varphi $ is finite and quantifier-free and in disjunctive normal form. For a disjunct $\varphi _i$ of $\varphi $ , let $T_{\varphi _i}$ be the formula expressing that $\varphi _i\subseteq l(x)$ and let $T_\varphi =\bigvee T_{\varphi _i}$ . Since formulas with free variable indices exceeding the length of a tuple $\bar a$ are considered to be false in $\mathcal {A}$ and $l(\sigma )\subseteq l(\tau )$ if $\sigma \preceq \tau $ , we have that $\mathcal {A}\models \varphi (\bar a)$ if and only if for every $\sigma \succeq \bar a$ , ${\mathcal {T}}_{\mathcal {A}}\models T_\varphi (\sigma )$ , as required.

Now, say that we have defined $T_\varphi $ given $\varphi $ and that Item 1 holds for $\varphi (x)$ . Define

where $\varphi [x/x_i]$ denotes $\varphi $ with all free occurrences of x replaced by $x_i$ . The need for these replacements arises from our coding: We have that $\sigma $ and $\tau $ in ${\mathcal {T}}_{\mathcal {A}}$ can code a witness a for x in different positions, say for example that $\sigma (i)=\tau (k)=a$ for $i\neq k$ . Then $\sigma $ satisfies $T_{\varphi [x/x_i]}$ but $\tau $ does not. To proceed we will need the following claim.

Claim 1.3.1. Suppose that $\varphi $ is a formula where exactly one free variable x is not in the range $x_0,\dots , x_{|a|}$ . Then for all b and $\bar d$ not containing b

$$\begin{align*}{\mathcal{T}}_{\mathcal{A}}\models T_{\varphi{[x/x_{|\bar a|+1}]}}(\bar a^{\smallfrown} b)\iff {\mathcal{T}}_{\mathcal{A}} \models T_{\varphi{[x/x_{|\bar a^{\smallfrown} \bar d|+1}]}}(\bar a^{\smallfrown} \bar d^{\smallfrown} b). \end{align*}$$

We can now proceed with the induction step of Item 1. We have by the claim that for given $\bar a$ and b, ${\mathcal {T}}_{\mathcal {A}}\models T_\varphi (\bar a^{\smallfrown } b)$ if and only if for every $\sigma \succeq \bar a$ , ${\mathcal {T}}_{\mathcal {A}}\models T_{\varphi [x/x_{|\sigma |+1}]} (\sigma ^{\smallfrown } b)$ if $b\not \in \sigma $ and ${\mathcal {T}}_{\mathcal {A}}\models T_{\varphi [x/x_i]}(\sigma )$ if $b=\sigma (i)$ . Thus, we get that $\mathcal {A}\models \exists x\varphi (\bar a)$ if and only if for every $\sigma \succeq \bar a$ , ${\mathcal {T}}_{\mathcal {A}}\models T_{\exists x\varphi }(\sigma )$ . For $T_{\forall x\varphi }$ note that ${\mathcal {T}}_{\mathcal {A}}\models T_{\forall x \varphi }(\bar a)$ if and only if for every $\sigma \succeq \bar a$ and every $i\leq |\sigma |$ , $\mathcal {A}\models \varphi (\bar a,\sigma (i))$ , and, since $\bar a=\sigma \operatorname {\mathrm {\upharpoonright }} |\bar a|$ , in particular $\mathcal {A}\models \varphi (\sigma (0)\dots \sigma (|\bar a|),\sigma (i))$ . Thus, $\mathcal {A}\models \forall x \varphi (\bar a)$ if and only if ${\mathcal {T}}_{\mathcal {A}}\models T_{\forall x \varphi }$ . We can extend our definitions to include infinite conjunctions and disjunctions by letting

It then follows that for every $\bar a$ , $\mathcal {A}\models \varphi (\bar a)$ if and only if $T_{\mathcal {A}}\models T_\varphi (\sigma )$ for all $\sigma \succeq \bar a$ , and, by construction $T_\varphi $ has the same quantifier complexity as $\varphi $ .

We now prove Item 2 by defining for each $\bar \sigma =(\bar a_1,\dots ,\bar a_n)\in {\mathcal {T}}_{\mathcal {A}}$ a Turing-computable embedding from the isomorphism class of $\mathcal {A}$ in the extended vocabulary with additional constant symbols $\bar p=\bar p_1\dots ,\bar p_n$ such that $|\bar p_i|=|\bar a_i|$ to the class of trees with constant symbols for $\sigma $ . That is, the embedding $\Phi _\sigma $ will map $Iso(\mathcal {A},\bar p)$ to $Iso({\mathcal {T}}_{\mathcal {A}},\bar \tau )$ , where $\tau _i=\bar p_i$ for all $i<n$ and $\bar p_i\in A^{<\omega }$ . Each of these embeddings will extend the Friedman–Stanley embedding that acts without parameters.

Fix $\sigma =(\bar a_1,\dots ,\bar a_n)\in {\mathcal {T}}_{\mathcal {A}}$ and consider a structure $(\mathcal {B},\bar p)$ in the extended vocabulary such that $\mathcal {B}\cong \mathcal {A}$ . The Turing computable embedding $\Phi _\sigma $ computes the standard tree of structures for $\mathcal {B}$ and picks the lexicographically least tuple $\bar \tau $ from ${\mathcal {T}}_{\mathcal {B}}$ such that each $\tau _i$ codes $\bar p_i$ and the finite subtree described by $\bar \tau $ in ${\mathcal {T}}_{\mathcal {B}}$ is isomorphic to the finite subtree described by $\bar \sigma $ (notice that this last condition is necessary since ${\mathcal {T}}_{\mathcal {A}}$ is replicated. While $\bar a_i$ and $\bar a_j$ could agree on an initial segment, it could happen that the subtrees generated by the elements coding these tuples in ${\mathcal {T}}_{\mathcal {A}}$ are disjoint). It is not difficult to check that $\Phi _\sigma : (\mathcal {B},\bar p) \mapsto ({\mathcal {T}}_{\mathcal {B}},\bar \tau )$ is a Turing computable embedding mapping $(\mathcal {A},\bar a_1,\dots ,\bar a_n)$ to $({\mathcal {T}}_{\mathcal {A}},\bar {\sigma })$ . Now, for any formula $\psi $ in the language of labeled trees and parameters $\sigma =(\bar a_1,\dots ,\bar a_n)$ by the pull-back theorem for $\Psi _{\bar {\sigma }}$ there is $\psi ^*$ of the same complexity as $\psi $ such that $\mathcal {A}\models \psi ^*(\bar a_1\dots \bar a_n)$ if and only if ${\mathcal {T}}_{\mathcal {A}}\models \psi (\bar {\sigma })$ . This proves Item 2.

Proof. We prove this by contraposition. Assume that for some i, $\bar a_i\not \leq _\alpha \bar b_i$ . This is the same thing as saying that there is a $\Pi ^{\mathrm {in}}_{\alpha }$ formula $\varphi $ with $\mathcal {A}\models \varphi (\bar a_i)$ and $\mathcal {A}\models \lnot \varphi (\bar b_i)$ . From Item 1 of Lemma 2.3 we get that ${\mathcal {T}}_{\mathcal {A}}\models T_\varphi (\bar a_i)$ and ${\mathcal {T}}_{\mathcal {A}}\models \lnot T_\varphi (\bar b_i)$ . Then, since $T_\varphi $ is $\Pi ^{\mathrm {in}}_{\alpha }$ , $\sigma \not \leq _\alpha \tau $ , as desired.

Proof. Since ${\mathcal {T}}_{\mathcal {A}}$ is replicated, for every child $\rho $ of $\sigma $ there are infinitely many children $\rho '$ of $\sigma $ such that ${\mathcal {T}}_\rho '\cong {\mathcal {T}}_\rho $ . Hence, ${\mathcal {T}}_\sigma \cong {\mathcal {T}}_\sigma \setminus {\mathcal {T}}_\rho $ . The full lemma follows by a trivial induction.

Proof. Let $\mathcal {A}$ be a structure such that $SR({\mathcal {T}}_{\mathcal {A}})=\gamma $ . Consider a tuple $\bar a\in \mathcal {A}$ . Let $\psi \in \Sigma ^{\mathrm {in}}_{\gamma }$ define the orbit of $\bar a\in {\mathcal {T}}_{\mathcal {A}}$ . By Item 2 in Lemma 2.3 we have for all $\bar b\in \mathcal {A}$

$$\begin{align*}\mathcal{A}\models \psi^*(\bar b)\iff {\mathcal{T}}_{\mathcal{A}}\models \psi(\bar b) \iff \bar b\cong \bar a. \end{align*}$$

Therefore, $\psi ^*$ defines the orbit of $\bar a$ as desired and hence, $SR(\mathcal {A})\leq SR({\mathcal {T}}_{\mathcal {A}})$ .

We now show that $SR({\mathcal {T}}_{\mathcal {A}})\leq SR(\mathcal {A})=\gamma $ . Let $\bar {\sigma }=\bar a_1\dots \bar a_n$ be a tuple in ${\mathcal {T}}_{\mathcal {A}}$ . The automorphism orbit of each $\bar a_i$ and each of its prefixes is $\Sigma ^{\mathrm {in}}_{\gamma }$ definable in $\mathcal {A}$ . Thus, by Item 1 in Lemma 2.3, for every k there is a $\Sigma ^{\mathrm {in}}_{\gamma }$ formula, $\chi _{i,k}$ , true only of elements in $\tau \in \mathcal {T}_{\mathcal {A}}$ where $\tau $ codes a tuple with length k prefix automorphic to the length k prefix of $\bar a_i$ . In particular, $\mathcal {T}_{\tau \operatorname {\mathrm {\upharpoonright }} k}\cong \mathcal {T}_{\bar a_i\operatorname {\mathrm {\upharpoonright }} k}$ . Now, let $\psi $ describe the finite subtree containing precisely the elements of $\sigma $ as its leaves and let $\varphi $ be the conjunction of $\psi $ together with the $\chi _{i,k}$ . Note that $\varphi $ can be taken to have free variables corresponding to $\sigma $ . Because the labels encode the height of the labeled element in the tree, $\psi $ can be taken $\Sigma ^{\mathrm {in}}_{1}$ .

Let $\bar \tau =\bar b_1\dots \bar b_n$ satisfy $\varphi $ and consider the subtrees $\mathcal T_\sigma $ and $\mathcal T_\tau $ containing elements of ${\mathcal {T}}_{\mathcal {A}}$ comparable with $\sigma $ , respectively $\tau $ . These two subtrees are isomorphic by Lemma 2.5 and as ${\mathcal {T}}_{\bar a_i\operatorname {\mathrm {\upharpoonright }} k}\cong {\mathcal {T}}_{\bar b_i\operatorname {\mathrm {\upharpoonright }} k}$ for all $i<n$ and $k<|\bar a_i|$ . Fix $h(\tau )$ such that ${\mathcal {T}}_\tau \cong {\mathcal {T}}_{h(\tau )}$ yet the tree ${\mathcal {T}}_{h(\tau )}$ is disjoint from both ${\mathcal {T}}_\sigma $ and ${\mathcal {T}}_\tau $ . Since ${\mathcal {T}}$ is replicated we can find such an $h(\tau )$ and furthermore find an automorphism h such that $\tau $ is switched with $h(\tau )$ and all points outside of ${\mathcal {T}}_\tau $ and ${\mathcal {T}}_{h(\tau )}$ are fixed. Similarly, as ${\mathcal {T}}_\sigma \cong {\mathcal {T}}_{h(\tau )}$ there is an automorphism f that switches $\sigma $ with $h(\tau )$ and all points outside of ${\mathcal {T}}_\sigma $ and ${\mathcal {T}}_{h(\tau )}$ are fixed. Composing these automorphisms appropriately, we obtain that $h^{-1}(f(\sigma ))=\tau $ , so $\tau $ is in the automorphism orbit of $\sigma $ . Thus, $\varphi $ gives a $\Sigma ^{\mathrm {in}}_{\gamma }$ definition of the automorphism orbit of $\sigma $ as required.

Proof. We go by transfinite induction on $\alpha $ . The $\alpha =0$ case is immediate, as is the limit case. Assume the result for $\alpha =\beta $ . If $\bar a\bar p\leq _{\beta +1}\bar b\bar p$ , then $\bar a\leq _{\beta +1}\bar b$ follows immediately. Now assume that $\bar a\leq _{\beta +1}\bar b$ and consider an arbitrary tuple $\bar c$ . We can split $\bar c$ into the points somewhat comparable to $\bar p$ , named $\bar c_p$ , and the points entirely incomparable to $\bar p$ , named $\bar c_i$ (one of these may be the empty tuple). Because $\bar a\leq _{\beta +1}\bar b$ , there is a tuple $\bar d_i$ such that $\bar a\bar d_i\geq _{\beta }\bar b\bar c_i$ . We show that we can find a $\bar d^{\prime }_i$ that is entirely incomparable to $\bar p$ and has $\bar a\bar d^{\prime }_i\geq _{\beta }\bar b\bar c_i$ by modifying the given $\bar d_i$ . Let $p_1\dots p_n$ enumerate the length 1 points below any element in the tuple $\bar p$ , and let $a_1\dots a_n$ be similar for $\bar a$ . Note that $p_1\dots p_n$ and $a_1\dots a_n$ do not intersect as $\bar a$ is entirely incomparable to $\bar p$ . We let $d_1\dots d_n$ be similar for $\bar d$ , but we remove the points that appear among $a_1\dots a_n$ . For every $d_i$ let $d_i^{\prime }$ be an element with ${\mathcal {T}}_{d_i}\cong {\mathcal {T}}_{d_i^{\prime }}$ that does not appear among the $p_1\dots p_n$ and $a_1\dots a_n$ . This is possible because ${\mathcal {T}}_{\mathcal {A}}$ is an infinitely replicated tree. Consider the automorphism $\Phi $ of ${\mathcal {T}}_{\mathcal {A}}$ that exchanges ${\mathcal {T}}_{d_i}$ and ${\mathcal {T}}_{d_i^{\prime }}$ but fixes all elements not among these subsets. We define $\bar d^{\prime }_i=\Phi (\bar d)$ and claim that this tuple has the desired properties. $\Phi $ was constructed to fix $\bar a$ ; this means that $\bar d$ is automorphic to $\bar d'$ over $\bar a$ and therefore $\bar a\bar d^{\prime }_i\geq _{\beta }\bar a\bar d_i\geq _{\beta }\bar b\bar c_i$ . Furthermore, none of the $d^{\prime }_i$ are among the $p_i$ by construction so $\bar d'$ and $\bar p$ are entirely incomparable. We can now note that $\bar a\bar d^{\prime }_i$ and $\bar b\bar c_i$ are entirely incomparable with $\bar p\bar c_p$ as somewhat comparability is an equivalence relation. In particular, the induction hypothesis gives that

$$\begin{align*}\bar a\bar d_i^{\prime}\bar p\bar c_p\geq_{\beta}\bar b\bar c_i\bar p\bar c_p.\end{align*}$$

Rearranging the tuples gives that

$$\begin{align*}\bar a\bar p\bar d_i^{\prime}\bar c_p\geq_{\beta}\bar b\bar p\bar c_i\bar c_p\end{align*}$$

which shows that $\bar a\bar p\leq _{\beta +1}\bar b\bar p$ , as desired.

Proof. Consider a tuple $\bar a$ that is $\alpha $ -free in ${\mathcal {T}}_{\mathcal {A}}$ . Without loss of generality (by picking parameters automorphic to $\bar p$ ) we have that $\bar a$ is entirely incomparable with $\bar p$ . We demonstrate that $\bar a$ is also $\alpha $ -free in $({\mathcal {T}}_{\mathcal {A}},\bar p)$ .

Consider $\bar b\in {\mathcal {T}}_{\mathcal {A}}$ and $\beta <\alpha $ . We wish to show that there are $\bar a',\bar b'$ such that $\bar a\bar b\bar p\leq _\beta \bar a'\bar b'\bar p$ and $\bar a\bar p\not \leq _\alpha \bar a'\bar p.$

We can split $\bar b$ into the points somewhat comparable to $\bar p$ , named $\bar b_p$ , and the points entirely incomparable to $\bar p$ , named $\bar b_i$ (one of these may be the empty tuple). Using the $\alpha $ -freeness of $\bar a$ in ${\mathcal {T}}_{\mathcal {A}}$ , we may find $\bar a'$ and $\bar b_i^{\prime }$ (entirely incomparable to p via an automorphism fixing $\bar a$ ) such that $\bar a\bar b_i\leq _\beta \bar a'\bar b_i^{\prime }$ and $\bar a\not \leq _\alpha \bar a'.$

It follows from the previous lemma that $\bar a\bar b_i\bar p\bar b_p\leq _\beta \bar a'\bar b_i^{\prime }\bar p\bar b_p$ and $\bar a\bar p\not \leq _\alpha \bar a'\bar p.$ Rearranging the tuples we get that $\bar a\bar b\bar p\leq _\beta \bar a'\bar b'\bar p$ and $\bar a\bar p\not \leq _\alpha \bar a'\bar p.$ Therefore, $\bar a$ is also $\alpha $ -free in $({\mathcal {T}}_{\mathcal {A}},\bar p)$ .

In particular, if there are no $\alpha $ -free tuples in $({\mathcal {T}}_{\mathcal {A}},\bar p)$ then there are no $\alpha $ -free tuples in ${\mathcal {T}}_{\mathcal {A}}$ . Hence, $SR({\mathcal {T}}_{\mathcal {A}})=pSR({\mathcal {T}}_{\mathcal {A}})$ .

Proof. We start with the right to left implication and argue by contraposition. Assume $SR(\mathcal {A})=\lambda $ , yet $\mathcal {A}$ does not have a $\Pi ^{\mathrm {in}}_{\lambda }$ Scott sentence. Then there is a structure $\mathcal {B}$ such that $\mathcal {A}\equiv _\lambda \mathcal {B}$ yet $\mathcal {A}\not \cong \mathcal {B}$ . Because $\mathcal {A}$ has Scott rank $\lambda $ this is equivalent to saying that $\mathcal {A}\equiv _\lambda \mathcal {B}$ yet $\mathcal {A}\not \leq _{\lambda +1} \mathcal {B}$ . In other words, there is a tuple $\bar x\in \mathcal {B}$ such that for any $\bar z\in \mathcal {A}$ , $\bar z\not \equiv _\lambda \bar x$ . However, as $\mathcal {A}\equiv _\lambda \mathcal {B}$ , given a fundamental sequence $(\alpha _i)_{i\in \omega }$ for $\lambda $ , for every i there is some $\bar y_i\in \mathcal {A}$ such that $\bar y_i\equiv _{\alpha _i} \bar x$ . It follows that the $\bar y_i$ are a $\lambda $ -sequence. Furthermore, given any i, there must be some $k>i$ such that $\bar y_i\not \equiv _{\alpha _{k}}\bar y_{k}$ . Otherwise, $\bar y_i\equiv _\lambda \bar x$ , a contradiction to the choice of $\bar x$ . The above k can be taken to equal $i+1$ if we thin out the sequence by removing intermediate elements between i and k. In particular, the sequence $(\bar y_i)_{i\in \omega }$ can be taken to be unstable.

We now prove the left to right implication, again by contraposition. Consider a structure $\mathcal {A}$ with an unstable $\lambda $ -sequence $(\bar y_i)_{i\in \omega }$ . Consider the sequence of structures given by $(\mathcal {A},\bar y_i)_{i\in \omega }$ . By [Reference Montalbán21, Lemma XII.6], there is a structure $\mathcal {B}$ and tuple $\bar z\in \mathcal {B}$ such that for each i, $(\mathcal {B},\bar z)\equiv _{\alpha _i}(\mathcal {A},\bar y_{i})$ . Note that, in particular, this means that $\mathcal {B}\equiv _\lambda \mathcal {A}$ . Furthermore, for each i there is some $k>i$ such that $\alpha _k\geq 2\alpha _i+3$ , as the difference between $2\alpha _i+3$ and $\alpha _i$ is finite. For this k, we can observe that

$$\begin{align*}(\mathcal{A},\bar y_k)\models \exists \bar x \ \bar x\not\equiv_{\alpha_{i+1}} \bar y_k \land \bar x\equiv_{\alpha_i} \bar y_k.\end{align*}$$

By [Reference Montalbán21, Lemma VI.14] this is a $\Sigma ^{\mathrm {in}}_{2\alpha _i+3}$ sentence that is computable in $\mathcal {A}$ . As $(\mathcal {B},\bar z)\equiv _{\alpha _k}(\mathcal {A},\bar y_k)$ , by choice of k,

$$\begin{align*}(\mathcal{B},\bar z)\models \exists \bar x ~ \bar x\not\equiv_{\alpha_{i+1}} \bar z \land \bar x\equiv_{\alpha_i} \bar z.\end{align*}$$

Now consider the automorphism orbit of $\bar z$ inside $\mathcal {B}$ . It cannot be defined by a $\Sigma ^{\mathrm {in}}_{\beta }$ formula for $\beta <\lambda $ , as if we take $\alpha _i>\beta $ , by the above observation, there is a tuple that is not in the automorphism orbit of $\bar z$ that is $\alpha _i$ -equivalent to $\bar z$ . This means that $SR(\mathcal {B})>\lambda $ so $\mathcal {B}\not \cong \mathcal {A}$ . As $\mathcal {B}\equiv _\lambda \mathcal {A}$ , there is no $\Pi ^{\mathrm {in}}_{\lambda }$ Scott sentence for A.

Proof. Say $\mathcal {A}$ has Scott sentence complexity $\Pi ^{\mathrm {in}}_{\lambda }$ and fix $m\in \omega $ . If $\mathcal {A}$ realizes all the $\delta _n$ -types $p_n(\bar x)$ with m free variables and $p_n\subset p_{n+1}$ , then any sequence of elements $(\bar y_n)_n\in \omega $ such that $\bar y_n$ realizes the type $p_n(\bar x)$ forms a $\lambda $ -sequence. If $\bar y_n\not \equiv _{\delta _{k}} \bar y_{k}$ for $k>n$ on a cofinal subset, then we can obtain an unstable sequence by thinning out the sequence, a contradiction. Therefore, there is some K for which $\bar y_n\equiv _{\delta _{k}} \bar y_{k}$ for all $k>n\geq K$ . Then $\bar y_K$ realizes every type $p_n$ .

On the other hand, if $\mathcal {A}$ does not have Scott sentence complexity $\Pi ^{\mathrm {in}}_{\lambda }$ it must have some unstable sequence, $(\bar z_n)_{n\in \omega }$ . If we take the $\delta _n$ -type of $\bar z_n$ to be $p_n$ , then clearly every type $p_n$ is realized in $\mathcal {A}$ . However, if there is $\bar a$ that realizes all of the types $p_n$ , then we have that $\bar a\equiv _{\delta _n}\bar z_n$ yet $\bar a\not \equiv _{\delta _{n+1}}\bar z_{n+1}$ . Therefore the orbit of $\bar a$ is not $\Sigma ^{\mathrm {in}}_{\lambda }$ definable, a contradiction as $SR(\mathcal {A})=\lambda $ .

Proof. If $S\leq _\alpha T$ , $x_i\leq _\alpha y_i$ for any i follows immediately from the monotonicity of $\leq _\alpha $ .

Say that for all i, $x_i\leq _\alpha y_i$ . Note that for all i, ${\mathcal {T}}_{ x_i}\leq _\alpha {\mathcal {T}}_{ y_i}$ . This holds because any $\Pi ^{\mathrm {in}}_{\alpha }$ formula about ${\mathcal {T}}_{ x_i}$ can be transformed into a $\Pi ^{\mathrm {in}}_{\alpha }$ formula about $x_i$ by restricting all quantifiers to being above $x_i$ . Let

$$\begin{align*}{\mathcal{T}}^*_{x_i} := {\mathcal{T}}_{ x_i} - \left(\bigcup_{j : x_j \text{ is a child of } x_i} {\mathcal{T}}_{ x_j}\right) \quad\text{ and }\quad {\mathcal{T}}^*_{y_i} := {\mathcal{T}}_{ y_i} - \left(\bigcup_{j : y_j \text{ is a child of } y_i} {\mathcal{T}}_{ y_j}\right). \end{align*}$$

Note that ${\mathcal {T}}_{\mathcal {A}} = \sqcup _i {\mathcal {T}}^*_{x_i} = \sqcup _i {\mathcal {T}}^*_{y_i}$ as sets. By Lemma 2.5 we can observe that ${\mathcal {T}}^*_{x_i}\cong {\mathcal {T}}_{ x_i}$ and ${\mathcal {T}}^*_{y_i}\cong {\mathcal {T}}_{ y_i}$ . In particular, this means that for all i, ${\mathcal {T}}^*_{x_i}\leq _\alpha {\mathcal {T}}^*_{y_i}$ .

We have a sequence of strategies $\sigma _i$ where each $\sigma _i$ wins the back-and-forth game for the $\exists $ -player demonstrating that ${\mathcal {T}}^*_{x_i}\leq _\alpha {\mathcal {T}}^*_{y_i}$ . We use these strategies to describe a winning strategy in the back-and-forth game for the $\exists $ -player demonstrating that $S\leq _\alpha T$ . At any given even stage of the game the $\forall $ -player will have played a tuple $(S,\bar d)$ . Write $\bar d=(\bar d_1\dots \bar d_n)$ where $\bar d_i$ is the (possibly empty) subset of $\bar d$ that is in ${\mathcal {T}}^*_{y_i}$ . The $\exists $ -player will play the move $(T,\sigma _1(\bar d_1),\dots ,\sigma _n(\bar d_n))$ in response. The analogous strategy on the ${\mathcal {T}}^*_{x_i}$ is executed on the odd stages. In sum, the $\exists $ -player will play a winning strategy on each part of the partition ${\mathcal {T}}_{\mathcal {A}} = \sqcup _i {\mathcal {T}}^*_{x_i} = \sqcup _i {\mathcal {T}}^*_{y_i}$ completely agnostic of what is being played on the other parts of the partition.

Consider tuples $(T,\bar a)$ and $(S,\bar b)$ that are produced at the end of a play where the $\exists $ -player plays according to the above strategy. To confirm that the strategy is winning, we need to show that these tuples have the same atomic diagrams. Write $\bar a=(\bar a_1\dots \bar a_n)$ and $\bar b=(\bar b_1\dots \bar b_n)$ where $\bar a_i$ is the (possibly empty) subset of $\bar a$ that is in ${\mathcal {T}}^*_{y_i}$ and $\bar b_i$ is the (possibly empty) subset of $\bar b$ that is in ${\mathcal {T}}^*_{x_i}$ . Because we played a winning strategy on each of the parts of the partition ${\mathcal {T}}_{\mathcal {A}} = \sqcup _i {\mathcal {T}}^*_{x_i} = \sqcup _i {\mathcal {T}}^*_{y_i}$ , we know that for all i, $\bar a_i$ and $\bar b_i$ have the same atomic diagram. We must only check that the binary relations between elements in different tuples $\bar a_i$ and $\bar a_j$ are mirrored in the binary relations between $\bar b_i$ and $\bar b_j$ and that the binary relations between $\bar a_i$ and T are mirrored in the binary relations between $\bar b_i$ and S. Note that no binary relations hold between elements of distinct $\bar a_i$ and $\bar a_j$ as these elements are not comparable; the same is true for distinct $\bar b_i$ and $\bar b_j$ . Given $y_k\in T$ , it is less than all elements of $\bar a_i$ if $y_k\leq y_i$ and incomparable otherwise; the same is true for $x_k\in S$ and the elements of $\bar b_i$ . This confirms that the binary relations between different parts of the tuples $(T,\bar a)$ and $(S,\bar b)$ are the same in both cases. This means that the strategy is winning for the $\exists $ -player as claimed and $S\leq _\alpha T$ as desired.

Proof. Consider an unstable $\lambda $ -sequence in $\mathcal {A}$ given by $(\bar y_k)_{k\in \omega }$ . Say each tuple is coded by the element $m_k\in {\mathcal {T}}_{\mathcal {A}}$ , then Lemma 2.3 gives us at once that $m_k$ is an unstable $\lambda $ -sequence.

On the other hand, consider an unstable $\lambda $ -sequence in ${\mathcal {T}}_{\mathcal {A}}$ given by the fundamental sequence $(\delta _k)_{k\in \omega }$ and associated tuples $(\bar z_k)_{i\in \omega }$ . Let $S_k$ denote the finite tree of elements less than or equal to some point in the tuple, $\bar z_k$ . Note that the isomorphism type of $S_k$ is fixed so long as we have without loss of generality that $\delta _k>1$ for all k. By the definition of unstable $\lambda $ -sequences we have that

$$\begin{align*}\bar z_{k}\equiv_{\delta_{k}}\bar z_{k+1} \text{ and } \bar z_{k}\not\equiv_{\delta_{k+1}}\bar z_{k+1}.\end{align*}$$

By picking all of the elements in $S_k$ or $S_{k+1}$ as the first move of a back-and-forth game, we obtain that

$$\begin{align*}S_{k}\equiv_{\delta_{k-1}}S_{k+1} \text{ and } S_{k}\not\equiv_{\delta_{k+1}}S_{k+1}.\end{align*}$$

It follows from Lemma 2.12 that by reducing to some reindexed fundamental subsequence of $(\delta _k)_{k\in \omega }$ , say $(\gamma _k)_{k\in \omega }$ , we have that for some sequence of points $x_k \in S_k$

$$\begin{align*}x_{k}\equiv_{\gamma_{k}}x_{k+1} \text{ and } x_{k}\not\equiv_{\gamma_{k+1}}x_{k+1}.\end{align*}$$

By Lemma 2.3, the $\bar y_k$ coded by the $x_k$ , satisfy

$$\begin{align*}\bar y_{k}\equiv_{\gamma_{k}}\bar y_{k+1} \text{ and } \bar y_{k}\not\equiv_{\gamma_{k+1}}\bar y_{k+1}.\end{align*}$$

Therefore, there is an unstable $\lambda $ -sequence in $\mathcal {A}$ . Together, we obtain the desired result.

Proof. If $SR(\mathcal {A})=SR({\mathcal {T}}_{\mathcal {A}})$ is not a limit ordinal, then it follows from $SR({\mathcal {T}}_{\mathcal {A}})=pSR({\mathcal {T}}_{\mathcal {A}})$ that ${\mathcal {T}}_{\mathcal {A}}$ has $\Pi ^{\mathrm {in}}_{SR(\mathcal {A})+1}$ Scott sentence complexity.

If $SR(\mathcal {A})=SR({\mathcal {T}}_{\mathcal {A}})=\lambda $ is a limit ordinal, then by Corollary 2.14 $SSC(\mathcal {A})=\Pi ^{\mathrm {in}}_{\lambda }$ if and only if $SSC({\mathcal {T}}_{\mathcal {A}})=\Pi ^{\mathrm {in}}_{\lambda }$ .

Proof. The proof is by transfinite induction with the only interesting case being the base case. For this note that the label and predecessor relation of ${\mathcal {T}}_{\mathcal {A}}$ in $L_{\mathcal {A}}$ are both $\Sigma ^{\mathrm {in}}_{3}$ and $\Pi ^{\mathrm {in}}_{3}$ definable in $L_{{\mathcal {T}}_{\mathcal {A}}}$ . Let $\varphi $ be a $\Sigma ^{\mathrm {in}}_{1}$ formula true of $\bar a$ , then this formula can be translated into a $\Sigma ^{\mathrm {in}}_{3}$ formula true of $f(\bar a)$ and thus $\bar a\leq _3 \bar b$ implies $f(\bar a)\leq _1 f(\bar b)$ .

On the other hand, assume that $f(\bar a)\leq _1 f(\bar b)$ and without loss of generality that $\bar a$ and $\bar b$ contain elements from exactly two different blocks. Let us consider the back-and-forth game where the $\forall $ -player plays elements $\bar b^1$ on their first turn. For every $b^1_i$ the $\exists $ -player looks for elements $a^1_i$ such that $l(f(a^1_i))=l(f(b^1_i))$ , $a^1_i$ is in the same position in its block as $b^1_i$ and $\bar a\bar a^1$ and $\bar b\bar b^1$ are isomorphic in the tree-ordering. Note that they will find a suitable $\bar a^1$ because $f(\bar a)\leq _1 f(\bar b)$ . Now on their last turn the $\forall $ -player plays a tuple $\bar a^2$ and the $\exists $ -player has to respond playing $\bar b^2$ such that $\bar a\bar a^1\bar a^2\leq _1 \bar b\bar b^1\bar b^2$ . All they need to do is ensure that the intervals in $\bar a\bar a^1\bar a^2$ are at least as large as the intervals in $\bar b\bar b^1\bar b^2$ . Between any two elements in different blocks in $L_{\mathcal {A}}$ , there are blocks coding paths in ${\mathcal {T}}_{\mathcal {A}}$ . Thus, between any two elements in different blocks there are blocks of arbitrary large size and thus the $\exists $ -player can find elements satisfying this requirement.

Proof. For successor ordinals it is sufficient to note that Lemma 2.17 implies that a tuple $\bar a$ in $L_{\mathcal {A}}$ is $(3+\alpha )$ -free if and only if $f(\bar a)$ is $(1+\alpha )$ -free in ${\mathcal {T}}_{\mathcal {A}}$ . Likewise, a tuple $\bar a$ is $(1+\alpha )$ -free in ${\mathcal {T}}_{\mathcal {A}}$ if and only if $f^{-1}(\bar a)$ is $(3+\alpha )$ -free in $L_{\mathcal {A}}$ .

For $\alpha $ a limit, note that by Lemma 2.17 an $\alpha $ -sequence for $L_{\mathcal {A}}$ is unstable if and only if the pull-back along f is unstable in ${\mathcal {T}}_{\mathcal {A}}$ .

Proof. Say $\Phi $ is -measurable and the image of $\Phi $ is . Let $\chi \in \Pi ^{\mathrm {in}}_{\beta }$ describe the image of $\Phi $ in $Mod(\tau )$ . Let $\mathcal {A}$ have a $\Gamma ^{\mathrm {in}}_\gamma $ Scott sentence for $\gamma>\delta $ , say $\varphi $ . Then $\varphi ^*\land \chi $ is a $\Gamma ^{\mathrm {in}}_\gamma $ Scott sentence for $\Phi (\mathcal {A})$ . On the other hand say $\Phi (\mathcal {A})$ has a $\Gamma ^{\mathrm {in}}_\gamma $ Scott sentence for any $\gamma $ , then by the pullback theorem $\mathcal {A}$ has a $\Gamma ^{\mathrm {in}}_{\lambda +\gamma }$ Scott sentence. So for any $\mathcal {A}$ with $SR(\mathcal {A})>\max (\lambda \cdot \omega , \delta ,\beta )$ , Scott sentence complexity is preserved.

Question 2.24. Does $\mathcal {A}$ have a computable $\Pi ^{\mathrm {in}}_{\alpha +1}$ Scott sentence if and only if ${\mathcal {T}}_{\mathcal {A}}$ has a computable $\Pi ^{\mathrm {in}}_{\alpha +1}$ Scott sentence?

Proof. Say $\mathcal {A}\in \mathrm {LO}$ has a $\Sigma ^{\mathrm {in}}_{3}$ Scott sentence, then by Table 1 there is a parameter $\bar p\in A^{<\omega }$ such that $(\mathcal {A},\bar p)$ has a $\Pi ^{\mathrm {in}}_{2}$ Scott sentence. By the $2$ -universality of $\mathbb N\cup \{\mathbb {Q}\}$ every interval induced by $\bar p$ is isomorphic to either $\mathbb {Q}$ or n. Hence, $\mathcal {A}$ has at most finitely many adjacencies.

On the other hand, say that $Adj^{\mathcal {A}}$ is finite and let $\bar p$ be the ordered tuple of elements in the field of $Adj^{\mathcal {A}}$ . Then every interval induced by $\bar p$ is either empty or isomorphic to $\mathbb {Q}$ . As $\mathbb {Q}$ has a $\Pi ^{\mathrm {in}}_{2}$ Scott sentence, $(\mathcal {A},\bar p)$ has parameterless Scott rank $1$ , $\mathcal {A}$ has parameterized Scott rank $2$ , and, thus a $\Sigma ^{\mathrm {in}}_{3}$ Scott sentence.

Proof. The only candidates for linear orderings with Scott sentence complexity $\Sigma ^{\mathrm {in}}_{3}$ are by Theorem 3.5 those with finite adjacency relation. Now, these linear orderings are either finite, isomorphic to $\mathbb {Q}$ , $1+\mathbb {Q}$ , $\mathbb {Q}+1$ , $1+\mathbb {Q}+1$ , or isomorphic to a linear ordering obtained by replacing finitely many points in one of these four orderings by finite intervals. All but the last case are well-known to have $\Pi ^{\mathrm {in}}_{3}$ Scott sentences and thus can not have Scott sentence complexity $\Sigma ^{\mathrm {in}}_{3}$ . Consider an ordering whose order type falls in the last case, and that, without loss of generality, its order type is $n_1+\mathbb {Q}+n_2+\mathbb {Q}+n_3+\mathbb {Q}+\dots +n_k$ . Let $N=\sum _{i\leq k} n_i$ and assume that x is the jth element in the ordered tuple containing all the successor chains. Then its orbit is defined by

$$\begin{align*}\exists x_1\dots x_N\forall y\left(y\geq x_1\land x_{j}=x \land \bigwedge_{i<j,i\not\in \{ n_1,n_1+n_2,\dots,N\}} S(x_i,x_{i+1})\right),\end{align*}$$

where S is the $\Pi ^0_1$ definable successor relation. The formula is $\Sigma ^{\mathrm {in}}_{2}$ and defines the orbit of the jth element in the successor chains as required. Now, let x be an element in the jth $\mathbb {Q}$ copy where $i=\sum _{l\leq j} n_l$ . Then its automorphism orbit is defined by

$$\begin{align*}\exists x_1\dots x_{N}\left(\bigwedge_{j<N, j\not\in \{ n_1,n_1+n_2,\dots,N\}} S(x_j,x_{j+1}) \land x_{i}<x<x_{i+1}\right)\end{align*}$$

and this definition is again $\Sigma ^{\mathrm {in}}_{2}$ . It is easy to see that the defining formula of the automorphism orbit of any ordered tuple is just the conjunction of the defining formulas of the automorphism orbits of its elements. Thus, $n_1+\mathbb {Q}+n_2+\mathbb {Q}+\dots +n_k$ has a $\Pi ^{\mathrm {in}}_{3}$ Scott sentence.

Proof. Given a linear ordering $\mathcal {L}$ we can write $\mathcal {L}=W+\mathcal {K}+R$ with W well ordered or empty, R reverse well ordered or empty, and $\mathcal {K}$ empty or without a greatest or least element.

The element in K that $\mathcal {L}$ is $\leq _3$ -below will depend on the sizes of W and R, and the order type of $\mathcal {K}$ . Let us consider the different cases.

Case 1. W is infinite and R is finite. In this case, $W=\omega +\alpha $ for some ordinal $\alpha $ , so $\mathcal {L}=\omega +\mathcal {K}'+k$ for some $k\in \mathbb {N}$ and $\mathcal {K}'$ is either empty or without greatest element. We claim that $\mathcal {L}\leq _3\omega +k$ . It is sufficient to show that $\omega +\mathcal {K}'\leq _3\omega $ . The $\exists $ -player always wins the corresponding back-and-forth game by playing the following strategy. In the first round they play isomorphically on the initial $\omega $ . Because of that they only need to win the back-and-forth game for $\omega \leq _2 \omega +\mathcal {K}'$ . Say the $\forall $ -player picks elements such that $\omega +\mathcal {K}'$ is partitioned into n intervals $\mathcal {A}_i$ , each of cardinality $m_i$ for $i<n$ where $m_i$ might be infinite. The $\exists $ -player must pick a partition of $\omega $ such that for all intervals $\mathcal {B}_i$ , each of cardinality $k_i$ , $\mathcal {A}_i\leq _1 \mathcal {B}_i$ . This inequality holds if and only if $m_i\geq k_i$ . Given this inequality, the intervals formed by picking the first n elements of $\omega $ clearly form the desired partition.

Case 2. W is finite and R is infinite. This case is analogous to the first case.

Case 3. Both W and R are infinite. In this case, we can write $\mathcal {L}=\omega +\mathcal {K}'+\omega ^*$ . We claim that $\mathcal {L}\leq _3 \omega +\omega ^*$ . The winning strategy for the $\exists $ -player is similar to the one for Case 1. In the first play they play isomorphically on the initial $\omega $ and final $\omega ^*$ to reduce the game to showing that $\omega +\omega ^*\leq _2 \omega +\mathcal {K}'+\omega ^*$ . They can then win this game by picking partitions with smaller intervals, exactly as above.

Case 4. Both W and R are finite. There are two subcases with different behavior here. In both we assume that $\mathcal {K}$ has no greatest and least element, as if it was empty, then $\mathcal {L}$ would be finite and thus isomorphic to a structure in K.

Subcase 1. There are arbitrarily large successor chains in $\mathcal {K}$ . Here we claim that $\mathcal {K}\leq _3\mathbb {Z}$ , which gives that $\mathcal {L}\leq _3 k+\mathbb {Z}+k'$ for $k,k'\in \mathbb {N}$ . The $\exists $ -player always wins the corresponding game by playing the following strategy. Assume the $\forall $ -player plays an ordered tuple with the distance between least and greatest element n. Then the $\exists $ -player plays a successor chain of size n in $\mathcal {K}$ such that $\mathcal {K}=\mathcal {K}_1+n+\mathcal {K}_2$ where $\mathcal {K}_1$ has no first element and $\mathcal {K}_2$ has no last element. It is then sufficient to show that $\omega ^*\leq _2 \mathcal {K}_1$ and $\omega \leq _2 \mathcal {K}_2$ . In these games, similar to the cases above, the $\exists $ -player just needs to ensure that they play partitions of smaller size then the $\forall $ -player and this is possible by the same strategy.

Subcase 2. There is an $n\in \mathbb N$ such that no element in $\mathcal {K}$ has n successors. In this case, we consider the block relation $\sim $ given by $a\sim b$ if and only if $[a,b]$ and $[b,a]$ are finite. By assumption every block is a linear ordering of size n or less. As no block can be infinite, no two blocks can be successors in the quotient $\mathcal {K}/{\sim }$ . Furthermore, as there is no least or greatest element, there are no least or greatest blocks in $\mathcal {K}/{\sim }$ . Therefore, $\mathcal {K}/{\sim }=\mathbb {Q}$ . In total, this means that $\mathcal {K}=\sum _{q\in \mathbb {Q}} i_n(q)$ where $i_n:\mathbb {Q}\to \{1,\dots , n\}$ . If there are only finitely many blocks of size n, we may write $\mathcal {K}$ as a sum $\mathcal {K}_1+n+\cdots +n+\mathcal {K}_l$ where no block of size n occurs in any of the $\mathcal {K}_i$ . Repeating this process as necessary, we can write $\mathcal {K}$ as $\mathcal {K}_1+n_1+\mathcal {K}_2+n_2+\dots \mathcal {K}_l$ where each $\mathcal {K}_i$ is given by $\mathcal {K}_i=\sum _{q\in (b_i,t_i)} i_n(q)$ where $t_i$ is the smallest element of $n_i$ and $b_i$ is the largest element of $n_{i-1}$ or $-\infty $ if $i=1$ such that $\{ q\in (b_i,t_i): i_n(q)=m_i\}$ is infinite for $m_i=\max {\text {range}(i_n\operatorname {\mathrm {\upharpoonright }} (b_i,t_i))}$ . Furthermore, we have that $m_i<n_i$ and if $i>1$ , $m_i<n_{i-1}$ .

We now show that $\mathcal {L}=k{\kern-1pt}+{\kern-1pt}\mathcal {K}_1{\kern-1pt}+{\kern-1pt}n_1+\dots \mathcal {K}_l{\kern-1pt}+{\kern-1pt}k'\leq _3 k{\kern-1pt}+{\kern-1pt}m_1\cdot \mathbb {Q}+n_1\dots m_l\cdot \mathbb {Q}{\kern-1pt}+{\kern-1pt}k'$ . It is enough to show that $\mathcal {K}_i=\sum _{q\in (b_i,t_i)}i_n(q) \leq _3 m_i\cdot \mathbb {Q}$ . The $\exists $ -player always wins this game by playing the following strategy. Every element the $\forall $ -player plays in the first play is in a block of size $m_i$ . The $\exists $ -player can respond by playing elements in the same position in blocks of size $m_i$ . The resulting intervals in $\mathcal {K}_i$ are of the form $l_1+\sum _{q\in (b_i^j,t_i^j)}i_n(q)+l_2$ where $b_i^j> b_i$ and $t_i^j<t_i$ . The corresponding intervals in $m_i\cdot \mathbb {Q}$ are of the form $l_1+m_i\cdot \mathbb {Q}+l_2$ . Winning the game thus comes down to finding a winning strategy for the game $m_i\cdot \mathbb {Q}\leq _2 \sum _{q\in (b_i^j,t_i^j)}i_n(q)$ . Given a partition in $\sum _{q\in (b_i^j,t_i^j)}i_n(q)$ , the $\exists $ -player needs to find a partition in $m_i\cdot \mathbb {Q}$ such that all intervals are smaller than the intervals in the partition picked by the $\forall $ -player. They can do that using the fact that the finite blocks are densely ordered and always of maximum size.

This shows that K is $3$ -universal. Standard arguments show that each element of K has a $\Pi ^{\mathrm {in}}_{3}$ Scott sentence. Therefore, by Lemma 3.2, there is no $J\subset K$ such that J is $3$ -universal.

Proof. We may assume that $\tau $ contains only one binary relation symbol, i.e., that the $\tau $ -structures are graphs. Notice that there are continuum many graphs with Scott sentence complexity $\Pi ^{\mathrm {in}}_{2}$ : For any $X\subseteq \omega $ the graph consisting of a cycle of size $n+2$ for every $n\in X$ has a $\Pi ^{\mathrm {in}}_{2}$ Scott sentence. To see this just notice that the automorphism orbit of any element x in a cycle of size $c_x$ is definable by the $\Sigma ^0_1$ -formula

$$\begin{align*}\exists y_1,\dots, y_{c_x} \left(y_1=x \land y_{c_x}\mathbin{E} y_1 \land \bigwedge_{i<c_x} y_i\mathbin{E} y_{i+1}\right).\end{align*}$$

However, by Corollary 3.9 there are only countably many linear orderings with a $\Sigma ^{\mathrm {in}}_{4}$ Scott sentence. As any potential embedding $\Phi $ needs to respect isomorphism, it cannot map every graph with a $\Pi ^{\mathrm {in}}_{2}$ Scott sentence to a linear ordering with a Scott sentence of complexity in $\{\Sigma ^{\mathrm {in}}_{4}, d\text{-}\Sigma ^{\mathrm {in}}_{3},\Pi ^{\mathrm {in}}_{3}\}$ .

Proof. As mentioned in the proof of Theorem 3.10 there are uncountably many graphs with Scott sentence complexity $\Pi ^{\mathrm {in}}_{2}$ . The Friedman–Stanley embedding transforms those into linear orderings of Scott sentence complexity $\Pi ^{\mathrm {in}}_{4}$ . Thus, by Lemma 3.2 there can not be a countable $4$ -universal set of linear orderings.