THE ISOMORPHISM PROBLEM FOR COMPUTABLE ABELIAN p-GROUPS OF BOUNDED LENGTH

WESLEY CALVERT

Abstract. Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples.

We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from nonclassifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated.

1. Introduction

In an earlier paper [4], we began to consider a notion of “classification” for classes of computable structures. For some classes, there is a “classification,” or “structure theorem” of some kind. For instance, the classification of algebraically closed fields states that a single cardinal (the transcendence degree) completely determines the structure up to isomorphism. For other classes (graphs, for example, or arbitrary groups) such a result would be surprising, and when we introduce the necessary rigor we can prove that there is none to be found. They simply have more diversity than any structure theorem could describe.

We assume all structures have for a universe some computable subset of ω and identify a structure with its atomic diagram. Thus, for instance, a structure is computable if and only if its atomic diagram is computable, as a set of Gödel numbers of sentences. Alternatively, we could use the quantifier-free diagram instead of the atomic diagram. Similarly, a structure is associated with the index of a Turing machine which enumerates its atomic diagram (assuming its universe is computable). In this paper, I will write A_{a} for the computable structure with atomic diagram W_{a} and will always assume that a class K of structures has only computable members. The following definition was recently proposed by Goncharov and Knight [7]. Definition 1.1. The isomorphism problem, denoted E(K), is the set

{(a, b)|A_{a}, A_{b} ∈ K, and A_{a} ≃ A_{b}}

If the set of indices for computable members of K, denoted I(K), is hyperarithmetical, then E(K) is Σ_{1}^{1}. Intuitively, in the worst case, where E(K) is properly Σ_{1}^{1}, the easiest way to say that two members of K are isomorphic is to say, “There exists a function which is an isomorphism between them.” Often there are easier ways to check isomorphism, such as counting basis elements of vector spaces. Such a “shortcut” is a classification. There is also a natural “floor” to the complexity of E(K), since to say that a ∈ I(K) requires saying that a is an index for some structure, which is already Π_{2}^{0}.

1991 Mathematics Subject Classification. 03D45, 03C57, 20K10.

Key words and phrases. Classification, Computable, Ulm, Back-and-forth.

The author was partially supported by NSF Grants DMS 9970452 and DMS 0139626. The author wishes to thank J. F. Knight for many helpful comments on this paper.

This notion is closely related to work in descriptive set theory, originating in the work of Friedman and Stanley [6]. In that context, the set of countable models of a theory is viewed as a topological space, and we would calculate the topological complexity of the isomorphism relation as a subset of the Cartesian product of two copies of the space (for a more complete description of the topological situation, see [9]). Many of the proofs that a class has maximal complexity, like the Friedman – Stanley proof of the Borel completeness of fields [6], require only minor modification.

Several classes are well-known to have maximally complicated isomorphism problems. The following theorem summarizes several classical results. Proofs may be found in articles by Rabin and Scott [16], Goncharov and Knight [7], Morozov [14], and Nies [15].

Theorem 1.2. If K is the set of computable members of any of the following classes, then E(K) is Σ_{1}^{1} complete:

(1) Undirected graphs

(2) Linear orders

(3) Trees

(4) Boolean algebras

(5) Abelian p-groups

The following additions to the list follow easily from recent work by Hirschfeldt, Khoussainov, Shore, and Slinko [8].

Theorem 1.3 (Hirschfeldt – Khoussainov – Shore – Slinko). If K is the set of computable members of any of the following classes, then E(K) is Σ_{1}^{1} complete:

(1) Rings

(2) Distributive lattices

(3) Nilpotent groups

(4) Semigroups

In an earlier paper [4], the following were added:

Theorem 1.4.

(1) If K is the set of computable members of any of the following classes, then E(K) is Σ_{1}^{1} complete:

(a) Fields of any fixed characteristic

(b) Real Closed Fields

(2) If K is the set of computable members of any of the following classes, then E(K) is Π_{3}^{0} complete:

(a) Vector spaces over a fixed computable field

(b) Algebraically closed fields of fixed characteristic (c) Archimedean real closed fields

In this paper, the complexity of the isomorphism problem will be calculated for other classes. Two major goals which are partially achieved here are the answers to the following questions:

ISOMORPHISM PROBLEM FOR ABELIAN p-GROUPS 3

Question 1.5. What are the possible complexities of the isomorphism problem for classes of structures?

Question 1.6. Do classes with high complexity acquire it all at once?

Considering Abelian p-groups of bounded Ulm length will give us a sequence of isomorphism problems whose degrees are cofinal in the hyperarithmetical degrees. In some sense, this also shows a smooth transition from very low complexity (say, Π_{3}^{0} complete) to the “non-classifiable” (that is, properly Σ_{1}^{1}).

2. Notation and Terminology for Abelian p-groups

Let p be an arbitrary prime number. Abelian p-groups are Abelian groups in which each element has some power of p for its order. 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.

It is often helpful to follow L. Rogers [18] in representing these groups by trees. Consider a tree T. The Abelian p-group G(T) is the group generated by the nodes in T (among which the root is 0), subject to the relations stating that the group is Abelian and that px is the predecessor of x in the tree. Reduced Abelian p-groups, from this perspective, are represented by trees with no infinite paths.

The idea of Ulm’s theorem is that it generalizes the notion that to determine a finitely generated torsion Abelian group it is only necessary to determine how many cyclic components of each order are included in a direct sum decomposition. Let G be an Abelian p-group. We will produce an ordinal sequence (usually transfinite) of cardinals u_{β}(G) (each at most countable), which is constant after some ordinal (called the “length” of G). If H is also an Abelian p-group and for all β we have u_{β}(G) = u_{β}(H), then H ≃ G (this is still subject to another condition we have yet to define).

First set G_{0} = G. Now we inductively define G_{β+1} = pG_{β} = {px|x ∈ G_{β}}, where px denotes the sum of x with itself p times. We also define, for limit β, the subgroup G_{β} = ⋂_{γ<β} G_{γ}. Further, let P (G) denote the subgroup of elements x for

which px = 0, and let P_{β}(G) = P ∩ G_{β}. Now the quotient P_{β}(G)/P_{β+1}(G) is a ℤ_{p} vector space, and we call its dimension u_{β}(G). Where no confusion is likely, we will omit the argument G and simply write P_{β}, and so forth.

For any Abelian p-group G, there will be some least ordinal λ(G) such that G_{λ(G)} = G_{λ(G)+1}. This is called the length of G. If G_{λ(G)} = {0}, then we say that G is reduced. Equivalently, G is reduced if and only if it has no divisible subgroup. The height of an element x is the unique β such that x ∈ G_{β}, but x ∉ G_{β+1}. It is conventional to write h(0) = ∞, where ∞ is greater than any ordinal. Similarly, if our group contains a divisible element x, we write h(x) = ∞. In the course of this paper, we will only consider reduced groups. When G is a direct sum of cyclic groups, u_{n}(G) is exactly equal to the number of direct summands of order p^{n+1}. We can now state Ulm’s theorem, but we will not prove it here.

Theorem 2.1 (Ulm). Let G and H be reduced countable Abelian p-groups. Then G ≃ H if and only if for every countable ordinal β we have u_{β}(G) = u_{β}(H).

It is interesting to note that this theorem is not “recursively true.” Lin showed that if two computable groups satisfying the hypotheses of this theorem have identical Ulm invariants, they may not be computably isomorphic [12]. However, it is known that (depending heavily on the particular statement of the theorem), Ulm’s theorem is equivalent to the formal system ATR_{0} [5, 19]. Related work from a constructivist perspective may be found in a paper by Richman [17].

A calculation of the complexity of the isomorphism problem for special classes of computable reduced Abelian p-groups is essentially a computation of the complexity of checking the equality of Ulm invariants. Given some computable ordinal α, we will consider the class of reduced Abelian p-groups of length at most α.

3. Bounds on Isomorphism Problems

When we begin to consider special classes of Abelian p-groups from the perspective described in section 1, it quickly becomes apparent that all examples in Theorems 1.2, 1.3, and 1.4 were especially nice ones. In all of these cases, I(K) was Π_{2}^{0} and E(K) was something worse. It is easy to see that I(K) ≤_{T} E(K), since

I(K) = {a|(a, a) ∈ E(K)}

For instance, if K is the class of reduced Abelian p-groups of length at most ω, I(K) is Π_{3}^{0} complete. Then to show that E(K) is Π_{3}^{0} complete, it is enough to show that E(K) is Π_{3}^{0}, and this is not difficult (the reader interested in the details of this may wish to glance ahead to Proposition 4.1).

However, this doesn’t tell us whether E(K) has high complexity “on its own,” or just by virtue of it being hard to tell whether we have something in K. In a talk in Almaty in the summer of 2002, J. Knight proposed the following definition to clear up the distinction: Definition 3.1. Suppose A ⊆ B. Let Γ be some complexity class (e.g. Π_{3}^{0}), and K a class of computable structures. Then A is Γ within B if and only if there is some R ∈ Γ such that A = R ∩ B

In the example above, saying that E(K) is Π_{3}^{0} within I(K) × I(K) means that there is a Π_{3}^{0} relation R(a, b) such that if a and b are indices for computable reduced Abelian p-groups, then R(a, b) defines the relation “A_{a} has the same Ulm invariants as A_{b}.” In general, it is possible that A is not Γ but that A is Γ within B. Consider for instance the case of a theory which is ℵ_{0}-categorical. If K is the class of models of such a theory, then E(K) is not computable, but E(K) is computable within I(K) × I(K).

We can also define a reducibility “within B”, which will, in turn, give us a notion of completeness. Definition 3.2. Let A, B, and Γ be as in the previous definition.

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

(2) A is Γ complete within B if A is Γ within B and for any S ∈ Γ we have S ≤_{m} A within B.

Essentially, this definition says that A is Γ complete within B if it is Γ within B and there is a function witnessing that it is Γ complete which only calls for questions about things in B. In fact, the questions are only about members of a c.e. subset of B. We will usually write “within K” for “within I(K) × I(K).” All results stated in section 1 remain true when we add “within K” to their statements, and the original proofs still work. In fact, this is intuitively the “right” way to say that the structure of a class is complicated: we say that if we look at some members, it is difficult to tell whether they are isomorphic. It would be unconvincing to argue that the structure of a class is complicated simply because it is difficult to tell whether things are in the class or not.

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 that G and H have the same Ulm invariants up to α. In particular, Barker [3] verified the following. Lemma 3.3. 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 α

□

Work by Lin [13], when viewed from our perspective, shows that for any m ∈ ω, there is a group G in which G_{m} is Σ_{1}^{0} complete. Given this lemma, we can place bounds on the complexity of I(K) and E(K). Lemma 3.4. If K_{α} is the class of reduced Abelian p-groups of length at most α, then I(K_{ω·β+m}) is Π_{2β+1}^{0}.

Proof. The class K_{ω·m+β} may be characterized by the axioms of an Abelian p-group (which are Π_{2}^{0}), together with the condition

∀x[x ∈ G_{ω·β+m} → x = 0]

Since the previous lemma guarantees that this condition is Π_{2β+1}^{0}, we know that I(K_{ω·β+m}) is also Π_{2β+1}^{0}. □

Lemma 3.5. If K_{α} is as in the previous lemma, we use α̂ to denote sup_{ω·γ<α}(2γ + 3).

Then E(K_{α}) is Π0 ; α̂ within K.

Proof. Note that the relation “there are at least n elements of height β which are ℤ_{p}-independent over G_{β+1}” is defined in the following way. To say that x_{i}, …, x_{n} are ℤ_{p}-independent over G_{β+1}, we write the computable Π_{2β+1}^{0} formula

D_{n,β}(x_{1}, …, x_{n}) = ⋀_{b_{1},...b_{n}∈ℤ_{p}}(∑_{i=1}^{n} b_{i}x_{i} ∉ G_{β+1})

Now to write “there are at least n independent elements of height β and order p,” we use the sentence

B_{n,β} = ∃x_{1}, …, x_{n}[(⋀_{i=1}^{n} G_{β}(x_{i})) ∧ (⋀_{i=1}^{n} px_{i} = 0)) ∧ D_{n,β}(\overline{x})]

which is a computable Σ_{2β+2}^{0} sentence. Now we can define isomorphism by

⋀_{{n∈ω \atop β<α}} ⋀ A_{a} ⊧ B_{n,β} ⇔ A_{b} ⊧ B_{n,β}

We write each β < α as β = ω · γ + m, where m ∈ ω. If α̂ is as defined in the statement of the lemma, then this can be expressed by a computable Π0 ; α̂ sentence.

□

4. Completeness for Length ω · m

Proposition 4.1. If K_{ω} is the class of computable Abelian p-groups of length at most ω, then E(K_{ω}) is Π_{3}^{0} complete within K_{ω}.

Proof. We first observe that the set is Π_{3}^{0} within K, by applying the previous lemma. Now let S = ∀e∃ỹ∀z\overline{R}(n, e, y, z) be an arbitrary Π_{3}^{0} set. We can represent S as the set defined by

∀e∃^{<∞}y R(n, e, y)

where ∃^{<∞} is read “there exist at most finitely many.” Consider the Abelian p-group G^{ω} with Ulm sequence

u_{α} = \{ \begin{matrix}ω & if α < ω \\ 0 & otherwise \end{matrix}

We will build a uniformly computable sequence H^{n} of reduced Abelian p - groups of height at most ω such that H^{n} ≃ G^{ω} if and only if n ∈ S. Let G^{ω,∞} denote the direct sum of countably many copies of the smallest divisible Abelian p-group ℤ(p^{∞}), and note that G^{ω,∞} has a computable copy, as a direct sum of copies of a subgroup of ℚ/ℤ. We will denote the element where x occurs in the ith place with zeros elsewhere by (x)_{i}. For instance, G^{ω,∞} set-wise is the collection of all sequences of proper fractions whose denominators are powers of p, and the element (\frac{1}{p})_{2} denotes the element (0, \frac{1}{p}, 0, 0, …).

List the atomic sentences by ϕ_{e}, the pairs of elements in G^{ω,∞} by ξ_{e}, and set D_{−1} = C_{−1} = Y_{e,−1} = X_{e,−1} = X̃_{e,−1} = T_{e,−1} = ∅. We will build groups to meet the following requirements:

P_{e} : There are infinitely many independent elements x ∈ H^{n} of order p and

height exactly e if and only if there are at most finitely many y such that R(n, e, y).

Q_{e} : If ξ_{e} = (a, b) and a, b ∈ H^{n}, then a + b ∈ H^{n}.
Z_{e} : If all parameters occurring in ϕ_{e} are in H^{n}, then exactly one of

ϕ_{e} ∈ D or ¬ϕ_{e} ∈ D.

Roughly speaking, D_{s} will be the diagram of H^{n}, and C_{s} will be its domain. For each e, the set Y_{e,s} will keep track of the y already seen, X_{e,s} the x created of height at least e, and X̃_{e,s} the x which are given greater height, as in P_{e}. The set T_{e,s} will keep track of the heights greater than e already used to put elements from X_{e} in X̃_{e}, so that we do not accidentally make infinitely many elements of height e + 1.

We say that P_{e} requires attention at stage s if there is some y < s such that y ∉ Y_{e,s−1} and R(n, e, y) and there is also some x ∈ X_{e,s−1} \ X̃_{e,s−1}, or if for all y < s we have either y ∈ Y_{e,s−1} or ¬R(n, e, y). We say that Q_{e} requires attention at stage s if ξ_{e} = (a, b) and a, b ∈ C_{s−1} but a + b ∉ C_{s−1}. We say that Z_{e} requires attention at stage s if all parameters that occur in ϕ_{e} are in C_{s−1} and D_{s−1} does not include either ϕ_{e} or ¬ϕ_{e}.

At stage s, to satisfy P_{e}, we will act by first looking for some y < s such that y ∉ Y_{e,s−1} and R(n, e, y). If none is found, the action will be to enumerate a new independent x of height at least e. To do this, find the first k such that (\frac{1}{p})_{k} does not occur in C_{s−1} or in any element of D_{s−1}. Let

C_{s} = C_{s−1} ∪ \{(\frac{1}{p^{j}})_{k}|j = 1, …, (e − 1)\}

and set X_{e,s} = X_{e,s−1} ∪ \{(\frac{1}{p})_{k}\}, X̃_{e,s} = X̃_{e,s−1}, T_{e,s} = T_{e,s−1}, and Y_{e,s} = Y_{e,s−1}. If such a y is found, on the other hand, the action will be to give all existing element of X_{e,s−1} height greater than e. To do this, collect

K = \{k|(\frac{1}{p})_{k} ∈ X_{e,s−1} \ X̃_{e,s−1}\}

and the least positive r ∉ T_{e,s−1}. Note that K is finite. Set

C_{s} = C_{s−1} ∪ ⋃_{k∈K}\{(\frac{1}{p^{j}})_{k}|j = (e, …, e + r + 1)\}

and set T_{e,s} = T_{e,s−1} ∪ \{r\}, X̃_{e,s} = X̃_{e,s−1} ∪ \{(\frac{1}{p})_{k}|k ∈ K\}, X_{e,s} = X_{e,s−1}, and Y_{e,s} = Y_{e,s−1} ∪ {y}.

To satisfy Q_{e} at stage s we will look to see whether the elements of ξ_{e} = (a, b) are in C_{s−1}. If they are both there, set C_{s} = C_{s−1} ∪{a+b}. Otherwise, set C_{s} = C_{s−1}.

To satisfy Z_{e}, we will act at stage s by first looking for the parameters in ϕ_{e} in C_{s−1}. If all of them are there and G^{ω,∞} ⊧ ϕ_{e}, then set D_{s} = D_{s−1} ∪ {ϕ_{e}}. If all of them are there and G^{ω,∞} ⊧ ¬ϕ_{e}, then set D_{s} = D_{s−1} ∪ {¬ϕ_{e}}. If some of the parameters are not in C_{s−1}, we set D_{s} = D_{s−1}.

Now if n ∈ S, for each e we have Q_{e} to guarantee that u_{e}(H^{n}) will be infinite, so H^{n} ≃ G^{ω}. If n ∉ S, there is some e such that Q_{e} guarantees that u_{e}(H^{n}) is finite, so H^{n} ≄ G^{ω}. □

Since this result is perfectly uniform, we can use it for induction. What we actually have established is the following: Proposition 4.2. If S is a set which is Π_{3}^{0} relative to X, then there is a uniformly X-computable sequence of reduced Abelian p-groups (H^{n})_{n∈ω}, each of length at most ω, such that H^{n} ≃ G^{ω} if and only if n ∈ S.

There is a result of Khisamiev [11], which allows us to transfer these X-computable groups down to the computable level.

Proposition 4.3 (Khisamiev). If G is a X′′-computable reduced Abelian p-group, then there is an X-computable reduced Abelian p-group H such that H_{ω} ≃ G and u_{n}(H) = ω for all n ∈ ω. Moreover, from an index for G, we can effectively compute an index for H.

These two results together can be used to establish Proposition 4.4. If K_{ω·m} is the class of computable reduced Abelian p-groups of length at most ω · m, then E(K_{ω·m}) is Π_{2m+1}^{0} complete within K.

Proof. Let S be an arbitrary Π_{2m+1}^{0} set. Since S is Π_{3}^{0} in ∅^{(2m−1)}, we have a uniformly ∅^{(2m+1)}-computable sequence of reduced Abelian p-groups (H^{n})_{n∈ω}, each of length at most ω, such that H^{n} ≃ G^{ω} if and only if n ∈ S. Now we can step each H^{n} down to a lower level using Khisamiev’s result, so that we have a uniformly ∅^{(2n−3)} = ∅^{(2(n−1)−1)}-computable sequence (H^{2,n})_{n∈ω} of reduced Abelian p-groups, each of height ω·2 which again have the property that H^{2,n} has a constantly infinite Ulm sequence if and only if n ∈ S. By induction, we define (H^{i,n})_{n∈ω}, and when we get to (H^{m,n})_{n∈ω}, it will be a uniformly computable sequence of groups of length at most ω · m such that H^{m,n} has constantly infinite Ulm sequence if and only if n ∈ S. □

5. Completeness for Higher Bounds on Length

Giving completeness results for higher levels requires more elaborate machinery. We will prove a more general result using an α-system, in the sense of Ash. These systems are explained in detail, along with several other variants, in the book of Ash and Knight [2]. The “metatheorem” for α-systems was proved in a paper by Ash [1].

Roughly speaking, an α-system describes all possible priority constructions of a given kind, and the metatheorem states that given an “instruction function” which is Δ_{α}^{0}, the system will produce a c.e. set (in our case, the diagram of a group) which incorporates the information given in the instruction function. More formally, we make the following definition: Definition 5.1 (Ash). Let α be a computable ordinal. An α-system is a structure

(L, U, P, ℓ̂, E, (≤_{β})_{β<α})

where L and U are c.e. sets, E is a partial computable function on L (it will eventually enumerate the diagram of the structure we are building), P is a c.e. alternating tree on L and U (that is, a set of strings with letters alternating between L and U) in which all members start with ℓ̂∈ L, and ≤_{β} are uniformly c.e. binary relations on L, where the following properties are satisfied:

(1) ≤_{β} is reflexive and transitive for all β < α

(2) a ≤_{γ} b ⇒ a ≤_{β} b for all β < γ < α

(3) If a ≤_{0} b, then E(a) ⊆ E(b)

(4) If σu ∈ P, where σ ends in ℓ^{0}, and

ℓ^{0} ≤_{β_{0}} ℓ^{1} ≤_{β_{1}} ⋯ ≤_{β_{k−1}} ℓ^{k}

where β_{0} > β_{1} > ⋯ > β_{k}, then there exists some ℓ^{∗} such that σuℓ^{∗} ∈ P and for all i ≤ k, we have ℓ^{i} ≤_{β_{i}} ℓ^{∗}.

If we have such a system, we say that an instruction function for P is a function q from the set of sequences in P of odd length (i.e. those with a last term in L) to U, so that for any σ in the domain of q, σq(σ) ∈ P. The following theorem, due to Ash [1], guarantees that if we have such a function, there is a string which represents “carrying out” the instructions while enumerating a c.e. set. We call an infinite string π = ℓ̂u_{1}ℓ_{1}u_{2}ℓ_{2} … a “run” of (P, q) if it is a path through P with the property that for any initial segment σu we have u = q(σ). The metatheorem also guarantees that there is a run with the property that ⋃_{i∈ω} E(ℓ_{i}) is computably

enumerable. Proposition 5.2 (Ash Metatheorem). If we have an α-system

(L, U, P, ℓ̂, E, (≤_{β})_{β<α})

and if q is a Δ_{α}^{0} instruction function for P, then there is a run π : ω → (L ∪ U) of (P, q) such that ⋃_{i∈ω} E(π(2i)) is c.e. Further, from computable indices for the

components of the system and a Δ_{α}^{0} index for q, we can effectively determine a c.e. index for ⋃_{i∈ω} E(π(2i)).

What this means is that if we can set up an appropriate system, then given some highly undecidable requirements, we can build a computable group to satisfy them. The difficulty (aside from digesting the metatheorem itself) mainly consists of defining the right system. Afterwards, it is no trouble to write out the high-level requirements we want to meet. Using such a system, we will prove the following generalization of Proposition 4.4. Theorem 5.3. Let α be a computable limit ordinal, and let α̂ = sup_{ω·γ<α}(2γ + 3), as

in Proposition 3.5. If K_{α} is the class of reduced Abelian p-groups of length at most α then E(K_{α}) is Π0 ; α̂ complete within K_{α}.

Proof. Let (α_{i})_{i∈ω\{0}} be a sequence cofinal in α (for instance, if α = ω · ω, then α_{i} = ω · i would do, or if α = ω · (β + 1), we could use α_{i} = ω · β + i). Consider the family of groups (Ĝ^{i})_{i∈ω}, each of length α where Ĝ_{0} has uniformly infinite Ulm sequence and

u_{β}(Ĝ^{i}) = \{ \begin{matrix}ω & if β < α_{i} or if β is even \\ 0 & otherwise \end{matrix}

Since the Ulm sequences of these groups are uniformly computable, there is a uniformly computable sequence (G^{i})_{i∈ω} such that G^{i} ≃ Ĝ^{i} for all i, and such that in each of these groups, for any β, the predicate “x has height β” is computable. The proof of this, which is due to Oates, is a modification of an argument of L. Rogers [18], and may be found in Barker’s paper [3].

For any set S ∈ Π0 ; α̂, we will construct a sequence of groups (H^{n})_{n∈ω} such that if n ∈ S then H^{n} ≃ G^{0}, and otherwise, H^{n} ≃ G^{i} for some i ≠ 0. To do this, we will define an α̂-system. Let L be the set of pairs (j, p), where j ∈ ω and p is a finite injective partial function from ω to G^{j}. Let U be the set {0, 1}. By E(j, p), we will mean the first |dom(p)| atomic or negation atomic sentences with parameters from the image of p which are true in G^{j}. Let ℓ̂ = (0, ∅), and P be the set of strings of the form ℓ̂u_{1}ℓ_{1}u_{2}ℓ_{2} … which satisfy the following properties:

(1) u_{i} ∈ U and ℓ_{i} ∈ L

(2) If u_{i} = 1 then u_{i+1} = 1

(3) If ℓ_{i} = (j_{i}, p_{i}), then both the domain and range of p_{i} contain at least the first i members of ω

(4) If ℓ_{i} = (j, p) and u_{i} = 1, then j ≠ 0. Otherwise, j = 0. Further, if u_{i−1} = 1 and ℓ_{i−1} = (j_{i−1}, q), then j = j_{i−1}.

For the ≤_{β} we will modify the standard back-and-forth relations on Abelian p-groups. In general, the standard back-and-forth relations on a class K are characterized as relations on pairs (A, \overline{a}) where A ∈ K and \overline{a} is a finite tuple of A.

Definition 5.4. If \overline{a} ⊆ A and \overline{b} ⊆ B are finite tuples of equal length, then we define the standard back-and-forth relations ≤_{β} as follows:

(1) (A, \overline{a}) ≤_{1} (B, \overline{b}) if and only if for all finitary Σ_{1}^{0} formulas true of \overline{b} in B are

true of \overline{a} in A.

(2) (A, \overline{a}) ≤_{β} (B, \overline{b}) if and only if for any finite \overline{d} ⊂ B and any γ with 1 ≤ γ < β

there is some \overline{c} ⊂ A of equal length such that (B, \overline{b}, \overline{d}) ≤_{γ} (A, \overline{a}, \overline{c}).

This definition extends naturally to tuples of different length as follows: we say that (A, \overline{a}) ≤_{β} (B, \overline{b}) if and only if \overline{a} is no longer than \overline{b} and that for the initial segment \overline{b}′ ⊂ \overline{b} of length equal to that of \overline{a}, we have (A, \overline{a}) ≤_{β} (B, \overline{b}′). Barker [3] gave a useful characterization of these relations in the case of Abelian p-groups A and B, where A = B.

Proposition 5.5 (Barker). If ≤_{β} are the standard back-and-forth relations on reduced Abelian p-groups, and if \overline{a} and \overline{b} are finite subsets of equal length in an Abelian p-group with the height of elements given by h respectively and with equal cardinality, with a function f mapping elements of b̄ to corresponding elements of ā, then the following hold:

(1) \overline{a} ≤_{2·δ} \overline{b} if and only if the two generate isomorphic subgroups and for every b ∈ \overline{b} and a = f(b) we have

h(a) = h(b) < ω · δ or h(b), h(a) ≥ ω · δ

(2) \overline{a} ≤_{2·δ+1} \overline{b} if and only if the two generate isomorphic subgroups and for every b ∈ \overline{b} and a = f(b) we have

(a) In the case that P_{ω·δ+k} is infinite for every k ∈ ω,

h(a) = h(b) < ω · δ

or

h(b) ≥ ω · δ and h(a) ≥ min{h(b), ω · δ + ω}

(b) In the case that P_{ω·δ+k} is infinite and P_{ω·δ+k+1} is finite,

h(a) = h(b) < ω · δ

or

ω · δ ≤ h(b) ≤ h(a) ≤ ω · δ + k

or

h(a) = h(b) > ω · δ + k

(c) In the case that P_{ω·δ} is finite,

h(x) = h(x)

Since in all groups with which we are concerned, P_{ω·δ+k} will be infinite for all δ < α, we will have no need for the more complicated cases. Also, it is helpful to deal with groups which satisfy the stronger condition that they have infinite Ulm invariants at each limit level.

Definition 5.6. Let A, B be countable reduced Abelian p-groups of length at most α such that for any limit ordinal ν < α we have u_{ν}(A) = u_{ν}(B) = ω. Let the height of an element in its respective group be given by h. Let \overline{a}, \overline{b} be finite sequences of equal length from A and B, respectively. Then define (≤_{δ})_{δ<ω_{1}} by the following:

(1) (A, \overline{a}) ≤_{2·δ} (B, \overline{b}) if and only if

(a) The function matching elements of \overline{a} to corresponding elements of \overline{b} extends to an isomorphism f :< \overline{b} >→< \overline{a} >,

(b) for every b ∈ \overline{b} and a = f(b) we have

h(a) = h(b) < ω · δ or h(b), h(a) ≥ ω · δ

and

(c) for all β < ω · δ we have u_{β}(A) = u_{β}(B).

(2) (A, \overline{a}) ≤_{2·δ+1} (B, \overline{b}) if and only if

(a) The function matching respective elements in \overline{a} and \overline{b} extends to an isomorphism f :< \overline{b} >→< \overline{a} >,

(b) for every b ∈ \overline{b} and a = f(b) we have

h(a) = h(b) < ω · δ

or

h(b) ≥ ω · δ and h(a) ≥ min{h(b), ω · δ + ω}
(c) for all β < ω · δ we have u_{β}(A) = u_{β}(B).
(d) for all β ∈ [ω · δ, ω · δ + ω) we have u_{β}(A) ≥ u_{β}(B).

In order to verify that we have an α̂-system, the following lemma will be important.

Lemma 5.7. Suppose (A, \overline{a}) ≤_{β} (B, \overline{b}). Then for any η < β and for any finite sequence \overline{d} ⊆ B there exists a sequence \overline{c} ⊆ A of equal length such that (B, \overline{b}, \overline{d}) ≤_{η} (A, \overline{a}, \overline{c}).

Proof. Suppose that the conditions stated for ≤_{2·δ} hold. Now suppose δ = γ + 1. It suffices to show that for all finite sequences \overline{d} ⊆ B there exists a sequence \overline{c} ⊆ A of equal length such that (B, \overline{b}, \overline{d}) ≤_{2·δ+1} (A, \overline{a}, \overline{c}). We will extend f to \overline{d} one element at a time. Let d ∈ \overline{d}, and suppose that d ∉< \overline{b} > (since if it were in that subgroup, we could simply map it to the corresponding element of < \overline{c} >. Further suppose, without loss of generality, that pd ∈< \overline{b} > and that h(d) ≥ h(d + s) for any s ∈< \overline{b} >. This last condition is often stated “d is proper with respect to < \overline{b} >.” These assumptions are reasonable, since if we need to extend f to an element farther afield, we can go one element at a time and work down to it. From this point, we essentially follow Kaplansky’s proof of Ulm’s theorem [10] to find the appropriate match for d. Use z to denote f(pd). It now suffices to find some c of height h(d) which is proper with respect to < \overline{a} > and such that pc = z.

First suppose that h(z) = h(d) + 1. Now both z and pd must be nonzero. For c we may choose any element of (A)_{h(d)} with pc = z. The height of z tells us that there must exist such an element. We first check that h(c) ≤ h(d), which is easy, since if h(c) > h(d), we would have

h(z) = h(pc) ≥ h(c) + 1 ⪈ h(d) + 1

Finally, it is necessary to show that c is proper with respect to < \overline{a} >. Suppose that c ∈< \overline{a} >. Then c = f(y) for some y ∈< \overline{b} >. Then pd = py and d − y ∉< \overline{b} > to avoid d ∈< \overline{b} >. Further, h(d − y) = h(d), since h(y) = h(d) and d is proper with respect to < \overline{b} >. However,

h(p(x − y)) = h(0) = ∞ ⪈ h(d) + 1

contradicting the maximality of h(px). Thus c ∉< \overline{a} >. Now suppose we have h (c + t) ≥ h(d) + 1 for some r ∈< \overline{a} > with r = f(s). Since c + r ≠ 0 (to avoid the case that c = −r ∈< \overline{a} >), we know that h(p(w + r)) ≥ h(d) + 2, so that h(p(d + s)) ≥ h(d) + 2. Since h(r) ≥ h(d), we also have h(s) ≥ h(d), so h(d + s) = h(d), contradicting the maximality of h(pd).

Suppose that h(z) > h(d) + 1. Now there is some v ∈ (B)_{h(d)+1} such that pd = pv. Then the element d − v is in P_{h(d)}(B), has height h(d), and is thus proper with respect to < \overline{b} >. I make the following claim.

Claim 5.8 (Lemma 13 of [10]). Let the function

r : (< \overline{b} >_{h(d)} ∩p^{−1}(B)_{h(d+2)}) → P_{h(d)}(B)

be defined as follows: For any x ∈ (< \overline{b} >_{h(d)} ∩p^{−1}(B)_{h(d)+2}) there exists some y ∈ (B)_{h(d)+1} such that py = px. Define Y by Y : x ↦ x − y and let Ŷ be the composition of this map with the projection onto P_{h(d)}(B)/P_{h(d)+1}(B). If

F : (< \overline{b} >_{h(d)} ∩p^{−1}(B)_{h(d)+2})/ < \overline{b} >_{h(d)+1}⟶ P_{h(d)}(B)/P_{h(d)+1}(B)

is the map induced by Ŷ on the quotient, then the following are equivalent:

(1) The range of F is not all of P_{h(d)}(B)/P_{h(d)+1}(B).

(2) There exists in P_{h(d)}(B) an element of height h(d) which is proper with respect to < \overline{b} >.

Proof. To show 2 → 1, suppose w ∈ P_{h(d)} has height h(d) and is proper with respect to < \overline{b} >. Then the coset of w is not in the range of F. Otherwise, w = x − y + q for some x ∈< \overline{b} >, some y ∈ (B)_{h(d)}, and some q ∈ P_{h(d)+1}(B). But then h(w − x) > h(d), so w was not proper.

To show the other implication, suppose that w is an element of P_{h(d)}(B) representing a coset not in the range of F. Then h(w) = h(d). Further, w is proper, since if it were not, and if h(s−w) > h(d) witnessed this, we could write s−w = pζ with ζ ∈ (B)_{h(d)}. But then ps = pζ since pw = 0. But then F will map s to the coset of v, giving a contradiction. □

Now since d − v is such an element as is described in the second condition of the claim, we know that the range of F is not all of P_{h(d)}(B)/P_{h(d)+1}(B). Since the vector spaces are finite (and thus finite dimensional), we know that the dimension of (< \overline{b} >_{h(d)} ∩p^{−1}(B)_{h(d)+2})/ < \overline{b} >_{h(d)+1} is less that u_{h(d)}(B). However, since f was height preserving, it maps

(< \overline{b} >_{h(d)} ∩p^{−1}(B)_{h(d)+2})/ < \overline{b} >_{h(d)+1}
↓ onto
(< \overline{a} >_{h(d)} ∩p^{−1}(A)_{h(d)+2})/ < \overline{a} >_{h(d)+1}

Thus the dimension of (< \overline{a} >_{h(d)} ∩p^{−1}(A)_{h(d)+2})/ < \overline{a} >_{h(d)+1} is less than u_{h(d)}(B).

In the case that h(d) < ω · δ + ω, we now know that the dimension of

( < \overline{a} >_{h(d)} ∩ p^{−1} (A)_{h(d)+2})/ < \overline{a} >_{h(d)+1}

is less than u_{h(d)}(A), so there is an element c_{1} in A such that pc_{1} = 0, h(pc_{1}) = h(d), and which is proper with respect to < \overline{a} >. Since h(z) > h(d) + 1, we may write z = pc_{2} where c_{2} ∈ (B)_{h(d)+1}. Now we write c = c_{1} + c_{2} and note that pc = z, that h(c) = h(d), and finally that c is proper with respect to < \overline{a} >.

If h(d) ≥ ω · δ + ω, we need considerably less. In particular, it suffices to find some c such that pc = z, such that c is proper with respect to < \overline{a} >, and such that h(c) = ω · δ + ω. This can be achieved by replacing h(d) with ω · δ + ω in the preceding argument, and noting that since ω · δ is a limit, u_{ω·δ} = ω. This completes the proof for the case (A, \overline{a}) ≤_{2·δ} (B, \overline{b}) with δ a successor.

If δ is a limit ordinal, it suffices to consider some odd successor ordinal 2·η +1 < 2 · δ and to show that for any \overline{d} ∈ B there is some \overline{c} ∈ A such that (B, \overline{b}, \overline{d}) ≤_{2·η+1} (A, \overline{a}, \overline{c}). Then the proof is exactly as in the successor case.

In the case that we start with (A, \overline{a}) ≤_{2·δ+1} (B, \overline{b}) , we need to show that for any \overline{d} ∈ B there is some \overline{c} ∈ A such that (B, \overline{b}, \overline{d}) ≤_{2·δ} (A, \overline{a}, \overline{c}). Now we can follow the proof exactly as in the even successor case, except that we replace ω · δ + ω with ω · δ. □

We now adapt the relations ≤_{β} on pairs (A, ā), (B, b̄) to relations on L.

Definition 5.9. We say that (j_{1}, p_{1}) ≤_{β} (j_{2}, p_{2}) if and only if

(G^{j_{1}}, ran(p_{1})) ≤_{β} (G^{j_{2}}, ran(p_{2}))

We need to verify that (L, U, P, ℓ̂, E, (≤_{β})_{β<α̂}) is an α̂-system. For the necessary effectiveness, notice that we need only consider ≤_{β} on members of L, so only the groups G^{i} are considered. Conditions 1 – 3 are clear, as is the fact that (≤_{β})_{β<α̂} is uniformly c.e. It remains to verify the following:

Lemma 5.10. If σu ∈ P where σ ends in ℓ^{0} and

ℓ^{0} ≤_{β_{0}} ℓ^{1} ≤_{β_{1}} ⋯ ≤_{β_{k−1}} ℓ^{k}

where β_{0} > β_{1} > ⋯ > β_{k}, then there exists some ℓ^{∗} such that σuℓ^{∗} ∈ P and for all i ≤ k, we have ℓ^{i} ≤_{β_{0}} ℓ^{∗}.

Proof. We write ℓ^{i} = (j_{i}, p_{i}). By Lemma 5.7, given ℓ^{k−1} ≤_{β_{k−1}} ℓ^{k} we can produce an ℓ̃^{k−1} = (j̃_{k−1}, p̃_{k−1}) such that p̃ extends p_{k−1} (mapping into the same structure) and ℓ^{k} ≤_{β_{k}} ℓ̃^{k−1}. Similarly, for each i, produce ℓ̃^{i} such that ℓ^{i+1} ≤_{β_{i+1}} ℓ̃^{i}. It will then be the case that for all i, ℓ^{i} ≤_{β_{i}} ℓ̃^{0}. If u = 0 or if 1 occurs somewhere in σ, let ℓ^{∗} = (j̃_{0}, p^{∗}), where p^{∗} extends p̃_{0} and its domain and range each contain the first n constants, where 2n + 1 is the length of σ. Now σuℓ^{∗} ∈ P and for all i, ℓ^{i} ≤_{β_{0}} ℓ^{∗}.

If, on the other hand, u = 1 and 1 does not occur in σ, then we may be sure that j̃_{0} = 0. In this case, find some j^{∗} > 0 such that α_{j^{∗}} > β_{0}. Note that since for each β < α_{j^{∗}} we have u_{β}(G^{j^{∗}}) = u_{β}(G^{0}), it follows that (G^{j^{∗}}, ∅) ≤_{β_{0}+1} (G^{0}, ∅). Thus, by Lemma 5.7, we have some sequence ran(p^{∗}) ⊆ G^{j^{∗}} such that (G^{0}, ran(p̃)) ≤_{β_{0}} (G^{j^{∗}}, ran(p^{∗})) and having length n where 2n + 1 is the length of σ. We define p^{∗} to be the function taking each of an initial sequence of the natural numbers to the corresponding element of that sequence. Then clearly σuℓ^{∗} ∈ P, and for any i, we have ℓ^{i} ≤_{β_{0}} (G^{0}, ran(p̃)) ≤_{β_{0}} (G^{j^{∗}}, ran(p^{∗})) □

Now let S be an arbitrary Π0 ; α̂ set. There is a Δ0 ; α̂ function g(n, s) : ω^{2} → 2 such that for all n, we have n ∈ S if and only if ∀s[g(n, s) = 0], and such that for all n, s ∈ ω, if g(n, s) = 1 then g(n, s + 1) = 1. We define a Δ0 ; α̂ instruction function q_{n} as follows. If σ ∈ P and σ is of length m, then we define q_{n}(σ) = g(n, m).

Now we certainly can find computable indices for all the components of the α̂-system, and we can uniformly find a Δ0 ; α̂ index for each q_{n}, so the Ash metatheorem gives us (uniformly in n), a run π_{n} of (P, q_{n}) and the index for the c.e. set ⋃_{i∈ω} E(π_{n}(2i)). Let H^{n} denote the group whose diagram this is. Note that if n ∈ S,

then q_{n}(m) = 0 for all m, and so H^{n} ≃ G^{0}. Otherwise there is some m̂ such that for all m > m̂, we have q_{n}(m) = 1, and so H^{n} ≃ G^{i} for some i ≠ 0. □

References

[1] C. J. Ash. Labelling systems and r.e. structures. Annals of Pure and Applied Logic, 47:99–119, 1990.

[2] C. J. Ash and J. F. Knight. Computable structures and the hyperarithmetical hierarchy. Elsevier, 2000.

[3] E. Barker. Back and forth relations for reduced Abelian p-groups. Annals of Pure and Applied Logic, 75:223–249, 1995.

[4] W. Calvert. The isomorphism problem for classes of computable fields. preprint, 2003.

[5] H. Friedman, S. Simpson, and R. Smith. Countable algebra and set existence axioms. Annals of Pure and Applied Logic, 25:141–181, 1983.

[6] H. Friedman and L. Stanley. A Borel reducibility theory for classes of countable structures. Journal of Symbolic Logic, 54:894–914, 1989.

[7] S. S. Goncharov and J. F. Knight. Computable structure and non-structure theorems. Algebra and Logic, 41:351–373, 2002.

[8] D. Hirschfeldt, B. Khoussainov, R. Shore, and A. M. Slinko. Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic, 115:71–113, 2002.

[9] G. Hjorth. Classification and orbit equivalence relations. American Mathematical Society, 1999.

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

[11] N. G. Khisamiev. Constructive Abelian p-groups. Siberian Advances in Mathematics, 2:68– 113, 1992.

[12] C. Lin. The effective content of Ulm’s theorem. In Aspects of effective algebra, pages 147–160. Upside Down A Book Company, 1979.

[13] C. Lin. Recursively presented Abelian groups: effective p-group theory I. Journal of Symbolic Logic, 46:617 – 624, 1981.

[14] A. S. Morozov. Functional trees and automorphisms of models. Algebra and Logic, 32:28–38, 1993.

[15] A. Nies. Undecidable fragments of elementary theories. Algebra Universalis, 35:8–33, 1996.

[16] M. O. Rabin and D. Scott. The undecidability of some simple theories. preprint.

[17] F. Richman. The constructive theory of countable Abelian p-groups. Pacific Journal of Mathematics, 45:621 – 624, 1973.

[18] L. Rogers. The structure of p-trees: algebraic systems related to Abelian groups. In Abelian Group Theory: 2nd New Mexico State Conference, pages 57–72. Springer-Verlag, 1976.

[19] S. Simpson. Subsystems of second order arithmetic. Springer-Verlag, 1999.

Department of Mathematics, 255 Hurley Hall, University of Notre Dame, Notre Dame, Indiana, 46556

E-mail address: wcalvert@nd.edu