1 Introduction
Scott [Reference Scott, Addison, Henkin and Tarski17] showed that for a countable language L every countable structure can be described up to isomorphism among countable structures by a sentence of the infinitary logic
$L_{\omega _1 \omega }$
. Such a sentence is called a Scott sentence of the structure. The standard proof uses back-and-forth relations and the key step is to show that for each countable structure
$\mathcal {A}$
there is an ordinal
$\alpha $
such that any two tuples which are
$\alpha $
-back-and-forth-equivalent are actually in the same automorphism orbit. The least such
$\alpha $
is a measure of the internal complexity of the structure and is one definition of the Scott rank of the structure.
Annoyingly, there are many similar but non-equivalent definitions of Scott rank in the literature, most of which agree up to a small factor. In an attempt to standardize the notion of Scott rank, Montalbán introduced a definition which connects the internal complexity of the automorphism orbits with the external complexity of describing the structure via a Scott sentence. Scott sentences, as with all formulas of
$L_{\omega _1 \omega }$
, can be classified up to equivalence by the number of quantifier alternations, where infinite conjunctions are viewed as universal quantifiers and infinite disjunctions as existential quantifiers. The
$\Sigma _n$
sentences have n alternations of quantifiers, beginning with existential quantifiers; the
$\Pi _n$
sentences are similar but begin with a universal quantifier. The hierarchy continues in the natural way through the transfinite.
Definition 1.1 (Montalbán [Reference Montalbán14])
The Scott rank of a countable structure
$\mathcal {A}$
is the least
$\alpha $
such that
$\mathcal {A}$
has a
$\Pi _{\alpha + 1}$
Scott sentence.
This definition is robust in the sense that there are many equivalent characterizations.
Theorem 1.2 (Montalbán [Reference Montalbán14])
Let
$\mathcal {A}$
be a countable structure, and
$\alpha $
a countable ordinal. The following are equivalent:
-
1.
$\mathcal {A}$
has a
$\Pi _{\alpha +1}$
Scott sentence. -
2. Every automorphism orbit in
$\mathcal {A}$
is
$\Sigma _{\alpha }$
-definable without parameters. -
3.
$\mathcal {A}$
is uniformly (boldface)
$\boldsymbol {\Delta }^0_{\alpha }$
-categorical.
The Scott ranks assigned by this definition are again not too different from the Scott ranks assigned by the definitions using back-and-forth relations.
Scott rank is a coarse measure of complexity in that it does not differentiate between, for example, whether the simplest Scott sentence for a structure is
$\Sigma _{\alpha }$
or
$\Pi _{\alpha + 1}$
; in either case, the Scott rank is
$\alpha $
. Recently there have been a number of interesting results at this finer level of detail. We make the following informal definition:
Definition 1.3. The Scott complexity of a countable structure
$\mathcal {A}$
is the least complexity of a Scott sentence for
$\mathcal {A}$
.
Now,
$\Sigma _{\alpha }$
and
$\Pi _{\alpha }$
are not the only possible complexities of a sentence of
$L_{\omega _1 \omega }$
. For example [Reference Carson, Harizanov, Knight, Lange, McCoy, Morozov, Quinn, Safranski and Wallbaum2, Reference Ho5, Reference Harrison-Trainor and Ho6, Reference Knight and Saraph10], many finitely generated groups, including all abelian groups and free groups, have a Scott sentence which is the conjunction of a
$\Sigma _2$
and a
$\Pi _2$
sentence, but no simpler sentence. We call such a sentence a
$\mathrm {d-}\Sigma _2$
sentence (with “d” standing for “difference”); so
$\mathrm {d-}\Sigma _2$
should also be a possible Scott complexity.
There are also other types of
$L_{\omega _1 \omega }$
formulas. For example, a formula might be the disjunction of a
$\Sigma _{\alpha }$
formula
$\varphi $
and
$\Pi _{\alpha }$
formula
$\psi $
. However, such a formula cannot be the simplest Scott sentence of a structure
$\mathcal {A}$
, for if
$\varphi \vee \psi $
is a Scott sentence for
$\mathcal {A}$
, then
$\mathcal {A} \models \varphi \vee \psi $
and so either
$\mathcal {A} \models \varphi $
in which case
$\varphi $
is a
$\Sigma _{\alpha }$
Scott sentence for
$\mathcal {A}$
, or
$\mathcal {A} \models \psi $
in which case
$\psi $
is a
$\Pi _{\alpha }$
Scott sentence for
$\mathcal {A}$
. In practice, it seems that
$\Sigma _{\alpha }$
,
$\Pi _{\alpha }$
, and
$\mathrm {d-}\Sigma _{\alpha }$
are the only possible Scott complexities. These are arranged from the simplest on the left to most complex on the right as follows:
Moreover, A. Miller [Reference Miller13] showed that if a structure has both a
$\Sigma _{\alpha }$
and a
$\Pi _{\alpha }$
Scott sentence, then it has a
$\mathrm {d-}\Sigma _{\beta }$
Scott sentence for some
$\beta < \alpha $
.
Are these the only possible Scott complexities? The problem is that there is no formal notion of what it means to be “a complexity class” of
$L_{\omega _1 \omega }$
formulas. However, it is well-known that there are connections between the Scott sentences of a structure
$\mathcal {A}$
and the topological complexity of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
, the set of isomorphic copies of
$\mathcal {A}$
with domain
$\omega $
, viewed as a subset of Baire space. For any reasonably robust notion of the complexity of
$L_{\omega _1 \omega }$
formulas, the complexity of a Scott sentence for a structure
$\mathcal {A}$
is in correspondence, via Vaught’s version of the López–Escobar theorem, with the topological complexity of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
. The fact that
$\mathcal {A}$
has a Scott sentence implies that
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is always Borel. The topological complexity of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
can be measured by its Wadge degree. This motivates the following formal definition:
Definition 1.4. The Scott complexity of a structure
$\mathcal {A}$
is the Wadge degree of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
.
In the first part of this paper, we show that the Scott complexity of a countable structure must be one of
$\boldsymbol {\Pi }^0_{\alpha }$
,
$\boldsymbol {\Sigma }^0_{\alpha }$
, and
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\alpha }$
; so, for example, if
$\mathcal {A}$
has a
$\Pi _{\alpha }$
Scott sentence but no
$\Sigma _{\alpha }$
Scott sentence, then
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\boldsymbol {\Pi }^0_{\alpha }$
-complete under Wadge reducibility.
By Vaught’s theorem, we associate each of these Wadge degrees of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
with the complexity class of the corresponding Scott sentence for
$\mathcal {A}$
, e.g., identifying the Wadge degree
$\boldsymbol {\Pi }^0_{\alpha }$
with the complexity
$\Pi _{\alpha }$
. So we need not consider Scott sentences of any complexity other than
$\Sigma _{\alpha }$
,
$\Pi _{\alpha }$
, and
$\mathrm {d-}\Sigma _{\alpha }$
. Under the natural correspondence between Wadge degrees and complexities of Scott sentences, we can also define:
Definition 1.5. The Scott complexity of a structure
$\mathcal {A}$
is the least complexity, from among
$\Sigma _{\alpha }$
,
$\Pi _{\alpha }$
, and
$\mathrm {d-}\Sigma _{\alpha }$
, of a Scott sentence for
$\mathcal {A}$
.
In the second part of the paper, we will give examples of structures with particular Scott complexities in order to give a complete classification of the possible Scott complexities. A. Miller [Reference Miller13] has given a number of examples, but the problem of constructing a structure of Scott complexity
$\Sigma _{\lambda + 1}$
for
$\lambda $
a limit ordinal was still open. We give such an example in Theorem 4.1. He also showed that for a language with no function symbols, if a structure has a
$\Sigma _2$
Scott sentence, then it has a
$\mathrm {d-}\Sigma _1$
Scott sentence. We give a proof of this fact for all languages in Theorem 5.1.
The complete classification is as follows:
Theorem 1.6. The possible Scott complexities of countable structures
$\mathcal {A}$
are:
-
1.
$\Pi _{\alpha }$
for
$\alpha \geq 1$
, -
2.
$\Sigma _{\alpha }$
for
$\alpha \geq 3$
a successor ordinal, and -
3.
$\mathrm {d-}\Sigma ^0_{\alpha }$
for
$\alpha \geq 1$
a successor ordinal.
There is a countable structure with each of these Wadge degrees.
Proof In Theorem 2.6 we show that the Scott complexity of a structure must be one of
$\Pi _{\alpha }$
,
$\Sigma _{\alpha }$
(for
$\alpha $
a non-limit), and
$\mathrm {d-}\Sigma _{\alpha }$
(for
$\alpha $
a non-limit). A. Miller [Reference Miller13] showed that no structure has a
$\Sigma _1$
Scott sentence. In Theorem 5.1 we show that
$\Sigma _2$
cannot be the Scott complexity of a countable structure.
A. Miller [Reference Miller13, Section 4] gave examples of structures which have Scott complexity
$\Pi _{\alpha }$
for
$\alpha \geq 1$
and
$\Sigma _{\alpha }$
and
$\mathrm {d-}\Sigma _{\alpha }$
for
$\alpha \geq 3$
if
$\alpha $
is not a limit ordinal or the successor of a limit ordinal. The group
$\mathbb {Z}$
has Scott complexity
$\mathrm {d-}\Sigma _2$
. An infinite structure with a single unary operator holding of exactly one element has Scott complexity
$\mathrm {d-}\Sigma _1$
. In Theorem 4.1, we give examples of structures of Scott complexity
$\Sigma _{\lambda +1}$
for
$\lambda $
a successor ordinal. Then the disjoint union of such a structure and a structure of Scott complexity
$\Pi _{\lambda +1}$
has Scott complexity
$\mathrm {d-}\Sigma _{\lambda +1}$
. ⊣
In the last part of this paper, we will investigate the Scott complexity of computable structures of high Scott rank and give a new example of such structures. We will see that some important properties of structures of high Scott rank can be rephrased in terms of Scott complexity.
If
$\mathcal {A}$
is a countable structure, then the Scott rank of
$\mathcal {A}$
is at most
$\omega _1^{\mathcal {A}} + 1$
[Reference Nadel16]; equivalently, the Scott complexity of
$\mathcal {A}$
is at most
$\Pi _{\omega _1^{\mathcal {A}}+2}$
. We say that
$\mathcal {A}$
has high Scott rank if it has Scott rank
$\geq \omega _1^{\mathcal {A}}$
; equivalently,
$\mathcal {A}$
has Scott complexity at least
$\Pi _{\omega _1^{\mathcal {A}}}$
, so we say:
Definition 1.7. A structure
$\mathcal {A}$
has high Scott complexity/rank if it has Scott complexity at least
$\Pi _{\omega _1^{\mathcal {A}}}$
, or equivalently, it has Scott rank
$\geq \omega _1^{\mathcal {A}}$
.
There are two possible Scott ranks for a structure of high Scott rank, namely
$\omega _1^{\mathcal {A}}$
and
$\omega _1^{\mathcal {A}}+1$
. There are examples of each of these [Reference Harrison4, Reference Knight and Millar9]. However, there are five possible high Scott complexities:
$\Pi _{\omega _1^{\mathcal {A}}}$
,
$\Pi _{\omega _1^{\mathcal {A}}+1}$
,
$\Sigma _{\omega _1^{\mathcal {A}}+1}$
,
$\mathrm {d-}\Pi _{\omega _1^{\mathcal {A}}+1}$
, and
$\Pi _{\omega _1^{\mathcal {A}}+2}$
. Of these,
$\Pi _{\omega _1^{\mathcal {A}}}$
and
$\Pi _{\omega _1^{\mathcal {A}}+1}$
correspond to Scott rank
$\omega _1^{\mathcal {A}}$
, and
$\Sigma _{\omega _1^{\mathcal {A}}+1}$
,
$\mathrm {d-}\Pi _{\omega _1^{\mathcal {A}}+1}$
, and
$\Pi _{\omega _1^{\mathcal {A}}+2}$
corresponds to Scott rank
$\omega _1^{\mathcal {A}}+1$
. We will show that all of these possibilities can be achieved:
Theorem 1.8. There are computable structures of all possible high Scott complexities:
$\Pi _{\omega _1^{CK}}$
,
$\Pi _{\omega _1^{CK}+1}$
,
$\Sigma _{\omega _1^{CK}+1}$
,
$\mathrm {d-}\Pi _{\omega _1^{CK}+1}$
, and
$\Pi _{\omega _1^{CK}+2}$
.
The standard example of a structure of Scott rank
$\omega _1^{CK}+1$
, the Harrison linear order
$\omega _1^{CK} \cdot (1 + \mathbb {Q})$
, has Scott complexity
$\Pi _{\omega _1^{CK}+2}$
. There are also known examples of computable structures with Scott complexity
$\Pi _{\omega _1^{CK}}$
and
$\Pi _{\omega _1^{CK}+1}$
. This is due to the following fact which we prove in §3.
Proposition 1.9. Let
$\mathcal {A}$
be a computable structure of high Scott complexity with a
$\Pi _{\omega _1^{CK}+1}$
Scott sentence (i.e., with Scott rank
$\omega _1^{CK}$
). Then:
-
• If the computable infinitary theory of
$\mathcal {A}$
is
$\aleph _0$
-categorical, then
$\mathcal {A}$
has Scott complexity
$\Pi _{\omega _1^{CK}}$
. -
• Otherwise,
$\mathcal {A}$
has Scott complexity
$\Pi _{\omega _1^{CK}+1}$
.
The standard examples of computable structures of Scott rank
$\omega _1^{CK}$
, constructed by Knight and Millar strengthening a construction of Makkai [Reference Knight and Millar9, Reference Makkai12], were known to have an
$\aleph _0$
-categorical computable infinitary theory and hence have Scott complexity
$\Pi _{\omega _1^{CK}}$
. For some time the most important open question about structures of high Scott rank was whether there is a computable structure of Scott rank
$\omega _1^{CK}$
whose computable infinitary theory is not
$\aleph _0$
-categorical—which, by the corollary above, is exactly the same as asking for a computable structure of Scott complexity
$\Pi _{\omega _1^{CK}+1}$
. Eventually Harrison-Trainor, Igusa, and Knight [Reference Harrison-Trainor, Igusa and Knight7] provided such an example.
Another important open question about structures of high Scott rank, which we answer in this paper, is whether there is a structure of Scott rank
$\omega _1^{CK}+1$
which becomes a structure of Scott rank
$\omega _1^{CK}$
after naming finitely many constants. This is equivalent to asking whether there is a computable structure of Scott complexity
$\Sigma _{\omega _1^{CK}+1}$
or
$\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$
. The equivalence follows from the following fact, which is less obvious than it seems:
Proposition 1.10. Let
$\mathcal {A}$
be a countable structure. Then:
-
1.
$\mathcal {A}$
has a
$\Sigma _{\alpha +1}$
Scott sentence if and only if for some
$\bar {c} \in \mathcal {A}$
,
$(\mathcal {A},\bar {c})$
has a
$\Pi _{\alpha }$
Scott sentence. -
2.
$\mathcal {A}$
has a
$\mathrm {d-}\Sigma _{\alpha }$
Scott sentence if and only if for some
$\bar {c} \in \mathcal {A}$
,
$(\mathcal {A},\bar {c})$
has a
$\Pi _{\alpha }$
Scott sentence and the automorphism orbit of
$\bar {c}$
is
$\Sigma _{\alpha }$
-definable.
This theorem was first stated without proof by Montalbán [Reference Montalbán14], but the proof was more subtle than it appeared at first; it was proved for
$\Sigma _3$
sentences in [Reference Montalbán, Day, Fellows, Greenberg, Khoussainov, Melnikov and Rosamond15]. We give a proof here.
The Harrison linear order has Scott complexity
$\Pi _{\omega _1^{CK} + 2}$
because after naming finitely many constants it still has Scott rank
$\omega _1^{CK}+1$
. We construct new examples of computable structures of Scott complexity
$\Sigma _{\omega _1^{CK}+1}$
and
$\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$
in §4.
Theorem 1.11. There is a computable structure of Scott rank
$\omega _1^{CK} +1$
which, after naming finitely many constants, has Scott rank
$\omega _1^{CK}$
.
2 The possible complexities of structures
2.1 Wadge degrees
The Wadge degrees were introduced by Wadge in his PhD thesis [Reference Wadge21] to measure the topological complexity of subsets of Baire space
$\omega ^{\omega }$
under continuous reductions.
Definition 2.1 (Wadge)
Let A and B be subsets of Baire space
$\omega ^{\omega }$
. We say that A is Wadge reducible to B, and write
$A \leq _W B$
, if there is a continuous function f on
$\omega ^{\omega }$
with
$A = f^{-1}[B]$
, i.e.,
$$ \begin{align*} x \in A \Longleftrightarrow f(x) \in B . \end{align*} $$
The equivalence classes under this pre-order are called the Wadge degrees; we write
$[A]_W$
for the Wadge degree of A. The Wadge hierarchy is the set of Wadge degrees under continuous reductions.
With enough determinacy, the Wadge hierarchy is very well-behaved; it is well-founded and almost totally ordered (in the sense that any anti-chain has size at most two).
Theorem 2.2 (Martin and Monk, AD, see [Reference Van Wesep, Kechris and Moschovakis20])
The Wadge order is well-founded.
Theorem 2.3 (Wadge’s Lemma, AD, [Reference Wadge21])
Given
$A,B \subseteq \omega ^{\omega }$
, either
$A \leq _W B$
or
$B \leq _W \omega ^{\omega } - A$
.
Since determinacy for Borel sets is provable in ZFC, this theorem holds in ZFC for such sets.
In general, for each of the pointclasses
$\Gamma $
from among
$\boldsymbol {\Sigma }^0_{\alpha }$
,
$\boldsymbol {\Pi }^0_{\alpha }$
,
$\boldsymbol {\Delta }^0_{\alpha }$
,
$\mathrm {d-}\boldsymbol {\Sigma }^0_{\alpha }$
, and other pointclasses arising from the Borel or difference hierarchies, if A is Wadge-reducible to a set in
$\Gamma $
, then A itself is in
$\Gamma $
; and moreover, there is a
$\Gamma $
-complete set. We denote by
$\Gamma $
the Wadge degree of a
$\Gamma $
-complete set. So, for example,
$\boldsymbol {\Sigma }^0_1$
is the Wadge degree of open, but not clopen, sets.
2.2 The Lopez-Escobar theorem
Fixing a language
$\mathcal {L}$
, we work in the Polish space
$ \operatorname {\mathrm {Mod}}(\mathcal {L})$
of structures in the language
$\mathcal {L}$
. Given a structure
$\mathcal {A}$
, we can view the set
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
of isomorphic copies of
$\mathcal {A}$
as a subset of Baire space
$\omega ^{\omega }$
. The syntactic form of a Scott sentence for
$\mathcal {A}$
puts a topological restriction on
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
. For example, if
$\mathcal {A}$
has a
$\Sigma _1$
Scott sentence, then
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is an open (
$\boldsymbol {\Sigma }^0_1$
) subset of
$\omega ^{\omega }$
. More generally, if
$\mathcal {A}$
has a
$\Sigma _{\alpha }$
(respectively
$\Pi _{\alpha }$
) Scott sentence, then
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\boldsymbol {\Sigma }^0_{\alpha }$
(respectively
$\boldsymbol {\Pi }^0_{\alpha }$
) in the hierarchy of Borel sets. Since every structure has a Scott sentence,
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is always Borel. By Vaught’s strengthening of the Lopez-Escobar [Reference Lopez-Escobar11] theorem, the correspondence of complexities also reverses.
Theorem 2.4 (Vaught [Reference Vaught18])
Let
$\mathbb {K}$
be a subclass of
$ \operatorname {\mathrm {Mod}}(\mathcal {L})$
which is closed under isomorphism. Then
$\mathbb {K}$
is
$\boldsymbol {\Sigma }^0_{\alpha }$
(respectively
$\boldsymbol {\Pi }^0_{\alpha }$
,
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\alpha }$
,
$\neg \mathbf {d-}\boldsymbol {\Sigma }^0_{\alpha }$
) in the Borel hierarchy if and only if
$\mathbb {K}$
is axiomatized by an infinitary
$\Sigma _{\alpha }$
(respectively,
$\Pi _{\alpha }$
,
$\mathrm {d-}\Sigma _{\alpha }$
,
$\neg \mathrm {d-}\Sigma _{\alpha }$
) sentence.
This theorem was later effectivized by Vanden Boom [Reference Vanden Boom19]. The inclusion of
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\alpha }$
and
$\neg \mathbf {d-}\boldsymbol {\Sigma }^0_{\alpha }$
in this theorem was not originally proved by Vaught, but it is well-known and not hard to show, e.g., by the forcing argument used by Vanden Boom. Moreover, one imagines that the theorem would extend to any reasonably defined class.
2.3 Possible Scott complexities
We will also use the following fact which has a short proof due to Alvir.
Theorem 2.5 (A. Miller [Reference Miller13])
Let
$\mathcal {A}$
be a countable structure. Then if
$\mathcal {A}$
has both a
$\Sigma _{\alpha }$
and a
$\Pi _{\alpha }$
Scott sentence, it has a
$\mathrm {d-}\Sigma _{\beta }$
Scott sentence for some
$\beta < \alpha $
.
Proof If
$\alpha $
is a limit ordinal, then the theorem is trivial: one of the disjuncts of the
$\Sigma _{\alpha }$
Scott sentence is true in
$\mathcal {A}$
, and this is a
$\Sigma _{\beta }$
Scott sentence for
$\mathcal {A}$
,
$\beta < \alpha $
. Otherwise, let
$\exists \bar {x} \Phi (\bar {x})$
be a
$\Sigma _{\alpha }$
Scott sentence for
$\mathcal {A}$
, with
$\Phi $
being
$\Pi _{\alpha -1}$
. Let
$\bar {a}$
be such that
$\mathcal {A} \models \Phi (\bar {a})$
. Since
$\mathcal {A}$
has a
$\Pi _{\alpha }$
Scott sentence, by Theorem 1.2 the automorphism orbit of
$\bar {a}$
is definable by a
$\Sigma _{\alpha -1}$
formula; call this formula
$\psi _{\bar {a}}(\bar {x})$
. Then
$\exists \bar {x} \psi _{\bar {a}} (\bar {x}) \land \forall \bar {x} \left ( \psi _{\bar {a}}(\bar {x}) \rightarrow \Phi (\bar {x}) \right )$
is a
$\mathrm {d-}\Sigma _{\alpha -1}$
Scott sentence for
$\mathcal {A}$
. ⊣
We can now show:
Theorem 2.6. The only possible Wadge degrees of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
for countable structures
$\mathcal {A}$
are
$\boldsymbol {\Pi }^0_{\alpha }$
(for any
$\alpha $
),
$\boldsymbol {\Sigma }^0_{\alpha }$
(for
$\alpha $
a non-limit), and
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\alpha }$
(for
$\alpha $
a non-limit).
Proof We will not have to use the Axiom of Determinacy because for any structure
$\mathcal {A}$
,
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is Borel.
Let
$\alpha $
be least such that
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\boldsymbol {\Sigma }^0_{\alpha }$
. First note that
$\alpha $
cannot be a limit ordinal; if it were, then
$\mathcal {A}$
would have a
$\Sigma _{\alpha }$
Scott sentence, and one of those disjuncts would be a
$\Sigma _{\beta }$
Scott sentence for
$\mathcal {A}$
for some
$\beta < \alpha $
. If the Wadge degree of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\boldsymbol {\Sigma }^0_{\alpha }$
, then we are done. Otherwise, by Wadge’s lemma,
$\boldsymbol {\Sigma }^0_{\alpha } \nleq _W [ \operatorname {\mathrm {Iso}}(\mathcal {A})]_W$
and so
$[ \operatorname {\mathrm {Iso}}(\mathcal {A})]_W \leq _W \boldsymbol {\Pi }^0_{\alpha }$
. Thus
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is both
$\boldsymbol {\Pi }^0_{\alpha }$
and
$\boldsymbol {\Sigma }^0_{\alpha }$
; by Vaught’s theorem,
$\mathcal {A}$
has both a
$\Sigma _{\alpha }$
and a
$\Pi _{\alpha }$
Scott sentence. Then, by Theorem 2.5,
$\mathcal {A}$
has a
$\mathrm {d-}\Sigma _{\beta }$
Scott sentence for some
$\beta < \alpha $
.
So now, assume that
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\beta }$
but not
$\boldsymbol {\Sigma }^0_{\beta }$
. First, if
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\boldsymbol {\Pi }^0_{\beta }$
, then we claim that
$[ \operatorname {\mathrm {Iso}}(\mathcal {A})]_W =_W \boldsymbol {\Pi }^0_{\beta }$
. Indeed, if
$\boldsymbol {\Pi }^0_{\beta } \nleq _W [ \operatorname {\mathrm {Iso}}(\mathcal {A})]_W$
, then by Wadge’s lemma,
$[ \operatorname {\mathrm {Iso}}(\mathcal {A})]_W \leq _W \boldsymbol {\Sigma }^0_{\beta }$
, and we know that this is not the case.
Finally, we are left with the case that
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\beta }$
but neither
$\boldsymbol {\Sigma }^0_{\beta }$
nor
$\boldsymbol {\Pi }^0_{\beta }$
. We can argue as before that
$\beta $
cannot be a limit ordinal (or
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
would be
$\boldsymbol {\Pi }^0_{\beta }$
). We argue by contradiction that the Wadge degree of
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\beta }$
. If
$\mathbf {d-}\boldsymbol {\Sigma }^0_{\beta } \nleq _W [ \operatorname {\mathrm {Iso}}(\mathcal {A})]_W$
then by Wadge’s lemma
$[ \operatorname {\mathrm {Iso}}(\mathcal {A})]_W \leq _W \neg \mathbf {d-}\boldsymbol {\Sigma }^0_{\beta }$
where
$\neg \mathbf {d-}\boldsymbol {\Sigma }^0_{\beta }$
is the subsets of Baire space which are a union of a
$\Sigma ^0_{\beta }$
set and a
$\Pi ^0_{\beta }$
set. So
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is of this form, and by Vaught’s theorem, it has a Scott sentence which is a disjunction of a
$\Sigma _{\beta }$
and a
$\Pi _{\beta }$
sentence. But
$\mathcal {A}$
, being a single structure, must satisfy one of these two disjuncts, and that disjunct is by itself a Scott sentence for
$\mathcal {A}$
. So
$ \operatorname {\mathrm {Iso}}(\mathcal {A})$
is either
$\boldsymbol {\Sigma }^0_{\beta }$
or
$\boldsymbol {\Pi }^0_{\beta }$
, a contradiction. ⊣
So—by the correspondence between the complexity of Scott sentences and Wadge degrees—the only possible Scott complexities are
$\Sigma _{\alpha }$
,
$\Pi _{\alpha }$
, and
$\mathrm {d-}\Sigma _{\alpha }$
. Note that this was all non-effective, and we do not know what happens in the lightface case.
3 Characterizations of structures of high Scott complexity
In this section we give the proofs of Propositions 1.9 and 1.10. We will need the back-and-forth relations. We will use the symmetric back-and-forth relations: given
$\bar {a} \in \mathcal {A}$
and
$\bar {b} \in \mathcal {B}$
, we define
$(\mathcal {A},\bar {a}) \equiv _0 (\mathcal {B},\bar {b})$
if
$\bar {a}$
and
$\bar {b}$
have the same atomic type, and
$(\mathcal {A},\bar {a}) \equiv _{\alpha } (\mathcal {B},\bar {b})$
if for every
$\bar {a}'$
and
$\beta < \alpha $
there is
$\bar {b}'$
such that
$(\mathcal {A},\bar {a}\bar {a}') \equiv _{\alpha } (\mathcal {B},\bar {b}\bar {b}')$
, and for every
$\bar {b}'$
and
$\beta < \alpha $
there is
$\bar {a}'$
such that
$(\mathcal {A},\bar {a}\bar {a}') \equiv _{\alpha } (\mathcal {B},\bar {b}\bar {b}')$
.
We also define
$\mathcal {A} \leq _{\alpha } \mathcal {B}$
if every
$\Pi _{\alpha }$
sentence true of
$\mathcal {A}$
is true of
$\mathcal {B}$
. We have that
$\mathcal {A} \equiv _{\alpha } \mathcal {B}$
implies
$\mathcal {A} \leq _{\alpha } \mathcal {B}$
and
$\mathcal {B} \leq _{\alpha } \mathcal {A}$
, but not vice versa. Note that this is different from being an
$\alpha $
-elementary substructure, which is sometimes denoted using the same notation; to have
$\mathcal {A} \leq _{\alpha } \mathcal {B}$
does not require that
$\mathcal {A}$
be a substructure of
$\mathcal {B}$
.
Proposition 3.1. Let
$\mathcal {A}$
be a countable structure and
$\alpha $
a countable limit ordinal. The following are equivalent:
-
1.
$\mathcal {A}$
has a
$\Pi _{\alpha }$
Scott sentence. -
2. Whenever
$\mathcal {A} \leq _{\alpha } \mathcal {B}$
for a countable structure
$\mathcal {B}$
,
$\mathcal {A} \cong \mathcal {B}$
.
Proof For
$1 \Rightarrow 2$
, if
$\mathcal {A} \leq _{\alpha } \mathcal {B}$
then every
$\Pi _{\alpha }$
sentence true of
$\mathcal {A}$
(including the Scott sentence for
$\mathcal {A}$
) is true of
$\mathcal {B}$
; thus
$\mathcal {B} \cong \mathcal {A}$
.
For
$2 \Rightarrow 1$
we use the standard technique for showing the back and forth relations are definable, proceeding by induction on
$\beta $
. For each
$\bar {a} \in A$
, let
$\varphi ^1_{\bar {a}}(\bar {x})$
be the conjunction of all
$\Pi _1$
and
$\Sigma _1$
formulas which are true of
$\bar {a}$
in A. For
$\beta> 1$
define
Note that we may assume
$|\bar {a}| = |\bar {x}|$
. By induction, we can show that
$$ \begin{align*} (\mathcal{B},\bar{b}) \models \varphi^{\beta}_{\bar{a}} \Longleftrightarrow (\mathcal{A},\bar{a}) \equiv_{\beta} (\mathcal{B},\bar{b}). \end{align*} $$
It also follows by induction on
$\beta \geq 1$
that
$\varphi _{\bar {a}}^{\beta }$
is a
$\Pi _{2 \cdot \beta }$
formula.
We claim that
is a
$\Pi _{\alpha }$
Scott sentence for
$\mathcal {A}$
. It is
$\Pi _{\alpha }$
because
$2 \cdot \beta < \alpha $
when
$0< \beta < \alpha $
and
$\alpha $
is a limit ordinal. If
$\mathcal {B} \models \Phi $
, then
$\mathcal {A} \equiv _{\beta } \mathcal {B}$
for all
$0 < \beta < \alpha $
, and so
$\mathcal {A} \leq _{\alpha } \mathcal {B}$
since
$\alpha $
is a limit ordinal; hence
$\mathcal {B} \cong \mathcal {A}$
.⊣
Proposition 1.9. Let
$\mathcal {A}$
be a computable structure of high Scott complexity with a
$\Pi _{\omega _1^{CK}+1}$
Scott sentence (i.e., with Scott rank
$\omega _1^{CK}$
). Then:
-
• If the computable infinitary theory of
$\mathcal {A}$
is
$\aleph _0$
-categorical, then
$\mathcal {A}$
has Scott complexity
$\Pi _{\omega _1^{CK}}$
. -
• Otherwise,
$\mathcal {A}$
has Scott complexity
$\Pi _{\omega _1^{CK}+1}$
.
Proof Since
$\mathcal {A}$
has high Scott complexity and has a
$\Pi _{\omega _1^{CK}+1}$
Scott sentence, the only possible Scott complexities are
$\Pi _{\omega _1^{CK}}$
and
$\Pi _{\omega _1^{CK}+1}$
. So it suffices to show that
$\mathcal {A}$
has a
$\Pi _{\omega _1^{CK}}$
Scott sentence if and only if the computable infinitary theory of
$\mathcal {A}$
is
$\aleph _0$
-categorical.
If the computable infinitary theory of
$\mathcal {A}$
is
$\aleph _0$
-categorical, then the conjunction of these sentences is a
$\Pi _{\omega _1^{CK}}$
Scott sentence for
$\mathcal {A}$
. On the other hand, suppose that
$\mathcal {A}$
has a
$\Pi _{\omega _1^{CK}}$
Scott sentence. Then by Proposition 3.1, whenever
$\mathcal {A} \leq _{\omega _1^{CK}} \mathcal {B}$
for a countable structure
$\mathcal {B}$
,
$\mathcal {A} \cong \mathcal {B}$
. In the proof of Proposition 3.1 we constructed for each
$\alpha < \omega _1^{CK}$
a computable
$\Pi _{2 \cdot \alpha }$
sentence
$\varphi _{\alpha }$
such that
$$ \begin{align*} \mathcal{B} \models \varphi_{\alpha} \Longleftrightarrow \mathcal{A} \equiv_{\alpha} \mathcal{B}. \end{align*} $$
Thus if
$\mathcal {B}$
satisfies the computable infinitary theory of
$\mathcal {A}$
, then for all
$\alpha < \omega _1^{CK}$
we have
$\mathcal {A} \equiv _{\alpha } \mathcal {B}$
, hence
$\mathcal {A} \leq _{\omega _1^{CK}} \mathcal {B}$
, and so
$\mathcal {A} \cong \mathcal {B}$
.⊣
Part (1) of the next theorem was first stated by Montálban for successor ordinals in [Reference Montalbán14]. The original proof proceeds by observing that the following are equivalent:
-
1. A is
$\Delta ^0_{\alpha }$
-categorical on a cone. -
2. A has a
$\Sigma _{\alpha + 2}$
Scott sentence. -
3. There is a tuple
$\bar {c}$
such that
$(A,\bar {c})$
has a
$\Pi _{\alpha + 1}$
Scott sentence.
That (1) and (3) are equivalent is obtained by considering Theorem 10.14 of [Reference Ash and Knight1] on a cone. Given this equivalence, the proof of
$(1) \Rightarrow (2)$
is immediate. After noticing that the proof of
$(2) \Rightarrow (1)$
was not trivial, Montalbán gave a proof of the fact (for
$\alpha = 1$
) in [Reference Montalbán, Day, Fellows, Greenberg, Khoussainov, Melnikov and Rosamond15] via Henkin construction. There is not yet a published proof in the literature for
$\alpha> 1$
, so we give a proof here; our proof uses Theorem 1.2.
Lemma 3.2. Let
$\mathcal {A}$
be a structure. If the automorphism orbit of every tuple in
$\mathcal {A}$
is definable by a
$\Sigma _{\alpha }$
formula, then each such orbit is definable by a
$\Pi _{\alpha }$
formula.
Proof Fix, for each
$\bar {a} \in \mathcal {A}$
, a
$\Sigma _{\alpha }$
definition
$\varphi _{\bar {a}}$
for
$\bar {a}$
. Given a tuple
$\bar {c}$
, the
$\Pi _{\alpha }$
formula
defines the orbit of
$\bar {c}$
.⊣
Proposition 1.10. Let
$\mathcal {A}$
be a countable structure. Then:
-
1.
$\mathcal {A}$
has a
$\Sigma _{\alpha +1}$
Scott sentence if and only if for some
$\bar {c} \in \mathcal {A}$
,
$(\mathcal {A},\bar {c})$
has a
$\Pi _{\alpha }$
Scott sentence. -
2.
$\mathcal {A}$
has a
$\mathrm {d-}\Sigma _{\alpha }$
Scott sentence if and only if for some
$\bar {c} \in \mathcal {A}$
,
$(\mathcal {A},\bar {c})$
has a
$\Pi _{\alpha }$
Scott sentence and the automorphism orbit of
$\bar {c}$
in
$\mathcal {A}$
is
$\Sigma _{\alpha }$
-definable.
Proof (1) The right-to-left direction is easy. For the left-to-right direction, suppose that
$\mathcal {A}$
has a
$\Sigma _{\alpha + 1}$
Scott sentence
$\exists \bar {x} \varphi (\bar {x})$
, with
$\varphi $
being
$\Pi _{\alpha }$
. Let
$\bar {c}$
be such that
$\mathcal {A} \models \varphi (\bar {c})$
. Note that the Scott sentence for
$\mathcal {A}$
is
$\Pi _{\alpha +2}$
and so by Theorem 1.2 each automorphism orbit is
$\Sigma _{\alpha + 1}$
-definable. Let
$\exists \bar {y} \psi (\bar {x},\bar {y})$
be a
$\Sigma _{\alpha + 1}$
formula defining the orbit of
$\bar {c}$
, with
$\psi $
being
$\Pi _{\alpha }$
. Let
$\bar {d}$
be such that
$\mathcal {A} \models \psi (\bar {c},\bar {d})$
. By Lemma 3.2 the automorphism orbit of
$\bar {c}$
is also
$\Pi _{\alpha +1}$
-definable, say by
$\gamma $
; so
$(\mathcal {A},\bar {c})$
has a
$\Pi _{\alpha +1}$
Scott sentence
$\varphi (\bar {c}) \wedge \gamma (\bar {c})$
. Thus by Theorem 1.2 and Lemma 3.2, the orbit of
$\bar {d}$
over
$\bar {c}$
is
$\Pi _{\alpha }$
- definable, say by
$\theta (\bar {c},\bar {y})$
. Then
$\varphi (\bar {c}) \wedge \psi (\bar {c},\bar {d}) \wedge \theta (\bar {c},\bar {d})$
is a
$\Pi _{\alpha }$
Scott sentence for
$(\mathcal {A},\bar {c}\bar {d})$
.
(2) We may assume that
$\alpha $
is not a limit ordinal. For the left-to-right direction, suppose that
$\mathcal {A}$
has a
$\mathrm {d-}\Sigma _{\alpha }$
Scott sentence
$\exists \bar {x} \varphi (\bar {x}) \wedge \gamma $
with
$\varphi $
being
$\Pi _{\beta }$
(
$\beta < \alpha $
) and
$\gamma $
being
$\Pi _{\alpha }$
. Let
$\bar {c}$
be such that
$\mathcal {A} \models \varphi (\bar {c})$
. Since
$\mathcal {A}$
also has a
$\Pi _{\alpha +1}$
Scott sentence, every automorphism orbit is
$\Sigma _{\alpha }$
-definable; by Lemma 3.2, every automorphism orbit is also
$\Pi _{\alpha }$
-definable. Let
$\psi (\bar {x})$
be a
$\Pi _{\alpha }$
formula defining the orbit
$\bar {c}$
in
$\mathcal {A}$
. Then
$\gamma \wedge \varphi (\bar {c}) \wedge \psi (\bar {c})$
is a
$\Pi _{\alpha }$
Scott sentence for
$(\mathcal {A},\bar {c})$
.
For the right-to-left direction, suppose that
$(\mathcal {A},\bar {c})$
has a
$\Pi _{\alpha }$
Scott sentence
$\varphi (\bar {c})$
and the automorphism orbit of
$\bar {c}$
is
$\Sigma _{\alpha }$
-definable by a formula
$\psi (\bar {x})$
. Then
$\mathcal {A}$
has a
$\mathrm {d-}\Sigma _{\alpha }$
Scott sentence
$\exists \bar {x} \psi (\bar {x}) \wedge \forall \bar {x} (\psi (\bar {x}) \rightarrow \varphi (\bar {x}))$
. ⊣
4 Structures of Scott complexity
$\Sigma _{\lambda + 1}$
In this section, we will show that for
$\lambda $
a limit ordinal, there are structures of Scott complexity
$\Sigma _{\lambda + 1}$
; this resolves an open question from [Reference Miller13].
Theorem 4.1. For every limit ordinal
$\lambda $
, there is a structure of Scott complexity
$\Sigma _{\lambda +1}$
.
We will also show that there are computable structures of Scott complexity
$\Sigma _{\omega _1^{CK}+1}$
; these are structures of Scott rank
$\omega _1^{CK}+1$
which, after naming finitely many constants, have Scott rank
$\omega _1^{CK}$
. This answers another open question.
Theorem 4.2. For every limit ordinal
$\lambda \le \omega _1^{CK}$
, there is a computable structure of Scott complexity
$\Sigma _{\lambda +1}$
.
From these, taking disjoint unions with known structures we can easily get structures with Scott complexity
$\mathrm {d-}\Sigma _{\lambda +1}$
.
Corollary 4.3. For every limit ordinal
$\lambda \le \omega _1^{CK}$
, there is a computable structure of Scott complexity
$\mathrm {d-}\Sigma _{\lambda +1}$
.
Proof It is known that there exists a computable structure
$\mathcal {C}$
of Scott complexity
$\Pi _{\lambda +1}$
([Reference Miller13] for the case
$\lambda < \omega _1^{CK}$
, and [Reference Harrison-Trainor, Igusa and Knight7] for the case
$\lambda = \omega _1^{CK}$
). Let
$\mathcal {A}$
be a computable structure of Scott complexity
$\Sigma _{\lambda +1}$
. Then
$\mathcal {A} \sqcup \mathcal {C}$
, where we add a unary relation to the language to distinguish
$\mathcal {A}$
and
$\mathcal {C}$
, has Scott complexity
$\mathrm {d-}\Sigma _{\lambda +1}$
. ⊣
Corollary 4.4. For every limit ordinal
$\lambda $
, there is a structure of Scott complexity
$\mathrm {d-}\Sigma _{\lambda +1}$
.
We prove Theorems 4.1 and 4.2 using a construction which takes as input a sequence of trees and produces a structure whose Scott complexity depends on the input trees. By feeding different sequences of trees into this construction, we get the two theorems.
In general in computable structure theory,
$\omega _1^{CK}$
behaves quite differently from computable limit ordinals, and so for Theorem 4.2 one would expect the construction of such a structure to proceed differently based on whether
$\lambda < \omega _1^{CK}$
or
$\lambda = \omega _1^{CK}$
. On the other hand, the difference between Theorem 4.1 and the case
$\lambda < \omega _1^{CK}$
of Theorem 4.2 is just the difference between effectiveness and non-effectiveness. We are able to isolate these differences to the proof of the following lemma.
Lemma 4.5. Given a limit ordinal
$\lambda $
, there are a pair of sequences of trees
$(S_i)_{i \in \omega }$
and
$(T_i)_{i\in \omega }$
such that the following all hold:
-
1. Each
$S_i$
and
$T_i$
has Scott complexity at most
$\Pi _{\lambda }$
; -
2. If
$S_i \not \cong T_i$
, then there is a
$\beta < \lambda $
such that
$S_i \not \equiv _{\beta } T_i$
; and -
3. For each
$\beta < \lambda $
, there is an i with
$S_i \not \cong T_i$
but
$S_i \equiv _{\beta } T_i$
.
If
$\lambda \leq \omega _1^{CK}$
, then we can take these sequences to be uniformly computable.
Proof For
$\lambda < \omega _1^{CK}$
, there are many examples appearing in the literature. For instance, we can fix a computable increasing sequence of successor ordinals
$(\alpha _i)_{i \in \omega }$
which converge to
$\lambda $
and let
$S_{i} = \mathcal {A}_{\alpha _i}$
and
$T_{i} = \mathcal {E}_{\alpha _i}$
, where these are the trees defined by Hirschfeldt and White [Reference Hirschfeldt and White8]. If we do not care about effectiveness (e.g., if
$\lambda> \omega _1^{CK}$
), we can take these same trees, relatived to some oracle which makes
$\lambda $
computable. We explain how to verify the properties (1)–(3):
-
1. Each
$\mathcal {A}_{\alpha }$
and
$\mathcal {E}_{\alpha }$
,
$\alpha < \lambda $
, is a tree of rank
$< \lambda $
. One can argue inductively by rank that a tree of rank
$\gamma $
has a Scott sentence of complexity
$\Pi _{2 \cdot \gamma }$
. -
2. This is Lemma 3.5 of [Reference Hirschfeldt and White8].
-
3. It suffices to see that
$\mathcal {A}_{\alpha } \ncong \mathcal {E}_{\alpha }$
, but
$\mathcal {A}_{\alpha } \equiv _{\alpha - 1} \mathcal {E}_{\alpha }$
. The (relativization of) Proposition 3.2 of [Reference Hirschfeldt and White8] implies that
$\mathcal {A}_{\alpha } \equiv _{\alpha - 1} \mathcal {E}_{\alpha }$
, as if
$\mathcal {A}_{\alpha }$
and
$\mathcal {E}_{\alpha }$
disagreed on an X-computable
$\Sigma _{\alpha -1}$
formula, then for
$\mathcal {P}(n)$
a
$\Sigma _{\alpha }(X)$
-complete predicate, we could not produce the sequence
$\mathcal {T}_n$
as in the proposition.
For
$\lambda = \omega _1^{CK}$
, Harrison-Trainor, Igusa, and Knight [Reference Harrison-Trainor, Igusa and Knight7] constructed appropriate trees. Fixing a presentation
$\mathcal {H}$
of the Harrison order, they constructed trees
$(T_a)_{a \in \mathcal {H}}$
such that if a is from the ill-founded part of
$\mathcal {H}$
, then
$T_a \cong T^*$
, where
$T^*$
is a fixed tree of Scott complexity
$\Pi _{\omega _1^{CK}}$
, and if a is from the well-founded part of
$\mathcal {H}$
and the part of
$\mathcal {H}$
to the left of a has order-type
$\alpha $
, then
$T_a$
is well-founded (so
for some
$\beta < \omega _1^{CK}$
) but
$T_a \equiv _{\alpha } T^*$
. Then we let
$(a_i)_{i \in \omega }$
be an enumeration of
$\mathcal {H}$
and set
$T_i = T_{a_i}$
and
$S_i = T^*$
. To verify the properties:
-
1.
$T^*$
has Scott complexity
$\Pi _{\omega _1^{CK}}$
because its computable infinitary theory is
$\aleph _0$
-categorical. If a is from the well-founded part of
$\mathcal {H}$
and the part of
$\mathcal {H}$
to the left of a has order-type
$\alpha $
, then
$T_a$
has tree rank at most
$\omega \cdot (\alpha + 1)$
, and hence has a
$\Pi _{2 \cdot (\omega \cdot (\alpha + 1))}$
Scott sentence. See the first paragraph after Theorem 2.1 of [Reference Harrison-Trainor, Igusa and Knight7], as well as [Reference Calvert, Knight and Millar3]. -
2. If
$S_i \ncong T_i$
, then this means that
$T_i = T_{a_i} \ncong T^*$
and
$a_i$
is in the well-founded part of
$\mathcal {H}$
. So
$T_{a_i}$
is well-founded, and hence has tree rank
$< \omega _1^{CK}$
. Thus there is
$\gamma < \omega _1^{CK}$
such that
. -
3. Given
$\beta < \lambda $
, let
$a_i$
be an element of the well-founded part of
$\mathcal {H}$
such that the predecessors of
$a_i$
in
$\mathcal {H}$
have order type greater than
$\beta $
. Then
$S_i = T_{a_i} \ncong T^* = T_i$
, but
$S_i = T_{a_i} \equiv _{\beta } T^* = T_i$
.⊣
Then the common construction is contained in the following theorem:
Theorem 4.6. Given a limit ordinal
$\lambda $
and a pair of sequences of trees
$(S_i)_{i \in \omega }$
and
$(T_i)_{i\in \omega }$
as in the previous lemma, there is a structure of Scott complexity
$\Sigma _{\lambda + 1}$
. If the sequences are uniformly computable, then the structure is computable.
Proof The language for our structure
$\mathcal {A}$
will have binary relations P, R, and
$E_i$
for
$i \in \omega $
. The universe of our structure will be
$$ \begin{align*} [\omega]^{<\omega} \sqcup \bigsqcup_{i \in \omega} S_i \sqcup \bigsqcup_{i \in \omega} T_i. \end{align*} $$
Thus we have disjoint copies of each of the
$S_i$
and
$T_i$
, and also we have every finite subset of
$\omega $
.
On each of the
$T_i$
and
$S_i$
, P is the tree relation. P has no other structure; that is, it does not hold for any pair
$(x,y)$
not drawn from the same tree.
Each of the
$E_i$
is defined on
$[\omega ]^{<\omega }$
by
$E_i(F,G) \leftrightharpoons F\triangle G = \{i\}$
. The
$E_i$
have no other structure; that is, they do not hold for any pair
$(x,y)$
not both drawn from
$[\omega ]^{<\omega }$
.
We can understand the structure on
$[\omega ]^{<\omega }$
as an affine space acted on by
$\bigoplus _{i \in \omega } \mathbb {Z}/2$
, where the action is
$F + e_i = F \triangle \{i\}$
. By an affine space, we mean a vector space except that we forget the origin. Then
$E_i(F, G) \iff F + e_i = G$
. Alternatively, we can think of the structure as the vertices of an infinite dimensional cube, where
$E_i$
is the edge relation in the “i direction”.
Finally, we define
$R(x,y)$
to hold if and only if one of the following is true:
-
•
$x \in [\omega ]^{<\omega }$
,
$y \in S_i$
, and
$i \not \in x$
or -
•
$x \in [\omega ]^{<\omega }$
,
$y \in T_i$
, and
$i \in x$
.
The affine space
$[\omega ]^{<\omega }$
is partitioned into two hyperplanes perpendicular to
$e_i$
: the first is
$\{ F \in [\omega ]^{<\omega } : i \not \in F\}$
, and the second is
$\{ F \in [\omega ]^{<\omega } : i \in F\}$
. Instead considering the infinite dimensional cube, these are the two connected components that result if we delete all the
$E_i$
edges. One of these sets is associated, via R, with
$S_i$
, and the other with
$T_i$
.
Claim 1. Let
$\mathcal {B}$
be the substructure
$\mathcal {A}\upharpoonright _{[\omega ]^{<\omega }}$
. The automorphisms of B are precisely the maps of the form
$g(F) = F\triangle H$
for some fixed
$H \in [\omega ]^{<\omega }$
.
Proof To see that such a map is an automorphism, observe that
$$ \begin{align*} E_i(F,G) &\iff F\triangle G = \{i\}\\ &\iff F\triangle G \triangle \emptyset = \{i\}\\ &\iff F\triangle G\triangle (H\triangle H) = \{ i\}\\ &\iff (F\triangle H)\triangle (G\triangle H) = \{ i\}\\ &\iff E_i(g(F), g(G)). \end{align*} $$
The relations R and P are empty on
$\mathcal {B}$
, and so this suffices.
Conversely, suppose g is an automorphism of
$\mathcal {B}$
. Let
$H = g(\emptyset )$
. We prove by induction on
$|F|$
that
$g(F) = F \triangle H$
. The case
$|F| = 0$
is immediate. For
$|F|> 0$
, fix
$i \in F$
, and let
$G = F - \{i\}$
. Then
$E_i(F, G)$
, so
$E_i(g(F), g(G))$
, and thus
$$ \begin{align*}\hspace{131pt} g(F) &= g(G) \triangle \{i\}\\ &= (G\triangle H)\triangle \{i\}\\ &= (G\triangle \{i\})\triangle H\\ &= F\triangle H. \hspace{150pt}\dashv\end{align*} $$
Claim 2. For every
$\beta < \lambda $
there is an
$H \in [\omega ]^{<\omega }$
such that
$(\mathcal {A}, \emptyset ) \equiv _{\beta } (\mathcal {A}, H)$
, but
$(\mathcal {A}, \emptyset ) \not \cong (\mathcal {A}, H)$
.
Proof Fix an i such that
$S_i \not \cong T_i$
but
$S_i \equiv _{2\beta } T_i$
, and let
$H = \{i\}$
. (Recall that since
$\lambda $
is a limit, if
$\beta < \lambda $
, then
$2\beta < \lambda $
.)
The elements of
$[\omega ]^{<\omega }$
are definable in
$\mathcal {A}$
by
$\exists y\, E_0(x,y)$
, and so any isomorphism
$g: (\mathcal {A}, \emptyset ) \cong (\mathcal {A}, H)$
must restrict to an isomorphism
$g: (\mathcal {B}, \emptyset ) \cong (\mathcal {B}, H)$
. Thus
$g(F) = F\triangle \{i\}$
on
$\mathcal {B}$
, by the previous claim. The tree
$S_i$
is associated via R with all the elements of
$\{ F \in [\omega ]^{<\omega } : i \not \in F\}$
, and it is the only tree associated with all of these elements. Similarly, the tree
$T_i$
is the only tree associated with all the elements of
$\{ F \in [\omega ]^{<\omega } : i \in F\}$
. As g interchanges these two sets, g must map
$S_i$
to
$T_i$
. But
$S_i \not \cong T_i$
, a contradiction. Thus
$(\mathcal {A}, \emptyset ) \not \cong (\mathcal {A}, H)$
.
Subclaim 2.1. Fix
$\alpha \le \beta $
. Suppose
$\bar {F}, \bar {G} \in [\omega ]^{<\omega }$
,
$\bar {x}, \bar {z} \in S_i$
,
$\bar {y}, \bar {w} \in T_i$
,
$\bar {q} \in \mathcal {A} - [\omega ]^{<\omega } - S_i - T_i$
are such that:
-
•
$|\bar {F}| = |\bar {G}|$
and for all
$j < |\bar {F}|$
,
$F_j\triangle G_j = \{i\}$
and -
•
$|\bar {x}| = |\bar {y}|$
,
$|\bar {z}| = |\bar {w}|$
and
$(S_i, \bar {x}, \bar {z}) \equiv _{2\alpha } (T_i, \bar {y}, \bar {w})$
.
Then
$(\mathcal {A}, \bar {F}, \bar {x}, \bar {w}, \bar {q}) \equiv _{\alpha } (\mathcal {A}, \bar {G}, \bar {y}, \bar {z}, \bar {q})$
.
Proof We argue by induction on
$\alpha $
. The case
$\alpha = 0$
is simply a matter of checking that R is preserved.
For
$\alpha> 0$
, without loss of generality we must argue that for any
$\gamma < \alpha $
and any finite extension of
$(\bar {F}, \bar {x}, \bar {w}, \bar {q})$
, there is a corresponding extension of
$(\bar {G}, \bar {y}, \bar {z}, \bar {q})$
which is
$\gamma $
-equivalent in
$\mathcal {A}$
. Fixing a finite extension of
$(\bar {F}, \bar {x}, \bar {w}, \bar {q})$
, we partition this extension into
$(\bar {F}', \bar {x}', \bar {w}', \bar {q}')$
, where
$\bar {F}' \in [\omega ]^{<\omega }$
, and similarly for the other entries.
Define
$\bar {G}'$
by
$G_j = F_j' \triangle \{i\}$
for all
$j < |\bar {F}'|$
. As
$2\alpha> 2\gamma +1$
, there is
$\bar {y}' \supseteq \bar {y}$
with
$(S_i, \bar {x}', \bar {z}) \equiv _{2\gamma +1} (T_i, \bar {y}', \bar {w})$
. So there is
$\bar {z}' \supseteq \bar {z}$
with
$(S_i, \bar {x}', \bar {z}') \equiv _{2\gamma } (T_i, \bar {y}', \bar {w}')$
.
By the inductive hypothesis,
$(\mathcal {A}, \bar {F}', \bar {x}', \bar {w}', \bar {q}') \equiv _{\gamma } (\mathcal {A}, \bar {G}', \bar {y}', \bar {z}', \bar {q}')$
. ⊣
It follows that
$(\mathcal {A}, \emptyset ) \equiv _{\beta } (\mathcal {A}, H)$
.⊣
So the automorphism orbit of
$\emptyset \in \mathcal {A}$
is not definable by a
$\Sigma _{\alpha }$
formula for any
$\alpha < \lambda $
. Then by Theorem 1.2,
$\mathcal {A}$
does not have a
$\Pi _{\lambda + 1}$
Scott sentence, and so the Scott complexity of
$\mathcal {A}$
is at least
$\Sigma _{\lambda +1}$
. To show that it is precisely
$\Sigma _{\lambda +1}$
, it suffices to show that
$(\mathcal {A}, \emptyset )$
has Scott complexity
$\Pi _{\lambda }$
.
Observe that
$(\mathcal {B}, \emptyset )$
is rigid, because any automorphism must be an automorphism of
$\mathcal {B}$
that fixes
$\emptyset $
, which by our characterization of the automorphisms of
$\mathcal {B}$
must be the identity. In fact, every element of
$(\mathcal {B}, \emptyset )$
is
$\Sigma _1$
definable:
$F = \{i_0, i_1, \dots , i_{k-1}\}$
is the unique element z of
$(\mathcal {A}, \emptyset )$
satisfying
This is the key fact that drops the Scott complexity of
$(\mathcal {A}, \emptyset )$
. It follows that each
$S_i$
and
$T_i$
is
$\Pi _2$
definable in
$(\mathcal {A},\emptyset )$
:
where “
$x = F$
” represents the appropriate
$\Sigma _1$
formula given above.
$T_i$
is similar.
By assumption, each
$S_i$
and
$T_i$
has a
$\Pi _{\lambda }$
Scott sentence
$\phi _i$
and
$\psi _i$
, respectively. We will construct a
$\Pi _{\lambda }$
Scott sentence for
$(\mathcal {A}, \emptyset )$
. The idea is that our ability to distinguish the elements of
$\mathcal {B}$
and the various
$S_i$
and
$T_i$
lets us give a complete description of the structure on
$\mathcal {B}$
and the relation R. We then use the
$\phi _i$
and
$\psi _i$
to give descriptions of the
$S_i$
and
$T_i$
.
More precisely, let
$\phi _i'$
be the sentence made from
$\phi _i$
by restricting the quantifiers to
$S_i$
. That is, each instance of
$\forall x\, \theta (x)$
becomes
$\forall x\, [x \in S_i \implies \theta (x)]$
, and each instance of
$\exists x\, \theta (x)$
becomes
$\exists x\, [x \in S_i \wedge \theta (x)]$
, where “
$x \in S_i$
” represents the
$\Pi _2$
formula given above. Similarly,
$\psi _i'$
is made from
$\psi _i$
by restricting the quantifiers to
$T_i$
. By an inductive argument on subformulas,
$\phi _i'$
and
$\psi _i'$
are both
$\Pi _{\lambda }$
.
We are now ready to give a
$\Pi _{\lambda }$
Scott sentence for
$(\mathcal {A}, \emptyset )$
:
The first four lines partition the structure into
$\mathcal {B}$
, the
$S_i$
and the
$T_i$
. The fifth and sixth lines state that the various
$E_i$
are defined correctly on
$\mathcal {B}$
, and further that none of the
$E_i$
hold with any elements outside of
$\mathcal {B}$
. The seventh line states that R is defined correctly. The final line determines the isomorphism types of the
$S_i$
and
$T_i$
(it is here that P is defined). Note that apart from the final line, this sentence is
$\Pi _4$
. Since the
$\phi _i'$
and
$\psi _i'$
are
$\Pi _{\lambda }$
, the entire sentence is a
$\Pi _{\lambda }$
Scott sentence for
$(\mathcal {A},\emptyset )$
, as desired.⊣
5 Scott complexity
$\Sigma _2$
is impossible
Theorem 5.1. There is no structure with Scott complexity
$\Sigma _2$
.
Proof Suppose that
$\mathcal {A}$
is a structure with a
$\Sigma _2$
Scott sentence. We may assume that the Scott sentence is of the form
$$ \begin{align*} \exists x_1,\ldots,x_n \varphi(\bar{x}), \end{align*} $$
where
$\varphi (\bar {x})$
is
$\Pi _1$
. Let
$\bar {a} \in \mathcal {A}$
be such that
$\mathcal {A} \models \varphi (\bar {a})$
. Let
$\mathcal {A}^*$
be the substructure of
$\mathcal {A}$
generated by
$\bar {a}$
. Then since
$\varphi $
is
$\Pi _1$
,
$\mathcal {A}^* \models \varphi (\bar {a})$
. Thus
$\mathcal {A}^* \cong \mathcal {A}$
. So we may assume that
$\bar {a}$
generates
$\mathcal {A}$
.
We repeat here Lemma 1.1 of [Reference Miller13]:
Claim.
$\mathcal {A}$
is saturated.
Proof If
$\mathcal {B}$
is any elementary extension of
$\mathcal {A}$
, then
$\mathcal {B} \models \varphi (\bar {a})$
and so
$\mathcal {B}$
is isomorphic to
$\mathcal {A}$
. So every type (with no parameters) in
$Th(\mathcal {A})$
is realized in
$\mathcal {A}$
, i.e.,
$\mathcal {A}$
is weakly saturated. In particular, there are countably many types in
$Th(\mathcal {A})$
, and so
$Th(\mathcal {A})$
has a countable saturated model
$\mathcal {B}$
. But then
$\mathcal {A}$
elementarily embeds into
$\mathcal {B}$
, and so
$\mathcal {B}$
is isomorphic to
$\mathcal {A}$
. Thus
$\mathcal {A}$
is saturated. ⊣
If
$\mathcal {A}$
were infinite, then the type of an element which is not generated by
$\bar {a}$
is consistent. But
$\mathcal {A}$
is saturated, and so this type must be realized in
$\mathcal {A}$
. This cannot happen as
$\mathcal {A}$
is generated by
$\bar {a}$
. So
$\mathcal {A}$
is finite, say with n elements. List out these elements as
$a_1,\ldots ,a_n$
. Let
$\langle \psi _m(a_1,\ldots ,a_n) \rangle $
be a list of the quantifier-free formulas true of
$a_1,\ldots ,a_n$
. (Note that among these formulas are those saying that
$a_1,\ldots ,a_n$
are distinct.)
Then
$\mathcal {A}$
has a
$\mathrm {d-}\Sigma _1$
Scott sentence:
$\mathcal {A}$
is axiomatized by saying that there exists n elements, there are not more than n elements, and also for each m,
$$ \begin{align*} \forall x_1,\ldots,x_n \left[ \bigwedge_{i \neq j} x_i \neq x_j \longrightarrow \bigvee_{\sigma \in S(n)} \bigwedge_{i \leq m} \psi_i(x_{\sigma(1)},\ldots,x_{\sigma(n)}) \right], \end{align*} $$
where
$S(n)$
is the set of permutations of
$\{1,\ldots ,n\}$
. (Since
$S(n)$
is finite, these conjunctions and disjunctions are all finite and hence do not increase the complexity.) Suppose that
$\mathcal {B}$
is a model of these sentences; then
$\mathcal {B}$
has exactly n elements
$b_1,\ldots ,b_n$
. Since there are only finitely many permutations in
$S(n)$
, there must be some permutation
$\sigma $
such that for arbitrarily large m,
$$ \begin{align*} \mathcal{B} \models \bigwedge_{i \leq m} \psi_i(b_{\sigma(1)},\ldots,b_{\sigma(n)}).\end{align*} $$
Then
$a_i \mapsto b_{\sigma (i)}$
is an isomorphism from
$\mathcal {A}$
to
$\mathcal {B}$
.⊣
