Index Sets of Computable Structures

Wesley Calvert^{∗} Department of Mathematics University of Notre Dame

wcalvert@nd.edu

Valentina S. Harizanov Department of Mathematics George Washington University harizanv@gwu.edu

Julia F. Knight Department of Mathematics University of Notre Dame knight.1@nd.edu

Sara Miller Department of Mathematics University of Notre Dame smiller9@nd.edu

June 15, 2005

Abstract The index set of a computable structure A is the set of all indices for computable isomorphic copies of A. We determine, using the arithmetical hierarchy and the difference hierarchy, the exact complexity of the index sets of structures within the following classes of structures: finite structures, vector spaces, Archimedean ordered fields, Abelian p-groups, and the models of the original Ehrenfeucht theory.

1 Introduction

One of the goals of computable structure theory is to study the relationship between algebraic and algorithmic properties of structures. Our languages are computable, and our structures have universe contained in ω, which we think of as a computable set of constants. In measuring complexity, we identify a structure A with its atomic diagram, D(A), via Gödel coding. In particular, A is computable if D(A) is computable. For a computable structure A, an index is a number a such that φ_{a} = χ_{D(A)}, where (φ_{a})_{a∈ω} is a computable enumeration of all unary partial computable functions. The index set for A is the set I(A) of all indices for computable (isomorphic) copies of A. For a class K of structures, closed under isomorphism, the index set is the set I(K) of all indices for computable members of K. There is quite a lot of work on index sets [14], [6], [2], [3], [5], [8], [20], [21], [7], etc. In this paper, we present evidence for the following thesis:

∗The first author was partially supported by NSF grants DMS 0139626 and DMS 0353748

For a given computable structure A, to calculate the precise complexity of I(A), we need a good description of A, and once we have an “optimal” description, we the complexity of I(A) will match that of the description.

Our evidence for this thesis consists of calculations for computable structures of several familiar kinds: finite structures, ℚ-vector spaces, Archimedean ordered fields, reduced Abelian p-groups of length less than ω^{2}, and models of the original Ehrenfeucht theory.

We should say what qualifies as a “description” of a structure, and how we measure the complexity. The Scott Isomorphism Theorem says that for any countable structure A there is a sentence of L_{ω_{1}ω} whose countable models are exactly the isomorphic copies of A (see [11]). Such a sentence is called a Scott sentence for A. A Scott sentence for A certainly describes A.

There is earlier work [16], [15] investigating subsets of the Polish space of structures with universe ω for a given countable language. Concerning the possible complexity (in the non-effective Borel hierarchy) of the set of copies of a given structure, it is shown in [16] that if the set is Δ_{α+1}^{0}, then it is d-Σ_{α}^{0}. In [15] it is shown that the set cannot be properly Σ_{2}^{0}. There are examples illustrating other possibilities.

Most of the structures we consider follow one of two patterns. Either there is a computable Π_{n} Scott sentence, and the index set is m-complete Π_{n}^{0}, or else there is a Scott sentence which is computable “d-Σ_{n}” (the conjunction of a computable Σ_{n} sentence and computable Π_{n} sentence), and the index set is mcomplete d-Σ_{n}. For example, a computable reduced Abelian p-group of length ω has a computable Π_{3} Scott sentence, and the index set is m-complete Π_{3}^{0}. A ℚvector space of finite dimension at least 2 has a Scott sentence that is computable d-Σ_{2}, and the index set is m-complete d-Σ_{2}^{0}. The “middle model” of the original Ehrenfeucht theory illustrates a further pattern. There is a computable Σ_{3} Scott sentence, and the index set is m-complete Σ_{3}^{0}. Often the first Scott sentence that comes to mind is not optimal. In some cases, in particular, for some of the Abelian p-groups, it requires effort to show that a certain sentence of a simpler form actually is a Scott sentence.

For some structures, we obtain more meaningful results by locating the given computable structure A within some natural class K. We say how to describe A within K, and also how to calculate the complexity of I(A) within K.

Definition 1.1. A sentence φ is a Scott sentence for A within K if the countable models of φ in K are exactly the isomorphic copies of A.

The following definitions were used already in [3].

Definition 1.2. Let Γ be a complexity class (e.g., Π_{3}^{0}).

1. I(A) is Γ within K if I(A) = R ∩ I(K) for some R ∈ Γ.

2. I(A) is m-complete Γ within K if I(A) is Γ within K and for any S ∈ Γ, there is a computable function f : ω → I(K) such that

n ∈ S iff n ∈ I(A) .

that is, there is a uniformly computable sequence (C_{n})_{n∈ω} such that

n ∈ S iff C_{n} ≅ A.

Example 1. Let A be the field with 3 elements, and let K be the class of finite prime fields. There is a Scott sentence for A within K saying 1 + 1 + 1 = 0. The index set for A is computable within K.

The example above is an exception. In most of the examples we consider, even when we locate our structure within a class K, the optimal description is a true Scott sentence, but the context helps us calculate the complexity of the index set in a meaningful way.

Example 2. Let A be a linear ordering of size 3, and let K be the class of linear orderings. There is a computable d-Σ_{1} Scott sentence saying that there are at least 3 elements ordered by the relation, and not more. We will show that the index set for A is m-complete d-c.e. within K.

Here we mention some related work. The proof of the Scott Isomorphism Theorem leads to an assignment of ordinals to countable structures. By a result of Nadel [17], for any hyperarithmetical structure, there is a computable infinitary Scott sentence iff the Scott rank is computable. There are several different definitions of Scott rank in use. Since we are more interested in Scott sentences, we shall not give any of them.

Work on index sets for particular computable structures is related to work on isomorphism problems for classes of computable structures [2], [3], [8]. The isomorphism problem for a class K is the set E(K) consisting of pairs (a, b) of indices for computable members of K that are isomorphic. It is often the case that for the classes K for which the complexity of the isomorphism problem is known, there is a single computable A ∈ K such that the index set for A has the same complexity as E(K). Results on index sets are useful in other contexts as well. In [4], they are used in connection with Δ_{2}^{0} categoricity of computable structures.

We consider finite structures in Section 2, vector spaces in Section 3, Archimedean ordered fields in Section 3, Abelian p-groups in Section 4, and models of the original Ehrenfeucht theory in Section 5.

2 Finite Structures

Finite structures are the easiest to describe. It is perhaps surprising that there should be any variation in complexity of index sets for different finite structures, and, indeed, there is almost none. In the following theorem, we break with convention by allowing a structure to be empty.

Theorem 2.1. Let L be a finite relational language. Let K be the class of finite L-structures, and let A ∈ K.

1. If A is empty, then I(A) is m-complete Π_{1}^{0} within K.

2. If A has size n ≥ 1, then I(A) is m-complete d-c.e. within K.

Proof. For 1, first note that A has a finitary Π_{1} Scott sentence saying that there is no element. From this, it is clear that I(A) is Π_{1}^{0} within K. For completeness, let B be an L-structure with just one element. For an arbitrary Π_{1}^{0} set S, we can produce a uniformly computable sequence (A_{n})_{n∈ω} such that

A_{n} ≅ \{ \begin{matrix}A & if n ∈ S , \\ B & if n ∉ S . \end{matrix}

For 2, we have a finitary existential sentence φ stating that there is a substructure isomorphic to A, and another finitary existential sentence ψ stating that there are at least n + 1 elements. Then φ & ¬ψ is a Scott sentence for A. It follows that I(A) is d-c.e. within K. For completeness, let S = S_{1} − S_{2}, where S_{1} and S_{2} are c.e. We have the usual finite approximations S_{1,s}, S_{2,s}.

Let A^{−} be a proper substructure of A, and let A^{+} be a finite proper superstructure of A. We will build a uniformly computable sequence (A_{n})_{n∈ω} such that

A_{n} ≅ \{ \begin{matrix}A^{−} & if n ∉ S_{1} , \\ A & if n ∈ S_{1} − S_{2} , \\ A^{+} & if n ∉ S_{1} ∩ S_{2} . \end{matrix}

To accomplish this, let D_{0} = D(A^{−}). At stage s, if n ∉ S_{1,s}, we let D_{s} be the atomic diagram of A^{−}. If n ∈ S_{1,s} − S_{2,s}, we let D_{s} be the atomic diagram of A. If n ∈ S_{1,s} ∩ S_{2,s}, we let D_{s} be the atomic diagram of A^{+}. There is some s_{0} such that for all s ≥ s_{0}, n ∈ S_{1} iff n ∈ S_{1,s}, and n ∈ S_{2} iff n ∈ S_{2,s}. Let A_{n} be the structure with diagram D_{s} for s ≥ s_{0}. It is clear that A_{n} ≅ A iff n ∈ S.

In the introduction, we mentioned finite prime fields. Let p be a prime number. By the results above, 𝔽_{p} has a Scott sentence of form φ & ¬ψ, where φ and ψ are finitary Σ_{1}. It follows that I(𝔽_{p}) has a Scott sentence which is the conjunction of a finitary existential sentence and a finitary universal sentence. Then the index set is d-c.e. within the class of finite structures for the appropriate language. However, within the class of finite prime fields, 𝔽_{p} has a finitary quantifier-free Scott sentence saying p · 1 = 0. Then I(𝔽_{p}) is computable within that class.

3 Vector Spaces

The finite dimensional vector spaces over a fixed field are completely determined by a finite set (a basis), so we might expect these to behave much like finite structures. However, we have added complexity because of the fact that for 1 ≤ m < n, if V_{n} is a space of dimension n, and V_{m} is an m-dimensional subspace, if V_{n} ⊧ φ(\overline{c}, \overline{a}), where φ is finitary quantifier-free, and \overline{c} is in V_{m}, then there exists \overline{a}′ such that V_{m} ⊧ φ(\overline{c}, \overline{a}′). We work with vector spaces over ℚ, for concreteness, but any other infinite computable field would give exactly the same results.

Proposition 3.1. Let K be the class of vector spaces over ℚ, and let A be a member of K.

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

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

3. If dim(A) > 1, then I(A) is m-complete d-Σ_{2}^{0} within K.

Proof. For 1, first we note that A has a a finitary Π_{1} Scott sentence, within K, saying (∀x) x = 0. It follows that I(A) is Π_{1}^{0} within K. Toward completeness, let S be a Π_{1}^{0} set. We build a uniformly computable sequence of structures (A_{n})_{n∈ω} such that

dim(A_{n}) = \{ \begin{matrix}0 & if n ∈ S , \\ 1 & if n ∉ S . \end{matrix}

Let V_{0} be a space of dimension 0, and let V_{1} be a computable extension having dimension 1. We have a computable sequence (S_{s})_{s∈ω} of approximations for S such that n ∈ S iff for all s, n ∈ S_{s}, and if n ∉ S_{s}, then for all t > s, n ∉ S_{t}. If n ∈ S_{s}, we let D_{s} = D(V_{0}). If n ∉ S_{s}, then we let D_{s} consist of the first s sentences of D(V_{1}). This completes the proof for 1.

Next, we turn to 2. First, we show that A has a computable Π_{2} Scott sentence. We have a computable Π_{2} sentence characterizing the class K. We take the conjunction of this with the sentence saying

(∃x) x ≠ 0 & (∀x) (∀y) ⋁_{λ∈Λ} ⋁ λ(x, y) = 0 ,

where Λ is the set of all non-trivial linear combinations q_{1}x + q_{2}y, for q_{i} ∈ ℚ. Now, I(A) is Π_{2}^{0}. We do not need to locate A within K, since the set of indices for members of K is Π_{2}^{0}.

For completeness, let S be a Π_{2}^{0} set. We build a uniformly computable sequence (A_{n})_{n∈ω} such that

dim(A_{n}) = \{ \begin{matrix}1 & if n ∈ S , \\ 2 & if n ∉ S . \end{matrix}

We have computable approximations S_{s} for S such that n ∈ S iff for infinitely many s, n ∈ S_{s}.

Let V^{+} be a two dimensional computable vector space and let V be a 1dimensional subspace. Let B be an infinite computable set of constants, for the universe of all A_{n}. At each stage s, we have a finite partial 1 − 1 function p_{s} from B to a target structure V (if n ∈ S_{s}) or V^{+} (if n ∉ S_{s}), and we have enumerated a finite set D_{s} (a part of the atomic diagram of A_{n}) such that p_{s} maps the constants mentioned in D_{s} into the target structure so as to make all of the sentences true. We arrange that if n ∈ S, then ∪_{n∈S_{s}}p_{s} maps B onto V. If n ∉ S, then there is some s_{0} such that for all s ≥ s_{0}, n ∉ S_{s}. In this case, ∪_{s≥s_{0}}p_{s} for s ≥ s_{0} maps B onto V^{+}. For all s (whether or not n ∈ S_{s}), D_{s} decides the first s atomic sentences involving constants in dom(p_{s}).

We start with p_{0} = ∅, and D_{0} = ∅. Without loss of generality, we may suppose that n ∈ S_{0}. We consider p_{0} to be mapping into V. If there is no change in our guess about whether n ∈ S at stage s + 1, then p_{s+1} ⊇ p_{s}, where the first s + 1 constants from B are in the domain, and the first s + 1 elements of the target structure are in the range. We must say what happens when we change our guess at whether n ∈ S.

There are two cases. First, suppose n ∈ S_{s+1} and n ∉ S_{s}. In this case, we take the greatest stage t ≤ s such that n ∈ S_{t}. We let p_{s+1} ⊇ p_{t} such that p_{s+1} makes the sentences of D_{s} true in V, extending so that the first s + 1 constants from B are in the domain, and the first s + 1 elements of V are in the range. Now, say n ∉ S_{s+1} and n ∈ S_{s}. In this case, we do not look back at any earlier stage. We let p_{s+1} ⊇ p_{s}, extending so that the first s + 1 constants from B are in the domain, and the first s + 1 elements of V^{+} are in the range. In either case, we let D_{s+1} ⊇ D_{s} so that for the first s + 1 atomic sentences β involving constants in the domain of p_{s+1}, D_{s+1} includes ±β, whichever is made true by p_{s+1}. This completes the proof for 2.

Finally, we turn to 3. Suppose A has dimension k, where k > 1. Then A has a d-Σ_{2} Scott sentence. We take the conjunction of the axioms for ℚ-vector spaces, and we add a sentence saying that there are at least k independent elements, and that there are not at least k + 1. Then I(A) is d-Σ_{2}^{0}. Toward completeness, let S = S_{1} − S_{2}, where S_{1} and S_{2} are both Σ_{2}^{0}. Let V^{+} be a computable vector space of dimension k + 1, and let

V^{−} ⊆ V ⊆ V^{+},

where V^{−} has dimension k − 1, and V has dimension k. We will produce a uniformly computable sequence of structures (A_{n})_{n∈ω} such that

dim(A_{n}) = \{ \begin{matrix}k − 1 & if n ∉ S_{1} , \\ k & if n ∈ S_{1} − S_{2} , \\ k + 1 & if n ∈ S_{1} ∩ S_{2} . \end{matrix}

The construction is similar to that for 2. We have computable approximations S_{1,s} and S_{2,s} for S_{1} and S_{2}, such that

n ∈ S_{i} iff for all but finitely many s, n ∈ S_{i,s} .

Let B be an infinite computable set of constants, for the universe of all A_{n}. At each stage s, we have a finite partial 1 − 1 function p_{s} from B to V^{−} if n ∉ S_{1,s}, to V if n ∈ S_{1,s} − S_{2,s}, and to V^{+} if n ∈ S_{1,s} ∩ S_{2,s}. We have D_{s}, a finite part of D(A_{n}) such that p_{s} makes D_{s} true in the target structure.

We arrange that if n ∉ S_{1}, then the union of the p_{s} for n ∉ S_{1,s} maps B onto V^{−}. If n ∈ S_{1} −S_{2}, then after some stage s_{0}, n ∈ S_{1,s} holds, while n ∈ S_{2,s} infinitely often. In this case, the union of p_{s} for s ≥ s_{0} such that n ∈ S_{2,s} maps B onto V. If n ∈ S_{1} ∩ S_{2}, then for some stage s_{1}, for s ≥ s_{1}, n ∈ S_{1,s} ∩ S_{2,s}, and the union of p_{s} for s ≥ s_{1} maps B onto V^{+}.

We may suppose that n ∉ S_{1,0}, so the target structure at stage 0 is V^{−}. At stage s + 1, if there is no change in the target structure, then we extend p_{s}. We must say what to do when we change our mind about the target structure. First, suppose the change is because of S_{1}. If n ∈ S_{1,s} and n ∉ S_{1,s+1}, then the target structure changes from V or V^{+} back to V^{−}. We take the greatest stage t < s such that n ∉ S_{1,t}. We let p_{s+1} ⊇ p_{t} such that p_{s+1} makes D_{s} true in V^{−}, extending so that the first s + 1 constants from B are in the domain, and the first s + 1 elements of V are in the range. If n ∉ S_{1,s} and n ∈ S_{1,s+1} − S_{2,s+1}, then the target structure changes from V^{−} to V. We let p_{s+1} ⊇ p_{s}, extending so that the first s + 1 constants from B are in the domain and the first s + 1 elements of V are in the range.

Now, suppose the change is because of S_{2}. We suppose that n ∈ S_{1,s} and n ∈ S_{1,s+1}. If n ∈ S_{2,s} and n ∉ S_{2,s+1}, then the target structure changes from V^{+} back to V. We take the greatest stage t ≤ s such that the target structure is V, and we have had n ∈ S_{1,s′} for all t < s′ < s. If there is no such t, then we take the greatest t < s such that n ∉ S_{1,t}. We let p_{s+1} ⊇ p_{t} such that p_{s+1} makes D_{s} true in V, extending to include the first s + 1 elements of B in the domain and the first s + 1 elements of V in the range. We let D_{s+1} ⊇ D_{s} so that for for the first s + 1 atomic sentences β involving constants in the domain of p_{s+1}, D_{s+1} includes ±β, whichever is made true by p_{s+1}. This completes the proof of 3.

The final case, that of an infinite dimensional space, is already known [2]. We include it here for completeness.

Proposition 3.2. Let K be the class of computable vector spaces over ℚ, and let A be a member of K of infinite dimension. Then I(A) is m-complete Π_{3}^{0} within K.

Proof. We have a computable Π_{3} Scott sentence for A, obtained by taking the conjunction of the axioms for ℚ-vector spaces and the conjunction over all k ∈ ω of computable Σ_{2} sentences saying that the dimension is at least k. Therefore, I(A) is Π_{3}^{0}. For completeness, let Cof denote the set of indices for co-finite c.e. sets. It is well known that the complement of Cof is Π_{3}^{0} complete (see [18]). We build a uniformly computable sequence of vector spaces (A_{n})_{n∈ω} such that A_{n} has infinite dimension iff n ∉ Cof.

Let V be an infinite dimensional vector space with basis {v_{i} : i ≥ −1}. Let B be an infinite computable set of constants, for the universe of all A_{n}. For each set S ⊆ ω, let V_{S} be the linear span of {v_{−1}} ∪ {v_{i} : i ∈ S}. Our goal is to make A_{n} ≅ V_{S}, where S = ω − W_{n}. At stage s, we have a finite approximation of S, as follows. Let S_{0} = ∅. If W_{n+1,s+1} includes some x ∈ S_{s}, we let S_{s+1} be the result of removing from S_{s} all y ≥ x. If W_{n+1,s+1} contains no elements of S_{s}, we let S_{s+1} be the result of adding to S_{s} the first element of ω not in W_{n+1,s+1}. Note for each k, there exists s such that for all t ≥ s, S ∩ k = S_{t} ∩ k. Moreover, for each s, there is some t ≥ s such that S_{t} ⊆ ω − W_{n}. For such t, for all t′ ≥ t, S′_{t} ⊇ S_{t}.

For the construction, at stage s we have a finite partial 1 − 1 function p_{s} from B into V_{S_{s}}. We include the first s elements of B in the domain and the first s elements of ω that are in V_{S_{s}} in the range. We also have D_{s} deciding the first s atomic sentences with constants in dom(p_{s}), such that p_{s} makes the sentences true in V_{S_{s}}. We start with p_{0} = ∅, D_{0} = ∅, and we think of p_{0} as mapping into V_{S_{0}}.

At stage s + 1, we define p_{s+1} as follows. First, suppose S_{s+1} is the result of adding an element to S_{s}. Then p_{s+1} ⊇ p_{s} including the first s + 1 elements of B in the domain, and the first s + 1 elements of ω that are in V_{s+1} in the range. Now, suppose S_{s+1} is the result of removing one or more elements from S_{s}, so that S_{s+1} = S_{t} for some greatest t < s. We take p_{s+1} ⊇ p_{t} such that p_{s+1} makes D_{s} true in V_{s+1} = V_{t}. We let D_{s+1} extend D_{s} so as to decide the first s + 1 atomic sentences involving constants in dom(p_{s+1}). This completes the construction.

There is an infinite sequence of stages t such that for all s > t, p_{s} ⊇ p_{t}. Let f be the union of the functions p_{t} for these t. We can see that f is a 1−1 mapping of B onto V_{S}. Moreover, if A_{n} ≅_{f} V_{S}, then ∪_{s}D_{s} is the atomic diagram of A_{n}.

We have completely characterized the m-degrees of index sets of computable vector spaces over ℚ, within the class of all such vector spaces.

4 Archimedean Ordered Fields

Archimedean ordered fields are isomorphic to subfields of the reals. They are determined by the Dedekind cuts that are filled.

Theorem 4.1. Let K be the class of Archimedean ordered fields. If A is either ℚ, or ℚ(a) for a real algebraic number a, then I(A) is m-complete Π_{2}^{0} within K.

Proof. For ℚ, we have a computable Π_{2} Scott sentence describing an ordered field in which each x is equal to a ratio of integers. For ℚ(a), where p(x) is the minimal polynomial with root a, we have a computable Π_{2} Scott sentence describing an ordered field such that (∃x) p(x) = 0 and for all x and y, if p(y) = 0, then y is equal to some rational function of x. It follows that the index set is Π_{2}^{0}. For m-completeness, let S be a Π_{2}^{0} set. We produce a uniformly computable sequence (A_{n})_{n∈ω} such that if n ∈ S, then A_{n} ≅ A, and if n ∉ S, then A_{n} ≅ A(e), where e ∈ ℝ.

We need a lemma, and for later use, it is convenient to have the following definition.

Definition 4.2. Let C be a substructure of B. We write

C ≤_{1} B

if for all finitary quantifier-free formulas φ, if B ⊧ φ(\overline{c}, \overline{b}), where \overline{c} is in C, then there exists \overline{b}′ such that C ⊧ φ(\overline{c}, \overline{b}′).

In other words, if C ≤_{1} B, then the satisfaction of finitary existential formulas by tuples in C is the same in B and C.

Lemma 4.3. If A is either ℚ or ℚ(a), where a is real algebraic, then A ≤_{1} A(e).

Proof. Let φ be finitary quantifier-free. Suppose

A(e) ⊧ φ(\overline{c}, e, \overline{a}) ,

where \overline{c} is in A. In the case where A = ℚ(a), we may suppose that a ∈ \overline{c}. Then \overline{a} is in the field generated by \overline{c} and e. There is an open interval I (in ℝ) containing e such that for all e′ ∈ I, we have ℝ ⊧ φ(\overline{c}, e′, \overline{a}′), where \overline{a}′ is obtained from \overline{c}, e′ in the same way that \overline{a} is obtained from \overline{c}, e. Taking e′ to be rational, we have \overline{a}′ in A such that A ⊧ φ(\overline{c}, e′, \overline{a}′).

Let M^{+} be a computable copy of A(e), and let M be the substructure isomorphic to A. What is important is that M^{+} is computable, and M is a c.e. substructure with M ≤_{1} M^{+}. Let B be an infinite computable set of constants, for the universe of all A_{n}. We have a computable approximation (S_{s})_{s∈ω} for S such that

n ∈ S iff n ∈ S_{s} for infinitely many s .

At each stage, we determine a finite partial 1 − 1 functions f_{s} to the target structure, M if n ∈ S_{s}, and M^{+} otherwise. The domain of f_{s} includes the first s constants from B, and the range includes the first s elements of the target structure. Also, at stage s, we enumerate a finite part of D_{s} of the diagram of A_{n}, such that f_{s} makes D_{s} true in the target structure. For the first s atomic sentences φ, involving only the first s constants, we put ±φ in D_{s}. We arrange that if n ∈ S, then f = ∪_{n∈S_{s}}f_{s} is an isomorphism from A_{n} onto M_{1}, and if n ∉ S, and s_{0} is least such that for all s ≥ s_{0}, n ∉ S_{s}, then f = ∪_{s≥s_{0}}f_{s} is an isomorphism from A_{n} onto M^{+}.

At stage 0, we let f_{0} = ∅, and D_{0} = ∅. At stage s + 1, if n ∈ S_{s+1} and n ∈ S_{s}, or if n ∉ S_{s+1} and n ∉ S_{s}, then we let f_{s+1} ⊇ f_{s}, adding to the domain and range. We extend D_{s} to D_{s+1} so that f_{s+1} makes the sentences true in the target structure. Suppose n ∈ S_{s+1} and n ∉ S_{s}. Let t < s be greatest such that n ∈ S_{t} or t = 0. We may suppose that f_{s} extends f_{t}. It follows from Lemma 4.3 that there is an extension of f_{t} which makes D_{s} true in M. We let f_{s+1} be such an extension that also includes the required elements in the domain and range. We extend D_{s} to D_{s+1} so that f_{s+1} makes the sentences true. Finally, suppose n ∈ S_{s} and n ∉ S_{s+1}. We let f_{s+1} ⊇ f_{s}, changing to the larger target structure. We add the required elements to the domain and range. We extend D_{s} to D_{s+1} so that f_{s+1} makes the sentences true in the target structure.

Theorem 4.4. Let K be the class of Archimedean ordered fields, and let A be ℚ(e_{1}, …, e_{k}), where the e_{i} are algebraically independent reals, k ≥ 1. Then I(A) is m-complete d-Σ_{2}^{0} within K.

Proof. We have a computable Σ_{2}^{0} sentence φ stating that there are elements e_{1}^{A}, …, e_{k}^{A} filling the cuts of e_{1}, …, e_{k}, and we have another computable Σ_{2}^{0} sentence ψ saying that there are elements x_{1}, …, x_{k} filling these cuts, and another element not equal to any rational function of them. Then φ & ¬ψ is a Scott sentence for A. It follows that I(A) is d-Σ_{2}^{0}.

Toward completeness, let S = S_{1} − S_{2}, where S_{i} is Σ_{2}^{0}. Let e_{k+1} be a computable real number algebraically independent of e_{1}, …, e_{k}. Let M^{+} be a computable copy of ℚ(e_{1}, …, e_{k}, e_{k+1}), let M be the subfield isomorphic to A, and let M^{−} be the subfield generated by the elements corresponding to e_{i} for i < k. (If k = 1, then A^{−} = ℚ.) We have the following lemma.

Lemma 4.5. M^{−} ≤_{1} M ≤_{1} M^{+}

What is important is that M^{+} is a computable structure, and M^{−} and M are c.e. substructures such that M^{−} ≤_{1} M ≤_{1} M^{+}. We will produce a uniformly computable sequence (A_{n})_{n∈ω} such that if n ∉ S_{1}, then A_{n} ≅ M^{−}, if n ∈ S_{1} − S_{2}, then A_{n} ≅ M, and if n ∈ S_{1} ∩ S_{2}, then A_{n} ≅ M^{+}. Let B be an infinite computable set of constants, for the universe of all A_{n}. We have computable approximations (S_{i,s})_{s∈ω} for S_{i} such that

n ∈ S_{i} iff (∃s_{0})(∀s ≥ s_{0})[n ∈ S_{i,s}] .

At each stage s, we will have a finite partial 1 − 1 function f_{s} from B to the appropriate target structure—M^{−} if n ∉ S_{1,s}, M if n ∈ S_{1,s} − S_{2,s}, and M^{+} if n ∈ S_{1,s} ∩ S_{2,s}. The domain of f_{s} will include the first s constants from B, and the range will include the first s elements of the target structure. We will also have a finite set D_{s} of atomic sentences and negations of atomic sentences such that f_{s} makes D_{s} true in the target structure. For the first s atomic sentences φ involving only the first s constants, D_{s} will include ±φ. We let A_{n} be the structure with atomic diagram ∪_{s}D_{s}.

We will arrange that if n ∉ S_{1}, then the union of f_{s} for n ∉ S_{1,s} will be an isomorphism from A_{n} onto M^{−}. If n ∈ S_{1} − S_{2}, and s_{0} is first such that for all s ≥ s_{0}, n ∈ S_{1,s}, then the union of f_{s}, for s ≥ s_{0} such that n ∉ S_{2,s}, will be an isomorphism from A_{n} onto M. If n ∈ S_{1} ∩ S_{2}, and s_{1} is first such that for all s ≥ s_{1}, n ∈ S_{1,s} and n ∈ S_{2,s}, then the union of f_{s} for s ≥ s_{1} will be an isomorphism from A_{n} onto M^{+}.

We start with f_{0} = ∅ and D_{0} = ∅. Suppose we have f_{s} and D_{s}. If the target structure at stage s + 1 is the same as at stage s, then we extend f_{s} and D_{s} in the obvious way. Suppose n ∉ S_{1,s+1}, where n ∈ S_{1,s}. Let t < s be greatest such that n ∉ S_{1,t} or t = 0. Say f_{t} maps \overline{d} to \overline{c} in M^{−}. We let f_{s+1} ⊇ f_{t}, where f_{s+1} makes the sentences of D_{s} true in M^{−}. Now, suppose n ∈ S_{1,s+1} − S_{2,s+1}, where n ∈ S_{1,s} ∩ S_{2,s}. Take t < s greatest such that n ∈ S_{1,t} − S_{2,t} and for all t < t′ < s, n ∈ S_{1,t′}. Then we let f_{s+1} ⊇ f_{t}, where f_{s+1} makes the sentences of D_{s} true in M.

Suppose that n ∈ S_{1,s+1} − S_{2,s+1}, where n ∉ S_{1,s}. Then we take f_{s+1} ⊇ f_{s}, where f_{s+1} makes D_{s} true in the target structure M. Similarly, if we have n ∈ S_{1,s+1} ∩ S_{2,s+1}, where either n ∉ S_{1,s} or n ∈ S_{1,s} − S_{2,s}, we let f_{s+1} ⊇ f_{s}, where f_{s+1} makes D_{s} true in the target structure M^{+}. We extend f_{s} to include the required elements in the domain and range, and we let D_{s+1} ⊇ D_{s} so that f_{s+1} makes D_{s+1} true.

Next, we consider Archimedean ordered fields with infinite transcendence degree. As for vector spaces, the complexity goes up by one quantifier. However, the proof is different. For an infinite dimensional vector space, we had proper substructures isomorphic to the whole, while for an Archimedean ordered field, this does not happen. (See [2] for a similar proof.)

Theorem 4.6. Let K be the class of Archimedean ordered fields, and let A ∈ K be the least field generated by a family of infinitely many algebraically independent reals. Then I(A) is m-complete Π_{3}^{0} within K.

Proof. We shall describe a computable Π_{3} Scott sentence for A. For each a ∈ A, let c_{a}(x) be the conjunction of formulas saying q < x < q′, where q, q′ are rationals, and A ⊧ q < a < q′. The Scott sentence describes an Archimedean ordered field such that

⋀_{a∈A} ⋀(∃x) c_{a}(x) & (∀x) ⋁_{a∈A} ⋁ c_{a}(x) .

For completeness, we need the following lemma.

Lemma 4.7. There is a sequence (M_{k})_{k∈ω} of subfields of A, uniformly c.e., such that for all k, M_{k+1} properly extends M_{k}, and ∪_{k}M_{k} = A.

Proof. Let (a_{n})_{n∈ω} be a computable list of all elements of A. We can arrange that M_{0} is the prime field A, and M_{k+1} is field generated by M_{k} and a_{n_{k}}, where n_{k} is first such that a_{n_{k}} ∉ M_{k}.

We need the following property.

Lemma 4.8. For all k, M_{k} ≤_{1} M_{k+1}. Hence, if k < m, then M_{k} ≤_{1} M_{m}.

Proof. Suppose M_{k+1} ⊧ φ(\overline{c}, \overline{b}), where φ is quantifier-free, and \overline{c} is in M_{k}. Let n_{k} be least such that a_{n_{k}} ∉ M_{k}. We may suppose that \overline{c} includes a_{m}, for all m < n_{k}, and \overline{b} has the form a_{n_{k}}, \overline{d}. Say ψ(\overline{c}, a_{n_{k}}, \overline{d}) says how \overline{d} are expressed as rational functions of \overline{c}, a_{n_{k}}. There is an interval I around a_{n_{k}}, with rational endpoints, such that for all x ∈ I, and all \overline{u} satisfying ψ(\overline{c}, x, \overline{u}), φ(\overline{c}, x, \overline{u}) holds in ℝ. Taking x rational, we have \overline{u} satisfying ψ(\overline{c}, x, \overline{u}) in M_{k}, so M_{k} ⊧ φ(\overline{c}, x, \overline{u}).

Recall that Cof = {n : ω − W_{n} is finite}. This set is m-complete Σ_{3}^{0}, so the complement is m-complete Π_{3}^{0}. We have a Δ_{2}^{0} function ν(n, r), non-decreasing in r, for each n, such that if n ∈ Cof, then lim_{r} ν(n, r) has value equal to the cardinality of ω − W_{n}, and if n ∉ Cof, then lim_{r} ν(n, r) = ∞. We have a computable approximation to ν, and we define a computable function g(n, s), such that g(n, 0) is our stage 0 guess at ν(n, 0). Supposing that g(n, s) is our stage s guess at ν(n, r), if our stage s+1 guess at ν agrees with the stage s guess at ν(n, j) for all j ≤ r, then g(n, s + 1) is the stage s + 1 guess at ν(n, r + 1). If there is a disagreement, say j is least such that our stage s and stage s + 1 guesses at ν(n, j) disagree. Let g(n, s + 1) be the stage s + 1 guess at ν(n, j). If n ∉ Cof, then for all k, there exists s_{0} such that

(∀s ≥ s_{0}) [g(n, s) ≥ k] .

If n ∈ Cof, and k is the cardinality of ω − W_{n}, then there are infinitely many s such that g(n, s) = k, and k is the least such number. In other words, lim inf_{s} g(n, s) is the cardinality of ω − W_{n}.

We will build a uniformly computable sequence (A_{n})_{n∈ω} of Archimedean ordered fields such that if n ∉ Cof, that is, ω − W_{n} is infinite, then A_{n} ≅ A. If n ∈ Cof, that is, ω − W_{n} has size k for some k ∈ ω, then A_{n} ≅ M_{k}. Let B be an infinite computable set of constants, for the universe of all A_{n}. At stage s, we have a finite partial 1 − 1 function f_{s} from B to the target structure M_{k}, where k = g(n, s). The domain of f_{s} will include the first s constants from B, and the range will include the first s elements of the target structure. We also have D_{s}, a finite set of atomic sentences and negations of atomic sentences such that f_{s} makes D_{s} true in the target structure. For the first s atomic sentences φ using only the first s constants, D_{s} will include ±φ.

We let A_{n} be the structure with

D(A_{n}) = ∪_{s}D_{s} .

Let T be the set of s such that for all t ≥ s, g(n, t) ≥ g(n, s). We shall arrange that f = ∪_{s∈T} f_{s} is an isomorphism from A_{n} onto the desired structure. With this goal, we maintain the following condition.

Condition Maintained: Suppose t < s, where g(n, t) ≤ g(n, s), and for all t < t′ < s, we have g(n, t′) ≥ g(n, t). Then f_{s} ⊇ f_{t}.

Let f_{0} = ∅, and let D_{0} = ∅. Given f_{s} and D_{s}, we must determine f_{s+1} and D_{s+1}. The target structure is M_{k}, where k = g(n, s + 1). First, suppose g(n, s + 1) ≥ g(n, s). Then we let f_{s+1} ⊇ f_{s}. We extend to include the required elements in the domain and range. We let D_{s+1} ⊇ D_{s}, where f_{s+1} makes the sentences true in the target structure. Now, suppose g(n, s + 1) < g(n, s). Let t < s be greatest such that g(n, t) = g(n, s + 1) and there is no t < t′ < s such that g(n, t′) < g(n, t), or if there is no t < s such that g(n, t) = g(n, s + 1), take the greatest t < s such that g(n, t) ≤ g(n, s + 1). We may assume that f_{s} extends f_{t}. We let f_{s+1} extend f_{t} such that f_{s+1} makes D_{s} true in the target structure.

What is important in the proof above is that A is computable, the substructures M_{k} are computably ennumerable, uniformly in k, and they form a ≤_{1}-elementary chain with union A. For an arbitrary computable Archimedean ordered field of infinite transcendence degree, we would have trouble getting the ≤_{1}-elementary chain. The difficulties disappear when we consider real closed fields.

Theorem 4.9. Let K be the class of computable Archimedean real closed ordered fields, and let A be a 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.

Proof. For 1, we have a computable Π_{2} Scott sentence describing the real closed ordered fields in which every element is a root of some non-trivial polynomial with integer coefficients. It follows that I(A) is Π_{2}^{0}. For completeness, the proof is as for ℚ or ℚ(a), where a is real algebraic. Let S be a Π_{2}^{0} set. We can produce a uniformly computable sequence (A_{n})_{n∈ω} such that if n ∈ S, then A_{n} ≅ A, and otherwise, A_{n} ≅ A(e). Let M^{+} be a computable copy of A(e), and let M be the substructure isomorphic to A. Note that M is c.e., and it is an elementary substructure of M^{+}.

For 2, let A be the real closure of a set of e_{1}, …, e_{k}, where the e_{i} are algebraically independent computable reals. We have a Scott sentence describing a real closed Archimedean ordered field, with elements filling the cuts of the chosen e_{i} and not having k + 1 algebraically independent elements. This sentence can be put in the form φ & ¬ψ, where φ and ψ are computable Σ_{2}. It follows that I(A) is d-Σ_{2}^{0}.

For completeness, the proof is the same as for ℚ(e_{0}, …, e_{k−1}). Let e_{k} be a further computable real, independent of e_{0}, …, e_{k−1}. Let M^{+} be a computable real closed ordered field, with elements filling the cuts of e_{i} for i ≤ k. Let M be the subfield isomorphic to A, and let M^{−} be the real closure of the elements corresponding to e_{i}, for i < k − 1. Then M^{−} and M are c.e. substructures of M^{+}, and

M^{−} ≤_{1} M ≤_{1} M^{+} .

(In fact, we have elementary substructures here.) We can produce a uniformly computable sequence (A_{n})_{n∈ω} such that if n ∉ S_{1}, then A_{n} ≅ M^{−}, if n ∈ S_{1} − S_{2}, then A_{n} ≅ M, and if n ∈ S_{1} ∩ S_{2}, then A_{n} ≅ M^{+}.

For 3, we have a computable Π_{3} Scott sentence describing an Archimedean real closed ordered field in which the cuts filled are exactly those of the elements of A. For completeness, the proof is as for ℚ(e_{1}, e_{2}, …), where e_{1}, e_{2}, … are algebraically independent reals. We have A computable. Let (a_{i})_{i∈ω} be a computable list of all elements of A, and let M_{k} be the real closure of {a_{i} : i < k} in A. Then the structures M_{k} are c.e. uniformly in k, and they form an elementary chain with union A. Therefore, we can produce a uniformly computable sequence (A_{n})_{n∈ω} such that if n ∉ Cof, then A_{n} ≅ A, and if n ∈ Cof, and k is the cardinality of ω − W_{n}, then A_{n} ≅ M_{k}.

5 Abelian p-Groups

5.1 Preliminaries on Abelian p-Groups

Fix a prime p. An Abelian group G is a p-group if for each x ∈ G, the order of x is p^{n} for some n. We will consider only countable Abelian p-groups. These groups are of particular interest because of their classification up to isomorphism by Ulm. For a classical discussion of this theorem and a more detailed discussion of this class of groups, consult Kaplansky’s book [10]. Generally, notation here will be similar to Kaplansky’s.

Let G be a countable Abelian p-group. We define a sequence of subgroups G_{α}, letting G_{0} = G, G_{α+1} = pG_{α}, and for limit α, G_{α} = ∩_{β<α}G_{β}. There is a countable ordinal α such that G_{α} = G_{α+1}. The least such α is the length of G, denoted by λ(G). The group is reduced if G_{λ(G)} = {0}. An element x ≠ 0 has height β if x ∈ G_{β} − G_{β+1}. Let P (G) be the set of element of G of order p. Let P_{α} = G_{α} ∩ P (G). For each β < λ, P_{β}/P_{β+1} is a vector space over ℤ_{p} of dimension ≤ ℵ_{0}, with dimension denoted by u_{β}(G). The Ulm sequence for G is the sequence (u_{β}(G))_{β<λ(G)}.

For any computable ordinal α, it is somewhat straightforward to write a computable infinitary sentence stating that G is a reduced Abelian p-group of length at most α and describing its Ulm invariants. In particular, Barker [1] verified the following.

Lemma 5.1. Let G be a computable Abelian p-group.

1. G_{ω·α} is Π_{2α}^{0}.

2. G_{ω·α+m} is Σ_{2α+1}^{0}.

3. P_{ω·α} is Π_{2α}^{0}.

4. P_{ω·α+m} is Σ_{2α+1}^{0}.

Proof. It is easy to see that 3 and 4 follow from 1 and 2 respectively. Toward 1 and 2, note the following:

x ∈ G_{m} ⟺ ∃y(p^{m}y = x) ;
x ∈ G_{ω} ⟺ ⋀_{m∈ω} ⋀ ∃y(p^{m}y = x) ;
x ∈ G_{ω·α+m} ⟺ ∃y[p^{m}y = x & G_{ω·α}(y)] ;
x ∈ G_{ω·α+ω} ⟺ ⋀_{m∈ω} ⋀ ∃y[p^{m}y = x & G_{ω·α}(y)] ;
x ∈ G_{ω·α} ⟺ ⋀_{γ<α} ⋀ G_{ω·γ}(x) for limit α .

Using Lemma 5.1, it is easy to write, for any computable ordinal β, a computable Π_{2β+1}^{0} sentence whose models are exactly the reduced Abelian p-groups of length ωβ.

Khisamiev gave a useful characterization of those Abelian p-groups which have computable copies [13], [12], at least for certain lengths. For groups of finite length, it is easy to produce computable copies. Khisamiev gave a characterization for length ω, and proved an inductive lemma that allowed him to build up to all lengths less than ω^{2}. Here is the result for length ω.

Proposition 5.2 (Khisamiev). Let A be a reduced Abelian p-group of length ω. Then A has a computable copy iff

1. the relation R_{A} = {(n, k) : u_{n}(A) ≥ k} is Σ_{2}^{0}, and

2. there is a computable function f_{A} such that for each n, f_{A}(n, s) is nondecreasing, with limit n^{∗} ≥ n such that u_{n^{∗}}(A) ≠ 0.

Moreover, we can effectively determine a computable index for a copy of A from a Σ_{2}^{0} index for R_{A} and a computable index for a function f_{A}.

Here is the inductive lemma.

Lemma 5.3 (Khisamiev). Let A be a reduced Abelian p-group. Suppose A_{ω} is Δ_{3}^{0}, the relation R_{A} is Σ_{2}^{0}(X), and there is a function f_{A} such that for all n, f_{A}(n, s) is non-decreasing, with limit r^{∗} ≥ r such that u_{r^{∗}}(A) ≠ 0. Then A has a computable copy, with index computed effectively from those for A_{ω}, R_{A}, and f_{A}.

The results above relativize. They yield the following two theorems, which we shall use in what follows.

Theorem 5.4 (Khisamiev). Let A be a reduced Abelian p-group of length ωM, where M ∈ ω. Then A has a computable copy iff for each k < M,

1. the relation R_{A}^{k} = {(r, t)|u_{ωk+r}(A) ≥ t}} is Σ_{2k+2}^{0}, and 2. there is a Δ_{2k+1}^{0} function f_{A}^{k}(r, s) such that for each n, the function

f_{A}^{k}(n, s) is nondecreasing, with limit r^{∗} ≥ r such that u_{ωk+r^{∗}}(A) ≠ 0.

Moreover, we can pass effectively from Σ_{2k+2}^{0} indices for the relations R_{A}^{k} and Δ_{2k+1}^{0} indices for appropriate functions f_{A}^{k} to a computable index for a copy of A.

Theorem 5.5 (Khisamiev). Let A be a reduced Abelian p-group of length ≤ ωM. Suppose A_{ωM} is Δ_{2M+1}^{0}, and for each k < M,

1. the relation R_{A}^{k} = {(r, t)|u_{ωk+r}(A) ≥ t}} is Σ_{2k+2}^{0}, and

2. there is a Δ_{2k+1}^{0} function f_{A}^{k}(r, s) such that for each n, f_{A}^{k}(n, s) is nondecreasing, with limit r^{∗} ≥ r such that u_{ωk+r^{∗}}(A) ≠ 0.

Then A has a computable copy, with index computed effectively from the Δ_{2M+1}^{0} index for A_{ωM}, Σ_{2k+2}^{0} indices for R_{A}^{k} and Δ_{2k+1}^{0} indices for appropriate functions f_{A}^{k}.

5.2 Index Sets of Groups of Small Ulm Length

In [3], it is shown that for the countable reduced Abelian p-group of length ωM with uniformly infinite Ulm invariants, the index set is m-complete Π_{2M+1}^{0}. It seemed that other complexities might be possible for groups of the same length. However, it turned out that the index set for any group of length ωM is also m-complete Π_{2m+1}^{0}. The case M = 1 of the following theorem was first proved in [4].

Proposition 5.6. Let K be the class of reduced Abelian p-groups of length ωM, and let A ∈ K. Then I(A) is m-complete Π_{2M+1}^{0} within K.

Proof. Let A ∈ K. First, we show that A has a computable Π_{2M+1} Scott sentence. There is a computable Π_{2} sentence θ characterizing the Abelian p-groups. Next, there is a computable Π_{2M+1} sentence λ characterizing the groups which are reduced and have length at most ωM. For each α < ωM, we can find a computable Σ_{2M} sentence φ_{α,k} saying that u_{α} ≥ k. The set of these Σ_{2M} sentences true in A is Σ_{2M}^{0}. For each φ_{α,k}, we can find a computable Π_{2M} sentence equivalent to the negation, and the set of these sentences true in A is Π_{2M}^{0}. We have a computable Π_{2M+1} sentence υ equivalent to the conjunction of the sentences ±φ_{α,k} true in A. Then we have a computable Π_{2M+1} Scott sentence equivalent to θ & λ & υ. It follows that I(A) is Π_{2M+1}^{0}.

For completeness, let S be a Π_{2M+1}^{0} set. We will produce a uniformly computable sequence (A_{n})_{n∈ω} of elements of K, such that n ∈ S if and only if A_{n} ≅ A. We will specify A_{n} by giving relations R_{A_{n}}^{k} and functions f_{A_{n}}^{k}, for k < M, as in Theorem 5.4. Since A is computable, there are relations R_{A}^{k} and functions f_{A}^{k}, as in the theorem. For k < M − 1, we let R_{A_{n}}^{k} = R_{A}^{k} and f_{A_{n}}^{k} = f_{A}^{k}.

We will define a single Δ_{2M−1}^{0} function g to serve as f_{A_{n}}^{M−1} for all n. We then define a family of relations R_{n} to serve as R_{A_{n}}^{M−1}, with the feature that if (m, k + 1) is included, so is (m, k). The relations will be uniformly Σ_{2M}^{0}. Moreover, if n ∈ S, then we will have R_{n} = R_{A}^{M−1}, and if n ∉ S, then R_{n} will include the pairs (m, 1) for m = lim_{s} g(r, s), but will omit some of the other pairs (m, 1) in R_{A}. Having determined g and R_{n} for n ∈ ω, we will be in a position to apply Theorem 5.4.

To get the function g, we first define a Δ_{2M}^{0} sequence (k_{n})_{n∈ω}, where

k_{0} = lim_{s} f_{A}^{M−1}(0, s) and k_{m+1} = lim_{s} f_{A}^{M−1}(k_{m+1}, s) .

We will define g(r, s) in such a way that lim_{s} g(r, s) = k_{2r+1}. We have a Δ_{2M−1}^{0} approximation to the sequence (k_{n})_{n∈ω}. Let k_{m,0} = m for all m, let k_{0,s+1} = f_{A}^{M−1}(0, s + 1), and let k_{m+1,s+1} be the maximum of f_{A}^{M−1}(k_{m+1,s+1}, s + 1) and k_{m+1,s}. For each m, the sequence k_{m,s} is nondecreasing in s and has limit k_{m}. Define g(r, s) = k_{2r+1,s}.

The relation R_{A}^{M−1} is c.e. in Δ_{2M}^{0}, and we have a sequence of finite approximations R_{A,s}^{M−1}. The set S is Π_{1}^{0} over Δ_{2M}^{0}. We have a Δ_{2M}^{0} approximation (S_{s})_{s∈ω} such that if n ∈ S, then n ∈ S_{s}, for all s, and if n ∉ S, then there exists s_{0} such that for s < s_{0}, n ∈ S_{s}, and for s ≥ s_{0}, n ∉ S_{s}. We define uniformly Σ_{2M}^{0} relations R_{n}. At stage 0, we have R_{n,0} = ∅. At stage s + 1, we extend R_{n,s} to R_{n,s+1}. We add the pair (k_{2s+1}, 1). If n ∉ S_{s}, this is all, but if n ∈ S_{s}, we include all pairs (r, k) in R_{A,s}^{M−1}. If n ∈ S, then R_{n} = R_{A}^{M−1}. If n ∉ S, then R_{n} includes only finitely many of the pairs (k_{2s}, 1), while R_{A}^{M−1} includes all of them.

We apply Theorem 5.4 as planned to obtain a uniformly computable sequence of reduced Abelian p-groups (A_{n})_{n∈ω}, all of length ωM, such that A_{n} ≅ A iff n ∈ S.

We have considered groups of limit length ωM. Now, we consider groups of successor length. There are several cases.

Proposition 5.7. Let K be the class of reduced Abelian p-groups of length ωM + N, where N > 0. Suppose A is a computable member of K, where A_{ωM} is finite.

1. If A_{ωM} is minimal for the prescribed length, (i.e. if it is of type ℤ_{p^{N}}), then I(A) is m-complete Π_{2M+1}^{0} within K. (It is m-complete d-Σ_{2M+1}^{0}

within the class of groups of length ≤ N.)

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

Proof. We use the following lemma.

Lemma 5.8. Let C be a non-trivial finite Abelian p-group of length N.

1. If C is minimal among groups of length N, of type ℤ_{p^{N}}, then it has a finitary Π_{1} Scott sentence within groups of length N. For any X, and any set S that is Π_{1}^{0}(X), there is a uniformly X-computable sequence (C_{n})_{n∈ω} consisting of groups of length N such that

C_{n} ≅ C iff n ∈ S .

2. If C is not minimal among groups of length N, then it has a finitary d-c.e. Scott sentence, and for any X, and any set S that is d-c.e. relative to X, there is a uniformly X-computable sequence (C_{n})_{n∈ω} consisting of groups of length N such that

C_{n} ≅ C iff n ∈ S .

Proof. For 1, we have a finitary Π_{1} Scott sentence within K saying that there are no more than p^{N} elements. The construction will be uniform in X, so without loss of generality we assume that X = ∅. If S is Π_{1}^{0}, we have a uniformly computable sequence (C_{n})_{n∈ω} of Abelian p-groups, all of length N, such that if n ∈ S, then C_{n} ≅ ℤ_{p^{N}}, and if n ∉ S, then C_{n} ≅ ℤ_{p^{N}}^{2} .

For 2, we have a finitary d-c.e. Scott sentence, as in the section on finite structures. Suppose S = S_{1} − S_{2}, where S_{1} and S_{2} are computably enumerable. We let C^{−} be a proper subgroup of C, still of length N, and we let C^{+} be a proper extension of C, also of length N. We get a uniformly computable sequence (C_{n})_{n∈ω} such that C_{n} ≅ C^{−} if n ∉ S_{1}, C_{n} ≅ C if n ∈ S_{1} − S_{2}, and C_{n} ≅ C^{+} if n ∈ S_{1} ∩ S_{2}.

Now, we can prove the proposition. Let C = A_{ωM}. For 1, we have a computable Π_{2M+1} sentence characterizing the groups G such that G_{ωM} ≅ C within the class of reduced Abelian p-groups of length ωM + N. We have a computable Π_{2M+1} sentence characterizing the Abelian p-groups G such that for all α < ωM, u_{α}(G) = u_{α}(A). The conjunction, equivalent to a computable Π_{2M+1} sentence, is a Scott sentence for A.

For completeness, let S be Π_{2M+1}^{0}. Note that S is Π_{1}^{0} over Δ_{2M+1}^{0}. By Lemma 5.8, we have a uniformly Δ_{2M+1}^{0} sequence (C_{n})_{n∈ω} of groups of length N such that C_{n} ≅ C iff n ∈ S. Since A is computable, we get Σ_{2k+2}^{0} relations R_{A}^{k}, and Δ_{2k+1}^{0} functions f^{k}, as required in Theorem 5.5. We obtain a uniformly computable sequence (A_{n})_{n∈ω} of groups of length ωM + N such that A_{n} ≅ A iff n ∈ S.

For 2, we have a computable d-Σ_{2M+1} sentence characterizing the groups G such that G_{ωM} ≅ C. We have a computable Π_{2M+1} sentence characterizing the Abelian p-groups such that for all α < ωM, u_{α}(G) = u_{α}(A). The conjunction, equivalent to a computable d-Σ_{2M+1} sentence, is a Scott sentence for A.

Toward completeness, let S be a d-Σ_{2M+1}^{0} set. Then S is d-c.e. relative to Δ_{2M+1}^{0}. By Lemma 5.8, there is a uniformly Δ_{2M+1}^{0} sequence (C_{n})_{n∈ω} of groups of length N such that C_{n} ≅ C iff n ∈ S. As above, since A is computable, we have relations R_{A}^{k} and functions f^{k} for k < M, as required in Theorem 5.5. We get a uniformly computable sequence (A_{n})_{n∈ω} of groups of length ωM +N such that A_{n} ≅ A iff n ∈ S.

We continue with reduced Abelian p-groups A of length ωM +N, but now we suppose that A_{ωM} is infinite. This means that for some k < N, u_{ωM+k}(A) = ∞.

Proposition 5.9. Let K be the class of reduced Abelian p-groups of length ωM+ N. Let A be a computable member of K. If there is a unique k < N such that u_{ωM+k}(A) = ∞, and for all m < k we have u_{ωM+m}(A) = 0, then I(A) is m-complete Π_{2M+2}^{0} within K.

Proof. We use the following lemma.

Lemma 5.10. Suppose C is a reduced Abelian p-group of length N, where there is a unique k < N such that u_{k}(C) = ∞, and for all m < k, u_{m}(C) = 0.

1. The structure C has a computable Π_{2} Scott sentence.

2. For any set X, if S is Π_{2}^{0}(X), there is a uniformly X-computable sequence (C_{2})_{n∈ω} of reduced Abelian p-groups, all of length N, such that

C_{n} ≅ C iff n ∈ S .

Proof. We have C ≅ H ⊕ ℤ_{p^{k+1}}^{∞}, where H is a finite direct sum of ℤ_{p^{i+1}} for k < i < N. Even part 1 requires some effort. There is a computable Π_{2} sentence characterizing the Abelian p-groups. There is a computable Π_{1} sentence saying that the length is at most N. There is a computable Π_{2} sentence saying that u_{m} = 0 for all m < k. There is a finitary d-Σ_{1} sentence characterizing the groups G of length N such that G_{k+1} ≅ C_{k+1}. Finally, there is a computable Π_{2} sentence saying that, for all r, there exists a substructure of type ℤ_{p^{k+1}}^{r}. The conjunction of these is equivalent to a computable Π_{2} sentence. We show that it is a Scott sentence for C.

We show that if G is a model of the proposed Scott sentence, then u_{k}(G) = ∞. To show that u_{k}(G) ≥ m, consider the set of statements z_{1}x_{1} + … + z_{m}x_{m} = h, where z_{i} ∈ ℤ_{p} and h ∈ G_{k+1}. Say the number of these statements is r. By Ramsey’s Theorem (the finite version), there exists M such that

M → (2m)_{r}^{k} ;

that is, for any partition of k-sized subsets of a set of size M into r classes, there is a set of size 2m which is “homogeneous” in the sense that all k-sized subsets lie in the same class in the partition (for example, see [9]). Take a substructure of G of type ℤ_{p^{k+1}}^{M}, and from each factor ℤ_{p^{k+1}}, take an element b_{i} of height k and order p. If there is no m-sized subset independent over G_{k+1}, then for each m-sized subset b_{i_{1}}, …, b_{i_{m}} (with i_{1} < … < i_{m}), one of the r statements above is satisfied. We partition according to the first such statement. Take a homogeneous set of size 2m, with all m-tuples satisfying the statement z_{1}x_{1} + … + z_{n}x_{n} = h. We have disjoint m-tuples c_{1}, …, c_{m} and d_{1}, …, d_{m} such that

z_{1}c_{1} + … + z_{m}c_{m} = z_{1}d_{1} + … + z_{m}d_{m} .

This is impossible. Therefore, we have u_{k}(G) ≥ m.

For 2, assume without loss of generality that X = ∅. Let S be a Π_{2}^{0} set. We can produce a uniformly computable sequence (C_{n})_{n∈ω} such that if n ∈ S, then C_{n} ≅ H ⊕ ℤ_{p^{k+1}}^{∞}, and otherwise C_{n} ≅ H ⊕ ℤ_{p^{k+1}}^{r}, for some finite r. We start with a copy of H. At each stage when we believe n ∈ S, we add a new direct summand of type ℤ_{p^{k+1}}. Otherwise, we add nothing. The resulting sequence has the desired properties.

Using Lemma 5.10, we can prove the proposition. Let C = A_{ωM}. We have a computable d-c.e. Scott sentence for C. It follows that there is a computable d-Σ_{2M+1} sentence describing the groups G with G_{ωM} ≅ C. We have a computable Π_{2m+1} sentence characterizing the Abelian p-groups G such that for α < ωM, u_{α}(G) = u_{α}(A). There is a computable Π_{2M+2} sentence equivalent to the conjunction, and this is a Scott sentence for A.

For completeness, let C = A_{ωM}. Let S be Π_{2M+2}^{0}. Then S is Π_{2}^{0} over Δ_{2M+1}^{0}. By Lemma 5.10, we get a sequence (C_{n})_{n∈ω}, uniformly Δ_{2M+1}^{0}, such that for all n, C_{n} has length N, and C_{n} ≅ C iff n ∈ S. Now, we apply Theorem 5.5. Since A is computable, we have Σ_{2k+2}^{0} relations R_{A}^{k} and Δ_{2k+1}^{0} functions f_{A}^{k} for all k < M. From these, together with the sequence (C_{n})_{n∈ω}, we obtain a uniformly computable sequence (A_{n})_{n∈ω} such that for all n, A_{n} has length ωM + N, and A_{n} ≅ A iff n ∈ S.

Proposition 5.11. Let K be the class of reduced Abelian p-groups of length ωM + N for some M, N ∈ ω. Let A ∈ K. If there is a unique k < N such that u_{ωM+k}(A) = ∞, and for at least one m < k we have 0 < u_{ωM+m}(A) < ∞, then I(A) is m-complete d-Σ_{2M+2}^{0} within K.

Proof. We use the following lemma.

Lemma 5.12. Suppose C has length N. Suppose there is a unique k < N such that u_{k}(C) = ∞, and for at least one m < k, 0 < u_{m}(C) < ∞.

1. The structure C has a computable d-Σ_{2} Scott sentence.

2. For any X, if S is d-Σ_{2}^{0}(X), there is a uniformly X-computable sequence (C_{n})_{n∈ω} of reduced Abelian p-groups of length N such that

C_{n} ≅ C iff n ∈ S .

For 1, the Scott sentence is the same as in Lemma 5.10, except that we must specify u_{m}, for m < k. If u_{m} ≠ 0, we need a computable d-Σ_{2} sentence.

For 2, assume without loss of generality that X = ∅. Let S be d-Σ_{2}^{0}, say S = S_{1}−S_{2}, where S_{i} is Σ_{2}^{0}. Let C^{−} have the same Ulm sequence as C except that u_{m}(C^{−}) = 0. Let C^{+} have the same Ulm sequence as C except that u_{m}(C^{+}) > u_{m}(C). We produce a uniformly computable sequence (C_{n})_{n∈ω} of Abelian pgroups of length N such that if n ∉ S_{1}, then C_{n} ≅ C^{−}, if n ∈ S_{1} − S_{2}, then C_{n} ≅ C, and if n ∈ S_{1} ∩ S_{2}, then C_{n} ≅ C^{+}.

We start with H and add further direct summands ℤ_{p^{i+1}}. At stage s, if we believe n ∉ S_{1}, then we convert any direct summands of the form ℤ_{p^{m+1}} to the form ℤ_{p^{k+1}}. If we believe n ∈ S_{1} − S_{2}, we make the number of direct summands of the form ℤ_{p^{m+1}} match that in C. If at stage s−1, we had none, then we create new ones. If at stage s − 1, we had too many, then we retain those from the greatest stage t < s where we had the right number (or too few), and convert the extra ones to ℤ_{p^{k+1}}. If we believe n ∈ S_{1} ∩ S_{2}, we make the number of direct summands of the form ℤ_{p^{m+1}} match that in C^{+}. In any case, we add a new direct summand of the form ℤ_{p^{k+1}}.

We turn to the proof of Proposition 5.11. Let C = A_{ωM}. By Lemma 5.12, C has a computable d-Σ_{2} Scott sentence. From this, we get a computable d-Σ_{2M+2} sentence describing the groups G such that G_{ωM} ≅ C. We have a computable Π_{2M+1} sentence characterizing Abelian p-groups with Ulm invariants matching those of A for α < ωM. The conjunction, which is equivalent to a d-Σ_{2M+2} sentence, is a Scott sentence for A.

For completeness, note that if S is d-Σ_{2M+2}^{0}, then S is d-Σ_{2}^{0} relative to Δ_{2M+1}^{0}. Applying Lemma 5.12, we get a uniformly Δ_{2M+1}^{0} sequence (C_{n})_{n∈ω} of groups of length N such that C_{n} ≅ C iff n ∈ S.

Now, we apply Theorem 5.5, with C_{n}, together with the Σ_{2k+2}^{0} relations R_{A}^{k}, and the Δ_{2k+1}^{0} functions f_{A}^{k}, for k < M. We get a uniformly computable sequence of groups (A_{n})_{n∈ω}, all of length ωM + N, such that A_{n} ≅ A iff n ∈ S.

Proposition 5.13. Let K be the class of reduced Abelian p-groups of length ωM + N for some M, N ∈ ω. Let A be a computable member of K. 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.

Proof. We use the following lemma.

Lemma 5.14. Let C be a reduced Abelian p-group of length N. Suppose k is greatest such that u_{k}(C) = ∞, and there exists m < k such that u_{m}(C) = ∞.

1. The structure C has a computable Π_{3} Scott sentence.

2. For any X, if S is Π_{3}^{0}(X), then there is a uniformly X-computable sequence (C_{n})_{n∈ω}, consisting of groups of length N, such that

C_{n} ≅ C iff n ∈ S .

Proof. For 1, we have a finitary Π_{2} sentence describing the reduced Abelian p-groups of length ≤ N. For each i < N, if u_{i}(C) is finite, we have a finitary d-Σ_{2} sentence specifying the value. If u_{i}(C) = ∞, we have a computable Π_{3} sentence saying this. The conjunction is equivalent to a computable Π_{3} sentence, and it is a Scott sentence for C.

For 2, assume without loss of generality that X = ∅. Let S be ω − Cof. We produce a uniformly computable sequence (C_{n})_{n∈ω} of groups of length N such that if n ∈ S, then C_{n} ≅ C, and if n ∉ S, say ω − W_{n} has cardinality r, then u_{m}(C_{n}) = r. We have a sequence of computable approximations to ω −W_{n}. Let P_{0} = ∅. Given P_{s}, if there is some x ∈ W_{n,s+1} − P_{s}, then for the first such x, we let P_{s+1} consist of all y < x in P_{s}. If there is no such x, then take the first y ∉ W_{n,s+1} such that y ∉ P_{s}, and let P_{s+1} be the result of adding y to P_{s}. We have x ∈ ω − W_{n} iff for all sufficiently large s, x ∈ P_{s}. Moreover, if ω − W_{n} is finite, then infinitely often P_{s} = W_{n}.

We may suppose that

C = H ⊕ ℤ_{p^{m+1}}^{∞} ⊕ ℤ_{p^{k+1}}^{∞} .

We construct C_{n} as follows. We start with a copy of H. At stage s, say P_{s} has cardinality r, where at stage s − 1 the cardinality was r′. If r′ < r, we add direct summands of the form ℤ_{p^{m+1}} to bring the number up to r. If r′ > r, we keep the direct summands of the form ℤ_{p^{m+1}} that we had at the greatest stage t < s, where the number was at most r, and we give the remaining ones the form ℤ_{p^{k+1}}. In any case, we add at least one new direct summand of the form ℤ_{p^{k+1}}.

Now, we turn to the proof of Proposition 5.13. Let C = A_{ωM}. By Lemma 5.14, C has a computable Π_{3} Scott sentence. It follows that there is a computable Π_{2M+3} sentence characterizing the groups G such that G_{ωM} ≅ C. We have a computable Π_{2M+1} sentence characterizing the Abelian p-groups G such that for α < ωM, u_{α}(G) = u_{α}(A). There is a computable Π_{2M+3} sentence equivalent to the conjunction, and this is a Scott sentence for A.

For completeness, let S be Π_{2M+3}^{0}. Then S is Π_{3}^{0} over Δ_{2M+1}^{0}. By Lemma 5.14, we have a uniformly Δ_{2M+1}^{0} sequence (C_{n})_{n∈ω} of groups of length N such that C_{n} ≅ C iff n ∈ S. Since A is computable, we have relations R_{A}^{k} and functions f_{A}^{k}, for k < M, as required in Theorem 5.5. We get a uniformly computable sequence (A_{n})_{n∈ω} of groups of length ωM + N, such that A_{n} ≅ A iff n ∈ S.

We can now summarize the results for groups A where λ(A) < ω^{2}.

Theorem 5.15. 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 (of 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 mcomplete 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.

5.3 Groups of Greater Ulm Length

Theorem 5.15 leaves open the possibility, counterintuitive though it may be, that there is an Abelian p-group of length at least ω^{2} with an arithmetical index set. The following result rules out this possibility.

Theorem 5.16. Let A be a computable reduced Abelian p-group of length greater than ωM. Then for any Δ_{2M+1}^{0} set S, there is a uniformly computable sequence (A_{n})_{n∈ω} such that

A_{n} ≅ A iff n ∈ S .

That is, I(A) is Δ_{2M+1}^{0}-hard.

Proof. Let C = A_{ωM}, and let C′ be a finite reduced Abelian p-group, not isomorphic to C. Let S be Δ_{2M+1}^{0}. We have a uniformly Δ_{2M+1}^{0} sequence (C_{n})_{n∈ω} such that C_{n} ≅ C if n ∈ S, and C_{n} ≅ C′ otherwise. Since A is computable, we have relations R_{A}^{k} and functions f_{A}^{k} as in Theorem 5.5. Then we get a uniformly computable sequence (A_{n})_{n∈ω} such that A_{n} ≅ A iff n ∈ S.

The following corollary is immediate.

Corollary 5.17. Let A be an Abelian p-group of length at least ω^{2}. Then I(A) is not arithmetical.

6 Models of the original Ehrenfeucht theory

An Ehrenfeucht theory, is a complete theory T having exactly n non-isomorphic countable models for some finite n > 1. A well-known result of Vaught shows that n cannot equal 2 [19]. Ehrenfeucht gave an example for n = 3. Ehrenfeucht told Vaught about his example, and it is described in [19]. The language of the theory has a binary relation symbol < and constants c_{n} for n ∈ ω. The axioms say that < is a dense linear ordering without endpoints, and the constants are strictly increasing. The theory T has the following three non-isomorphic countable models. There is the prime model, in which there is no upper bound for the constants. There is the saturated model, in which the constants have an upper bound but no least upper bound. There is the middle model, in which there is a least upper bound for the constants.

Proposition 6.1. Let K be the class of models of the original Ehrenfeucht theory T. Let A^{1} be the prime model, let A^{2} be the middle model, and A^{3} be the saturated model.

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.

Proof. For 1, first note that there is a computable Π_{2} sentence characterizing the models of T such that

(∀x) ⋁_{n∈ω} ⋁ x < c_{n} .

This is a Scott sentence for A^{1}. Therefore, I(A^{1}) is Π_{2}^{0}.

Toward completeness, let S be a Π_{2}^{0} set. We will build a uniformly computable sequence (A_{n})_{n∈ω} such that

A_{n} ≅ \{ \begin{matrix}A^{1} & if n ∈ S , \\ A^{2} & otherwise . \end{matrix}

We have a computable approximation (S_{s})_{s∈ω} for S such that

n ∈ S iff n ∈ S_{s} for infinitely many s .

For fixed n, when n ∉ S, we build the middle model by creating a least upper bound for the constants we have placed so far and preserving it until/unless our approximation changes. When n ∈ S_{s}, we destroy the current least upper bound and place the next constant at the end of the ordering. If n really is in S, then the sequence of constants is cofinal, and we get a copy of the prime model. If n is not in S, then for some stage s_{0}, for all s ≥ s_{0}, we have n ∉ S_{s}, and we will preserve the least upper bound created at stage s_{0}, so we get a copy of the middle model.

We turn to 2. First, note that there is a computable Σ_{3} Scott sentence for A^{2}, describing a model of T such that

(∃x) [ ⋀_{n∈ω} ⋀ x > c_{n} & (∀y) [( ⋀_{n∈ω} ⋀ y > c_{n}) → y ≥ x]].

It follows that I(A^{2}) is Σ_{3}^{0}.

Toward completeness, let S be a Σ_{3}^{0} set. We build a uniformly computable sequence (A_{n})_{n∈ω} such that

A_{n} ≅ \{ \begin{matrix}A^{2} & if n ∈ S , \\ A^{3} & otherwise . \end{matrix}

Note that S is Σ_{2}^{0} over Δ_{2}^{0}. We have a Δ_{2}^{0} approximation (S_{k})_{k∈ω}, such that n ∈ S iff for all sufficiently large k, n ∈ S_{k}. Fix n. Then there is a Δ_{2}^{0} sequence of instructions (i_{k})_{k∈ω}. We start with an upper bound for the constants. If n ∉ S_{k}, then i_{k} says to destroy the current least upper bound for the constants, moving left, closer to the constants. If n ∈ S_{k}, then i_{k} says to preserve the current least upper bound for the constants.

Now, we build the computable model A_{n} based on approximations of the sequence of instructions. There are mistakes of two kinds. We may wrongly guess that i_{k} said to preserve the current least upper bound for the constants. The result is a delay. We may wrongly guess that i_{k} said to destroy the current least upper bound for the constants. Having introduced a new upper bound to the left of this one, we correct our mistake by putting the next constant to the right of any added elements, so as to preserve the upper bound as in the instruction.

Again, if n is in S, Δ_{2}^{0} will eventually think so, and we will eventually preserve a particular least upper bound for the constants, building the middle model. Otherwise, infinitely often we will create a new upper bound for the constants, moving to the left, closer to the constants. The result is the saturated model.

Finally, we turn to 3. We have a Π_{3}^{0} Scott sentence for A^{3}, describing a model of T such that

(∃x) [ ⋀_{n∈ω} ⋀ x > c_{n}] & (∀y) [ ⋀_{n∈ω} ⋀ y > c_{n} ⟹ ∃z[ ⋀_{n∈ω} ⋀ z > c_{n}&z < y]] .

It follows that I(A^{3}) is Π_{3}^{0}.

For completeness, we notice that the proof is the symmetric case of the proof in part 2.

References

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

[2] W. Calvert, “The isomorphism problem for classes of computable fields,” Archive for Mathematical Logic 75 (2004), pp. 327–336.

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

[4] W. Calvert, D. Cenzer, V. Harizanov, and A. Morozov, “Δ_{2}^{0} categoricity of Abelian p-groups,” preprint.

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

[6] B. F. Csima, A. Montalbán, and R. A. Shore, “Boolean algebras, Tarski invariants, and index sets,” to appear in the Notre Dame Journal of Formal Logic.

[7] V. P. Dobritsa, “Complexity of the index set of a constructive model,” Algebra and Logic 22 (1983), pp. 269–276.

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

[9] W. Hodges, A Shorter Model Theory, Cambridge University Press, 1997.

[10] I. Kaplansky, Infinite Abelian Groups, University of Michigan Press, Ann Arbor, 1954.

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

[12] N. G. Khisamiev, “Constructive Abelian groups,” Handbook of Recursive Mathematics (Yu. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors), vol. 2, North-Holland, Amsterdam, 1998, pp. 1177–1231.

[13] N. G. Khisamiev, “Constructive Abelian p-groups ”Siberian Advances in Mathematics, vol. 2(1992), pp. 68–113.

[14] S. Lempp and T. Slaman, “The complexity of the index sets of ℵ_{0}- categorical theories and of Ehrenfeucht theories,” to appear in the Advances in Logic (Proceedings of the North Texas Logic Conference, October 8–10, 2004), Contemporary Mathematics, American Mathematical Society.

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

[16] D. E. Miller, “The invariant Π_{α}^{0} separation principle”, Transactions of the American Mathematical Society, vol. 242(1978), pp. 185–204.

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

[18] R. I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, 1987.

[19] R. L. Vaught, “Denumerable models of complete theories,” Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959, Pergamon Press, 1961, pp. 303–231.

[20] W. White, “On the complexity of categoricity in computable structures,” Mathematical Logic Quarterly vol. 49 (2003), pp. 603–614.

[21] W. White, Characterizations for Computable Structures, PhD dissertation, Cornell University, 2000.