Scott spectral gaps for trees are bounded

Abstract

Given a Borel class of trees, we show that there is a tree in that class whose Scott sentence is not too much more complicated than the definition of the class. In particular, if the class is definable by a ${\mathrm{\Pi }}_{\alpha }$ sentence, then there is a model of Scott rank at most $\alpha +2$. This gives another proof—and one that does not require first proving Vaught’s conjecture for trees—of the fact that trees are not faithfully Borel complete.

1 Introduction

Given a countable mathematical structure $𝒜$, such as a graph, group, or linear order, Scott [SCO65] showed that there is a sentence $\phi$ of the infinitary logic ${ℒ}_{{\omega }_1\omega }$ that characterizes that structure up to isomorphism among countable structures in the sense that for countable structures $ℬ$, we have $ℬ\vDash \phi$ if and only if $ℬ\cong 𝒜$. Such a sentence is called a Scott sentence for $𝒜$. We can measure the complexity of describing $𝒜$ up to isomorphism by assigning to $𝒜$ an ordinal-valued Scott rank. There are a number of almost but not quite equivalent definitions of Scott rank. The one that we will use is due to Montalbán [MON15] and defines the Scott rank of $𝒜$ to be the least $\alpha$ such that $𝒜$ has a ${\mathrm{\Pi }}_{\alpha +1}$ Scott sentence. This definition is particularly robust, and measures in addition the complexity of describing the automorphism orbits of the structure.

Given an ${ℒ}_{{\omega }_1\omega }$ sentence $\phi$, we think of $\phi$ as a theory defining a class of models, and we ask what the possible Scott ranks of the models of $\phi$ might be.

Definition 1.1.

Let $\phi$ be an ${ℒ}_{{\omega }_1\omega }$ sentence. The Scott spectrum of $\phi$ is the set

$$\text{SS}(\phi )=\{\alpha \in {\omega }_1|\text{there is }𝒜\vDash \phi \text{ of Scott rank }\alpha \}.$$

In [HAR18] the first author showed that there are theories $\phi$ which have low complexity, but all of whose models have high complexity. For example, for any $\alpha$, there is a ${\mathrm{\Pi }}_2$ sentence $\phi$ all of whose models have Scott rank $\ge \alpha$. Moreover, such an example could be found within any universal class of structures (see [HKS+02] and Chapter VI of [MON21]), such as graphs or fields. On the other hand, in [4], the first author and Gonzalez showed that if a ${\mathrm{\Pi }}_{\alpha }$ sentence $\phi$ extends the axioms of linear orders then there is a model of $\phi$ of Scott rank at most $\alpha +4$. This was the first non-trivial case in which such a result is known.

In this paper we consider the case of (simple) trees, which are rooted connected acyclic graphs. We use the language ${ℒ}_{tree}=\{r,P\}$ where $r$ is a constant standing for the root and $P$ is the parent relation, that is, $P(x)=y$ means that $y$ is the parent of $x$. (We write the parent relation using functional notation for clarity, but formally we take our language to be a relational language so that we can define the back-and-forth relations in the standard way.) Our motivation for considering trees arises from faithful Borel embeddings, a topic somewhat connected to Vaught’s conjecture. Steel [STE78] proved that Vaught’s conjecture is true for linear orders and trees, while of course Vaught’s conjecture is open in general. While linear orders and trees are Borel complete [FS89], this is not enough to imply that Vaught’s conjecture is true in general. The reason is that, as shown by Gao [GAO01], linear orders and trees are not faithfully Borel complete, that is, the saturation of the image of a Borel reduction from graphs to linear orders or trees cannot be Borel. For classes of structures which are faithfully Borel complete, including for example graphs, Vaught’s conjecture for that class would imply the full Vaught’s conjecture. As proved in [4], having bounded Scott spectral gaps implies that a class is not faithfully Borel complete, and in a way which does not require first verifying Vaught’s conjecture for that class (whereas Gao’s argument went through proving a strengthening of Vaught’s conjecture for linear orders and trees). A central open question is whether Boolean algebras are faithfully Borel complete and whether Vaught’s conjecture is true for them, and so studying Scott spectral gaps for Boolean algebras would be a way of studying the former question without having to first resolve the latter. We refer the reader to [4] for a more detailed discussion of these connections.

In this context, it is natural to try to prove that Scott spectral gaps are bounded for trees. This is the main result of this paper.

Theorem 1.2.

Given a satisfiable ${\mathrm{\Pi }}_{\alpha }$ sentence $\phi$ of trees, there is a tree $𝒜\vDash \phi$ with a ${\mathrm{\Pi }}_{\alpha +3}$ Scott sentence and hence Scott rank at most $\alpha +2$.

The high-level structure of the argument is similar to the case of linear orders, though of course the details differ. In particular, the reader will note that we obtain a better bound for trees than that for linear orders. While this paper is mathematically self-contained, our explanatory discussion of material that is analogous to that appearing in [4], especially that in Section 2, will be brief. We refer the reader to [4] for a more detailed development.

As for linear orders, we also obtain non-trivial lower bounds, but there remains a gap between the lower bounds and the upper bounds.

Theorem 1.3.

There is a ${\mathrm{\Pi }}_2$ theory of trees such that no model of $\phi$ has a ${\mathrm{\Sigma }}_3$ Scott sentence, and hence every model has Scott rank at least $3$.

2 Back-and-forth relations and hierarchies of formulas

In this section we outline the general background needed to carry out the argument. Throughout this paper, all structures will be countable and all languages relational. Central to the ideas of the argument are the asymmetric back-and-forth relations.

Definition 2.1.

The asymmetric back-and-forth relations ${\le }_{\alpha }$, for , are defined by:

• $(ℳ,\overline{a}){\le }_0(𝒩,\overline{b})$ if $\overline{a}$ and $\overline{b}$ satisfy the same quantifier-free formulas from among the first $|\overline{a}|$-many formulas.

• For $\alpha >0$, $(ℳ,\overline{a}){\le }_{\alpha }(𝒩,\overline{b})$ if for each and $\overline{d}\in 𝒩$ there is $\overline{c}\in ℳ$ such that $(𝒩,\overline{b}\overline{d}){\le }_{\beta }(ℳ,\overline{a}\overline{c})$.

We define $\overline{a}{\equiv }_{\alpha }\overline{b}$ if $\overline{a}{\le }_{\alpha }\overline{b}$ and $\overline{b}{\le }_{\alpha }\overline{a}$.

The interpretation of $(ℳ,\overline{a}){\le }_{\alpha }(𝒩,\overline{b})$ is that in the back-and-forth game between $ℳ$ and $𝒩$, starting with the partial isomorphism $\overline{a}\mapsto \overline{b}$ and with the first player Spoiler to play next in $𝒩$, the second player Duplicator can play without losing along an ordinal clock $\alpha$. Recall that if Duplicator can continue playing forever, then $ℳ\cong 𝒩$.

The asymmetric back-and-forth relations can be characterized in relation to the quantifier complexity hierarchy ${\mathrm{\Sigma }}_{\alpha }$/${\mathrm{\Pi }}_{\alpha }$ of ${ℒ}_{{\omega }_1\omega }$-formulas.

Theorem 2.2 (Karp [KAR65]).

For any $\alpha \ge 1$, structures $𝒜$ and $ℬ$, and tuples $\overline{a}\in 𝒜$ and $\overline{b}\in ℬ$, the following are equivalent:

1. $(𝒜,\overline{a}){\le }_{\alpha }(ℬ,\overline{b})$.

2. Every ${\mathrm{\Pi }}_{\alpha }$ formula true about $\overline{a}$ in $𝒜$ is true about $\overline{b}$ in $ℬ$.

3. Every ${\mathrm{\Sigma }}_{\alpha }$ formula true about $\overline{b}$ in $ℬ$ is true about $\overline{a}$ in $𝒜$.

However, as shown in [4], there is no ${\mathrm{\Pi }}_{\alpha }$ formula defining the set of $\overline{b}\in ℬ$ such that $(𝒜,\overline{a}){\le }_{\alpha }(ℬ,\overline{b})$. Instead, as there, we will make use of the hierarchies ${𝔄}_{\alpha }$ and ${𝔈}_{\alpha }$ as introduced in [1].

Definition 2.3.

All connectives below are countable.

• ${𝔄}_1:={\mathrm{\Pi }}_1$

• ${𝔈}_1:={\mathrm{\Sigma }}_1$

• ${𝔄}_{\alpha }:=$ closure of under $\forall$ and $\bigwedge \bigwedge$

• ${𝔈}_{\alpha }:=$ closure of under $\exists$ and $\bigvee \bigvee$

• ${\overline{𝔈}}_{\alpha }:=$ closure of ${𝔈}_{\alpha }$ under $\bigvee \bigvee ,\bigwedge \bigwedge$

• ${\overline{𝔄}}_{\alpha }:=$ closure of ${𝔄}_{\alpha }$ under $\bigvee \bigvee ,\bigwedge \bigwedge$

Each ${𝔄}_{\alpha }$ formula can be written in the form

$$\underset{i\in I}{\bigwedge \bigwedge }\forall {\overline{y}}_i{\phi }_i(\overline{x},{\overline{y}}_i)$$

where the formulas ${\phi }_i$ are ${\overline{𝔈}}_{\beta }$ for some , and similarly a ${𝔈}_{\alpha }$ formula can be written in the form

$$\underset{i\in I}{\bigvee \bigvee }\exists {\overline{y}}_i{\phi }_i(\overline{x},{\overline{y}}_i)$$

where each ${\phi }_i$ is ${\overline{𝔄}}_{\beta }$ for some .

The key difference between these two hierarchies is that a formula of the form $\forall \bigvee \bigvee \bigwedge \bigwedge \exists$ is only ${𝔄}_2$ while being ${\mathrm{\Pi }}_4$. The two main facts we use are stated in the following lemmas.

Lemma 2.4 (Chen, Gonzalez, and Harrison-Trainor [1]).

For any $\alpha \ge 1$, structures $𝒜$ and $ℬ$, and tuples $\overline{a}\in 𝒜$ and $\overline{b}\in ℬ$, the following are equivalent:

1. $(𝒜,\overline{a}){\le }_{\alpha }(ℬ,\overline{b})$.

2. Every ${𝔄}_{\alpha }$ formula true about $\overline{a}$ in $𝒜$ is true about $\overline{b}$ in $ℬ$.

3. Every ${𝔈}_{\alpha }$ formula true about $\overline{b}$ in $ℬ$ is true about $\overline{a}$ in $𝒜$.

Lemma 2.5 (Chen, Gonzalez, and Harrison-Trainor [1]).

Let $ℒ$ be a countable language and $𝒜$ be a countable $ℒ$-structure. For each $\overline{a}\in A$ and nonzero there is an ${𝔄}_{\alpha }$ formula ${\psi }_{\overline{a},𝒜,\alpha }$ such that for any countable $ℒ$-structure $ℬ$ and $\overline{b}\in ℬ$,

$$ℬ\vDash {\psi }_{\overline{a},𝒜,\alpha }(\overline{b})⟺(ℬ,\overline{b}){\ge }_{\alpha }(𝒜,\overline{a}).$$

3 Back-and-forth relations and trees

A common assumption when working with back-and-forth relations and trees is that whenever a tuple $\overline{a}$ of a tree $T$ appears, it is closed under the parent relation and so is a subtree of $T$. We will make this assumption, which we will often abbreviate by saying that “$\overline{a}$ is a finite subtree of $T$”. In the context of this paper, this assumption can be justified by the following lemma.

Lemma 3.1.

Let $S$ and $T$ be trees and $\overline{a}\in S$ and $\overline{b}\in T$. Let ${\overline{a}}^{\prime }\in S$ consist of $\overline{a}$ and all of its ancestors, and similarly for ${\overline{b}}^{\prime }$ and $\overline{b}$ in $T$, with both tuples listed in corresponding order. Then for any $\alpha >0$, $(S,\overline{a}){\le }_{\alpha }(T,\overline{b})$ if and only if $(S,{\overline{a}}^{\prime }){\le }_{\alpha }(T,{\overline{b}}^{\prime })$.

Proof.

If $(S,{\overline{a}}^{\prime }){\le }_{\alpha }(T,{\overline{b}}^{\prime })$ then $(S,\overline{a}){\le }_{\alpha }(T,\overline{b})$ as $\overline{a}$ and $\overline{b}$ are subtuples of ${\overline{a}}^{\prime }$ and ${\overline{b}}^{\prime }$ respectively. On the other hand, suppose that $(S,\overline{a}){\le }_{\alpha }(T,\overline{b})$. We know that if $T\vDash \psi (\overline{b})$ then $T\vDash \psi (\overline{a})$ for any ${\mathrm{\Sigma }}_{\alpha }$ formula $\psi (\overline{x})$. In particular, if $\eta (\overline{y},\overline{b})$ is a finitary quantifier-free formula defining ${\overline{b}}^{\prime }$ with respect to $\overline{b}$, then $T\vDash \eta ({\overline{a}}^{\prime },\overline{a})$ and moreover ${\overline{a}}^{\prime }$ is the only such tuple. We must argue that if $T\vDash {\psi }^{\prime }({\overline{b}}^{\prime })$ then $S\vDash {\psi }^{\prime }({\overline{a}}^{\prime })$ for any ${\mathrm{\Sigma }}_{\alpha }$ formula ${\psi }^{\prime }({\overline{x}}^{\prime })$. Suppose $T\vDash {\psi }^{\prime }({\overline{b}}^{\prime })$. Then $T\vDash \exists \overline{y}[\eta (\overline{y},\overline{b})\wedge {\psi }^{\prime }(\overline{y})]$ so $S\vDash \exists \overline{y}[\eta (\overline{y},\overline{a})\wedge {\psi }^{\prime }(\overline{y})]$. Since $\eta (\overline{y},\overline{a})$ is a defining formula for ${\overline{a}}^{\prime }$, we see $T\vDash {\psi }^{\prime }({\overline{a}}^{\prime })$. ∎

For linear orders, the analysis in [4] breaks the linear order up into intervals. The point was that the back-and-forth relations on linear orders can be broken up into the back-and-forth relations on intervals as follows. Given linear orders $𝒜$ and $ℬ$, and elements and , we have $(\overline{a},𝒜){\le }_{\alpha }(\overline{b},ℬ)$ if and only if each of the corresponding intervals in $𝒜$ and $ℬ$ are related in the same way, that is $(-\mathrm{\infty },a_1){\le }_{\alpha }(-\mathrm{\infty },b_1)$, $(a_1,a_2){\le }_{\alpha }(b_1,b_2)$, and so on. We must identify an analogous way of breaking trees up into their constituent parts. We do this as follows.

Definition 3.2.

Let $\overline{a}=(a_1,\mathrm{\dots },a_n)$ be a finite subtree of $T$. Define $T_{\overline{a}}^{a_i}$, the descendant tree of $a_i$ avoiding $\overline{a}$, to be the tree consisting of $a_i$ and its descendants that are not in $\overline{a}$, with $a_i$ as its root.

Note that the trees $T_{\overline{a}}^{a_i}$ are all disjoint from each other, and that the isomorphism type of $T$ is determined by the finite tree $\overline{a}$ together with the isomorphism types of $T_{\overline{a}}^{a_i}$. $T_{\overline{a}}^{a_i}$ can be defined by the following ${\mathrm{\Sigma }}_1$ formula ${\eta }_i(x;a_i,\overline{a})$:

$${\eta }_i(x,a_i,\overline{a}):=\underset{n=0}{\overset{\mathrm{\infty }}{\bigvee \bigvee }}\exists y_0,\mathrm{\dots },y_n\left[a_i=y_0\wedge P(y_1)=y_0\wedge \mathrm{\cdots }\wedge P(y_n)=y_{n-1}\wedge y_n=x\wedge \left(\underset{j\ne i}{\bigwedge }{y}_1\ne a_j\right)\right].$$

With the formula $\eta (x,y_i,\overline{y})$ we may relativize a formula $\phi$ to a tree $T_{\overline{a}}^{a_i}$. We obtain a formula $\phi {\upharpoonright }_{\overline{x}}^{x_i}$ of the same complexity such that if $\overline{a}\in T$ is a finite subtree of $T$ then

$$T\vDash \phi {\upharpoonright }_{\overline{a}}^{a_i}⟺T_{\overline{a}}^{a_i}\vDash \phi .$$

We do this by replacing each quantifier $\exists x\mathrm{\dots }$ in $\phi$ with $\exists x(\eta (x,a_i,\overline{a})\wedge \mathrm{\dots })$ and each quantifier $\forall x\mathrm{\dots }$ in $\phi$ with $\forall x({\eta }_i(x,a_i,\overline{a})\to \mathrm{\dots })$. Since $\eta (x,y,\overline{z})$ is a ${\mathrm{\Sigma }}_1$ formula, $\phi$ and $\phi {\upharpoonright }_{\overline{a}}^{a_i}$ are the same complexity ${\mathrm{\Sigma }}_{\alpha }$/${\mathrm{\Pi }}_{\alpha }$ or ${𝔈}_{\alpha }$/${𝔄}_{\alpha }$.

Remark 3.3.

Corresponding to the fact that a subinterval of a subinterval of a linear order is a subinterval of that linear order, we have the following fact. Given $\overline{a}$ a subtree of $T$, and $\overline{b}=({\overline{b}}_1,\mathrm{\dots },{\overline{b}}_n)$ where each ${\overline{b}}_i$ is a subtree of $T_{\overline{a}}^{a_i}$ containing the roots $a_i$, note that ${(T_{\overline{a}}^{a_i})}_{\overline{b_i}}^{b_{i,j}}=T_{\overline{a}\overline{b_i}}^{b_{i,j}}=T_{\overline{b}}^{b_{i,j}}$. Note that each entry of $\overline{a}$ is contained in $\overline{b}$, so that for example $\overline{a}{\overline{b}}_i$ has $a_i$ appearing twice, which we will allow to avoid cumbersome notation. We will sometimes write $T_{\overline{a}\overline{b}}^{b_{i,j}}$ for $T_{\overline{b}}^{b_{i,j}}$.

To see that the $T_{\overline{a}}^{a_i}$ are the right analogue of intervals in a linear order, we prove the following fact about how back-and-forth relations between tuples in trees break up into back-and-forth relations between their descendant trees.

Lemma 3.4.

Let $A$ and $B$ be trees and let $\overline{a}\in A$ and $\overline{b}\in B$ be finite subtrees. Let $\alpha \ge 1$. Then $(A,\overline{a}){\ge }_{\alpha }(B,\overline{b})$ if and only if $\overline{a}{\cong }_{\mathrm{tree}}\overline{b}$ and $A_{\overline{a}}^{a_i}{\ge }_{\alpha }{B}_{\overline{b}}^{b_i}$ for each $i$. Here $\overline{a}{\cong }_{\mathrm{tree}}\overline{b}$ means $\overline{a}$ and $\overline{b}$ are isomorphic as trees.

Proof.

First suppose $(A,\overline{a}){\ge }_{\alpha }(B,\overline{b})$. Clearly $\overline{a}{\cong }_{\mathrm{tree}}\overline{b}$. Given $i$, suppose that $B_{\overline{b}}^{b_i}\vDash \phi$ where $\phi$ is ${\mathrm{\Pi }}_{\alpha }$. Then $B\vDash \phi {\upharpoonright }_{\overline{b}}^{b_i}$, so $A\vDash \phi {\upharpoonright }_{\overline{a}}^{a_i}$, meaning $A_{\overline{a}}^{a_i}\vDash \phi$. Thus $A_{\overline{a}}^{a_i}{\ge }_{\alpha }{B}_{\overline{b}}^{b_i}$.

Now suppose $\overline{a}{\cong }_{\mathrm{tree}}\overline{b}$ and $A_{\overline{a}}^{a_i}{\ge }_{\alpha }{B}_{\overline{b}}^{b_i}$ for each $i$. Let and $\overline{c}\in A$. Without loss of generality let $\overline{c}=({\overline{c}}_1,{\overline{c}}_2,\mathrm{\dots },{\overline{c}}_n)$ where $\overline{c_i}\in A_{\overline{a}}^{a_i}$ for each $i$. Then there are $\overline{d_i}\in B_{\overline{b}}^{b_i}$ such that $(A_{\overline{a}}^{a_i},\overline{c_i}){\le }_{\beta }(B_{\overline{b}}^{b_i},\overline{d_i})$. We may assume that the ${\overline{c}}_i$ are subtrees of $A_{\overline{a}}^{a_i}$ containing $a_i$ and similarly for ${\overline{d}}_i$ and $B_{\overline{b}}^{b_i}$. Then, by the induction hypothesis we have ${(A_{\overline{a}}^{a_i})}_{{\overline{c}}_i}^{c_{i,j}}{\le }_{\beta }{(B_{\overline{b}}^{b_i})}_{{\overline{d}}_i}^{d_{i,j}}$ which is the same as $A_{\overline{a}\overline{c}}^{c_{i,j}}{\le }_{\beta }{B}_{\overline{b}\overline{d}}^{d_{i,j}}$ by Remark 3.3. Then—again, by the induction hypothesis—we have $(A,\overline{a}\overline{c}){\le }_{\beta }(B,\overline{b}\overline{d})$ and thus $(A,\overline{a}){\ge }_{\alpha }(B,\overline{b})$. ∎

The following lemma is a syntactic version of this previous fact. As with linear orders, the lemma is only true for ${𝔈}_{\alpha }$ sentences, and not for ${\mathrm{\Sigma }}_{\alpha }$ sentences. (A counterexample arises from the sentence defined in Proposition 5.1, with the proof being similar to the corresponding lemma from [4].)

Lemma 3.5.

Let $T$ be a tree and $\overline{a}\in T$ be a finite subtree containing the root. Suppose $T\vDash \phi (\overline{a})$ where $\phi$ is a ${𝔈}_{\alpha }$ formula. Then there are ${𝔈}_{\alpha }$ sentences ${\theta }_i$ such that $T_{\overline{a}}^{a_i}\vDash {\theta }_i$ and if $S$ is a tree and $\overline{b}\in S$ has $\overline{b}{\cong }_{\mathrm{tree}}\overline{a}$ and $S_{\overline{b}}^{b_i}\vDash {\theta }_i$ then $S\vDash \phi (\overline{b})$.

Proof.

Without loss of generality let $\phi (\overline{x})$ be of the form where each ${\psi }_k$ is ${\overline{𝔄}}_{\beta }$ for some . Since $T\vDash \phi (\overline{a})$ there is some $\overline{c}\in T$ and such that $T\vDash {\psi }_k(\overline{a},\overline{c})$. Without loss of generality suppose $\overline{c}=({\overline{c}}_1,{\overline{c}}_2,\mathrm{\dots },{\overline{c}}_n)$ where $\overline{c_i}$ is a subtree of $T_{\overline{a}}^{a_i}$ containing $a_i$. Note that following Remark 3.3 we have ${(T_{\overline{a}}^{a_i})}_{\overline{c_i}}^{c_{i,j}}=T_{\overline{c}}^{c_{i,j}}$. By Lemma 2.5 there are ${𝔄}_{\beta }$ sentences ${\chi }_{i,j}$ such that $S\vDash {\chi }_{i,j}$ if and only if $S{\ge }_{\beta }{T}_{\overline{a}\overline{c}}^{c_{i,j}}$. For each $i$ define

$${\theta }_i:=\exists \overline{x}[\overline{x}{\cong }_{\mathrm{tree}}\overline{c_i}\wedge \underset{j}{\bigwedge \bigwedge }{\chi }_{i,j}{\upharpoonright }_{\overline{x}}^{x_j}]$$

where $\overline{x}{\cong }_{\mathrm{tree}}\overline{c_i}$ stands for the infinitary quantifier-free formula with free variables $\overline{x}$ which expresses that the parent relations on $\overline{x}$ is the same as on $\overline{c}$ after identifying the roots. Then $T_{\overline{a}}^{a_i}\vDash {\theta }_i$. Suppose $S$ is a tree and $\overline{b}\in S$ is a finite subtree containing the root with $\overline{b}{\cong }_{\mathrm{tree}}\overline{a}$ and $S_{\overline{b}}^{b_i}\vDash {\theta }_i$ for each $i$. Let $\overline{d_i}$ be the witness of ${\theta }_i$ in $S_{\overline{b}}^{b_i}$. Then $S_{\overline{b}\overline{d}}^{d_{i,j}}{\ge }_{\beta }{T}_{\overline{a}\overline{c}}^{c_{i,j}}$, so by Lemma 3.4 $(S,\overline{d}){\ge }_{\beta }(T,\overline{c})$. Thus $S\vDash {\psi }_k(\overline{b},\overline{d})$ for $\overline{d}=({\overline{d}}_1,\mathrm{\dots },{\overline{d}}_n)$ and therefore $S\vDash \phi (\overline{b})$. ∎

4 Proof of the main theorem

In this section we prove the main theorem, which is that given a ${\mathrm{\Pi }}_{\alpha }$ sentence $\phi$ of trees, there is a tree $T\vDash \phi$ such that $T$ has a ${\mathrm{\Pi }}_{\alpha +3}$ Scott sentence and hence has Scott rank at most $\alpha +2$. As in [4], since each ${\mathrm{\Pi }}_{\alpha }$ sentence is ${𝔈}_{\alpha +1}$, after replacing $\alpha +1$ by $\alpha$ it suffices to assume that $\phi$ is ${𝔈}_{\alpha }$ and show that is has a model with a ${\mathrm{\Pi }}_{\alpha +2}$ Scott sentence and hence Scott rank at most $\alpha +1$. This sentence $\phi$ will be fixed for the remainder of this section.

The overall strategy is as follows. We use a Henkin construction to build a model of $\phi$ which is generic in a certain sense. Intuitively, one should think that we try to make any two tuples different from each other, if possible, by a ${𝔈}_{\alpha }$ sentence. If this fails, then we will try to make them be automorphic. We will show that the automorphism orbit of each tuple of this model is ${𝔈}_{\alpha +1}$-definable. This will imply that such a generic model has a ${\mathrm{\Pi }}_{\alpha +2}$ Scott sentence and hence has Scott rank at most $\alpha +1$. This last step uses a result of Chen, Gonzalez, and Harrison-Trainor [1] that having a ${\mathrm{\Pi }}_{\alpha +2}$ Scott sentence is equivalent to each automorphism orbit being ${𝔈}_{\alpha +1}$-definable, a strengthening (in the direction in which we apply it) of a result of Montalbán that having a ${\mathrm{\Pi }}_{\alpha +2}$ Scott sentence is equivalent to each automorphism orbit being ${\mathrm{\Sigma }}_{\alpha +1}$-definable.

4.1 Forcing and generic trees

Definition 4.1.

A set $𝔸$ of ${ℒ}_{{\omega }_1\omega }$ formulas is an existential fragment if it satisfies the following properties:

1. $𝔸$ contains the atomic and negated atomic formulas.

2. $𝔸$ is stable under taking subformulas, finite conjunctions and disjunctions, and existential quantification.

3. If $\phi (v_0,\mathrm{\dots },v_n)\in 𝔸$ and $\tau$ is a term, then $\phi (\tau ,v_1,\mathrm{\dots },v_n)\in 𝔸$.

Lemma 4.2.

Let $\phi$ be an ${𝔈}_{\alpha }$ sentence of trees. Then there is a countable existential segment $𝔸$ of ${𝔈}_{\alpha }$ formulas which contains $\phi$. Furthermore, we may find such an $𝔸$ together with a countable collection $ℂ$ of countable trees with the following properties

1. For any variables $\overline{x}$ appearing in $𝔸$ and $\psi \in 𝔸$, $\psi {\upharpoonright }_{\overline{x}}^{x_i}\in 𝔸$.

2. If $\psi (\overline{x})\in 𝔸$ is satisfiable, then there is some $T\in ℂ$ and $\overline{a}\in T$ such that $T\vDash \psi (\overline{a})$.

3. Suppose $T\in ℂ$, $\overline{a}\in T$, and $T\vDash \psi (\overline{a})$ where $\psi (\overline{x})\in 𝔸$. Then there are ${\theta }_i\in 𝔸$ for each $i$ as in Lemma 3.5.

Proof.

We build finite approximations and with ${𝔸}_n\subseteq {𝔸}_{n+1}$ and ${ℂ}_n\subseteq {ℂ}_{n+1}$ for each . Set ${𝔸}_0=\{\phi \}$ and ${ℂ}_0=\mathrm{\varnothing }$. We first ensure that $𝔸$ is an existential segment. It is easy to add all the atomic and negated atomic formulas. For each formula which appears in ${𝔸}_n$ we can ensure each of its subformulas and term substitutions appear at a later stage because there are only countably many of them. Similarly, it is easy to ensure that $𝒜$ satisfies the other conditions to be an existential fragment.

We satisfy the remaining three properties in a similar way. For each $\psi \in {𝔸}_k$ and variable $\overline{x}$ that appeared in ${𝔸}_k$, we can ensure $\psi {\upharpoonright }_{\overline{x}}^{x_i}\in {𝔸}_n$ for some $n>k$. For infinitely many $k$, we may let ${𝔸}_{k+1}={𝔸}_k$ and

$${ℂ}_{k+1}={ℂ}_k\cup \{T_{\psi (\overline{x})}:\psi (\overline{x})\in {𝔸}_k\text{ satisfiable}\}$$

where the countable trees $T_{\psi (\overline{x})}$ are chosen such that there is $\overline{c}\in T_{\psi (\overline{x})}$ with $T_{\psi (\overline{x})}\vDash \psi (\overline{c}).$ Finally suppose $T\in {ℂ}_k$, $\psi (\overline{x})\in {𝔸}_k$, and $\overline{a}\in T$ where $T\vDash \psi (\overline{a})$. Then for each $i$, there is a sentence ${\theta }_i$ as in Lemma 3.5. We may include all of them in some ${𝔸}_n$ where $n>k$. ∎

Given the fixed ${𝔈}_{\alpha }$ sentence $\phi$ we fix such $𝔸$ and $ℂ$ for the rest of this article. Let ${𝔸}^{\ast }$ be the satisfiable formulas of $𝔸$. For two sentences $\chi$ and $\psi$ in ${𝔸}^{\ast }$, we write $\chi \le \psi$ if every model of $\chi$ is a model of $\psi$. We say $\chi \in {𝔸}^{\ast }$ forces unity if for any ${\psi }_0,{\psi }_1\le \chi$ with ${\psi }_0,{\psi }_1\in {𝔸}^{\ast }$, ${\psi }_0\wedge {\psi }_1$ is satisfiable. Also, we say $\chi \in {𝔸}^{\ast }$ forces splitting if for every $\psi \in {𝔸}^{\ast }$ with $\psi \le \chi$, there are ${\psi }_0,{\psi }_1\in {𝔸}^{\ast }$ with ${\psi }_0,{\psi }_1\le \psi$ where ${\psi }_0\wedge {\psi }_1$ is not satisfiable.

We say that a tree $T$ is generic if

1. For any finite subtree $\overline{a}\in T$ containing the root there is a $\chi \in {𝔸}^{\ast }$ that forces unity or splitting such that $T\vDash {\chi }_{\overline{a}}^{a_0}$, and

2. For any finite subtree $\overline{a}\in T$ containing the root and any $\psi \in {𝔸}^{\ast }$ either $T\vDash {\psi }_{\overline{a}}^{a_0}$ or there is some $\chi \in {𝔸}^{\ast }$ incompatible with $\psi$ such that $T\vDash {\chi }_{\overline{a}}^{a_0}$.

We have stated all of these conditions as referring specifically to $a_0$ from among $\overline{a}$, but because they apply to all tuples from the tree in any order, they are equivalent to the conditions holding for any $a_i$, e.g., (1) is equivalent to

1. For any finite subtree $\overline{a}\in T$ containing the root and any $i$ there is a $\chi \in {𝔸}^{\ast }$ that forces unity or splitting such that $T\vDash {\chi }_{\overline{a}}^{a_i}$.

Writing the conditions in terms of only $a_0$ will simplify the notation, but sometimes we will apply, e.g., (1) in the form of (1*) when we have a fixed tuple $\overline{a}$ for which we want to apply the condition to every $a_i$ at the same.

We say that a tree $T$ has property $(\ast )$ if for any finite subtrees $\overline{a},\overline{b}\in T$ containing the root and with $a_0\ne b_0$ at the same level of the tree, either

1. There are incompatible ${\psi }_0,{\psi }_1\in {𝔸}^{\ast }$ such that $T\vDash {\psi }_0{\upharpoonright }_{\overline{a}}^{a_0}\wedge {\psi }_1{\upharpoonright }_{\overline{b}}^{b_0}$ or

2. There is some $\psi \in {𝔸}^{\ast }$ that forces unity such that $T\vDash \psi {\upharpoonright }_{\overline{a}}^{a_0}\wedge \psi {\upharpoonright }_{\overline{b}}^{b_0}$.

4.2 Construction of a generic tree

Here we prove that there is a countable model of $\phi$ with the aforementioned properties.

Theorem 4.3.

There is a countable generic tree with property $(\ast )$ satisfying $\phi$.

Proof.

We execute a Henkin-type construction. Let $C$ be a countably infinite set of constant symbols. We will build finite collections of ${𝔈}_{\alpha }$ sentences ${\mathrm{\Phi }}_n$ in the language of trees with additional constants $C$. The ${\mathrm{\Phi }}_n$ will be an increasing sequence of finite sets, starting with ${\mathrm{\Phi }}_0=\{\phi \}$, and each consisting of sentences of the form $\psi (\overline{c})$ where $\psi (\overline{x})\in {𝔸}^{\ast }$ and $\overline{c}\in C$. will satisfy the following conditions.

1. If then ${\psi }_n\in \mathrm{\Phi }$ for some .

2. If $\exists \overline{x}\psi (\overline{x})\in \mathrm{\Phi }$ then $\psi (\overline{c})\in \mathrm{\Phi }$ for some $\overline{c}\in C$.

3. If then ${\psi }_n\in \mathrm{\Phi }$ for every .

4. If $\forall \overline{x}\psi (\overline{x})\in \mathrm{\Phi }$ then $\psi (\overline{c})\in \mathrm{\Phi }$ for every $\overline{c}\in C$.

5. For each atomic sentence, either it or its negation is in $\mathrm{\Phi }$.

6. The end product is generic:

   1. For each $\overline{c}\in C$ such that $\mathrm{\Phi }$ implies that $\overline{c}$ is a finite tree there is a sentence $\psi \in {𝔸}^{\ast }$ that either forces unity or splitting with $\psi {\upharpoonright }_{\overline{c}}^{c_0}\in \mathrm{\Phi }$.

   2. For each $\overline{c}\in C$ such that $\mathrm{\Phi }$ implies that $\overline{c}$ is a finite tree, and each $\psi \in {𝔸}^{\ast }$, either $\psi {\upharpoonright }_{\overline{c}}^{c_0}\in \mathrm{\Phi }$ or there is some $\chi \in {𝔸}^{\ast }$ that’s incompatible with $\psi$ and $\chi {\upharpoonright }_{\overline{c}}^{c_0}\in \mathrm{\Phi }$.

7. The end product has property $(\ast )$: for each $\overline{c}\in C$ such that $\mathrm{\Phi }$ implies that $\overline{c}$ is a finite tree, if $\mathrm{len}(\overline{c})>1$ and $c_0$ and $c_1$ are at the same level, then either there are incompatible ${\psi }_0,{\psi }_1\in {𝔸}^{\ast }$ where ${\psi }_0{\upharpoonright }_{\overline{c}}^{c_0}\in \mathrm{\Phi }$ and ${\psi }_1{\upharpoonright }_{\overline{c}}^{c_1}\in \mathrm{\Phi }$ or there is a $\psi \in {𝔸}^{\ast }$ that forces splitting and $\psi {\upharpoonright }_{\overline{c}}^{c_0}\wedge \psi {\upharpoonright }_{\overline{c}}^{c_1}\in \mathrm{\Phi }$.

   (Though this does not look like $(\ast )$, it is enough to imply it. To achieve $(\ast )$ more directly, we would want to meet the following condition: Given a pair of tuples $\overline{c},\overline{d}\in C$ such that $\mathrm{\Phi }$ implies that $\overline{c}$ and $\overline{d}$ are finite trees, and $c_0$ and $d_0$ are at the same level, either there are incompatible ${\psi }_0,{\psi }_1\in {𝔸}^{\ast }$ where ${\psi }_0{\upharpoonright }_{\overline{c}}^{c_0}\in \mathrm{\Phi }$ and ${\psi }_1{\upharpoonright }_{\overline{d}}^{d_0}\in \mathrm{\Phi }$ or there is a $\psi \in {𝔸}^{\ast }$ that forces splitting and $\psi {\upharpoonright }_{\overline{c}}^{c_0}\wedge \psi {\upharpoonright }_{\overline{d}}^{d_0}\in \mathrm{\Phi }$. Given such $\overline{c}$ and $\overline{d}$, we can assume without loss of generality that no element of $\overline{c}$ is a descendant of $d_0$, and no element of $\overline{d}$ is a descendant of $c_0$. Thus for any tree $T$, $T_{\overline{c}\overline{d}}^{c_0}=T_{\overline{c}}^{c_0}$ and $T_{\overline{c}\overline{d}}^{d_0}=T_{\overline{d}}^{d_0}$, and similarly for a sentence $\phi$, ${\phi }_{\overline{c}\overline{d}}^{c_0}={\phi }_{\overline{c}}^{c_0}$ and ${\phi }_{\overline{c}\overline{d}}^{d_0}={\phi }_{\overline{d}}^{d_0}$. We could then form the joint tuple $\overline{c}\overline{d}$, and rearrange it so that the first two entries are $c_0$ and $d_0$. Thus we arrive at the condition above.)

In the conditions above, when we say that $\mathrm{\Phi }$ implies that $\overline{c}$ is a finite tree, we mean that there is some $c_i$ such that $c_i=r$ is in $\mathrm{\Phi }$, and for each other $c_j$ there is $c_k$ such that $P(c_j)=c_k$ is in $\mathrm{\Phi }$.

We will ensure that each ${\mathrm{\Phi }}_n$ is satisfiable in a tree by having, at each stage $n$, a tree $T\in ℂ$ and an assignment $v$ which assigns to each constant in $C$ an element of $T$ making ${\mathrm{\Phi }}_n$ true in $T$. Moreover, for any constant $c$ appearing in ${\mathrm{\Phi }}_n$ there will be a constant $d$ such that $P(c)=d$ is in ${\mathrm{\Phi }}_n$ and for some $k$, $P^k(c)=r$ will be in ${\mathrm{\Phi }}_n$, and we will have $c\ne d$ in ${\mathrm{\Phi }}_n$ for any two constants $c,d$ in $C$. Thus ${\mathrm{\Phi }}_n$ will put the structure of a finite tree containing the root on the constants that appear in ${\mathrm{\Phi }}_n$.

Given $\mathrm{\Phi }=\bigcup {\mathrm{\Phi }}_n$ we can build a model of $\mathrm{\Phi }$ whose domain is the constants $C$, as usual. This model will be a tree because of of the conditions described in the previous paragraph. Since $\phi \in {\mathrm{\Phi }}_0\subseteq \mathrm{\Phi }$ we know that $\phi$ is true in this tree. Also, conditions (6) and (7) will guarantee that this tree is generic and has property $(\ast )$.

We now describe our construction of the ${\mathrm{\Phi }}_n$. We begin with ${\mathrm{\Phi }}_0=\{\phi ,c=r\}$ for some constant $c$ and $T\in ℂ$ satisfying $\phi$. At each stage $n+1$, we will define ${\mathrm{\Phi }}_{n+1}$ by taking a single step towards satisfying a single instance of one of the above conditions. We use standard dovetailing techniques to make sure that, in the end, all of the conditions are satisfied and will just describe below how to take a single step towards satisfying each of these conditions. For some conditions, namely (3) and (4), we must handle each instance of the condition infinitely many times. As an example, in (3), if ${\bigwedge \bigwedge }_n{\psi }_n\in \mathrm{\Phi }$ then we must return infinitely at infinitely many later stages each time adding a new ${\psi }_n$ to $\mathrm{\Phi }$. We cannot add them all at once as each ${\mathrm{\Phi }}_n$ must be finite. For each $n$, we also attach a countable tree $T\in ℂ$ that satisfies ${\mathrm{\Phi }}_n$, interpreting constants as elements from $T$. Assuming ${\mathrm{\Phi }}_n$ is satisfiable, such a tree can be chosen from $ℂ$ specifically due to (2) of Lemma 4.2.

Step 1:

If, at some stage $n+1$, we are handling the instance of (1) corresponding to with $T\vDash {\mathrm{\Phi }}_n$: There is some ${\psi }_m$ such that $T\vDash {\psi }_m$. We add ${\psi }_m$ to ${\mathrm{\Phi }}_{n+1}$. We still have $T\vDash {\mathrm{\Phi }}_{n+1}$.

Step 2:

If, at some stage $n+1$, we are handling the instance of (2) corresponding to $\exists x\psi (x)\in {\mathrm{\Phi }}_n$ with $T\vDash {\mathrm{\Phi }}_n$: There is some $a\in T$ such that $T\vDash \psi (a)$. If $a=c$ in $T$ for some constant symbol $c\in C$ that appears in ${\mathrm{\Phi }}_n$, then add $\psi (c)$ to ${\mathrm{\Phi }}_{n+1}$. Otherwise add $\psi (c^{\prime })$ to ${\mathrm{\Phi }}_{n+1}$ where $c^{\prime }\in C$ is some constant symbol that is not mentioned in ${\mathrm{\Phi }}_n$. In the latter case, we must also choose new constants for any ancestors of $a\in T$ which are do not already correspond to constants, and also add to ${\mathrm{\Phi }}_n$ the formulas determining the parents of any of these other new constants. We still have $T\vDash {\mathrm{\Phi }}_{n+1}$.

Step 3:

If, at some stage $n+1$, we are handling the instance of (3) corresponding to : We add ${\psi }_m$ to ${\mathrm{\Phi }}_{n+1}$ where ${\psi }_m$ is the next conjunct that has not yet been added to $\mathrm{\Phi }$. We still have $T\vDash {\mathrm{\Phi }}_{n+1}$.

Step 4:

If, at some stage $n+1$, we are handling the instance of (4) corresponding to $\forall x\psi (x)\in {\mathrm{\Phi }}_n$: We add $\psi (c)$ to ${\mathrm{\Phi }}_{n+1}$ where $c$ is the next constant from $C$ (according to some enumeration) for which $\psi (c)$ has not yet been added to $\mathrm{\Phi }$. If $c$ does not appear in ${\mathrm{\Phi }}_n$, we must choose some new element $a$ of $T$ for it to correspond to, and we must also choose new constants from $C$ for any ancestors of $a\in T$ which are do not already correspond to constants, and also add to ${\mathrm{\Phi }}_n$ the formulas determining the parents of any of these other new constants. We still have $T\vDash {\mathrm{\Phi }}_{n+1}$.

Step 5:

If at stage $n+1$ we are handling (5) and have $T\vDash {\mathrm{\Phi }}_n$: Let $F\subseteq C$ be the finite set of constants that appears in ${\mathrm{\Phi }}_n$. Then for each atomic sentence involving constants in $F$, include one of it or its negation to ${\mathrm{\Phi }}_{n+1}$ based on whether or not $T$ satisfies it. We still have $T\vDash {\mathrm{\Phi }}_{n+1}$.

Step 6(a):

If at stage $n+1$ we are handling the instance of (6a) corresponding to constants $\overline{c}$ appearing in ${\mathrm{\Phi }}_n$ and have $T\vDash {\mathrm{\Phi }}_n$: Suppose that ${\mathrm{\Phi }}_n$ implies that $\overline{c}$ is a finite tree. Let $\eta (\overline{c},\overline{b}):=\bigwedge {\mathrm{\Phi }}_n$ where $\overline{b}$ are the constants in ${\mathrm{\Phi }}_n$ that are not $\overline{c}$. Then $T\vDash \exists \overline{x}\eta (\overline{c},\overline{x})$, so by Lemma 3.5 there are sentences ${\chi }_i\in {𝔸}^{\ast }$ such that $T_{\overline{c}}^{c_i}\vDash {\chi }_i$ and for any countable tree $S$ if $\overline{d}\in S$ is a subtree of $S$ isomorphic to $\overline{c}$ in $T$, and if $S_{\overline{d}}^{d_i}\vDash {\chi }_i$, then $S\vDash \exists \overline{x}\eta (\overline{d},\overline{x})$. There is a sentence $\psi \le {\chi }_0$ that either forces unity or splitting. Let ${\mathrm{\Phi }}_{n+1}={\mathrm{\Phi }}_n\cup \{{\psi }_{\overline{c}}^{c_0}\}$. It remains to find a tree in $ℂ$ that satisfies ${\mathrm{\Phi }}_{n+1}$. Since $\psi \in {𝔸}^{\ast }$ there is a countable tree $U\vDash \psi$. We modify $T$ to obtain a tree $\widehat{T}$ by setting ${\widehat{T}}_{\overline{c}}^{c_0}=U$, and ${\widehat{T}}_{\overline{c}}^{c_i}=T_{\overline{c}}^{c_i}$ for $i>0$. (Essentially, we do “surgery” on $T$ by replacing the subtree below $c_0$ with a new subtree.) Then $\widehat{T}\vDash {\psi }_{\overline{c}}^{c_0}$. Since ${\widehat{T}}_{\overline{c}}^{c_i}\vDash {\chi }_i$ for each $i$, we have ${\widehat{T}}_{\overline{c}}^{c_i}\vDash \exists \overline{x}\eta (\overline{c},\overline{x})$ and so we can choose some assignment of the constants such that $\widehat{T}\vDash {\mathrm{\Phi }}_n$. Thus ${\mathrm{\Phi }}_{n+1}$ is satisfiable, meaning there a tree in $ℂ$ that satisfies it by (2) of Lemma 4.2.

Step 6(b):

If at stage $n+1$ we are handling the instance of (6b) corresponding to constants $\overline{c}$ appearing in ${\mathrm{\Phi }}_n$ and a formula $\psi \in {𝔸}^{\ast }$, and have $T\vDash {\mathrm{\Phi }}_n$: Suppose that ${\mathrm{\Phi }}_n$ implies that $\overline{c}$ is a finite tree. Set $\eta (\overline{c},\overline{b}):=\bigwedge {\mathrm{\Phi }}_n$ where $\overline{b}$ are the constants in ${\mathrm{\Phi }}_n$ that are not $\overline{c}$ and define the ${\chi }_i$ as we did in the previous step. If ${\chi }_0$ and $\psi$ are incompatible, we let ${\mathrm{\Phi }}_{n+1}={\mathrm{\Phi }}_n\cup \{{\chi }_0{\upharpoonright }_{\overline{c}}^{c_0}\}$ and don’t change $T$. Otherwise, we let ${\mathrm{\Phi }}_{n+1}={\mathrm{\Phi }}_n\cup \{\psi {\upharpoonright }_{\overline{c}}^{c_0}\}$. In this case ${\chi }_0\wedge \psi$ is satisfiable, so there is a countable tree $U\vDash {\chi }_0\wedge \psi$. We can obtain a tree $\widehat{T}\vDash {\mathrm{\Phi }}_{n+1}$ in $ℂ$ exactly as in the previous step.

Step 7:

If at stage $n+1$ we are handling the instance of (7) corresponding to constant $\overline{c}$ appearing in ${\mathrm{\Phi }}_n$ with $\mathrm{len}(\overline{c})>1$ and $T\vDash {\mathrm{\Phi }}_n$: Suppose that ${\mathrm{\Phi }}_n$ implies that $\overline{c}$ is a finite tree. Find ${\chi }_i$ as before. Suppose there are incompatible ${\psi }_0,{\psi }_1\in {𝔸}^{\ast }$ where ${\chi }_0\wedge {\psi }_0$ and ${\chi }_1\wedge {\psi }_1$ are each satisfiable. Then we set ${\mathrm{\Phi }}_{n+1}={\mathrm{\Phi }}_n\cup \{{\psi }_0{\upharpoonright }_{\overline{c}}^{c_0},{\psi }_1{\upharpoonright }_{\overline{c}}^{c_1}\}$ and find a model of ${\mathrm{\Phi }}_{n+1}$ in $ℂ$ as before. Thus we may assume that there are no such ${\psi }_0,{\psi }_1$. In this case ${\chi }_0\wedge {\chi }_1$ is satisfiable and forces unity. It is satisfiable because otherwise ${\chi }_0$ and ${\chi }_1$ themselves serve as the witnesses ${\psi }_0$ and ${\psi }_1$. If ${\chi }_0\wedge {\chi }_1$ did not force unity, then there would be incompatible ${\psi }_0,{\psi }_1\le {\chi }_0\wedge {\chi }_1$ which again we assumed was not the case. So ${\chi }_0\wedge {\chi }_1$ is satisfiable and forces unity, and we may set ${\mathrm{\Phi }}_{n+1}={\mathrm{\Phi }}_n\cup \{({\chi }_0\wedge {\chi }_1){\upharpoonright }_{\overline{c}}^{c_0}\wedge ({\chi }_0\wedge {\chi }_1){\upharpoonright }_{\overline{c}}^{c_1}\}$ and find a model in $ℂ$ as before.∎

4.3 Verification

In this section we prove that a generic tree with property $(\ast )$ has Scott rank at most $\alpha +1$.

Lemma 4.4.

Suppose $\sigma \in {𝔸}^{\ast }$ forces unity, $A,B$ are generic countable trees, $\overline{a}\in A,\overline{b}\in B$ are finite subtrees containing the root, and $A\vDash \sigma {\upharpoonright }_{\overline{a}}^{a_0},B\vDash \sigma {\upharpoonright }_{\overline{b}}^{b_0}$. Further suppose for any finite subtree ${\overline{a}}^{\prime }\in A_{\overline{a}}^{a_0}$ containing $a_0$, and any $i$, $A_{\overline{a}{\overline{a}}^{\prime }}^{a_i^{\prime }}$ satisfies a sentence that forces unity. Then the same is true of every finite subtree ${\overline{b}}^{\prime }\in B_{\overline{b}}^{b_0}$ containing $b_0$ and every $i$, that is, $B_{\overline{b}{\overline{b}}^{\prime }}^{b_i^{\prime }}$ satisfies a sentence that forces unity.

Proof.

Assume for the sake of contradiction that there is some finite subtree ${\overline{b}}^{\prime }\in B_{\overline{b}}^{b_0}$ containing $b_0$ and some $i$ such that $B_{\overline{b}{\overline{b}}^{\prime }}^{b_i^{\prime }}$ does not satisfy a sentence that forces unity. By genericity, $B_{\overline{b}{\overline{b}}^{\prime }}^{b_i^{\prime }}$ satisfies a sentence that forces splitting, say $\psi$. Thus $B_{\overline{b}}^{b_0}\vDash \exists \overline{x}[(\overline{x}{\cong }_{\mathrm{tree}}{\overline{b}}^{\prime })\wedge (\psi {\upharpoonright }_{\overline{x}}^{x_i})]$. Since $A$ is generic and $A_{\overline{a}}^{a_0}$ satisfies $\sigma$ which forces unity, it also satisfies $\exists \overline{x}[(\overline{x}{\cong }_{\mathrm{tree}}{\overline{b}}^{\prime })\wedge (\psi {\upharpoonright }_{\overline{x}}^{x_i})]$. If ${\overline{a}}^{\prime }\in A_{\overline{a}}^{a_0}$ is its witness, then $A_{\overline{a}{\overline{a}}^{\prime }}^{a_i^{\prime }}$ both satisfies a sentence that forces splitting and unity, a contradiction. ∎

Definition 4.5.

We say a sentence $\sigma$ is Scott-like if it forces unity and for every $T\vDash \sigma$ and finite subtree $\overline{a}\in T$ that contains the root, $T_{\overline{a}}^{a_0}$ satisfies a sentence in ${𝔸}^{\ast }$ that forces unity. We say a tree $T$ is Scott if it satisfies a Scott-like sentence.

Lemma 4.6.

Suppose $\sigma \in {𝔸}^{\ast }$ is Scott-like, $A,B$ are generic trees, and $\overline{a}\in A,\overline{b}\in B$ are finite subtrees containing the root. Then if $A_{\overline{a}}^{a_0},B_{\overline{b}}^{b_0}\vDash \sigma$ then $A_{\overline{a}}^{a_0}\cong B_{\overline{b}}^{b_0}$.

Proof.

We will define a back-and-forth family $F$ consisting of pairs of tuples from $A_{\overline{a}}^{a_0}$ and from $B_{\overline{b}}^{b_0}$. We put $(\overline{u},\overline{v})\in F$ if $\overline{u}\in A_{\overline{a}}^{a_0}$ and $\overline{v}\in B_{\overline{b}}^{b_0}$ are finite subtrees containing the root, $\overline{u}{\cong }_{\mathrm{tree}}\overline{v}$, and for each $i$ both $A_{\overline{a}\overline{u}}^{u_i}$ and $B_{\overline{b}\overline{v}}^{v_i}$ satisfy the same sentence that forces unity. We prove that $F$ is a back-and-forth family. Clearly $(a_0,b_0)\in F$. Suppose $(\overline{u},\overline{v})\in F$ where ${\sigma }_i$ are sentences forcing unity with $A_{\overline{a}\overline{u}}^{u_i}\vDash {\sigma }_i$ and $B_{\overline{b}\overline{v}}^{v_i}\vDash {\sigma }_i$, and let $u^{\prime }\in A$. Suppose the closest ancestor of $u^{\prime }$ in $\overline{u}$ is $u_i$ and let $\overline{c}\in A$ be the smallest subtree containing $u_i$ and $u^{\prime }$. Thus for each $c_j$ there is a some ${\psi }_j$ that forces unity and $A_{\overline{a}\overline{u}\overline{c}}^{c_j}\vDash {\psi }_j$. Define

Then $A_{\overline{a}\overline{u}}^{u_i}\vDash \eta$ and thus ${\phi }_i\wedge \eta$ is consistent. If $B_{\overline{b}\overline{c}}^{v_i}⊭\eta$ then by genericity, there is some sentence $\theta$ such that $B_{\overline{b}\overline{c}}^{v_i}\vDash \theta$ but $\theta$ and $\eta$ is incompatible. This contradicts that ${\phi }_i$ forces unity, and thus $B_{\overline{b}\overline{c}}^{v_i}\vDash \eta$. If $\overline{d}$ is the witness of $B_{\overline{b}\overline{c}}^{v_i}$ to $\eta$, then $(\overline{u}\overline{c},\overline{v}\overline{d})\in F$. The other direction follows similarly, proving that $F$ is a back-and-forth family. ∎

Lemma 4.7.

Each automorphism orbit of a generic tree with property $(\ast )$ is definable by a ${𝔈}_{\alpha +1}$ sentence. In particular, such a tree has a ${\mathrm{\Pi }}_{\alpha +2}$ Scott sentence and hence has Scott rank at most $\alpha +1$.

Proof.

Let $T$ be a generic tree with property ($\ast$). If we can show that each automorphism orbit of $T$ is definable by an ${𝔈}_{\alpha +1}$ sentence, then by Theorem 7.7 of [1], $T$ has a ${\mathrm{\Pi }}_{\alpha +2}$ Scott sentence.

Let $\overline{a}=(a_0,\mathrm{\dots },a_{n-1})\in T$ be a finite subtree containing the root. For each we define ${\phi }_i$ the following way. If $T_{\overline{a}}^{a_i}\vDash \psi$ where $\psi$ is Scott-like, then set ${\phi }_i:=\psi$. Otherwise, there’s some $\overline{b}\in T_{\overline{a}}^{a_i}$ where $T_{\overline{a}\overline{b}}^{b_0}\vDash \psi$ for some $\psi$ that forces splitting. By property $(\ast )$, for each finite tree $\overline{c}\in T$ where $c_0$ is of the same distance from the root as $b_0$, there is some ${\psi }_{\overline{c}}$ such that $T_{\overline{a}\overline{b}}^{b_0}\vDash \neg {\psi }_{\overline{c}}$ but $T_{\overline{c}}^{c_0}\vDash {\psi }_{\overline{c}}$. Using these, set

$${\phi }_i:=\exists \overline{y}[\left(\overline{y}{\cong }_{\mathrm{tree}}\overline{b}\right)\wedge \underset{\overline{c}}{\bigwedge \bigwedge }\neg {\psi }_{\overline{c}}{\upharpoonright }_{\overline{y}}^{y_0}].$$

For each $i$ we have $T_{\overline{a}}^{a_i}\vDash {\phi }_i$.

Now define $\theta (\overline{x})$ by

Since each ${\phi }_i$ is either ${𝔈}_{\alpha }$ or ${𝔄}_{\alpha }$, $\theta (\overline{x})$ is ${𝔈}_{\alpha +1}$. Clearly $T\vDash \theta (\overline{a})$. We prove that $\theta (\overline{x})$ defines the automorphism orbit of $\overline{a}.$ Suppose $T\vDash \theta (\overline{d})$ for $\overline{d}\in T$, and we want to show that $(T,\overline{a})\cong (T,\overline{d})$. We have, for each $i$, $T_{\overline{d}}^{d_i}\vDash {\phi }_i$. Since we already have $\overline{d}{\cong }_{\mathrm{tree}}\overline{a}$, it remains to prove $T_{\overline{d}}^{d_i}\cong T_{\overline{a}}^{a_i}$ for each . We induct on the tree structure of $\overline{a}$, starting with the leaves as the base case. Suppose $a_i$ is a leaf of $\overline{a}$. If ${\phi }_i$ is Scott-like, $T_{\overline{d}}^{d_i}\cong T_{\overline{a}}^{a_i}$ by Lemma 4.6. If ${\phi }_i$ is not Scott-like, if $a_i=d_i$ then since they are leaves we have $T_{\overline{a}}^{a_i}=T_{\overline{d}}^{d_i}$. We argue that $a_i=d_i$ by contradiction; suppose to the contrary that that $a_i\ne b_i$. For $\overline{b}$ the tuple in $T_{\overline{a}}^{a_i}$ used in the definition of ${\phi }_i$, we have $T_{\overline{d}}^{d_i}\vDash \exists \overline{y}[(\overline{y}{\cong }_{\mathrm{tree}}\overline{b})\wedge {\bigwedge \bigwedge }_{\overline{c}}\neg {\psi }_{\overline{c}}{\upharpoonright }_{\overline{y}}^{y_0}]$. Since $a_i$ and $d_i$ are of the same distance from the root and $a_i\ne d_i$, for any possible witness $\overline{y}=\overline{c}$ in $T_{\overline{d}}^{d_i}$ we would have $b_0\ne c_0$ as they extend $a_i$ and $b_i$ respectively. Also, $b_0$ and $c_0$ are of the same height. Thus $T_{\overline{d}}^{d_0}\vDash {\psi }_{\overline{c}}{\upharpoonright }_{\overline{c}}^{c_0}$, contradicting that $\overline{y}=\overline{c}$ was a witness to $T_{\overline{d}}^{d_0}\vDash {\phi }_i$.

Now for the inductive case, suppose $T_{\overline{d}}^{d_j}\cong T_{\overline{a}}^{a_j}$ for every descendant $a_j$ of $a_i$ and $d_j$ or $d_i$. We must argue that $T_{\overline{a}}^{a_i}\cong T_{\overline{d}}^{d_i}$. If ${\phi }_i$ is Scott-like, $T_{\overline{d}}^{d_i}\cong T_{\overline{a}}^{a_i}$. If not, by similar reasoning as before, $a_i=d_i$. This part of the argument in the previous paragraph did not use the assumption that $a_i$ and $d_i$ were leaves; it was only to then argue that if $a_i=d_i$ then $T_{\overline{d}}^{d_i}\cong T_{\overline{a}}^{a_i}$ that we used this fact. We will now argue for this same fact but this time we must use the inductive hypothesis. Consider the children of $a_i=d_i$. Without loss of generality let the children of $a_i$ which also appear in $\overline{a}$ be $a_0,\mathrm{\dots },a_k$. Similarly, the children of $d_i$ which also appear in $\overline{d}$ are $d_0,\mathrm{\dots },d_k$. Using the induction hypothesis, the full subtrees of $T$ below each of $a_0,\mathrm{\dots },a_k$ are isomorphic to the full subtrees of $T$ below each of $d_0,\mathrm{\dots },d_k$ respectively. The isomorphism type of $T_{\overline{a}}^{a_i}$ is determined by the isomorphism types of the full subtrees of $T$ below the children of $a_i$ which do not appear in $\overline{a}$, and the isomorphism type of $T_{\overline{d}}^{d_i}$ is determined by the isomorphism types of the full subtrees of $T$ below the children of $d_i$ which do not appear in $\overline{d}$. Since $a_i=d_i$, the isomorphism types of full subtrees of $T$ below the children of $a_i$ are the same as the isomorphism types of full subtrees of $T$ below the children of $d_i$, counting multiplicity. Taking away the isomorphism types corresponding to $a_0,\mathrm{\dots },a_k$ on one side and $d_0,\mathrm{\dots },d_k$ on the other, we still have the same isomorphism types. Thus, we conclude that $T_{\overline{a}}^{a_i}\cong T_{\overline{d}}^{d_i}$. ∎

Remark 4.8.

A key fact for the analogue of Lemma 4.7 for linear orders, in the treatment overlapping intervals, was a theorem of Lindenbaum and Tarski [LT30]: If $K$ and $L$ are linear order, and for each $n$ the product order $K\cdot n$ is an initial segment of $L$, then $K\cdot \omega$ is an initial segment of $L$ and so $K+L\cong L$. No analogous fact is required for trees. Instead, we are able to argue that we do not need to consider overlapping trees. This is responsible for the improved upper bounds we obtain.

5 Lower bounds

Here we give a lower bound: We find a ${\mathrm{\Pi }}_2$ theory of trees with no models with ${\mathrm{\Sigma }}_3$ Scott sentence.

Proposition 5.1.

There is a satisfiable ${\mathrm{\Pi }}_2$ sentence $\phi$ extending the axioms of trees such that every model of $\phi$ has a ${\mathrm{\Pi }}_3$ Scott sentence but no ${\mathrm{\Sigma }}_3$ Scott sentence.

Proof.

Consider a language with the parent relation $P$, constant symbol $r$ for the root, and unary predicates $R_i$ for each . One may think of the $R_i$ as colours, and we call a tree with the additional relations $R_i$ a coloured tree. We can transform any coloured tree into a tree, and these two structures are effectively ${\mathrm{\Sigma }}_1$ bi-interpretable with the bi-interpretation being uniform among all coloured trees. (See [12] or [HMM+17, HMM18] for background on infinitary bi-interpretability.) Thus we can prove the theorem by constructing such an example of coloured trees. The transformation can be defined recursively. Given a coloured tree $T$ with root $r$, let $a_0,a_1,\mathrm{\dots }$ be the children of $r$, and let $T_i$ be the coloured subtrees of $T$ below $a_i$.

$$ra0a1a2⋯T0T1T2.$$

Let $n$ be the colour of $r$. Then $\mathrm{\Phi }(T)$ will be the following tree.

$$ra0a1a2⋯Φ⁢(T0)Φ⁢(T1)Φ⁢(T2)length n+1.$$

It is straightforward to see that each of the colours are both universally and existentially definable in $\mathrm{\Phi }(T)$, and $T$ and $\mathrm{\Phi }(T)$ are infinitary bi-interpretable. For the remainder of the proof we work with coloured trees.

The sentence $\phi$ will say that the $P$ is the parent relation of a tree with root $r$. The sentence $\phi$ will also say that the tree has height 1 ($\forall xx=r\vee P(x)=r$) and is infinite (${\exists }^{\mathrm{\infty }}xP(x)=r$), as well as that any two children of the root differ on some colour () and that each finite set of colours is realized. This last condition can be expressed as

where ${(\neg )}^1$ is just $\neg$ and ${(\neg )}^0$ is ignored. Thus $\phi$ is ${\mathrm{\Pi }}_2$ and one can show it is consistent using standard arguments.

By [Mon15] it suffices to show that if $T\vDash \phi$ then each automorphism orbit is ${\mathrm{\Sigma }}_2$ definable but there is some automorphism orbit that is not ${\mathrm{\Sigma }}_1$ definable, even with parameters. Let $\overline{a}\in T$. For let ${\sigma }_i\in 2^{\omega }$ be such that . Then the formula defines $\overline{a}$, and this is a ${\mathrm{\Pi }}_1$ formula.

For the sake of contradiction suppose every automorphism orbit is ${\mathrm{\Sigma }}_1$-definable with parameters $\overline{p}\in T$. Since $T$ is infinite, we may pick some $b\in T$ that is not the root and not part of $\overline{p}$. Suppose $\exists \overline{y}\psi (x,\overline{y},\overline{p})$ is a ${\mathrm{\Sigma }}_1$ formula defining $b$, where $\psi$ is a first order quantifier free formula. Let $T\vDash \psi (b,\overline{c},\overline{p})$ where $\overline{c}\in T$ and let $R_0,\mathrm{\dots },R_{n-1}$ be the only unary predicates that appears in $\psi$. Because every finite choice of colours appears and every vertex receives different colours, there is a $b^{\prime }\in T$ that is not $b$, the root, nor one of $\overline{p}$, but agrees with $b$ on the first $n$ colours, i.e., . If ${\overline{c}}^{\prime }$ is $\overline{c}$ with changing the appearances of $b$ to $b^{\prime }$, then $(b,\overline{c},\overline{p})$ and $(b^{\prime },{\overline{c}}^{\prime },\overline{p})$ have the same first order quantifier free diagram if we restrict the colours to $R_0,\mathrm{\dots },R_{n-1}$. Thus $T\vDash \psi (b^{\prime },{\overline{c}}^{\prime },\overline{p})$, meaning $b\cong b^{\prime }$. However, since $b$ and $b^{\prime }$ disagree on one of the colours $R_i$ (for $i\ge n$), this is a contradiction. ∎