Computable structures of Scott rank ω_{1}^{CK} in familiar classes

W. Calvert, S. S. Goncharov, and J. F. Knight^{∗}

July 6, 2005

Abstract There are familiar examples of computable structures having various computable Scott ranks. There are also familiar structures, such as the Harrison ordering, that have Scott rank ω_{1}^{CK} + 1. Makkai [13] produced a structure of Scott rank ω_{1}^{CK}, which can be made computable [12], and simplified so that it is just a tree [4]. In the present paper, we show that there are further computable structures of Scott rank ω_{1}^{CK} in the following classes: undirected graphs, fields of any characteristic, and linear orderings. The new examples share with the Harrison ordering and the tree in [4] a strong approximability property.

1 Introduction

Scott rank is a measure of model-theoretic complexity. For a countable structure, the Scott rank is a countable ordinal. For a computable structure, it is at most ω_{1}^{CK} + 1. There are familiar examples of computable structures of computable Scott rank, and of Scott rank ω_{1}^{CK} + 1. In [12], there is an example of a computable tree T of Scott rank ω_{1}^{CK}. In fact, there is an example which is strongly computably approximable; i.e., for any Σ_{1}^{1} set S, there is a uniformly computable sequence of trees (C_{n})_{n∈ω} such that if n ∈ S, then C_{n} ≅ T and if n ∉ S, then C_{n} has computable Scott rank.

Here we produce further examples of computable structures of Scott rank ω_{1}^{CK} in some further familiar classes.

Main Theorem Each of the following classes includes a computable structure of Scott rank ω_{1}^{CK}. Moreover, the structure can be taken to be strongly computably approximable.

1. undirected graphs,

2. fields of any desired characteristic, 3. linear orderings.

∗The authors acknowledge NSF support under bi-national Grant DMS-0075899. In addition, the first author was partially supported by NSF Grants DMS 0139626 and DMS 0353748.

We conclude that computable structures of rank ω_{1}^{CK} are not so rare as they once seemed. However, there are classes, in particular, Abelian p-groups, with computable structures of arbitrarily large computable rank, and of rank ω_{1}^{CK} + 1, but none of rank ω_{1}^{CK} (see Barwise [2]).

In proving the Main Theorem, we use some special computable embeddings. The notion of computable embedding, inspired by that of Borel embedding, was introduced in [3]. There are known embeddings of trees in undirected graphs (described in [13] and elsewhere). Friedman and Stanley [5] found embeddings of graphs in fields of arbitrary characteristic, and of graphs in linear orderings. These embeddings all turn out to be computable. These embeddings (after modification, in one case) can be shown to preserve Scott rank, to the extent that for a computable input structure, either the corresponding output structure has the same rank, or else both have computable rank.

Starting with a computable tree of rank ω_{1}^{CK}, and applying a rank-preserving computable embedding of trees in undirected graphs, we get a computable graph of rank ω_{1}^{CK}. Similarly, starting with a computable graph of rank ω_{1}^{CK}, and applying a rank-preserving computable embedding of undirected graphs in fields, or linear orderings, we get a field, or linear ordering of rank ω_{1}^{CK}. Moreover, if the input structure is strongly computably approximable, then so is the output structure.

Abstracting from the sample embeddings, we obtain some fairly general conditions sufficient for rank preservation. The particular notion of computable embedding is not important. Roughly, our conditions say that the orbits in the input structure correspond, in a hyperarithmetical way, to orbits in the output structure. Moreover, there is not much more to the output structure. Certain elements of the output structure correspond to orbits in the input structure, and the orbits of arbitrary tuples in the output structure are definable by formulas of bounded complexity over these elements.

In the remainder of the present section, we give a little background on Scott rank and computable structures. In Section 2, we begin with familiar examples of computable structures having computable Scott ranks and Scott rank ω_{1}^{CK}+1. We then summarize the results from [13], [12], and [4] leading to computable trees of Scott rank ω_{1}^{CK}. In Section 3, we describe the computable embeddings that we shall use, and we show that they have the rank-preservation property. In Section 4, we use the embeddings from Section 3 to prove the Main Theorem. We also discuss Abelian p-groups and some related classes with no computable structure of rank ω_{1}^{CK}.

1.1 Scott rank

Scott rank is a measure of model-theoretic complexity. The notion comes from the Scott Isomorphism Theorem (see [19], or [10]).

Theorem 1.1 (Scott Isomorphism Theorem). For each countable structure A (for a countable language L) there is an L_{ω_{1}ω} sentence whose countable models are just the isomorphic copies of A.

In the proof of Theorem 1.1, Scott assigned countable ordinals to tuples in A, and to A itself. There are several different definitions of Scott rank in use. We begin with a family of equivalence relations.

Definition 1. Let \overline{a}, \overline{b} be tuples in A.

1. We say that \overline{a} ≡^{0} \overline{b} if \overline{a} and \overline{b} satisfy the same quantifier-free formulas,

2. For α > 0, we say that \overline{a} ≡^{α} \overline{b} if for all β < α, for each \overline{c}, there exists \overline{d}, and for each \overline{d}, there exists \overline{c}, such that \overline{a}, \overline{c} ≡^{β} \overline{b}, \overline{d}.

Definition 2.

1. The Scott rank of a tuple \overline{a} in A is the least β such that for all \overline{b}, the relation \overline{a} ≡^{β} \overline{b} implies (A, \overline{a}) ≅ (A, \overline{b}).

2. The Scott rank of A, SR(A), is the least ordinal α greater than the ranks of all tuples in A.

Example: If A is an ordering of type ω, then SR(A) = 2. We have \overline{a} ≡^{0} \overline{b} iff \overline{a} and \overline{b} are ordered in the same way. We have \overline{a} ≡^{1} \overline{b} iff the corresponding intervals (before the first element and between successive elements) have the same size, and this is enough to assure isomorphism. From this, it follows that the tuples have Scott rank 1, so the ordering itself has Scott rank 2.

1.2 Background from computable structure theory

For basic background from computability (arithmetical, hyperarithmetical, Σ_{1}^{1}, and Π_{1}^{1} sets and relations) see [18]. Here we give a little background from computable structure theory. For more, see [1]. We are interested in computable structures. We adopt the following conventions.

1. Languages are computable, and each structure has for its universe a subset of ω.

2. We identify a structure A with its atomic diagram D(A).

3. We identify sentences with their Gödel numbers.

By these conventions, a structure A is computable (or arithmetical) if D(A), thought of as a subset of ω, is computable (or arithmetical).

Computable infinitary formulas are useful in describing computable structures. Roughly speaking, these are infinitary formulas in which the disjunctions and conjunctions are over c.e. sets. They are essentially the same as the formulas in the least admissible fragment of L_{ω_{1}ω}. For a more precise description of computable infinitary formulas, see [1]. We classify computable infinitary formulas as computable Σ_{α}, or computable Π_{α}, for various computable ordinals α. We then have a nice match with the hyperarithmetical hierarchy.

Proposition 1.2. In a computable structure, a relation defined by a computable Σ_{α} (or computable Π_{α}) formula is Σ_{α}^{0} (or Π_{α}^{0}).

To illustrate the expressive power of computable infinitary formulas, we note that there is a natural computable Π_{2} sentence characterizing the class of Archimedean ordered fields. Similarly, there is a computable Π_{2} sentence characterizing the class of Abelian p-groups. For each computable ordinal α there is a computable Π_{2α} formula saying (of an element of an Abelian p-group), that the height is at least ω · α.

This expressive power is not compatible with the ordinary Compactness Theorem. However, there is a version of Compactness for computable infinitary formulas.

Theorem 1.3 (Barwise-Kreisel Compactness). Let Γ be a Π_{1}^{1} set of computable infinitary sentences. If every Δ_{1}^{1} subset of Γ has a model, then Γ has a model.

Barwise-Kreisel Compactness can be used to produce computable structures.

Corollary 1.4. Let Γ be a Π_{1}^{1} set of computable infinitary sentences. If every Δ_{1}^{1} subset has a computable model, then Γ has a computable model.

The next two corollaries give further evidence of the expressive power of computable infinitary formulas.

Corollary 1.5. If A, B are computable structures satisfying the same computable infinitary sentences, then A ≅ B.

Corollary 1.6. Suppose \overline{a}, \overline{b} are tuples satisfying the same computable infinitary formulas in a computable structure A. Then there is an automorphism of A taking \overline{a} to \overline{b}.

The Barwise-Kreisel Compactness Theorem and the three corollaries are all well known, and may be found in [1]. One point in the proof of the Barwise-Kreisel Compactness Theorem is expanded in [6].

2 Scott ranks for computable structures

Corollary 1.6 yields a bound on the Scott ranks for computable structures [16].

Proposition 2.1. If A is a computable structure, then SR(A) ≤ ω_{1}^{CK} + 1.

Different definitions of Scott rank all agree on which computable structures have computable rank, although they disagree on the precise value assigned. In what follows, we ignore the value of the rank, if it is computable. The definition in [2] does not distinguish between rank ω_{1}^{CK} and rank ω_{1}^{CK} + 1. The definitions that do distinguish between these ranks, as ours does, agree on which computable structures have which rank. The following result gives conditions under which a computable structure has computable rank, or has one of the two non-computable values.

Proposition 2.2 (folklore). For a computable structure A,

1. SR(A) < ω_{1}^{CK} if there is some computable ordinal β such that the orbits of all tuples are defined by computable Π_{β} formulas.

2. SR(A) = ω_{1}^{CK} if the orbits of all tuples are defined by computable infinitary formulas, but there is no computable bound on the complexity of these formulas.

3. SR(A) = ω_{1}^{CK} + 1 if there is some tuple whose orbit is not defined by any computable infinitary formula.

We shall give a variant of Proposition 2.2, in which the bounds on complexity of the defining formulas for the orbits are replaced by bounds on the complexity of the orbits themselves. We need the following result of Soskov [20], which is re-worked in [7].

Theorem 2.3 (Soskov). Suppose A is a hyperarithmetical structure, and let R be a relation on A. If R is invariant under automorphisms, and hyperarithmetical, then it is definable in A by a computable infinitary formula.

Theorem 2.3 implies that if an invariant relation R is hyperarithmetical in one hyperarithmetical copy of a given structure A, then in all hyperarithmetical copies of A, the image of R is hyperarithmetical. Here is the variant of Proposition 2.2.

Proposition 2.4. For a computable structure A,

1. SR(A) < ω_{1}^{CK} if there is a computable ordinal β such that all orbits are Π_{β}^{0}.

2. SR(A) = ω_{1}^{CK} if all orbits are hyperarithmetical, but there is no computable ordinal β such that all ordinals are Δ_{β}^{0}.

3. SR(A) = ω_{1}^{CK} + 1 if some orbit is not hyperarithmetical.

Proof. By Proposition 1.2, if an orbit is defined by a computable infinitary Π_{β} formula, then it is Π_{β}^{0}. By Theorem 2.3, if the orbit is hyperarithmetical, then it is definable by a computable infinitary formula. From this, we immediately get 3, and we also get 2. For 1, we consider the orbit equivalence relation. This is the relation that holds between a pair of tuples iff they are in the same orbit. Let A^{∗} be the variant of A with added elements representing the tuples from A. We include disjoint unary predicates U_{n} representing n-tuples from A. We identify U_{1} with the universe of A, and put on this set the relations of A. For n ≥ 2, we have projection functions p_{i}^{n}, for 1 ≤ i ≤ n, mapping each element of U_{n} to the i^{th} element of the corresponding tuple in U_{1}. Clearly, A^{∗} is hyperarithmetical, and the orbit equivalence relation is represented by an invariant relation E ⊇ ⋃_{n}(U_{n} × U_{n}). By Theorem 2.3, E is definable in A^{∗} by a

computable infinitary formula.

Claim: There is a fixed α such that for all tuples \overline{a} in A, the orbit of \overline{a} is defined by the conjunction of all computable Π_{α} formulas true of \overline{a} in A.

Proof of Claim: Suppose not. Let Γ(x, y) be a Π_{1}^{1} set of computable infinitary formulas saying that ¬Exy, but x, y are in the same U_{n} and for each computable infinitary formula φ in variables u_{1}, …, u_{n}, if x, y ∈ U_{n}, then φ is satisfied by the tuple represented by x iff it is satisfied by the tuple represented by y. If there is no α as in the claim, then every hyperarithmetical subset of Γ is satisfied by some pair in A^{∗}. Therefore, the whole of Γ is satisfied, a contradiction.

Using the claim, we get a bound on the complexity of formulas defining the orbits in A. Therefore, A has computable Scott rank.

A Scott sentence for A is a sentence whose countable models are just the isomorphic copies of A (as in the Scott Isomorphism Theorem). Low Scott rank is associated with a simple Scott sentence. Nadel [16], [17] showed the following.

Theorem 2.5 (Nadel). For a computable structure A, SR(A) is computable iff A has a computable infinitary Scott sentence.

2.1 Some examples

We turn to examples of computable structures illustrating the different possible Scott ranks. There are familiar examples of computable structures of computable rank.

Proposition 2.6. For the following classes of structures, all computable members have computable Scott rank, and each class includes computable members of arbitrarily large computable rank.

1. well orderings,

2. superatomic Boolean algebras,

3. reduced Abelian p-groups.

There are some well-known examples of computable structures of Scott rank ω_{1}^{CK} + 1. Harrison [8] showed that there is a computable ordering of type ω_{1}^{CK}(1 + η). This ordering, the Harrison ordering, gives rise to some other computable structures with similar properties. The Harrison Boolean algebra is the interval algebra of the Harrison ordering. The Harrison Abelian p-group has length ω_{1}^{CK}, with all infinite Ulm invariants, and with a divisible part of infinite dimension.

Proposition 2.7. The Harrison ordering, Harrison Boolean algebra, and Harrison Abelian p-groups all have Scott rank ω_{1}^{CK} + 1.

Proof. For the Harrison ordering, the rank is witnessed by any element a outside the initial copy of ω_{1}^{CK}. Similarly, in the Harrison Boolean algebra, the rank is witnessed by any non-superatomic element, and in the Harrison Abelian p-group, the rank is witnessed by any divisible element.

The Harrison ordering has some further interesting features. First, the computable infinitary sentences true in the Harrison ordering are all true in orderings of type ω_{1}^{CK}, so the conjunction of these sentences is not a Scott sentence. Second, although there are many automorphisms, there is at least one computable copy in which there is no non-trivial hyperarithmetical automorphism.

For computable structures of Scott rank ω_{1}^{CK}, it is not so easy to think of examples. There is an arithmetical example in [13].

Theorem 2.8 (Makkai). There is an arithmetical structure A of rank ω_{1}^{CK}.

For Makkai’s example, in contrast to the Harrison ordering, the set of computable infinitary sentences true in the structure A is ℵ_{0} categorical, so the conjunction of these sentences is a Scott sentence for A. In [12], Makkai’s result is refined as follows.

Theorem 2.9. There is a computable structure of Scott rank ω_{1}^{CK}.

In [12], there are two different proofs of Theorem 2.9. The first takes Makkai’s example and, without examining it, codes it into a computable structure in a way that preserves the rank. The second is a re-working of Makkai’s construction, which incorporates a suggestion of Shelah, given at the end of Makkai’s paper, together with a suggestion of Sacks.

The structure is a “group tree” A(T ), derived from a tree T . Morozov [15] used the same construction. He showed that if T is a computable tree having a path but no hyperarithmetical path, then A(T ) is a computable structure with many automorphisms but no non-trivial hyperarithmetical automorphism. Above we mentioned that the Harrison ordering has this feature. To obtain a structure of the form A(T ) as in Theorem 2.9, we need a tree T with special properties. We use some definitions to state these properties.

Let T be a subtree of ω^{<ω}. We have a top node ∅. Below, we define tree rank for σ ∈ T , and then for T itself. We use the notation rk(σ), rk(T ).

Definition 3.

1. rk(σ) = 0 if σ is terminal, 2. for α > 0, rk(σ) = α if all successors of σ have ordinal rank, and α is the

first ordinal greater than these ordinals,

3. rk(σ) = ∞ if σ does not have ordinal rank.

We let rk(T ) = rk(∅).

Fact. rk(σ) = ∞ iff σ extends to a path.

For a tree T , we let T_{n} be the set of elements at level n in the tree— T_{n} = T ∩ ω^{n}.

Definition 4. The tree T is thin provided that for all n, the set of ordinal ranks of elements of T_{n} has order type at most ω · n.

Thinness is used in the following way.

Fact: If T is a computable thin tree, then for each n, there is some computable α_{n} such that for all σ ∈ T_{n}, if rk(σ) ≥ α_{n}, then rk(σ) = ∞.

The following result is from [12].

Theorem 2.10.

1. There exists a computable thin tree T with a path but no hyperarithmetical path.

2. If T is a computable thin tree with a path but no hyperarithmetical path, then A(T ) is a computable structure of Scott rank ω_{1}^{CK}.

In [4], there is a construction of a computable tree of Scott rank ω_{1}^{CK}. The tree satisfies the conditions from [12], together with the following homogeneity property.

Definition 5. A tree T is rank-homogeneous provided that for all n,

1. for all σ ∈ T_{n} and all computable α, if there exists τ ∈ T_{n+1} such that rk(τ) = α < rk(σ), then σ has infinitely many successors σ′ with rk(σ′) = α.

2. for all σ ∈ T_{n}, if rk(σ) = ∞, then σ has infinitely many successors σ′ with rk(σ′) = ∞.

Fact. If T and T′ are rank-homogeneous trees, and for all n there is an element in T_{n} of rank α ∈ Ord ∪ {∞} if and only if there is an element in T′_{n} of rank α, then T ≅ T′.

In [4], the tree of Scott rank ω_{1}^{CK} is obtained as follows.

Theorem 2.11.

1. There is a computable, thin, rank-homogeneous tree T such that rk(T ) = ∞ but T has no hyperarithmetical path.

2. If T is a computable, thin, rank-homogeneous tree such that rk(T ) = ∞ but T has no hyperarithmetical path, then SR(T ) = ω_{1}^{CK}.

Like the earlier group-trees, the trees in [4] have the feature that the computable infinitary theory is ℵ_{0} categorical. Unlike the group-trees, these trees have many non-trivial hyperarithmetical automorphisms. It is possible to produce a tree as above, with the further feature of strong computable approximability [4].

Definition 6. A structure A is strongly computably approximable if for any Σ_{1}^{1} set S, there is a uniformly computable sequence (C_{n})_{n∈ω} such that n ∈ S iff C_{n} ≅ A. The structures C_{n} for n ∉ S are called approximating structures.

For example, it is well-known that the Harrison ordering is strongly computably approximable by computable well orderings. The following result is in [4].

Theorem 2.12. There is a computable tree T , of Scott rank ω_{1}^{CK}, such that T is strongly computably approximable. Moreover, the approximating structures are trees of computable Scott rank.

The trees in Theorem 2.12 are transformed, using rank-preserving computable embeddings, into the structures in our Main Theorem.

3 Rank-preserving computable embeddings

We use a notion of computable embedding from [3]. Let K and K′ be classes of structures. We suppose that each structure has universe a subset of ω. Each class consists of structures for a fixed computable language. Moreover, the class is closed under isomorphism, modulo the restriction on the universes. Let Φ be a c.e. set Φ of pairs (α, φ), where α is a finite set appropriate to be a subset of the atomic diagram of a structure in K, and φ is a sentence appropriate to be in the atomic diagram of a structure in K′. For each A ∈ K, let Φ(A) be the set of φ such that for some α ⊆ D(A), (α, φ) ∈ Φ. Suppose for all A ∈ K, the set Φ(A) is the atomic diagram of some B ∈ K′. We identify the structure with its atomic diagram. Now, Φ is a computable embedding of K in K′ if for all A, A′ ∈ K, we have A ≅ A′ iff Φ(A) ≅ Φ(A).

Remark: If Φ is a computable embedding of K in K′, and A ∈ K is a computable structure, then Φ(A) has a computable copy, with index computable from that of A.

The following result is proved in [11].

Theorem 3.1. If Φ is a computable embedding of K in K′, then for any computable infinitary formula φ, we can find a computable infinitary formula φ^{∗} such that for all A in K, Φ(A) ⊧ φ iff A ⊧ φ^{∗}. Moreover, φ^{∗} has the same complexity as φ; i.e., if φ is computable Σ_{α}, then so is φ^{∗}.

Using Theorem 3.1, we get the following.

Corollary 3.2. Let Φ be a computable embedding of K in K′, where K is axiomatized by a computable infinitary sentence. For a hyperarithmetical structure A ∈ K, if SR(Φ(A)) is computable, then SR(A) is also computable.

Proof. Suppose SR(Φ(A)) is computable. By Theorem 2.5, Φ(A) has a computable infinitary Scott sentence φ. Let φ^{∗} be as guaranteed by Theorem 3.1. If ψ is a computable infinitary sentence axiomatizing K, then ψ & φ^{∗} is a Scott sentence for A. Then, again by Theorem 2.5, SR(A) is computable.

To prove the Main Theorem, we describe a computable embedding of trees in undirected graphs, one of undirected graphs in fields of the desired characteristic, and one of undirected graphs in linear orderings. We show that each of these embeddings preserves ranks as follows.

Definition. Let Φ be a computable embedding of K into K′. We say that Φ has the rank-preservation property provided that for all computable A ∈ K, and B = Φ(A), either SR(A), SR(B) are both computable, or else they are equal.

Corollary 3.2 says that for a computable embedding Φ from K into K′ and a computable structure A ∈ K, if SR(A) ≥ ω_{1}^{CK}, then SR(Φ(A)) ≥ ω_{1}^{CK}. For rank preservation, we need more. In particular, we must show that if all tuples in A have computable Scott rank, then the same is true of the tuples in Φ(A), and if there is a computable bound on the Scott ranks of the tuples in A, then there is also a computable bound on the Scott ranks of the tuples in Φ(A).

3.1 Embedding trees in undirected graphs

There are several well-known methods for coding a tree in an undirected graph so that given a tree, we effectively obtain a graph in which a copy of the tree is definable by existential formulas (see, for example, Marker [14]). Here we think of tree elements not as elements of ω^{<ω} but as numbers. For convenience, we consider the top node of the tree to be a successor of itself. In the graph, we represent a tree element a by a point r(a) with an edge connecting it to a triangle graph. To indicate in the graph that a′ is a successor of a in the tree, we add a point q(a, a′), connected by an edge to a square, and we connect r(a) and r(a′) to q(a, a′) by chains of length 2, 3, respectively. We make all of these elements distinct.

In [3], it is shown that this idea yields a computable embedding. We start with a large computable graph G including for each n ∈ ω a representative r(n)

(with triangle attached), allowing for the possibility that n might be in T , and also including for each pair (m, n) ∈ ω^{2}, a point s(m, n) (with attached square), allowing for the possibility that n might be a successor of m in T . For a given tree T , Φ(T ) is the subgraph of G representing just the elements n that are actually in T and the pairs (m, n) that are actually in the successor relation in T . Formally, Φ is the set of pairs (α, φ), where α is the diagram of a finite tree T , and φ is in the diagram of Φ(T ). Note that there are finitary existential formulas u(x) and s(x, y) such that for any tree T , u and s define in Φ(T ) the universe and successor relation of a copy of T .

For a computable tree T , if B = Φ(T ) and A is the copy of T defined in B by the formulas u(x) and s(x, y), then A and B satisfy the hypotheses of the following proposition.

Proposition 3.3. Let B be a hyperarithmetical structure, and let A be another structure such that

1. A is definable in B by computable infinitary formulas, and in case the language of A is infinite, there is a bound on the complexity of these formulas,

2. all automorphisms of A extend to automorphisms of B,

3. for each tuple \overline{b} in B, the orbit of \overline{b} under automorphisms of B that fix A pointwise is definable by a computable infinitary formula ψ(\overline{a}, \overline{x}), and there is a bound on the complexity of these formulas.

Then either SR(A) and SR(B) are both computable, or else they are equal.

Proof. Let \overline{b} be a tuple in B. Let ψ(\overline{a}, \overline{x}) define the orbit of \overline{b} under automorphisms of B that fix the elements of A. Then \overline{b}′ is in the orbit of \overline{b} in B iff there exists \overline{a}′ such that \overline{a}′ is in the orbit of \overline{a} in A and B ⊧ ψ(\overline{a}′, \overline{b}′). Therefore, if the orbit of \overline{a} in A is hyperarithmetical, so is the orbit of \overline{b} in B. Moreover, if the orbits in A have bounded complexity, so do the orbits in B. From this, it is clear that if SR(A) is computable, so is SR(B). If SR(A) = ω_{1}^{CK} + 1, then there is some tuple \overline{a} whose orbit is not defined by any computable infinitary formula. By Soskov’s Theorem, the orbit is not hyperarithmetical. The orbit of \overline{a} in B is the same, so SR(B) = ω_{1}^{CK} + 1. Finally, suppose SR(A) = ω_{1}^{CK}. The argument above shows that the orbits in B are all hyperarithmetical, since those in A are. There is no bound on the complexity, since the orbits in A are among the orbits in B.

Corollary 3.4. There is a computable embedding Φ of trees into graphs such that Φ has the rank preservation property.

In [9], there is a notion of embedding with some conditions in common with ours. There is a copy A of the input structure definable in the output structure B, and every automorphism of A extends to an automorphism of B—exactly our conditions 1 and 2. There are further conditions in [9] that seem unrelated to rank preservation. From the proof above, we see that Conditions 1 and 2 imply SR(A) ≤ SR(B). The following example shows that without Condition 3, we may have SR(B) = ω_{1}^{CK} + 1, while SR(A) ≤ ω_{1}^{CK}.

Example. Let K be the class of linear orderings, and let K′ be the class of structures B = (U ∪ V, U, V, <_{U}, <_{V}), where U and V are disjoint sets, (U, <_{U}) is an arbitrary linear ordering, and (V, <_{V}) is a Harrison ordering. For any ordering A, let Φ(A) be the structure B = (U ∪ V, U, V, <_{U}, <_{V}), where A is isomorphic to (U, <_{U}) under the isomorphism taking n to 2n, and (V, <_{V}) is a fixed Harrison ordering with universe equal to the set of odd numbers. This is a computable embedding of K in K′, and we have Conditions 1 and 2, but SR(B) = ω_{1}^{CK} + 1, for all computable orderings A.

3.2 Embedding undirected graphs in fields

We obtain a computable embedding Φ of undirected graphs into fields of any desired characteristic by modifying a construction of Friedman and Stanley [5]. We describe embedding in the case where the characteristic ≠ 2. Let F be a computable algebraically closed field with a computable sequence (b_{n})_{n∈ω} of algebraically independent elements. We let Φ(G) be the subfield of F generated by the algebraic closures of the elements b_{n}, for n ∈ G, and the elements \sqrt{c_{i} + c_{j}}, where i and j are connected by an edge in G and c_{i} is inter-algebraic with b_{i}. (For characteristic 2, the construction is similar except that we would use cube roots instead of square roots.) Formally, Φ is the set of pairs (α, φ), where α is the diagram of a finite graph G, and φ is in the diagram of the corresponding field. It is not difficult to see that this set is c.e.

In the Friedman and Stanley embedding, the only added square roots were \sqrt{b_{i} + b_{j}}, where there is an edge connecting i and j. The proof that the embedding preserves isomorphism is the same for the Friedman and Stanley embedding and the variant described above. We need the fact that for all d in Φ(G), if the algebraic closure of d is present in Φ(G), then d is interalgebraic with b_{i} for some i ∈ G. We also need the fact that for i, j ∈ G, not connected by an edge, there is no square root for b_{i} + b_{j} in Φ(G).

We must show that our computable embedding has the rank-preservation property. Let G be a computable graph. If B = Φ(G), and A is the copy of G with universe consisting of the algebraic closures of the special basis elements b_{i}, for i ∈ G and edge relation defined in terms of existence of square roots (or cube roots). It is not difficult to see that A and B satisfy the conditions for the following.

Proposition 3.5. Let B be a hyperarithmetical structure. Suppose A is a definable quotient in B; i.e., there exist a structure A^{∗} (for the language of A) and a congruence relation ≡ such that A^{∗} and ≡ are definable in B by computable infinitary formulas of bounded complexity, and A = A^{∗}/_{≡}. For simplicity, we assume that the language of A is relational. For a choice function c : A → A^{∗}, where c(a/_{≡}) ∈ a/_{≡}, we let A_{c} be the substructure of A^{∗} such that A ≅_{c} A_{c}. Suppose the following conditions are satisfied.

1. For any automorphism f of A and any choice function c, the automorphism of A_{c} given by c ∘ f ∘ c^{−1} extends to an automorphism of B.

2. For any tuple \overline{b} in B, the orbit of \overline{b} under automorphisms of B that fix D pointwise is defined by a computable infinitary formula, φ(\overline{d}, \overline{x}), of bounded complexity, where for any choice function c, the parameters \overline{d} may be chosen to be in A_{c}.

Then either A and B have the same Scott rank, or else both have computable Scott rank.

Proof. There is a hyperarithmetical choice function c. We have a hyperarithmetical copy A_{c} of A such that A ≅_{c} A_{c}. Suppose \overline{a}, \overline{a}′ are tuples in A_{c}. If \overline{a} and \overline{a}′ are in the same orbit in A_{c}, then by 1, they are in the same orbit in B. Conversely, if \overline{a} and \overline{a}′ are in the same orbit in B, the automorphism f of B taking \overline{a} to \overline{a}′ restricts to an automorphism of A^{∗} taking the equivalence class of a_{i} to that of a′_{i}. We get an induced automorphism f_{c} of A_{c} taking \overline{a} to \overline{a}′. It follows that if SR(B) is computable, or at most ω_{1}^{CK}, then the same is true of SR(A).

Now, let \overline{b} be a tuple in B. Take φ(\overline{d}, \overline{x}) as in 2, defining the orbit of \overline{b} over D, where the parameters \overline{d} are in A_{c}.

Claim: \overline{b}′ is in the orbit of B iff there exists \overline{d}′ in the orbit of \overline{d} in A_{c} such that φ(\overline{d}′, \overline{b}′) holds in B.

Proof of Claim: First, suppose \overline{b}′ is in the orbit of \overline{b}. If f is an automorphism of B taking \overline{b} to \overline{b}′, then, as above, f restricts to an automorphism of A^{∗}, and we get an automorphism f_{c} of A_{c}, taking c(d_{i}) to c(f(d_{i})). While f(\overline{d}) may not be in A_{c}, \overline{d}′ = f_{c}(\overline{d}) is in A_{c}. By 1, there is an automorphism of B extending f_{c}, and we have φ(\overline{d}′, \overline{b}′). Now, suppose φ(\overline{d}′, \overline{b}′) holds in B, where \overline{d}′ is in the orbit of \overline{d} in A_{c}. By 1, an automorphism of A_{c} mapping \overline{d}′ to \overline{d} extends to an automorphism f of B. Then f maps \overline{b}′ to a tuple \overline{b}′′ satisfying φ(\overline{d}, \overline{x}), and this \overline{b}′′ is in the orbit of \overline{b}. This completes the proof of the claim.

Using the claim, we can see that if the orbit of \overline{d} in A_{c} is hyperarithmetical, then the orbit of \overline{b} in B is also hyperarithmetical. Moreover, if the orbits of tuples in A_{c} have bounded complexity, then the orbits in B also have bounded complexity. Therefore, if SR(A) is computable, or at most ω_{1}^{CK}, then so is SR(B). Putting together what we have shown, we get the fact that either SR(A) and SR(B) are both computable or else they are equal.

Corollary 3.6. There is a computable embedding Φ of undirected graphs into fields of any desired characteristic, such that Φ has the rank-preservation property.

3.3 Embedding undirected graphs in linear orderings

Friedman and Stanley [5] gave an embedding of undirected graphs in linear orderings. We start with the lexicographic ordering on Q^{<ω}. Let (t_{n})_{n∈ω} be a list of the atomic types for tuples in graphs, such that the types with m variables appear before those with m+1 variables. Let (Q_{a})_{a∈ω} be a computable partition of Q into dense subsets. The sets Q_{0} and Q_{1} have special roles. For a graph G, we let Φ(G) be the sub-ordering of Q^{<ω} consisting of the sequences r_{0}q_{1}r_{1}q_{2}r_{2}, … q_{n}r_{n}k such that for some tuple a_{1} … a_{n} in G, of atomic type t_{m}, we have q_{i} ∈ Q_{a_{i}}, for i < n, r_{i} ∈ Q_{0}, r_{n} ∈ Q_{1}, and k < m.

It is clear that this gives a computable transformation. Formally, we may take Φ to be the set of pairs (α, φ), where α is the diagram of finite graph G, and φ is in the atomic diagram of the corresponding linear ordering. It is not so obvious that Φ is 1 − 1 on isomorphism types. The authors are grateful to Desmond Cummins for providing a complete proof (in work related to his senior thesis).

Lemma 3.7. The transformation Φ is 1 − 1 on isomorphism types.

Proof. For b of length 2n + 2, we say that b is at level n. Note that we can recover the level of b from the size of the maximal discrete set containing it. If b and b′ agree on the first 2m tems, then between b and b′, all elements have level at least m. We refer to the greatest such m as the level of agreement. If b = r_{0}q_{1}r_{1} … q_{n}r_{n}k, where q_{i} ∈ Q_{a_{i}}, we let g(b) = a_{1} … a_{n}. We say that b represents the tuple a_{1} … a_{n}.

Suppose G ≅_{f} G′. We must show that Φ(G) ≅ Φ(G′). We define a backand-forth family. Let F_{1} be the set of finite partial 1 − 1 functions p from Φ(G) to Φ(G′) such that the domain and range are unions of maximal discrete sets, p preserves order, level, and level of agreement, and if p(b) = b′, and g(b) = a_{1} … a_{n}, then g(b′) = f(a_{1}) … f(a_{n}). Let p be in F_{1}. We show how to extend p, adding a new element b to the domain (adding an element to the range is the same).

Let b be a new element, not in dom(p). Say m is the greatest such that b agrees with some d in dom(p) down to level m. There may be more than one such d. We can choose b′ in the appropriate interval in the ordering, agreeing up to level m with d′ = p(d), such that b′ has the required g(b′). Let b = r_{0}q_{1}r_{1} … r_{n}q_{n}k, and let d′ = r′_{0}q′_{1}r′_{1} … q′_{m}r′_{m} . . .. We take b′ = r′_{0}q′_{1}r′_{1} … q′_{m}r^{∗}q_{m+1}r_{m+1} … q_{n}r_{n}k, matching d′ up to level m, and with q′_{i}, for m < i ≤ n such that if q_{i} ∈ Q_{a_{i}}, then q′_{i} ∈ Q_{f(a_{i})}. We choose r^{∗} in Q_{1} (or in Q_{0} in case m = n), so as to locate b′ to the left or right of d′, and other elements of ran(p), to preserve order. We extend p, mapping the maximal discrete interval of b to that of b′. Using the back-and-forth family, we get an isomorphism between Φ(G) and Φ(G′).

Now, suppose Φ(G) ≅_{f} Φ(G′). We must show that G ≅ G′. We define another back-and-forth family. Let F_{2} be the set of finite partial 1 − 1 functions p from G to G′ such that for some b in Φ(G) and b′ = f(b) in Φ(G′), g(b) = a_{1} … a_{n} is the domain of p, arranged in a sequence, and g(b′) = a′_{1} … a′_{n} is the corresponding sequence with a′_{i} = p(a_{i}). We say how to extend p, adding a new element a_{n+1} to the domain (adding an element to the range is the same). Say b = r_{0}q_{1}r_{1} … q_{n}r_{n}k and f(b) = r′_{0}q′_{1}r′_{1} … q′_{n}r′_{n}k witness the fact that p ∈ F_{2}. Take d agreeing with b to level n (i.e., through q_{n}), with further terms r_{n}^{∗}, q_{n+1}, r_{n+1}, 0, where q_{n+1} ∈ Q_{a_{n+1}}. Then f(d) must agree with f(b) to level n (through q′_{n}). Moreover, f(d) has the same level as d, with further terms r_{n}^{∗} ∗ q′_{n+1}r′_{n+1}0. Say q′_{n+1} ∈ Q_{a′_{n+1}}. We extend p mapping a_{n+1} to a′_{n+1}. Using the back-and-forth family, we get an isomorphism between G and G′.

We must show that Φ has the rank-preservation property.

Claim 1: There is a computable function f from tuples in G to elements of Φ(G), such that \overline{a} and \overline{a}′ are in the same orbit in G iff f(\overline{a}) and f(\overline{a}′) are in the same orbit in Φ(G).

Proof of Claim 1: For each tuple \overline{a} = a_{1}, …, a_{n} in G, we let f(\overline{a}) be the element q_{1}r_{1}q_{2}r_{2}, … q_{n}r_{n}0, where q_{i} is the first element that we find in Q_{a_{i}} (we may take the one with least Gödel number), for i < n, r_{i} is the first element that we find in Q_{0}, and r_{n} is the first element that we find in Q_{1}. Then \overline{a} and \overline{a}′ are in the same orbit in G iff their f-images are in the same orbit in Φ(G). This is clear from the proof above that Φ is 1 − 1 on isomorphism types.

Claim 2: There is a definable set X ⊆ Φ(G) with a computable function g from X to tuples in G, such that for b, b′ ∈ X, b and b′ are in the same orbit in Φ(G) iff g(b) and g(b′) are in the same orbit in G.

Proof of Claim 2: We let X consist of the sequences in Φ(G) ending in 0. These are the left limit points (i.e, the limits approached from the left). Suppose b ∈ X, say b = q_{1}r_{1}q_{2}r_{2}, … q_{n}r_{n}0, where q_{i} ∈ Q_{a_{i}}, for i < n, r_{i} ∈ Q_{0}, and r_{n} ∈ Q_{1}. For b, b′ ∈ X, b and b′ are in the same orbit in Φ(G) iff g(b) and g(b′) are in the same orbit in G. Again, this is clear from the proof above that Φ is 1 − 1 on isomorphism types.

Claim 3: For each tuple \overline{b} in Φ(G), there is a tuple \overline{d} in X, and a computable infinitary formula φ(\overline{u}, \overline{x}) such that Φ(G) ⊧ φ(\overline{d}, \overline{b}), and \overline{b}′ is in the orbit of \overline{b} iff there exists \overline{d}′ in X such that each d_{i} in \overline{d} is in the same orbit as the corresponding d′_{i} in \overline{d}′, and Φ(G) ⊧ φ(\overline{d}′, \overline{b}′).

Proof of Claim 3: Let \overline{b} = b_{1}, …, b_{r} be a tuple in Φ(G). For each b_{i}, we let d_{i} be the first element of the maximal discrete set containing b_{i}. From the size of the maximal discrete set, we can recover the length of the tuple g(d_{i}). If d_{i} agrees with d_{j} on the first 2m terms, so that g(d_{i}) and g(d_{j}) agree on the first m terms, then the interval between d_{i} and d_{j} consists of elements representing extensions of the same tuple in G of length m. Then the pair (b_{i}, b_{j}) satisfies a formula a_{m}(x, y) saying that for all z in the interval between x and y, the maximal discrete set containing z has size corresponding to the atomic type of a tuple of length at least m. Conversely, if (b_{i}, b_{j}) satisfies the formula a_{m}(x, y), where b_{i} and b_{j} lie on different maximal discrete sets and each represents a tuple from G of length at least m, then the tuples agree on the first m terms.

Suppose A is a computable graph, and let B = Φ(A). Let X, f, and g be as described above. Then A and B satisfy the hypotheses of the following result.

Theorem 3.8. Let A and B be hyperarithmetical structures.

1. Suppose there is a hyperarithmetical map f from tuples in A to tuples in B such that \overline{a} and \overline{a}′ are in the same orbit in A iff f(\overline{a}) and f(\overline{b}) are in the same orbit in B. If SR(B) is computable, then so is SR(A), and if SR(B) ≤ ω_{1}^{CK}, then SR(A) ≤ ω_{1}^{CK}.

2. Suppose g is a hyperarithmetical map from a set X of tuples in B, invariant under automorphism, to tuples in A, such that for \overline{d}, \overline{d}′ ∈ X, \overline{d} and \overline{d}′ are in the same orbit in B iff g(\overline{d}) and g(\overline{d}′) are in the same orbit in A. Suppose further that for each tuple \overline{b} in B, there is a finite collection of tuples \overline{d}_{1}, …, \overline{d}_{n} in X, and for some β < α there is a computable Σ_{β} formula φ which is true of \overline{d}_{1}, …, \overline{d}_{n}, \overline{b}, such that for all \overline{b}′ in B, \overline{b} and \overline{b}′ are in the same orbit iff there exist \overline{d}′_{1}, …, \overline{d}′_{n} in X such that \overline{d}_{i} and \overline{d}′_{i} are in the same orbit, and φ is satisfied by \overline{d}′_{1}, …, \overline{d}_{n}, \overline{b}′ in B. Then if SR(A) is computable, or at most ω_{1}^{CK}, so is SR(B).

Proof. For 1, suppose f is Δ_{α}^{0}. If the orbits in B are all Δ_{α}^{0}, then so are the orbits in A. If the orbits in B are all hyperarithmetical, but not necessarily of bounded complexity, then the orbits in A are also all hyperarithmetical. Therefore, if SR(B) is computable, or at most ω_{1}^{CK}, then the same is true of SR(A).

For 2, suppose g is Δ_{α}^{0}. If the orbits in A are all Δ_{α}^{0}, or all hyperarithmetical, then the same is true of the orbits of tuples in X. Take a tuple \overline{b} in B, and let \overline{d}_{1}, \overline{d}_{n} and φ be as in 2. Then the orbit of \overline{b} is Δ_{α}^{0}, or hyperarithmetical, depending on the complexity of the orbits of certain tuples in X. Therefore, if SR(A) is computable, or at most ω_{1}^{CK}, the same is true of SR(B).

Corollary 3.9. There is a computable embedding Φ of graphs into linear orderings such that Φ has the rank-preservation property.

Remarks: Part 2 of Theorem 3.8 implies Part 1, with the roles of A and B reversed. If (A, B) satisfies 1 and 2, or (A, B) and (B, A) both satisfy 2, then either A and B both have computable Scott rank or else the ranks are the same. We can also show that this implies our earlier “general” results: Proposition 3.3 and Proposition 3.5.

Proposition 3.3. Suppose A is definable in B and every automorphism of A extends to an automorphism of A. Suppose for all \overline{b} in B, there is a formula φ(\overline{c}, \overline{b}), of bounded complexity, defining the orbit of B over A. Then either A and B both have computable Scott rank or else the Scott ranks are the same.

Proof of Proposition 3.3 from Theorem 3.8: Let f be the identity function on tuples from A. If \overline{a} and \overline{a}′ are in the same orbit in A, then they are in the same orbit in B. The converse is obvious. Applying 1 above, we conclude that if SR(B) is computable, or at most ω_{1}^{CK}, then SR(A) is computable, or at most ω_{1}^{CK}. Let g also be the identity function on tuples from A. Let \overline{b} be a tuple in \overline{B}, and let φ(\overline{c}, \overline{x}) define the orbit of B over A, as in the hypothesis. Then \overline{b}′ is in the same orbit as \overline{b} iff there exists \overline{c}′ ∈ A, in the orbit of \overline{c}, such that φ(\overline{c}′, \overline{b}′) holds. Applying 2 above, we conclude that if SR(A) is computable, or at most ω_{1}^{CK}, then SR(A) is computable, or at most ω_{1}^{CK}.

Proposition 3.5. Let B be a hyperarithmetical structure, and let A = A^{∗}/_{≡}, where ≡ is a congruence relation on A^{∗} = (D, (R_{i})_{i∈I}), and A^{∗} and ≡ are definable in B by computable infinitary formulas of bounded complexity. Further suppose that for any choice function c choosing one element from each a ∈ A, we have A ≅_{c} A_{c}. Suppose in addition that the following conditions are satisfied.

1. For any automorphism f of A and any choice function c, the automorphism given by c ∘ f ∘ c^{−1} of A_{c} extends to an automorphism of B.

2. For any tuple \overline{b} in B, the orbit of \overline{b} under automorphisms of B that fix D pointwise is defined by a computable infinitary formula, φ(\overline{d}, \overline{x}), of bounded complexity, where the parameters \overline{d} may be chosen to be in ran(c) for any choice function c.

Then either A and B have the same Scott rank, or else both have computable Scott rank.

Proof of Proposition 3.5 using Theorem 3.8: Let c be a hyperarithmetical choice function. We obtain a hyperarithmetical copy of A with universe equal to ran(c). We identify this with A. Let f(\overline{a}) = \overline{a}, for \overline{a} in A, and for \overline{d} in D, let g(\overline{d}) = \overline{a}, where c(d_{i}) = a_{i}. For any \overline{b} in B, we have a tuple \overline{a} in A and a formula φ(\overline{a}, \overline{x}) defining the orbit of \overline{b} over A. Then \overline{b}′ is in the orbit of \overline{b} iff there exists \overline{d} in the orbit of \overline{a} such that φ(\overline{d}, \overline{b}′) holds.

Take \overline{a}, \overline{a}′ in A. If \overline{a} and \overline{a}′ are in the same orbit in A, then by 1 above, they are in the same orbit in B. Conversely, if they are in the same orbit in B, then because A is a definable quotient, they are in the same orbit in A. Therefore, if SR(B) is computable, or at most ω_{1}^{CK}, SR(A) is also. Next, take a tuple \overline{d} of elements representing different equivalence classes in D. Say g(\overline{d}) = \overline{a} and g(\overline{d}′) = \overline{a}′. If \overline{d} and \overline{d}′ are in the same orbit in B, then \overline{a} and \overline{a}′ are in the same orbit in A, since A is a definable quotient structure. If \overline{a} and \overline{a}′ are in the same orbit in A, then by 1 and 2 above, \overline{d} and \overline{d}′ are in the same orbit in B. We have \overline{d}′ in the same orbit as \overline{d} iff g(\overline{d}) is in the same orbit as g(\overline{d}′). If SR(A) is computable, or ω_{1}^{CK}, then the orbits of tuples from D have bounded complexity, or are all hyperarithmetical.

Now, take \overline{b} in B, and let φ(\overline{a}, \overline{x}) be as in 2 above, defining the orbit of \overline{b} under automorphisms of B that fix D. Then \overline{b}′ is in the orbit of \overline{b} iff there exists \overline{d} in the orbit of \overline{a} such that φ(\overline{d}, \overline{b}′) holds. The complexity of the orbit of \overline{b} is not far from the complexity of that of \overline{a} (as a tuple in D). Therefore, if SR(A) is computable, or ω_{1}^{CK}, then SR(B) is also.

4 Conclusion

We are ready to prove the result stated in the introduction.

Theorem 4.1 (Main Theorem). Each of the following classes contains a computable structure of Scott rank ω_{1}^{CK}. Moreover, there is one which is strongly computably approximable.

1. undirected graphs,

2. fields of any characteristic,

3. linear orderings.

Proof. For 1, let T be a computable tree of Scott rank ω_{1}^{CK}, and let Φ be a rank-preserving computable embedding of trees in undirected graphs. We get a computable undirected graph of Scott rank ω_{1}^{CK} by taking Φ(T ) and then passing to a computable copy G.

We show that if T is strongly computably approximable, then so is G. Let S be a Σ_{1}^{1} set. Take a uniformly computable sequence of trees (T_{n})_{n∈ω} such that if n ∈ S, then T_{n} ≅ T , and otherwise, T_{n} has computable rank. Applying Φ to the sequence (T_{n})_{n∈ω}, and then applying a uniform effective procedure to pass to computable copies, we get a uniformly computable sequence of graphs (G_{n})_{n∈ω} such that if n ∈ S, then G_{n} ≅ G, and if n ∉ S, then G_{n} has computable rank. Therefore, G is strongly computably approximable.

For 2 and 3, let G be a computable undirected graph of Scott rank ω_{1}^{CK}, and let Φ be a rank-preserving computable embedding of undirected graphs in fields of the desired characteristic, or in linear orderings. In the same way as above, we get a computable field, or linear ordering, of Scott rank ω_{1}^{CK}. Moreover, if G is strongly computably approximable, then so is the field, or linear ordering.

We have used computable embeddings to transfer results on trees to further classes of structures. Our results are not sensitive to the precise definition of computable embedding. What we need is a function Φ from K to K′ such that

1. for A, A′ in K, A ≅ A′ iff Φ(A) ≅ Φ(A′),

2. if A ∈ K is computable, then Φ(A) has a computable copy B, with index computable from that for A, 3. if A ∈ K is computable, then either SR(A) and SR(Φ(A)) are both

computable, or SR(A) = SR(Φ(A)).

Suppose Φ satisfies these three properties. If K contains a computable structure A of Scott rank ω_{1}^{CK}, then K′ contains a computable structure B with this same rank. Moreover, if A is strongly computably approximable, then so is B.

We have shown that there are computable structures of Scott rank ω_{1}^{CK} in some familiar classes. There are classes with computable members of arbitrarily large computable rank, but with no computable member of Scott rank ω_{1}^{CK}.

Proposition 4.2 (essentially, Barwise). If A is a computable Abelian pgroup, then SR(A) ≠ ω_{1}^{CK}.

Proof. If A has computable length, then the Scott rank is computable. The only non-computable length possible for a computable group is ω_{1}^{CK}. If A has length ω_{1}^{CK}, then it cannot be reduced. The divisible elements have Scott rank ω_{1}^{CK}, so A has Scott rank ω_{1}^{CK} + 1.

The last result gives two further classes, not so nicely axiomatized as Abelian p-groups, but similar in other ways.

Proposition 4.3.

1. If A is a computable model of the computable infinitary theory of well orderings, then SR(A) ≠ ω_{1}^{CK}.

2. If A is a computable model of the computable infinitary theory of superatomic Boolean algebras, then SR(A) ≠ ω_{1}^{CK}.

Proof. For 1, suppose A is a computable model of the computable infinitary theory of well orderings, and SR(A) is not computable. The theory has sentences saying that if there is an element satisfying φ(x), then there is a first such element. Suppose that for some computable ordinal β, every element is least to satisfy some computable Π_{β} formula. Then each element b is defined by the conjunction of the computable Π_{β} formulas true of b, and a formula saying that it is first to satisfy all of these formulas. This formula is computable Π_{β+1}. Then each tuple \overline{b} is defined by a computable Π_{β+1} formula. Since SR(A) is not computable, this is impossible. For each β, there exists b not first to satisfy any computable Π_{β} formula. Let Γ(x) be a Π_{1}^{1} set of formulas saying that x is not first to satisfy any computable infinitary formula. Every Δ_{1}^{1} subset is satisfied in A. Therefore, the whole set is satisfied by some b. We show that b has rank ω_{1}^{CK}. Say the orbit of b is defined by a computable infinitary formula φ(x). Now, b is not least to satisfy φ(x), and the least is not in the same orbit.

For 2, suppose A is a model of the computable infinitary theory of superatomic Boolean algebras, and SR(A) is not computable. We say that b is minimal satisfying φ(x) if b satisfies φ(x) and there does not exist a ≤ b such that both a and b−a satisfy φ(x). The theory has sentences saying that if there is an element satisfying φ(x), then there is a minimal such element. To see this, recall that in a countable superatomic Boolean algebra, each element is a finite join of α-atoms, for some countable ordinal α. Take the least α and the least n for this α such that some join of n α-atoms satisfies φ(x). Then this is minimal.

Suppose there is some computable β such that each element of A is minimal satisfying some computable Π_{β} formula. Then for any tuple \overline{b} in A, the orbit of \overline{b} is defined by giving the computable Π_{β} formulas satisfied by the atoms of the finite subalgebra generated by \overline{b}. Since SR(A) is not computable, this is impossible. For each computable ordinal β, there exists b such that b is not minimal satisfying any computable Π_{β} formula. Let Γ(x) say that for all computable infinitary formulas φ(x), b is not minimal satisfying φ(x). Every Δ_{1}^{1} subset is satisfied in A. Therefore, the whole set is satisfied by some b. We show that b has rank ω_{1}^{CK}. Say the orbit of b is defined by φ(x). Now, b is not minimal satisfying φ(x), and if a is minimal satisfying φ(x), then a is not in the orbit of b.

For each of the theories above, we have given a Π_{1}^{1} set of axioms, included in the theory, such that no computable model of the axioms has Scott rank ω_{1}^{CK}.

References

[1] Ash, C. J., and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, 2000.

[2] Barwise, J., “Infinitary logic and admissible sets”, J. Symb. Logic, vol. 34(1969), pp. 226–252.

[3] Calvert, W., D. Cummins, J. F. Knight, and S. Miller, “Comparing classes of finite structures”, Algebra and Logic, vol. 43(2004), pp. 365–373.

[4] Calvert, W., J. F. Knight, and J. M. Young, “Computable trees of Scott rank ω_{1}^{CK}”, pre-print.

[5] Friedman, H., and L. Stanley, “A Borel reducibility theory for classes of countable structures”, J. Symb. Logic, vol. 54(1989), pp. 894–914.

[6] Goncharov, S. S., and J. F. Knight, “Computable structure and nonstructure theorems”, Algebra and Logic, vol. 41(2002) (English), pp. 351– 373.

[7] Goncharov, S. S., V. S. Harizanov, J. F. Knight, and R. Shore, “Π_{1}^{1} relations and paths through O”, J. Symb. Logic, vol. 69(2004), pp. 585–611.

[8] Harrison, J., “Recursive pseudo well-orderings”,Transactions of the Amer. Math. Soc., vol. 131(1968), pp. 526–543.

[9] Hirschfeldt, D., B. Khoussainov, A. Slinko, and R. Shore, “Degree spectra and computable dimension in algebraic structures”, Annals of Pure and Appl. Logic, vol. 115(2002), pp. 71–113.

[10] Keisler, H. J., Model Theory for Infinitary Logic, North-Holland, 1971.

[11] Knight, J. F., “Effective transfer of invariants”, submitted to J. Symb. Logic.

[12] Knight, J. F., and J. M. Young, “Computable structures of Scott rank ω_{1}^{CK}”, submitted to J. Math. Logic.

[13] Makkai, M., “An example concerning Scott heights”, J. Symb. Logic, vol. 46(1981), pp. 301–318.

[14] Marker, D., Model theory: An Introduction, Springer-Verlag, 2002.

[15] Morozov, A. S., “Groups of computable automorphisms”, in Handbook of Recursive Mathematics, ed. by Yu. L. Ershov, et. al., 1998, Elsevier, pp. 311–345.

[16] Nadel, M. E., “Scott sentences for admissible sets”, Annals of Math. Logic, vol. 7(1974), pp. 267–294.

[17] Nadel, M. E., “L_{ω_{1}ω} and admissible fragments”, in Model-Theoretic Logics, ed. by K. J., Barwise and S. Feferman, Springer-Verlag, 1985, pp. 271–316.

[18] Rogers, H., Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.

[19] Scott, D., “Logic with denumerably long formulas and finite strings of quantifiers”, in The Theory of Models, ed. by J. Addison, L. Henkin, and A. Tarski, North-Holland, 1965, pp. 329–341.

[20] Soskov, I. N., “Intrinsically Δ_{1}^{1} relations”, Math. Logic Quarterly, vol. 42(1996), pp. 469–480.