Classification From a Computable Viewpoint

W. Calvert and J. F. Knight

June 15, 2005

1 Introduction

Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work, showing that certain classes of mathematical structures admit classification, while others do not. In the present paper, we describe some recent work on classification in computable structure theory.

Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.

Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings.

We shall assume some background in computability—m-reducibility, arithmetical and hyperarithmetical hierarchies, Σ_{1}^{1} and Π_{1}^{1} sets and relations. This material may be found in [46], or in [1].

1.1 Background from model theory

In classical model theory, the basic setting is the class K of models for a countable complete elementary first order theory. If the theory has an infinite model, then there are models of all infinite cardinalities. For the theory of vector spaces over the rationals, each model is determined up to isomorphism by its dimension. More generally, for an ℵ_{1}-categorical theory T, each model is determined, up to isomorphism, by the dimension of a “strongly minimal” formula, with parameters satisfying a principal type [39], [2]. This is the prototypical structure theorem. For the theory of dense linear orderings without endpoints, or other unstable theory, there are 2^{κ} non-isomorphic models of cardinality κ, for all κ ≥ ℵ_{1}, too many to allow nice invariants [51]. (See [25] for a discussion of further structure and non-structure theorems in the setting of models having arbitrary cardinality.)

Vaught [54] focused attention on countable models. Let T be a countable complete elementary first order theory, and consider the number of countable models, up to isomorphism. There are familiar examples illustrating some possible numbers. For the theory of dense linear orderings without endpoints, the number is 1. For the theory of vector spaces over the rationals, the number is ℵ_{0}. For true arithmetic, the number is 2^{ℵ_{0}}. Ehrenfeucht found an example for which the number is 3: the theory of dense linear orderings without endpoints, with a strictly increasing sequence of constants. The example is easily modified to give examples for which the number is n, for all n ≥ 3. The Ehrenfeucht examples are described in [54]. Vaught showed that for a countable complete theory, the number of isomorphism types of countable models cannot be 2.

Vaught conjectured that for a countable complete theory, the number of countable models, up to isomorphism is either ≤ ℵ_{0} or 2^{ℵ_{0}}. Vaught’s Conjecture has been proved for many special kinds of theories, including theories of linear orderings [47] and trees [53], ω-stable theories [52], and superstable theories of finite rank [6]. In the setting of Vaught’s Conjecture, the statement that T has 2^{ℵ_{0}} isomorphism types of countable models is a non-structure theorem. The statement that T has only countably many isomorphism types of countable models is a kind of structure theorem. While it does not provide descriptions for the models, it holds out the possibility that there may be nice descriptions.

1.2 Infinitary formulas

In describing countable structures, certain infinitary (but still first order) sentences are useful. For a language L, the L_{ω_{1}ω} formulas are infinitary formulas in which the disjunctions and conjunctions over countable sets. For a thorough discussion of L_{ω_{1}ω}, see Keisler’s beautiful book [28]. Scott [49] proved the following.

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

A sentence σ with the property of Theorem 1.1 is called a Scott sentence for A. In proving 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. \overline{a} ≡^{0} \overline{b} if \overline{a} and \overline{b} satisfy the same quantifier-free formulas,

2. for α > 0, \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}.

Our relations ≡^{α} differ from Scott’s in that we consider tuples \overline{c} and \overline{d}, where Scott considered only single elements c and d.

Definition 2.

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

2. The Scott rank of the structure A, denoted by 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.

Morley [40] showed that if T is a counter-example to Vaught’s Conjecture, then the number of isomorphism types of countable models must be ℵ_{1}. The idea is behind the proof is that each model must have countable Scott rank, and for each countable ordinal α, the number of models of rank α must be countable or 2^{ℵ_{0}}. Vaught’s Conjecture holds for T iff for some countable ordinal α either there are 2^{ℵ_{0}} non-isomorphic models of rank α, or else all countable models have Scott rank at most α. Shelah’s proof of Vaught’s Conjecture for ω-stable theories [52] involves putting a fixed countable ordinal bound on the Scott ranks of all models. For more information related to Scott rank, see [48].

1.3 Background from descriptive set theory

Next, we turn to descriptive set theory. We mention only a few notions and results. For more information, see [24] or [5]. We describe a version of the basic setting. The structures are countable, with fixed universe ω. The languages are also countable. For a given language L, we have a list (φ_{n})_{n∈ω} of all atomic sentences involving symbols from L plus constants from ω. We may identify a structure A with the function f ∈ 2^{ω} such that

f(n) = \{ \begin{matrix}1 & if A ⊧ φ_{n} \\ 0 & if A ⊧ ¬φ_{n} \end{matrix}

The class of all structures for the language, or functions in 2^{ω}, has a natural metric topology, where the distance between f, g ∈ 2^{ω} is 1/2^{n} if n is least such that f(n) ≠ g(n). The class of structures for the language forms a Polish space; i.e., it is separable and complete. The basic open neighborhoods have the form N_{σ} = {f ∈ 2^{ω} : f ⊇ σ}, where σ ∈ 2^{<ω}. The Borel subsets are generated from the basic open neighborhoods, by taking countable unions and complements. We may also consider Borel subsets of a product of classes. We have Borel relations on a given class, and Borel functions from one class to another.

We consider classes K, contained in the Polish space described above, such that K is closed under isomorphism. By results of Scott [49], Vaught [55], and D. Miller [38], K is Borel iff it is the class of models of some L_{ω_{1}ω} sentence. We add the assumption that K is Borel. One approach to classification in this setting is to consider the isomorphism relation on K. A result saying that the isomorphism relation on a class K is Borel is a weak kind of structure theorem, and a result saying that the isomorphism relation is not Borel is a non-structure theorem.

For the class of vector spaces over ℚ, or the class of algebraically closed fields of a given characteristic, the isomorphism relation is Borel. More generally, for any class K with only countably many isomorphism types, the isomorphism relation is Borel. The converse is not true. For example, if K is the class of Archimedean ordered fields, then there are 2^{ℵ_{0}} different isomorphism types, but the isomorphism relation is still Borel. For the class of linear orderings, the isomorphism relation is not Borel. Perhaps surprisingly, Hjorth [23] showed that for the class of torsion-free Abelian groups, the isomorphism relation is not Borel.

There is a second approach to classification, which involves comparing classes, and provides a great deal of information. This is the approach of Friedman and Stanley [16].

Definition 3. Let K, K′ be classes of structures. We say that Φ is a Borel embedding of K in K′ if Φ is a Borel function from K to K′, and for A, A′ ∈ K, A ≅ A′ iff Φ(A) ≅ Φ(A′). (More properly, we might say that Φ is an embedding of K in K′ up to isomorphism, or an embedding of K/≅ in K′/≅.)

Notation: We write K ≤_{B} K′ if there is a Borel embedding of K in K′.

Proposition 1.2. The relation ≤_{B} is a partial order on the set of all classes.

A Borel embedding gives us a way of transferring descriptions from one class to another. If K ≤_{B} K′, under the Borel embedding Φ, and K′ has simple invariants, then we may describe A ∈ K by giving the invariants for Φ(A). We say that K is Borel complete if for all K′, K′ ≤_{B} K; equivalently, K′ ≤_{B} K, where K′ is the class of all structures for a language with at least one at least binary relation symbol. Our intuition says that K′ cannot be classified, so the statement that K is Borel complete is a convincing non-structure theorem. Friedman and Stanley [16] produced Borel embeddings of undirected graphs in fields of arbitrary characteristic, trees, and linear orderings, showing that all of these classes are “Borel complete”. We shall say more later about some of these embeddings.

2 Computable structures

We now turn to computable structures. The languages that we consider are computable; i.e., the set of non-logical symbols is computable, and we can effectively determine the kind (relation or function) and the arity. The structures have universe a subset of ω, and we identify a structure A with its atomic diagram D(A). A structure A is computable if D(A) is computable. Then a computable index for A is a number e such that φ_{e} is the characteristic function of D(A). We write A_{e} for the structure with index e (if there is such a structure).

2.1 Computable infinitary formulas

In describing computable structures, it is helpful to use computable infinitary formulas. Roughly speaking, these are infinitary formulas in which the disjunctions and conjunctions are over computably enumerable sets. For a more thorough discussion, see [1].

Example: There is a natural computable infinitary sentence whose models are just the Abelian p-groups—the conjunction of the usual axioms for Abelian groups, plus

∀x ⋁_{n} ⋁ \underbrace{x + … + x}_{p^{n}} = 0 .

All together, computable infinitary formulas have the same expressive power as those in the least admissible fragment of L_{ω_{1},ω}. The usefulness comes from the following classification.

Complexity of formulas

1. A computable Σ_{0} and Π_{0} formula is a finitary open formula.

2. For α > 0, a computable Σ_{α} formula φ(\overline{x}) is a c.e. disjunction of formulas of the form ∃\overline{u} ψ(\overline{u}, \overline{x}), where ψ is computable Π_{β} for some β < α.

3. For α > 0, a computable Π_{α} formula is a c.e. conjunction of formulas of the form ∀\overline{u} ψ(\overline{u}, \overline{x}), where ψ is computable Σ_{β} for some β < α.

Proposition 2.1. Satisfaction of computable Σ_{α} (or Π_{α}) formulas in computable structures is Σ_{α}^{0} (or Π_{α}^{0}), with all possible uniformity.

There is a version of Compactness for computable infinitary formulas which, unlike the usual Compactness, can be used to produce computable structures. The original result of this kind, for weak second order logic, is due to Kreisel (in a footnote in [35]). Barwise [4] gave a result for countable admissible fragments of L_{ω_{1}ω}. The special case below, with its corollaries, may be found in [1].

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

Corollary 2.3. If Γ is a Π_{1}^{1} set of computable infinitary sentences and every Δ_{1}^{1} subset has a computable model, then Γ has a computable model.

The next two corollaries illustrate the power of computable infinitary formulas to describe computable structures.

Corollary 2.4. If A and B are computable (or hyperarithmetical) structures satisfying the same computable infinitary sentences, then A ≅ B.

Corollary 2.5 (Nadel [42]). Let A be a computable (or hyperarithmetical) structure. If \overline{a} and \overline{b} are tuples in A satisfying the same computable infinitary formulas, then there is an automorphism of A taking \overline{a} to \overline{b}.

The final corollary is a special case of a stronger result, due to Ressayre [45].

Corollary 2.6 (Ressayre). Let A be a computable (or hyperarithmetical) structure, and let Γ be a Π_{1}^{1} set of computable infinitary sentences involving finitely many new symbols, in addition to those in the language of A. If every Δ_{1}^{1} subset of Γ is satisfied in an expansion of A, then A has an expansion satisfying Γ.

2.2 Structure and non-structure theorems

Certain classes of structures arising in computable structure theory can be classified simply. Goncharov [18], [17] showed that the Boolean algebras with a property of “computable categoricity” are the ones with only finitely many atoms, and the linear orderings with this property are the ones with finitely many successor pairs. In a talk in Kazan in 1997, Goncharov stated a large number of further problems, calling for classification of further classes of computable structures. Some of these problems seemed likely to have nice answers, while others did not. At the end of the talk, Shore asked Goncharov what would make him give up. Shore’s question was considered in [21]. The aim was to find convincing statements for structure and non-structure theorems, like those in model theory and descriptive set theory.

Let K be a class of structures, closed under isomorphism. Let K^{c} be the set of computable elements of K. Let I(K) be the set of computable indices for elements of K^{c}. We suppose that there is a computable infinitary sentence for which K^{c} is the class of computable models. Equivalently, I(K) is hyperarithmetical. In [21], three different approaches are discussed. All give intuitively correct answers for some familiar classes (e.g., ℚ-vector spaces can be classified, linear orderings cannot).

The first approach involves “Friedberg enumerations”.

Definition 4. An enumeration of K^{c}/≅ is a sequence (C_{n})_{n∈ω} of elements of K^{c} such that for all A ∈ K^{c}, there exists n such that C_{n} ≅ A; i.e., the sequence represents all isomorphism types of computable members of K. The enumeration is Friedberg if for each A ∈ K^{c}, there is a unique n such that C_{n} ≅ A; i.e., each isomorphism type appears just once.

The complexity of the enumeration is that of the sequence of computable indices for elements of K. Saying that K^{c}/≅ has a hyperarithmetical Friedberg enumeration is an assertion of classifiability. Lack of repetition in the list reflects understanding of the different isomorphism types. This approach has considerable appeal. For one thing, in mathematical practice, a classification is often given by a list—think of the classification of finite simple groups. Another attractive feature of this approach is that it fits with an established body of work on enumerations, in computability and computable structure theory [15].

The second approach to classification considered in [21] is related to Scott ranks and Scott sentences. The result below, a consequence of Corollary 2.5, says which Scott ranks are possible for computable structures. We have already mentioned computable ordinals. These are the order types of computable well orderings of ω, and they form a countable initial segment of the ordinals. The first non-computable ordinal is denoted by ω_{1}^{CK}. Nadel used a different definition of Scott rank, but his work in [42] shows the following.

Theorem 2.7. For a computable structure A, SR(A) ≤ ω_{1}^{CK} + 1.

There are computable structures taking the maximum possible rank. Harrison [22] proved the following.

Proposition 2.8 (Harrison). There is a computable ordering of type ω_{1}^{CK}(1 + η) (with a first interval of type ω_{1}^{CK}, followed by densely many more).

Proof. Kleene showed that there is a computable tree T ⊆ ω^{<ω} with a path but no hyperarithmetical path. Let < be the Kleene-Brouwer ordering on T. Under this ordering, σ < τ iff either σ properly extends τ or else there is some first n on which σ and τ differ, and for this n, σ(n) < τ(n). Harrison showed that (T, <) has order type ω_{1}^{CK}(1 + η) + α, where α is a computable ordinal. There is an initial segment of type ω_{1}^{CK}(1 + η).

The Harrison ordering has Scott rank ω_{1}^{CK} + 1. If a is an element outside the initial interval of type ω_{1}^{CK}, then a has Scott rank ω_{1}^{CK}.

Theorem 2.9. 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 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.

If a computable structure has low Scott rank, then we expect it to have a simple Scott sentence. Nadel [42], [43] showed the following.

Theorem 2.10 (Nadel). A computable (or hyperarithmetical) structure has computable Scott rank iff it has a computable infinitary Scott sentence.

Proposition 2.11. Suppose K is a class of structures closed under isomorphism. If there is a computable bound on the Scott ranks of elements of K^{c}, then there is a computable ordinal α such that the elements of K^{c} all have computable Π_{α} Scott sentences.

If we understand that goal of computable classification is to describe each computable member of K, so as to distinguish its computable copies from other computable structures, then something weaker than a Scott sentence may suffice. A pseudo-Scott sentence for A is a sentence whose computable models are just the computable copies of A. We do not know whether there is a computable structure with a computable infinitary pseudo-Scott sentence but no computable infinitary Scott sentence. What we can prove is the following.

Proposition 2.12. Let K be a class of structures closed under isomorphism. Then the following are equivalent.

1. There is a computable ordinal α such that any elements of K^{c} satisfying the same computable Π_{α} sentences are isomorphic.

2. Each A ∈ K^{c} has a computable infinitary pseudo-Scott sentence.

The statements in Proposition 2.12 are structure theorems.

We turn to the third approach.

Definition 5. The isomorphism problem for K is

E(K) = {(a, b) : a, b ∈ I(K) & A_{a} ≅ A_{b}} .

The statement that E(K) is hyperarithmetical is one more structure theorem. For the class of computable models of a computable infinitary sentence, the three approaches are equivalent.

Theorem 2.13. If I(K) is hyperarithmetical, then the following are equivalent:

1. there is a computable ordinal α such that any two members of K^{c} satisfying the same computable Π_{α} sentences are isomorphic,

2. E(K) is hyperarithmetical,

3. K^{c}/≅ has a hyperarithmetical Friedberg enumeration.

Proof. It is not difficult to show that 1 implies 2 and 2 implies 3. To see that 3 implies 1, we form a hyperarithmetical structure A^{∗} including all structures in K^{c}, made disjoint. We also include a set corresponding to I(K) and a relation ℚ associating each index a ∈ I(K) with the elements of the corresponding structure A_{a}. Let I be a hyperarithmetical subset of I(K), representing indices in the Friedberg enumeration. We add this to A^{∗}. Let a, b be new constants, and let Γ(a, b) be a Π_{1}^{1} set of computable infinitary formulas saying a, b ∈ I, x ≠ y, and for all computable ordinals α, A_{a} and A_{b} satisfy the same computable Π_{α} sentences. If 1 fails, then every Δ_{1}^{1} subset of Γ(a, b) is satisfiable in A^{∗}. Then using Corollary 2.6, we can show that the whole set is satisfiable. This is a contradiction.

3 Isomorphism problems

Proposition 2.12 says that the three approaches to classification for computable structures are all equivalent. The first approach, involving Friedberg enumerations, is certainly appealing. However, the third approach, involving isomorphism problems, has proved to be more productive. When we attempt to determine, for various specific classes K, whether there is a hyperarithmetical Friedberg enumeration of K^{c}/≅, it seems that we must first calculate the complexity of E(K). In this section, we give a number of these calculations, mainly from [7], [8].

Of course, if I(K) is hyperarithmetical, then E(K) must be Σ_{1}^{1}, since the isomorphism relation may be defined by a statement that asserts the existence of a function that is total and bijective and preserves the basic relations and operations. For some classes of structures, it is well-known that the isomorphism problem is m-complete Σ_{1}^{1}.

Theorem 3.1 (Folklore). For each of following classes K, E(K) is m-complete Σ_{1}^{1}:

1. linear orderings

2. undirected graphs

3. Boolean algebras

4. Abelian p-groups

5. arbitrary structures for language with at least one at least binary relation symbol.

The ideas go back to Kleene and the fact that the class of indices for computable trees without paths, and the class of indices for well orderings are mcomplete Π_{1}^{1} (see [46]). For 1, we show that for any Σ_{1}^{1} set S, there is a uniformly computable sequence (A_{n})_{n∈ω} such that if n ∈ S, then A_{n} is a Harrison ordering, and if n ∉ S, then A_{n} is a well ordering. We have an m-reduction of S to the set of indices for the Harrison ordering. For parts 2-5, the proof is similar. In each case, the class K contains a structure A such that for any Σ_{1}^{1} set S, there is a uniformly computable sequence (A_{n})_{n∈ω} in K such that A_{n} ≅ A iff n ∈ S. For complete proofs of all parts of the theorem, see [21].

Items 1, 2, and 5 in Theorem 3.1 match our intuition. Whatever classification means, it should be impossible for these classes. Items 3 and 4 may be less clear. There are well-known results describing the structure of countable Abelian p-groups [27] in terms of the Ulm sequence and the dimension of the divisible part. Similarly, there are results of Ketonen [29], [44] describing the structure of countable Boolean algebras. Theorem 3.1 says that the invariants for computable Abelian p-groups, and computable Boolean algebras are not not uniformly simple. For the classes in the following theorem, which is proved in [7], our intuition may not say whether there should be a structure theorem, but the proofs make it clear that these are as bad as linear orderings or undirected graphs.

Theorem 3.2. For the following classes K, E(K) is m-complete Σ_{1}^{1}.

1. Ordered real closed fields (not necessarily Archimedean),

2. Arbitrary fields of any fixed characteristic.

The proof for 1 uses a lemma of van den Dries. For an ordered real closed field F, we define an equivalence relation ∼, where a ∼ b if there are polynomials p(x) and q(x), with rational coefficients, such that p(a) ≥ b and q(b) ≥ a. The equivalence classes are intervals, so we have an induced ordering on F/_{∼}. We can pass from a computable linear ordering L to a computable real closed field F (L) such that {x ∈ F : x ≥ 0}/ ∼ has order type L.

For 2, we get the characteristic zero case from 1. An alternate proof of that case, which extends to arbitrary characteristic, uses the Friedman and Stanley embedding of undirected graphs in fields (see Section 4).

Friedman and Stanley conjectured (in 1989) that the class of countable torsion-free Abelian groups is Borel complete [16]. The conjecture remains open, although Hjorth [23] succeeded in showing that the isomorphism relation on this class is not Borel. In [9], Hjorth’s proof is adapted to give the following result.

Theorem 3.3. Let K be the class of torsion-free Abelian groups. Then E(K) is not hyperarithmetical.

The proof involves coding trees in torsion-free Abelian groups (Hjorth used slightly different structures). For each α, we can show that E(K) is Δ_{α}^{0} hard, but the coding method varies with α, so we do not get the fact that the isomorphism problem is m-complete Σ_{1}^{1}.

So far, we have considered classes for which the isomorphism problem is complicated. Now, we turn to classes where the isomorphism problem should be less complicated. We consider classes with simple invariants. Perhaps the nicest examples are vector spaces over a fixed field and algebraically closed fields of fixed characteristic. For these classes, results on the isomorphism problems match our intuition. For the vector spaces, we assume that the relevant field is infinite, so that the class has infinite members of finite as well as infinite dimension. We also suppose that the field is computable. The following result is in [7].

Theorem 3.4. For the following classes K, E(K) is m-complete Π_{3}^{0}.

1. Vector spaces over a fixed infinite computable field,

2. Algebraically closed fields of fixed characteristic.

Proof. In each case, we show that E(K) is Π_{3}^{0} by noting that I(K) is Π_{2}^{0} and the following relation, on pairs (a, b) in I(K), is Π_{3}^{0}:

“For all n, the structure A_{a} has at least n independent elements if and only if A_{b} does.”

For completeness, we show that for any Π_{3}^{0} set S, there is a uniformly computable sequence (A_{n})_{n∈ω} in K such that n ∈ S iff A_{n} has infinite dimension.

In [9], Theorem 3.4 is generalized to the class K of models of a strongly minimal theory satisfying some extra conditions. The models are classified by dimension. We add a model-theoretic condition (acl(∅) is infinite) to guarantee that there are infinite models of finite as well as infinite dimension. We also need some effectiveness conditions (e.g., T is decidable with effective elimination of quantifiers).

It is also relatively simple to classify the computable Archimedean real closed fields, since each is determined, up to isomorphism, by the Dedekind cuts that are filled. The following result is in [7].

Theorem 3.5. If K is the class of Archimedean real closed fields, then E(K) is m-complete Π_{3}^{0}.

At this point, we return to the class of Abelian p-groups. Although we have an algebraic classification of countable Abelian p-groups, we have seen that the isomorphism problem is m-complete Σ_{1}^{1}. In fact, there is a single computable Abelian p-group whose inclusion in the class guarantees this. Below, we consider subclasses of Abelian p-groups that are “reduced” and have Ulm sequences of bounded length. For these subclasses, the isomorphism problem is hyperarithmetical, with complexity increasing with the bound on the length.

Below, we summarize the definitions leading to the Ulm sequence. For more information, see [27]. An Abelian p-group is reduced if it has no nontrivial divisible subgroup. Let G be a countable reduced Abelian p-group. We begin with the sequence of subgroups G_{α}, where G_{0} = G, G_{α+1} = pG_{α}, and for limit α, G_{α} = ∩_{β<α}G_{β}. Let P be the set of elements of G of order p, and let P_{α} = P ∩ G_{α}. Since G is reduced, there is a countable ordinal α such that G_{α} = {0}. The least such α is the length λ(G). For each β < α, P_{β}/P_{β+1} is a vector space over the field with p elements. We write u_{β}(G) for the dimension, which is either finite or ∞. The Ulm sequence is the sequence (u_{β}(G))_{β<λ(G)}.

Ulm’s Theorem says that a countable reduced Abelian p-group is determined, up to isomorphism, by its Ulm sequence. Previous papers, including [3] and [8] have given formulas, for any α and k, of complexity (depending on α), expressing that the αth Ulm invariant is at least k. Let K_{α} be the class of reduced Abelian p-groups of length at most α. In [8], there are results for these classes. It is shown that E(K_{ω}) is Π_{3}^{0}, E(K_{ω·2}) is Π_{5}^{0}, and in general, E(K_{ω·α}) is Π0 ; α̂, where

α̂ = sup_{γ<α}(2γ + 3)

We have a problem in expressing a meaningful completeness result. Until now, we have considered classes K for which I(K) was simpler than E(K). However, I(K_{ω}) is Π_{3}^{0}, the same complexity as E(K_{ω}) (and, in general, I(K_{ω·α}) is Π0 ; α̂, the same as E(K_{ω·α})) . It is conceivable that when we decide whether (a, b) ∈ E(K_{ω}), the main difficulty is determining whether a, b ∈ I(K). The following definition, stated in [8], separates the isomorphism problem from the problem of determining membership in the class.

Definition 6. Suppose A ⊆ B, and let Γ be a complexity class (e.g. Π_{3}^{0}).

1. We say that A is Γ within B if there is some R ∈ Γ such that A = R ∩ B.

2. We say that S ≤_{m} A within B if there is a computable f : ω → B such that for all n, n ∈ S iff f(n) ∈ A.

3. We say that A is m-complete Γ within B if A is Γ within B and for all S ∈ Γ, we have S ≤_{m} A within B.

The relevant example is where B = I(K)^{2} for some class K, and A = E(K). Note that the condition of being m-complete Γ within B is stronger that simply being m-complete Γ, since the “negative” examples produced by the reduction must be members of B. We will often write “Within K” to mean “Within I(K)^{2}.” All previous theorems in this section remain true when “Within K” is added to the statement. Using these definitions, we state the result from [8], with the appropriate completeness.

Theorem 3.6. Let K_{ω·α} be the class of reduced Abelian p-groups of length at most ω · α, and let α̂ = sup_{γ<α}(2γ + 3). Then E(K_{ω·α}) is m-complete Π0 ; α̂

within K_{α}.

Now we return to torsion-free groups, to consider a simpler subclass of those. The torsion-free Abelian groups are, essentially, subgroups of vector spaces over the rationals. The rank of such a group is the dimension of the least ℚ-vector space in which the group can be embedded. For groups of finite rank, the isomorphism problem is simple because there are simple isomorphisms.

We say that a structure A is computably categorical if for any B ≃ A, there is some computable function f : B → A which is an isomorphism. (For more about computable categoricity, see [1].) If all computable members of a class K are computably categorical, then E(K) must be Σ_{3}^{0}, at least within K.

Any torsion-free Abelian group of finite rank is computably categorical. Using this, it is possible to prove the following [9].

Theorem 3.7. Let K be either the class of all torsion-free Abelian groups of finite rank, or the class of torsion-free Abelian groups of rank 1. Then E(K) is m-complete Σ_{3}^{0} within K.

3.1 Optimal Scott sentences and index sets

Classification involves describing the structures in a class, up to isomorphism. One way to do this is by giving Scott sentences. If we consider only computable structures, it is enough to give pseudo-Scott sentences. How do we know when we have an optimal Scott sentence, or pseudo-Scott sentence?

For inspiration, we go to the setting of descriptive set theory, with arbitrary countable structures and Scott sentences in L_{ω_{1}ω}. As we said in Section 1, a class K closed under automorphism is Borel iff it is the class of models of some L_{ω_{1}ω} sentence. More is true. The class K is Σ_{α}^{0}, or Π_{α}^{0}, iff it is the class of models of some Σ_{α}, or Π_{α} sentence. If K(A) is the class of copies of a given A, then the form of the optimal Scott sentence matches the complexity of K. D. Miller [38] showed that if K(A) is Δ_{α}^{0}, then it is d-Σ_{α}^{0}. A. Miller [37] gave examples of structures A such that K(A) is Σ_{α}^{0}, Π_{α}^{0}, or d-Σ_{α}^{0} for various countable ordinals. He showed that K(A) cannot be properly Σ_{2}^{0}.

Now, we return to the computable setting, with computable structures and computable infinitary sentences. Let A be a computable structure, and let K be the class of structures for the language of A. If A has a computable Π_{α} Scott sentence, or pseudo-Scott sentence, then it is easy to see that I(A) is Π_{α}^{0}, within I(K). Similarly, if A has a computable d-Σ_{α} Scott sentence, or pseudo-Scott (i.e., one of the form φ & ¬ψ, where φ and ψ are computable Σ_{α}), then I(A) is d-Σ_{α}^{0} within I(K).

In [12], there are preliminary results supporting the thesis that for computable structures A of various familiar kinds, when we have found an optimal Scott sentence, or pseudo-Scott sentence, then the complexity of I(A) matches that of the sentence, and I(A) is m-complete in the complexity class. We begin with vector spaces.

Theorem 3.8. Let K be the class of vector spaces over ℚ, let K_{f} consist of the finite dimensional members of K, and let A be a computable member of K.

1. If dim A = 0 then I(A) is m-complete Π_{1}^{0} within K_{f}.

2. If dim A = 1 then I(A) is m-complete Π_{2}^{0} within K_{f}.

3. If 1 < dim A < ℵ_{0} then I(A) is m-complete d-Σ_{2}^{0} within K_{f}.

4. If dim A = ℵ_{0} then I(A) is m-complete Π_{3}^{0} within K.

For 3, the Scott sentence for A, within K_{f}, says that there are at least n linearly independent elements and there are not at least n + 1. For 2, we might first write a Scott sentence of the same kind, but this is not optimal. The optimal sentence says that any two elements are linearly dependent.

The situation for Archimedean ordered real closed fields is similar.

Theorem 3.9. Let K be the class of computable Archimedean real closed ordered fields, and let A be a computable member of K.

1. If the transcendence degree of A is 0, then I(A) is m-complete Π_{2}^{0} within K.

2. If the transcendence degree of A is finite but greater than 0, then I(A) is m-complete d-Σ_{2}^{0} within K.

3. If the transcendence degree of A is infinite then I(A) is m-complete Π_{3}^{0} within K.

There is a computable Π_{2} sentence φ characterizing the Archimedean real closed ordered fields. For 1, there is a computable Π_{2} Scott sentence, the conjunction of φ and a sentence saying that all elements are algebraic. For 2, fix a transcendence base, of size n, say. There is a computable Σ_{2} Scott sentence— the conjunction of φ and a sentence saying that the cuts of the transcendence base are filled, and there do not exist n + 1 algebraically independent elements. For 3, there is a computable Π_{3} Scott sentence—the conjunction of φ and a sentence saying the appropriate cuts are filled, and every element lies in one of the cuts that should be filled.

Now, we turn to Abelian p-groups. The proof of Theorem 3.6 does some index set calculations. In each case, the completeness was witnessed by a single reduced Abelian p-group. We get the following.

Proposition 3.10. Let A be the reduced Abelian p-group of length ω · α, with u_{γ}(A) = ∞ for all γ < α. Let α̂ = sup_{ωγ<α}(2γ + 3). Then I(A) is m-complete Π0 ; α̂ within the class of reduced Abelian p-groups of length ≤ ω · α.

A theorem of Khisamiev [30], [31] gives a description of the Ulm invariants of computable Abelian p-groups of length less than ω^{2}. For each of these groups, we can determine the complexity of the index set.

Theorem 3.11. Let K be the class of reduced Abelian p-groups of length ω M + N for some M, N ∈ ω. Let A ∈ K.

1. If A_{ωM} is minimal for the given length (i.e., it has the form ℤ_{p^{N}}), then I(A) is m-complete Π_{2M+1}^{0} within K.

2. If A_{ωM} is finite but not minimal for the given length, then I(A) is m-complete d-Σ_{2M+1}^{0} within K.

3. If there is a unique k < N such that u_{ωM+k}(A) = ∞, and for all m < k, u_{ωM+m}(A) = 0, then I(A) is m-complete Π_{2M+2}^{0} within K.

4. If there is a unique k < N such that u_{ωM+k}(A) = ∞ and for some m < k we have 0 < u_{ωM+m}(A) < ∞, then I(A) is m-complete d-Σ_{2M+2}^{0} within K.

5. If there exist m < k < N such that u_{ωM+m}(A) = u_{ωM+k}(A) = ∞, then I(A) is m-complete Π_{2M+3}^{0} within K.

In most cases here, the first Scott sentence that we write down, describing the Ulm sequence in a straightforward way, is not optimal. To specify that u_{ωM+k}(A) = ∞, it suffices, via a Ramsey’s Theorem argument, to say that for all r, the group A_{ωM} has a subgroup of type ℤ_{p^{k+1}}. This gives a simpler Scott sentence.

In [12], the models of the original Ehrenfeucht theory T illustrate a further pattern. Recall that T is the theory of a dense linear ordering without endpoints, with an infinite increasing sequence of constants. The three non-isomorphic models are as follows:

1. the prime model, in which the sequence has no upper bound,

2. a “middle” model, in which the sequence has an upper bound but no least upper bound, and

3. the saturated model, in which the sequence has a least upper bound.

Theorem 3.12. Let K be the class of models of the original Ehrenfeucht theory, and let A^{1}, A^{2}, and A^{3} be the prime model, the middle model, and the saturated model, respectively. Then

1. I(A^{1}) is m-complete Π_{2}^{0} within K.

2. I(A^{2}) is m-complete Σ_{3}^{0} within K.

3. I(A^{3}) is m-complete Π_{3}^{0} within K.

In related work, Csima, Montalban, and Shore [14] calculated the index sets for Boolean algebras up to elementary equivalence. The calculation was based on elementary invariants isolated by Tarski (see Chapter 7 of [34], or [19]).

4 Computable embeddings

In [10], there is a notion of computable embedding, inspired by that of Borel embedding. The goal was a definition that would allow meaningful comparisons even of classes of finite structures. There are different possible definitions. The one chosen in [10] is essentially uniform enumeration reducibility. Recall that B is enumeration reducible to A, or B ≤_{e} A, if there is a computably enumerable set Φ of pairs (α, b), where α is a finite set and b is a number such that B = {b : (∃α ⊆ A) (α, b) ∈ Φ}.

Note: Given Φ, for each set A, there is a unique set B such that B ≤_{e} A via Φ. Thus, Φ yields a function from P (ω) to P (ω).

As in the setting of descriptive set theory, we consider structures that need not be computable. We suppose that each structure has universe a subset of ω. For simplicity, we suppose that the language consists of finitely many relation symbols—we could allow more general languages. Each class consists of structures for a single language, and, modulo the restriction on the universes, each class is closed under isomorphism.

Definition 7. Let K, K′ be classes of structures. A computable transformation from K to K′ is a computably enumerable set Φ of pairs (α, φ), where

1. α is a finite set of sentences appropriate to be in the atomic diagram of a member of K,

2. φ is a sentence appropriate to be in the atomic diagram of a member of K′, and

3. for each A ∈ K, there exists B ∈ K′ such that Φ(D(A)) = D(B); i.e., D(B) ≤_{e} D(A) via Φ.

Identifying the structures with their atomic diagrams, we write Φ(A) = B.

Definition 8. Let K, K′ be classes of structures. A computable embedding of K in K′ is a computable transformation Φ such that for all A, A′ ∈ K, A ≅ A′ iff Φ(A) ≅ Φ(A′)

We write K ≤_{c} K′ if there is a computable embedding of K into K′.

Example 1. Let F LO be the class of finite linear orders, and let F V S be the class of finite-dimensional vector spaces over ℚ. Then F LO ≤_{c} F V S.

Proof. Let V be a computable vector space, with a computable sequence (b_{k})_{k∈ω} of linearly independent elements. For each finite set S, let V(S) be the linear span of {b_{k} : k ∈ S}. Let Φ be the set of pairs (α, φ) such that for some finite linear order L, with universe S, α = D(L) and φ ∈ D(V(S)).

Example 2. Let UG be the class of undirected graphs, and let F_{χ} be the class of fields of any characteristic χ (0, or p, for some prime p). Then UG ≤_{c} F_{χ}.

Proof. We adapt a Borel embedding given by Friedman and Stanley [16]. Let F be a computable algebraically closed field of characteristic χ, with a computable sequence (b_{k})_{k∈ω} of algebraically independent elements. For χ ≠ 2, for each graph G, let F(G) be the subfield of F generated by the elements

( ⋃_{k∈G} acl(b_{k})) ∪ \{\sqrt{d_{i} + d_{j}}|(d_{i}, d_{j}) ∈ R\}

where R is the set of all pairs of elements (d_{i}, d_{j}) where i, j are elements of G joined by an edge, and we have acl(d_{i}) = acl(b_{i}) and acl(d_{j}) = acl(b_{j}).^{1} For χ = 2, we use cube roots instead of square roots to indicate edges. Let Φ be the set of pairs (α, φ), where for some finite undirected graph G, α = D(G) and φ ∈ D(F(G)). It is not at all easy to see that if Φ(A) ≅ Φ(A′), then A ≅ A′. The difficulty is showing that square roots of the kind representing edges do not appear in the field by accident. One of several proofs in the literature is given in [50].

Example 3. Let LO be the class of linear orderings. Then UG ≤_{c} LO.

Proof. Again we adapt a Borel embedding given by Friedman and Stanley [16]. Let L be Q^{<ω}, under the lexicographic ordering. Let (Q_{a})_{a∈ω} be a uniformly computable disjoint family of dense subsets of ℚ. Let (t_{n})_{n∈ω} be a computable list of the atomic types of tuples in the language of graphs. For a graph G, we let L(G) be the sub-ordering of L 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}) realizing type t_{m} in G, q_{i} ∈ Q_{a_{i}}, for i < n, r_{i} ∈ Q_{0}, r_{n} ∈ Q_{n}, and k is a natural number with k < m + 1. We let Φ be the set of pairs (α, φ), where for some finite undirected graph G, α = D(G), and φ ∈ D(L(G)).

The following fact has no analogue in the setting of Borel embeddings.

Proposition 4.1. Suppose K ≤_{c} K′ via Φ. If A, B ∈ K, where A ⊆ B, then Φ(A) ⊆ Φ(B).

It follows that if K contains a properly increasing chain of structures of length α, and K′ has no such chain, then K ≰_{c} K′. Using this proposition, we can see that there is no computable embedding of the class LO of linear orderings in the class of vector spaces.

Proposition 4.2. The relation ≤_{c} is a partial order on the set C of all classes of structures.

1Friedman and Stanley put in only \sqrt{b_{i} + b_{j}}. This is enough for a computable embedding.

The added elements \sqrt{d_{i} + d_{j}} give the embedding a further property of “rank preservation,”

which will be helpful in section 5.

As usual, from the partial ordering ≤_{c} on C, we get an equivalence relation ≡_{c}, also on C, where K ≡_{c} K′ iff K ≤_{c} K′ and K′ ≤_{c} K. Moreover, ≤_{c} induces a partial order on the ≡_{c}-classes, which we call c-degrees. Let C be the resulting degree structure (C/_{≡_{c}}, ≤_{c}).

4.1 Using computable embeddings to compare classes

Familiar classes of finite structures seem to lie in one of two c-degrees. Recall that F LO is the class of finite linear orders. Let P F be the class of finite prime fields.

Proposition 4.3.

1. P F <_{c} F LO,

2. the c-degree of P F also contains the class of finite cyclic graphs,

3. the c-degree of F LO, maximum for classes of finite structures, also contains the following classes: finite undirected graphs, finite cyclic groups, and finite simple groups.

Considering infinite structures, we come to further landmark c-degrees. Recall that F V S is the class of finite dimensional vector spaces over ℚ. Let LO be the class of linear orders, infinite as well as finite.

Proposition 4.4.

1. F LO <_{c} F V S <_{c} LO,

2. the c-degree of LO, maximum over-all, also contains the class of undirected graphs, and the class of fields of characteristic 0 (or p).

The class of vector spaces over ℚ, the class of algebraically closed fields of fixed characteristic, and the class of models of T h(Z, S) (the integers with successor) share some important features. We do not know whether they represent the same c-degree.

There are natural questions about the degree structure itself. Is it a linear order? Is it a lattice? The first of these questions is answered in [10], and the second is answered in [32].

Theorem 4.5. There is a family of 2^{ℵ_{0}} pairwise incomparable c-degrees. Therefore, C is not a linear order.

The proof of Theorem 4.5 uses the following notion.

Definition 9. We say that sets A, B are bi-immune^{2} if for any partial computable function f, 1. if ran(f ↾ A) is infinite, then ran(f ↾ A) ⊈ B,

2The term “bi-immune” was used earlier in a quite different way in, for instance, [26].

2. if ran(f ↾ B) is infinite, then ran(f ↾ B) ⊈ A.

For each natural number n, we have a finite prime field of size p_{n}, where p_{n} is the n^{th} prime. Below, we write P F (X) for the class of finite prime fields having size p_{n} for n ∈ X.

Lemma 4.6. If A, B are bi-immune, then P F (A) ≰_{c} P F (B) and P F (B) ≰_{c} P F (A).

Lemma 4.6 reduces the proof of Theorem 4.5 to the following.

Lemma 4.7. There is a family of 2^{ℵ_{0}} pairwise bi-immune sets.

By relativizing the notion, and the lemma, we obtain further families of incomparable c-degrees in various intervals.

The result below says that C is not a lattice.

Theorem 4.8. There is a pair of c-degrees with no join and no meet.

Proof. Let A, B be mutually generic. The forcing conditions are the pairs (p_{1}, p_{2}) with p_{1}, p_{2} ∈ 2^{<ω} (representing finite partial characteristic functions for A, B, respectively). Take the c-degrees of P F (A) and P F (B). With some effort, it can be shown that this pair of degrees has neither meet nor join.

For computable embeddings, the connection between the classes is much tighter than for Borel embeddings. One piece of evidence for this is Proposition 4.1, on preservation of the substructure relation. As further evidence, we consider transfer of invariants. Suppose K ≤_{c} K′ via Φ. If there are nice invariants for elements of K′, we may use them to describe elements of K. There are two methods for doing this. The first is trivial. We describe A ∈ K as the structure whose Φ-image satisfies the description of Φ(A). The second method is more satisfying, as it allows us to describe A in its own language. The following result is from [32].

Theorem 4.9. Suppose K ≤_{c} K′ via Φ. There is a partial computable function taking computable infinitary sentences φ in the language of K′ to computable infinitary sentences φ^{∗} in the language of K such that for all A in K, Φ(A) ⊧ φ iff A ⊧ φ^{∗}. Moreover, if φ is computable Σ_{α}, then so is φ^{∗}.

Proof. For all A ∈ K, we can build generic copies. The forcing conditions are members of the set F_{A} of finite 1 − 1 partial functions from ω to A. From a generic copy A^{∗} of A, we get Φ(A^{∗}) ∈ K′. The forcing language, which describes Φ(A^{∗}), is quite different from the language of K. However, forcing is definable in the language of K. For each sentence σ in the forcing language and each tuple \overline{b} in ω, we can find a formula F orce(\overline{x}) such that A ⊧ F orce(\overline{a}) iff we have p ∈ F_{A} taking \overline{b} to \overline{a} and p forces σ. The formulas defining forcing are in the language of K. Moreover, they do not depend on A. The sentence φ^{∗} says, in all A ∈ K, (∃p ∈ F_{A}) [ p ⊩“Φ(A^{∗}) ⊧ φ” ].

5 Computable structures of high Scott rank

We return to computable structures. By Theorem 2.7, these structures all have Scott rank at most ω_{1}^{CK} + 1. We consider examples of computable structures having different Scott ranks. We begin with structures having computable ranks. The exact value is unimportant—that depends on our choice of definition.

Proposition 5.1. For all computable structures A in the following classes, SR(A) < ω_{1}^{CK}.

1. well orderings,

2. superatomic Boolean algebras,

3. reduced Abelian p-groups.

For 2, note that a countable superatomic Boolean algebra can be expressed as a finite join of α-atoms, for some countable ordinal α. In a computable Boolean algebra A, any element that bounds α-atoms for all computable ordinals α can be split into two disjoint elements with this feature. It follows that if A bounds α-atoms for all computable ordinals α, then it has an atomless subalgebra, so it cannot be superatomic. For 3, we show that for a computable Abelian p-group, if the length is not computable, then there is a non-zero divisible element.

Next, we consider computable structures of Scott rank ω_{1}^{CK} + 1. We have already discussed one example, the Harrison ordering. This gives rise to some other structures. In particular, the Harrison Boolean algebra is the interval algebra of the Harrison ordering. The Harrison Abelian p-group is the Abelian p-group of length ω_{1}^{CK}, with all infinite Ulm invariants, and with a divisible part of infinite dimension. Clearly, the Harrison Boolean algebra has a computable copy. The Harrison Abelian p-group does as well.

Theorem 5.2. The Harrison Boolean algebra, and the Harrison Abelian p-groups have Scott rank ω_{1}^{CK} + 1.

In the Harrison Boolean algebra, any non-superatomic element has Scott rank ω_{1}^{CK}. In the Harrison Abelian p-group, any divisible element has Scott rank ω_{1}^{CK}. See [20] for more about these structures.

Finally, we turn to Scott rank ω_{1}^{CK}. The following is in [36].

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

In [33], Makkai’s example is made computable.

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

There are two proofs in [33]. The first simply codes Makkai’s example in a computable structure, without examining it. The second proof re-works Makkai’s construction, incorporating suggestions of Shelah and Sacks. The structures are “group trees”. To obtain a group tree, we start with a tree. Next, we define a family of groups, one for each level of the tree. Using the groups, we get a new, more homogeneous tree structure. We then throw away most of the structure. We retain a family of unary functions, one for each element. Morozov [41] gives a nice description of the construction. He was interested in the fact that if we start with a computable tree T having a path but no hyperarithmetical path, then the resulting group tree (Morozov calls it a “polygon”) has non-trivial automorphisms but no hyperarithmetical ones. The Harrison ordering (as originally constructed) has no hyperarithmetical infinite decreasing sequence, so it also has no non-trivial hyperarithmetical automorphisms.

5.1 Trees

In [13], there are simpler examples of computable structures of rank ω_{1}^{CK}, which are just trees. We consider subtrees of ω^{<ω} and their isomorphic copies. We write ∅ for the top node. To describe the examples, we need some terminology. We define tree rank for a ∈ T, and for T itself.

Definition 10.

1. rk(a) = 0 if a is terminal,

2. for an ordinal α > 0, rk(a) = α if all successors of a have ordinal rank, and α is the first ordinal greater than any of these ranks,

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

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

Fact. rk(a) = ∞ iff there is a path through a.

For a tree T, let T_{n} be the set of elements at level n.

Definition 11. The tree T is rank-homogeneous if

1. for all a ∈ T_{n} and all ordinals α, if there exists b ∈ T_{n+1} with rk(b) = α < rk(a), then a has infinitely many successors a′ with rk(a′) = α.

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

The following is clear.

Proposition 5.5. If T and T′ are rank-homogeneous trees, and for all n, T_{n} and T′_{n} represent the same ranks, then T ≅ T′.

Definition 12. A tree T is thin if for all n, the set of ordinal ranks of elements of T_{n} has order type at most ω · n.

We use thinness in the following way.

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

To show that there is a computable tree of Scott rank ω_{1}^{CK}, we show the following.

Theorem 5.7.

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

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

Proof. Part 1 is proved using Barwise-Kreisel Compactness. There is a Π_{1}^{1} set of computable infinitary sentences describing the desired tree, and we show, in several steps, that every Δ_{1}^{1} subset has a computable model.

For Part 2, first we note that the orbit of each tuple in T is defined by a computable infinitary formula—this is where we use thinness. It follows that SR(T) ≤ ω_{1}^{CK}. To show that SR(T) ≥ ω_{1}^{CK}, we show that if a and b are elements of T at the same level, and are such that rk(a) = ∞ and b has computable tree rank at least ≥ ω · α, then a ≡^{α} b. In fact, two tuples are α-equivalent if they generate isomorphic subtrees and for each pair of corresponding elements in the two subtrees, either the tree ranks match, or else both are at least ω · α.

In [11], examples are given of structures of Scott rank ω_{1}^{CK} in further familiar classes.

Theorem 5.8. Each of the following classes contains computable structures of Scott rank ω_{1}^{CK}:

1. undirected graphs,

2. fields of any fixed characteristic,

3. linear orderings.

To prove Theorem 5.8, we use some special computable embeddings.

Definition 13. Let Φ be an embedding of K in K′. We say that Φ has the rank preservation property if for all computable A ∈ K, either A and Φ(A) both have computable Scott rank, or else they have the same non-computable Scott rank.

Theorem 5.9. For each of the following pairs of classes (K, K′), there is a computable embedding of K in K′ with the rank preservation property:

1. K is the class of trees and K′ is the class of undirected graphs, 2. K is the class of undirected graphs and K′ is the class of fields, of any

desired characteristic,

3. K is the class of undirected graphs and K′ is the class of linear orderings.

Proof. For 1, if G is the graph corresponding to a tree T, then we have a copy T_{G} of T, which is definable in G using existential formulas. Each automorphism of T_{G} extends to an automorphism of G. This implies that if G has Scott rank less than ω_{1}^{CK}, or at most ω_{1}^{CK}, then so does T. In addition, for each tuple \overline{b} in G, there is an existential formula defining the orbit of \overline{b} under automorphisms that fix the elements of T_{G}. This implies that if T has Scott rank less than ω_{1}^{CK}, or at most ω_{1}^{CK}, then so does G.

For 2, we use the embedding of graphs in fields described in Section 4 (a variant of the one due to Friedman and Stanley). There is a copy of the graph sitting in the corresponding field as a quotient of a definable structure by a definable congruence relation, and we obtain rank preservation by proving properties analogous to the ones above.

For 3, we use the embedding of graphs in linear orderings described in Section 4 (due to Friedman and Stanley). There is no copy of the graph definable, even as a quotient structure, in the corresponding linear ordering. Even so, the orbit of each tuple in the graph corresponds to an orbit of an element in the linear ordering, and each orbit in the linear ordering is determined by an existential formula together with a finite tuple of orbits from the graph.

Definition 14. A computable structure A of non-computable rank is computably approximable if every computable infinitary sentence σ true in A is also true in some computable B ≅ A̸.

For all we know, every computable structure of high rank is computably approximable. Failure to be computably approximable is equivalent to existence of a computable infinitary pseudo-Scott sentence.

Sometimes we want a stronger computable approximability.

Definition 15. Suppose A is computable, with non-computable Scott rank. We say that A is strongly computably approximable if for all Σ_{1}^{1} sets S, there is a uniformly computable sequence (C_{n})_{n∈ω} such that if n ∈ S, then C_{n} ≅ A, and if n ∉ S, then C_{n} has computable rank.

Example: The Harrison ordering is strongly computably approximable.

Theorem 5.10. There is a computable tree T such that SR(T) = ω_{1}^{CK} and T is strongly computably approximable.

The proof of Theorem 5.10 in [13] uses the technical proposition below. The proposition below refers to Kleene’s system for assigning numbers to ordinals. The system O, with a partial ordering <_{O}, assigns many notations to a single ordinal. However, for path P through O, there is a unique notation a for each computable ordinal α. In the proof of Theorem 5.10, the path P comes from an initial segment of a Harrison ordering. We write |a| for the ordinal with notation a.

Proposition 5.11. Let P be a path through O. Let A be a computable structure. Let (A_{a})_{a∈P} be a uniformly computable family of structures. Suppose that the following are satisfied:

1. A_{a} satisfies the computable Σ_{|a|} sentences true in A.

2. (≤_{a})_{a∈P} are reflexive, transitive binary relations on tuples from the structures A_{a}

3. the relations have the back-and-forth property; i.e., ≤_{0} preserves satisfaction of quantifier-free formulas, and if (A_{a}, \overline{a}) ≤_{b} (A′_{a}, \overline{a}′), and b′ <_{O} b, then for all \overline{c}′, there exists \overline{c} such that (A_{a′}, \overline{a}′, \overline{c}′) ≤_{b′} (A_{a}, \overline{a}, \overline{c}), and

4. the restriction of ≤_{b} to pairs (\overline{a}, \overline{a}′), where \overline{a} ∈ A_{a} and \overline{a}′ ∈ A_{a′}, is c.e. uniformly in b, a, a′.

Then for any Σ_{1}^{1} set S, there is a uniformly computable sequence (C_{n})_{n∈ω} such that if n ∈ S, then C_{n} ≅ A, and if n ∉ S, then C_{n} ≅ A_{a}, for some a ∈ P.

Proof. The proof of Proposition 5.11 is a priority construction with actions described by a Π_{1}^{1} set Γ of computable infinitary sentences. To show that every Δ_{1}^{1} subset of Γ is satisfied, we use an infinitely nested priority construction. We then apply Barwise-Kreisel Compactness.

The conditions of Proposition 5.11 seem very strong. However, with effort, we can show that they are satisfied by a special tree of Scott rank ω_{1}^{CK}, and a family of approximating trees of computable rank.

In [11], Theorem 5.10 is combined with Theorem 5.9, to produce further structures of Scott rank ω_{1}^{CK} that are strongly computably approximable.

Theorem 5.12. There are strongly computably approximable structures of Scott rank ω_{1}^{CK} in each of the following classes:

1. undirected graphs,

2. fields of any characteristic,

3. linear orderings.

Moreover, in each case, the approximating structures have computable Scott rank.

References

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

[2] Baldwin, J., and A. Lachlan, “On strongly minimal sets”, J. Symb. Logic, vol. 36(1971), pp. 79–96.

[3] Barker, E., “Back and forth relations for reduced Abelian p-groups”, Annals of Pure and Appl. Logic, vol. 75 (1995), pp. 223–249.

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

[5] Becker H. and A. S. Kechris, The Descriptive Set Theory of Polish Group Actions, Cambridge, 1996.

[6] Buechler, S., “Vaught’s conjecture for superstable theories of finite rank”, to appear in Annals of Pure and Appl. Logic.

[7] Calvert, W., “The isomorphism problem for classes of computable fields”, Arch. for Math. Logic, vol. 43(2004), pp. 327–336.

[8] Calvert, W., “The isomorphism problem for computable Abelian p-groups of bounded length”, J. Symb. Logic, vol. 70(2005), pp. 331–345.

[9] Calvert, W., “Algebraic structure and algorithmic structure”, Ph.D. thesis, University of Notre Dame, 2005.

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

[11] Calvert, W., S. S. Goncharov, and J. F. Knight, “Computable structures of Scott rank ω_{1}^{CK} in familiar classes, pre-print.

[12] Calvert, W., V. S. Harizanov, J. F. Knight, and S. Miller, “Index sets of computable structures”, pre-print.

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

[14] Csima, B., A. Montalban, and R. Shore, “Boolean algebras, Tarski invariants, and index sets”, pre-print.

[15] Ershov, Yu. L., Enumeration Theory, Siberian School of Algebra and Logic (Russian), Kluwer (English), 1974.

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

[17] Goncharov, S. S., “Constructive Boolean algebras”, in Third All-Union Conf. in Math. Logic, Novosibirsk (1974).

[18] Goncharov, S. S., and V. D. Dzgoev, “Autostability of models”, Algebra and Logic, vol. 19(1980), pp. 45-58 (Russian), pp. 28-37 (English).

[19] Goncharov, S. S., Countable Boolean Algebras, Siberian School of Algebra and Logic (Russian version), Kluwer (English version), 1996.

[20] 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.

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

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

[23] Hjorth, G., “The isomorphism relation on countable torsion-free Abelian groups”, Fund. Math., vol. 175(2002), pp. 241–257.

[24] Hjorth, G., and A. S. Kechris, “Recent developments in the theory of Borel reducibility”, Fund. Math., vol. 170(2001), pp. 21–52.

[25] Hodges, W., “What is a structure theory”, Bull. London Math. Soc., vol. 19(1987), pp. 209–237.

[26] Jockusch, C. G., “The degrees of bi-immune sets”, Z. Math. Logik Grundlagen Math., vol. 15(1969), pp. 135–140.

[27] Kaplansky, I., Infinite Abelian groups, University of Michigan Press, 1969.

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

[29] Ketonen, J., “The structure of countable Boolean algebras”, Ann. Math., vol. 108(1976), pp. 41–89.

[30] Khisamiev, N. G., “The arithmetic hierarchy of Abelian groups”, Sibirsk. Mat. Zh., vol. 29(1988), pp. 144–159.

[31] Khisamiev, N. G., “Constructive Abelian groups”, in Handbook of Recursive Mathematics, vol. II, ed. by Ershov et al, Elsevier, 1998, pp. 1177– 1231.

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

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

[34] Koppelberg, S., Handbook of Boolean Algebras, vol. 1, ed. by J. D. Monk and R. Bonnet, North Holland, 1989.

[35] Kreisel, G., “Set theoretic problems suggested by the notion of potential totality”, in Infinitistic Methods, Oxford, 1961, pp. 103–140.

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

[37] A. W. Miller, “On the Borel classification of the isomorphism class of a countable model”, Notre Dame J. Formal Logic, vol. 24(1983), pp. 22–34.

[38] Miller, D. E., “The invariant Π_{α}^{0} separation principle”, Trans. Amer. Math. Soc., vol. 242(1978), pp. 185-204.

[39] Morley, M., “Categoricity in power”, Trans. Amer. Math. Soc., vol. 114(1965), pp. 514–538.

[40] Morley, M., “The number of countable models”, J. Symb. Logic, vol. 35(1970), pp. 14–18.

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

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

[43] Nadel, M., “L_{ω_{1}ω} and admissible fragments”, in Model-Theoretic Logics, vol. 45(1980), pp. 612–622.

[44] Pierce, R. S., “Countable Boolean algebras”, in Handbook of Boolean Algebras, vol. 3, ed. by J. D. Monk and R. Bonnet, North-Holland, 1989, pp. 775–876.

[45] Ressayre, J.-P., “Models with compactness properties relative to an admissible language”, Annals of Math. Logic (now Annals of Pure and Applied Logic), vol. 11(1977), pp. 31–55.

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

[47] Rubin, M., “Theories of linear order”, Israel J. of Math., vol. 17(1974), pp. 392–443.

[48] Sacks, G. E., “Bounds on weak scattering”, pre-print.

[49] 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.

[50] Shapiro, D. B., “Composites of algebraically closed fields”, Journal of Algebra, vol. 130 (1990), pp. 176–190.

[51] Shelah, “The number of non-isomorphic models of an unstable first-order theory”, Israel J. of Math., vol. 9(1971), pp. 473–487.

[52] Shelah, S., L. Harrington, and M. Makkai, “A proof of Vaught’s Conjecture for totally transcendental theories”, Israel J. of Math, vol. 49(1984), pp. 259–278.

[53] Steel, J., “On Vaught’s Conjecture”, in Cabal Seminar 76–77: Proceedings of the Caltech-UCLA Logic Seminar 1976–77, ed. by A. S. Kechris and Y. N. Moschovakis, Springer-Verlag, 1978, pp. 193–208.

[54] Vaught, R. L., “Denumerable models of complete theories”, in Infinitistic Methods, Pergamon, 1961, pp. 303–321.

[55] Vaught, R. L., “Invariant sets in topology and logic”, Fund. Math., vol. 82(1974/75), pp. 269–294.