ALGEBRAIC STRUCTURE AND COMPUTABLE STRUCTURE

A Dissertation

Submitted to the Graduate School of the University of Notre Dame in Partial Fulfillment of the Requirements for the Degree of

Doctor of Philosophy

by

Wesley Crain Calvert, B.A., M.S.

Julia F. Knight, Director

Graduate Program in Mathematics Notre Dame, Indiana March 2005 Abstract

by

Wesley Crain Calvert

The problem often arises, given some class of objects, to classify its members up to isomorphism. The goal of classification theory is to determine whether there is a satisfactory classification, and, if so, to give it. For instance, vector spaces over a fixed field are classified by the dimension. We will consider computable structures, i.e. structures with computable atomic diagram.

We write A_{e} for the computable structure with index e. If K is a class of structures, we write

I(K) = {e|A_{e} ∈ K}

and define the isomorphism problem for K to be

E(K) = {(a, b)|a, b ∈ I(K) and A_{a} ≃ A_{b}}.

For some classes (graphs, linear orders, Abelian p-groups, etc.), it is known that the isomorphism problem is m-complete Σ_{1}^{1}. This thesis describes the addition of new items to this list, and gives the precise complexity for many simpler classes.

Theorem.

1. If K is the set of computable members of either of the following, then E(K) is m-complete Σ_{1}^{1}:

Wesley Crain Calvert

(a) Fields of any fixed characteristic

(b) Real closed ordered fields

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

(a) The class of models of a first-order strongly minimal theory which is not ℵ_{0}-categorical but which has effective elimination of quantifiers and a computable model.

(b) Archimedean real closed ordered fields

3. Let α be a computable limit ordinal, and let α̂ = sup_{ω·γ<α}(2γ + 3). If K_{α} is the class of reduced Abelian p-groups of length at most α then E(K_{α}) is Π0 ; α̂ complete.

4. The isomorphism problem for computable torsion-free Abelian groups is not hyperarithmetical.

We will also describe related collaborative work in which the author is involved. This includes a different notion of classification, as well as preliminary results on the following: the complexity of the index sets of particular structures, a calculation of the complexity of the set of indices for structures with Scott rank α, where α is either ω_{1}^{CK} or ω_{1}^{CK} + 1, and the construction of a structure of Scott rank ω_{1}^{CK} with a strong approximability property.

A. M. D. G. ii

CONTENTS

SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi

CHAPTER 1: INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Basic Techniques for Computable Structures . . . . . . . . . . . . . . 2 1.2 Classification of Computable Structures . . . . . . . . . . . . . . . . . 2

CHAPTER 2: ALGEBRAIC AND ALGORITHMIC PROPERTIES OF ABELIAN GROUPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Notation and Terminology for Abelian p-Groups . . . . . . . . . . . . 5 2.2 The Isomorphism Problem for Ableian p-Groups of Bounded Ulm

Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 Bounds on Isomorphism Problems . . . . . . . . . . . . . . . . 8 2.2.2 Completeness for Length ω · m . . . . . . . . . . . . . . . . . . 10 2.2.3 Completeness for Higher Bounds on Length . . . . . . . . . . 14

2.3 Index Sets for Abelian p-Groups of Small Ulm Length . . . . . . . . . 24 2.4 The Isomorphism Problem for Torsion-Free Abelian Groups . . . . . 26

2.4.1 Finite Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.2 Infinite Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

CHAPTER 3: ALGEBRAIC AND ALGORITHMIC PROPERTIES OF FIELDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1 Degrees of Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 The Isomorphism Problem for Computable Fields . . . . . . . . . . . 42

3.2.1 Borel Completeness for Fields: The Friedman-Stanley Em-

bedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2.2 Computable Construction of the Friedman-Stanley Embedding 50

3.3 The Isomorphism Problem for Computable Real Closed Fields …. 51 3.4 The Isomorphism Problem and Index Sets for Computable Models of

Certain Strongly Minimal Theories . . . . . . . . . . . . . . . . . . . 54 3.5 The Isomorphism Problem for Computable Archimedean Real Closed

Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.6 Index Sets for Computable Archimedean Real Closed Fields . . . . . 63 CHAPTER 4: FINITE STRUCTURES AND COMPARISONS . . . . . . . . 66

4.1 Index Sets of Finite Structures . . . . . . . . . . . . . . . . . . . . . . 66 4.2 Comparing Classes of Structures . . . . . . . . . . . . . . . . . . . . . 67

4.2.1 Basic Properties of the Order ≤_{c} . . . . . . . . . . . . . . . . 69 4.2.2 Applications to Infinite Structures . . . . . . . . . . . . . . . . 71

CHAPTER 5: COMPUTABLE STRUCTURES AND HIGH SCOTT RANK 72 5.1 Scott Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.2 Examples of Structures of High Scott Rank . . . . . . . . . . . . . . . 74 5.3 Index Sets for High Scott Rank . . . . . . . . . . . . . . . . . . . . . 77

BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

SYMBOLS

φ_{e} The eth partial recursive function
W_{e} The eth computably enumerable set
A_{a} The structure whose diagram has characteristic function φ_{a}
I(K) {a |A_{a} ∈ K}
E(K) {(a, b) |a, b ∈ I(K) & A_{a} ≃ A_{b}}

ACKNOWLEDGMENTS

Anyone who has ever undertaken a project of this kind understands immediately the depth of my debt to my thesis advisor, Julia F. Knight. From the day I visited her as a prospective student to the present she has been generous with her time, her ideas, and her experience. It is my great honor to thank her here.

I also thank Valentina Harizanov, Andrei Morozov, and Steven Buechler for serving on my committee. All three have been extremely helpful in the preparation of this thesis. Moreover, I have had very interesting conversations with each of them in which I have learned much of the mathematics that I know.

My other collaborators have also been a great help to me. I have enjoyed working with them, I have learned a lot from them, and I thank them. They are Douglas Cenzer, Desmond Cummins, Sergey Goncharov, Oleg Kudinov, Steffen Lempp, Sara Miller, Vadim Puzarenko, Alexandra Shlapentokh, and Jessica M. Young.

Others have also been helpful with particularly extended or frequent conversations, and with especially helpful ideas. In this vein, I thank Howard Becker, Alexander Berenstein, Peter Cholak, William Dwyer, Jacob Heidenreich, Keith Hubbard, George McNinch, Reed Solomon, Sergei Starchenko, Lou van den Dries, and Rebecca Weber.

The total list of people to whom I am indebted would run to an unmanageable length. However, I would still like to thank the following people for helpful conversations and ideas: John Baldwin, Karen Chandler, Harvey Friedman, Su Gao, Noam Greenberg, Denis Hirschfeldt, Greg Hjorth, Carl Jockusch, David Lippel, Kenneth Manders, Juan Migliore, Joseph Mileti, Benjamin Miller, Joseph Miller, Gerald Sacks, and Richard Shore. I also gladly express here my gratitude to those who taught me these arts in earlier years: Dwayne Fields, Brenda Bratcher, Robert Johnson, Douglas Nelson, and Thomas Bengtson in mathematics; Cleo Harris, Phillip Janes, and Sherri Hunter in writing; and William Yau in scientific research.

During my graduate studies, I have received financial support from NSF grants DMS 9970452, DMS 0139626, DMS 0353748, and NSF bi-national grant DMS 0075899. I gratefully acknowledge the beneficial effect of this support on my training and research, including the present thesis.

Last, but certainly not least, I thank my family and my friends not already mentioned. In particular, but by no means exclusively, the friendship of Julia Bergner, Erica Olson, and Brian Hall has made graduate school not only bearable but often enjoyable. I don’t know how many times I have been saved from disaster or given cause for happiness due to the prayers of my parents and grandparents. The love and friendship of Brandy Barnes has often refreshed me in these past few years, and I thank her for these, as well as for consenting to be my wife.

CHAPTER 1

INTRODUCTION

Computable structure theory, a branch of mathematical logic, seeks to describe relationships between algebraic structure and algorithmic properties. We say that a set S is computabe if there is some algorithm which will decide, in a finite amount of time, for a given n, whether n ∈ S. A structure (e.g. group, vector space) is said to be computable if the set of basic arithmetical facts (technically called the atomic diagram; in a vector space, it is the set of true linear equations and inequations) is computable.

Working with computable structures gives a uniform baseline for using algorithmic properties to “measure” algebraic information. That is, we often find that rich algebraic structure is associated with highly undecidable problems. A book describing computable structure theory from this viewpoint is [5].

In the present chapter, some broad motivation will be given for the work in this thesis, and some notation will be fixed. In Chapters 2 and 3, particular application of these concepts will be made to various classes of Abelian groups and fields. Chapter 4 will analyze finite structures from the perspective of computable structure theory, and develop a general method of comparison of classes of structures with broader application. Chapter 5 will describe work on structures of high Scott rank, a subject that bears importantly on questions of classification.

1.1 Basic Techniques for Computable Structures

We can identify a computable structure with a natural number in the following way: there is an algorithm witnessing that the structure is computable, and each algorithm is associated with a natural number, so we identify the structure with the number of its algorithm, writing A_{e} for the structure with χ_{D(A)} = φ_{e}. Of course, it is possible that e_{1} ≠ e_{2} but A_{e_{1}} ≃ A_{e_{2}} (or even A_{e_{1}} = A_{e_{2}}).

We will also make extensive use of computable infinitary formulas. Since nothing will depend on the choice of ordinal notations, we will in all cases assume that we are working below some (large) computable ordinal and fix some particular set of notations for ordinals below it.

Definition 1.1.1. We define the set of computable Σ_{α} and Π_{α} formulas inductively on α.

1. The Σ_{0} and Π_{0} formulas coincide, and are the finitary quantifier-free formulas.

2. For α > 0, a computable Σ_{α} formula is a disjunction of a c.e. set of formulas φ_{i}, where φ_{i} is of the form ∃xψ_{i}, where ψ_{i} is Π_{β_{i}} for some β_{i} < α, and where for any γ < α there is some i such that β_{i} ≥ γ.

3. For α > 0, a computable Π_{α} formula is a conjunction of a c.e. set of formulas φ_{i}, where φ_{i} is of the form ∀xψ_{i}, where ψ_{i} is Σ_{β_{i}} for some β_{i} < α, and where for any γ < α there is some i such that β_{i} ≥ γ.

1.2 Classification of Computable Structures

In many areas of mathematics the problem arises, given some class of objects, to classify them up to isomorphism. In some cases, we expect that there is some reasonable solution, while in others there seems unlikely to be any satisfactory classification. The goal of classification theory is to determine whether there is a satisfactory classification, and, if so, to give it. For instance, vector spaces over a fixed field are classified up to isomorphism by a single cardinal, the dimension.

Approaches to classification in model theory [66] and set theory [25, 38] have given important progress on these issues. Approaches which focus on computable structures sometimes reveal finer structure. Also, they can show special consequences of the hypothesis that our models be computable.

One way to think about classification of computable structures is through index sets. We can identify a class of computable structures with the set

I(K) = {e|A_{e} ∈ K}

and the equivalence relation of isomorphism becomes the set

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

called the isomorphism problem for K.

If I(K) is hyperarithmetical, which, in practice, is usually a mild assumption, then E(K) is, at worst, Σ_{1}^{1}. That is, it may be described by some statement involving a single existential quantifier ranging over functions and perhaps some quantifiers ranging over numbers. For instance, E(K) may be described by stating that there is a function from A_{a} to A_{b} which is bijective and respects all of the structure. If E(K) has a simpler description — perhaps one involving only number quantifiers — we take this to be a classification. Goncharov and Knight showed that this notion is closely related to other promising notions of classification for computable structures [31]. We may focus on a class of structures, differing in isomorphism type, or we may focus on a single isomorphism type.

For some classes (graphs, linear orders, Boolean algebras, Abelian p-groups, etc.) that are non-classifiable from other points of view, it is known from folklore that the isomorphism problem is m-complete Σ_{1}^{1}. In Chapter 3 of the present work, more items will be added to this list, and at various points the m-degree of the isomorphism problem will be computed for other classes of structures.

One further issue will be relevant: context. Sometimes describing that the structure in question is, for instance, a vector space, is sufficiently difficult to swamp the complexity of a description that distinguishes it from other vector spaces. It is this second description that interests us, since in practice one typically knows what type of structure one will encounter (a vector space, a graph, a group, etc.).

Definition 1.2.1. Suppose A ⊆ B. Let Γ be some complexity class (e.g. Π_{3}^{0}), and let S ⊆ ω. We define complexity within B:

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

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

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

The last part of the 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 sometimes write “within K” for “within I(K)” or “within I(K) × I(K).”

ALGEBRAIC AND ALGORITHMIC PROPERTIES OF ABELIAN GROUPS

Abelian groups are well-travelled terrain in logic. They seem to have a good mix of being sufficiently determined by well-understood information (roughly, order and divisibility of elements) and yet admitting enough variation to be interesting. The case of torsion groups, particularly Abelian p-groups, is especially noteworthy in this respect.

In this chapter, we will calculate the degree of the isomorphism problem for various classes of Abelian p-groups and the degrees of the index sets of many such groups. Finally, we will see the little that is known about the isomorphism problem for torsion-free Abelian groups.

2.1 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 [39]. Generally, notation here will be similar to Kaplansky’s.

It is often helpful to follow S. Feferman [22] 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 a countable 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 a countable 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 countable Abelian p-group G, there will be some least ordinal λ(G) such that G_{λ(G)} = G_{λ(G)+1}. This is 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}, provided that such a β exists. 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.1 (Ulm). Let G and H be countable 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 [46]. In reverse mathematics, there is a theorem stating that (depending heavily on the particular statement of the theorem), Ulm’s theorem is equivalent over a weak base system to a formal system called ATR_{0}, corresponding roughly to the existence of all countable ordinals [24, 67]. Related work from a constructivist perspective may be found in a paper by Richman [62].

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 α.

2.2 The Isomorphism Problem for Ableian p-Groups of Bounded Ulm Length

In view of Ulm’s theorem, and in view of previous work by Barker [9], Nadel [56], and others on the expressibility of Ulm information in L_{ω_{1}ω}, it seems reasonable to try to calculate the complexity of the isomorphism problem for Abelian p-groups. Getting upper bounds on the complexity is not difficult. The completeness results for lengths less than ω^{2} will follow from a theorem of N. Khisamiev, which characterizes which Abelian p-groups of small Ulm length have computable copies. For greater lengths, completeness proofs will use the Ash Metatheorem. The results of this section will appear in [13].

2.2.1 Bounds on Isomorphism Problems

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 [9] verified the following.

Lemma 2.2.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 α

Work by Lin [47], 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 2.2.2. If K_{α} is the class of reduced Abelian p-groups of length at most α, and β > 0 is a computable ordinal, then I(K_{ω·β+m}) is Π_{2β+1}^{0}.

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

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

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

Lemma 2.2.3. If α > 0 is a computable ordinal and 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_{1}, …, x_{n} are ℤ_{p}-independent over G_{β+1}, we write the computable Π_{2β+1} formula

D_{n,β}(x_{1}, …, x_{n}) = ⋀_{b⃗≠0^{b_{1},...bn∈ℤ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} 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 Πα̂ sentence.

2.2.2 Completeness for Length ω · m Proposition 2.2.4. 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 be an arbitrary Π_{3}^{0} set. We can represent S as the set defined by

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

where R is computable and ∃^{<∞} is read “there exist at most finitely many.” Consider the Abelian p-group G^{ω} of length ω and with Ulm sequence u_{α} = ω for all α < ω.

We will build a uniformly computable sequence (H^{n})_{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, set-wise, G^{ω,∞} 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})_{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 2.2.5. 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 N. Khisamiev [41], which allows us to transfer these X-computable groups down to the computable level. Although we only use the weaker corollary here, the result is stated in its full strength because it will be needed in a later section.

Theorem 2.2.6 (N. Khisamiev [41]). For a reduced Abelian p-group A of height ω · M, where M ∈ ω, the following are equivalent:

1. A has an X-computable copy.

2. For each k < N, the relation

R_{A}^{k} = {(r, t)|u_{ωk+r}(A) ≥ t}}

is Σ_{2k+2}^{0}(X), and there is a Δ_{2k+1}^{0}(X) function f_{A}^{k}(r, s) such that for any fixed r, the function f_{A}^{k}(r, s) is nondecreasing and lim_{s} f(r, s) = r^{∗} ≥ r exists, with

u_{ωk+r^{∗}}(A) ≠ 0.

Moreover, we can pass effectively from Σ_{2k+2}^{0}(X) indices for the relations R_{A}^{k} and Δ_{2k+1}^{0}(X) indices for the functions f_{A}^{k} to an X-computable index for an Xcomputable copy of A, and conversely.

Corollary 2.2.7 (N. Khisamiev [41]). 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.

Of course, the theorem would allow many other choices for u_{n}(H), beyond what we need here. We can now combine Proposition 2.2.5 and Corollary 2.2.7 to obtain the following completeness result.

Proposition 2.2.8. If K_{ω·m} is the class of computable reduced Abelian p-groups of length at most ω · m, for some m > 0, then E(K_{ω·m}) is m-complete Π_{2m+1}^{0} 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.

2.2.3 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 [5]. The “Metatheorem” for α-systems was originally proved in a paper by Ash [2]. The version presented here was stated in Ash’s later paper [3].

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 2.2.9 (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 “enumeration” function on L, P is a c.e. “alternating tree” on L and U (that is, a set of strings closed under nonempty initial segments, and 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}} ℓ^{∗}.

In the systems we will use here, E will eventually enumerate the diagram of the structure we are building. 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 [3], 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 2.2.10 (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 and c.e. 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 2.2.8.

Theorem 2.2.11. Let α > 0 be a computable limit ordinal, and let

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

as in Proposition 2.2.3. 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 computable sequence of computable ordinals, cofinal in α (for instance, if α = ω · ω, then α_{i} = ω · i would do, or if α = ω · (β + 1), we could use α_{i} = ω · β + i; in any case, since α is computable, there is such a sequence). 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 [64], and may be found in Barker’s paper [9].

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}. Use n_{p} to denote |dom(p)|. By E(j, p), we will mean the first n_{p} atomic sentences or negations of 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 2.2.12. 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 [9] gave a useful characterization of these relations in the case of Abelian p-groups A and B, where A = B.

Proposition 2.2.13 (Barker [9]). 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. For the proof of the present theorem, we do not actually need the standard back and forth relations, but only relations which satisfy the hypotheses of the Ash Metatheorem, including the back and forth property. In exchange, however, we need a system that considers tuples from different groups.

Definition 2.2.14. 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 — which, when combined with the preservation of atomic formulas, is called the back and forth property — will be important.

Lemma 2.2.15. 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 [39] 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}⟩. Claim 2.2.16 (Lemma 13 of [39]). 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 that Condition 2 implies Condition 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 2.2.17. 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 2.2.18. 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}} ℓ^{∗}.

Proof. We write ℓ^{i} = (j_{i}, p_{i}). By Lemma 2.2.15, 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 2.2.15, we have some sequence ran(p^{∗}) ⊆ G^{j^{∗}} of length k such that (G^{0}, ran(p̃)) ≤_{β_{0}} (G^{j^{∗}}, ran(p^{∗})), where 2k + 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 and c.e. indices for all the components of the α̂-system (these indices do not vary with n), and uniformly in n we can 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.

2.3 Index Sets for Abelian p-Groups of Small Ulm Length

In all cases in the previous section, the completeness side of the result followed from the fact that the group with uniformly infinite Ulm invariant (up to the specified length) had an index set which was complete at the required level. We would like to know how exceptional this one structure is. For instance, might the group G with the same length but with u_{α}(G) = 1 for all α < λ(G) have a simpler index set? The present section will document preliminary work toward this question and other related questions, which will appear in joint work of the present author with Harizanov, Knight, and S. Miller in [16].

In making these calculations for arbitrary Abelian p-groups of specified length, we give up many of the favorable conditions that made possible our use of the Ash Metatheorem, and have to fall back on the Khisamiev characterization. This limits most of our knowledge so far to the groups of length less than ω^{2}.

Proposition 2.3.1. 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.

Actually, the case m = 1 was proved first in joint work of the present author with Cenzer, Harizanov, and Morozov, which is also still at a preliminary stage and will appear in [14].

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

1. If for all n we have u_{ωM+n}(A) < ∞, then I(A) is m-complete Π_{2M+1}^{0} within K.

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

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

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

The previous two results suffice for all Abelian p-groups of length less than ω^{2}. Some limited information is available on groups of greater length. Theorem 2.3.3. Let K be the class of reduced Abelian p-groups. Let A be a member of K with length greater than ωm. Then I(A) is not Σ_{2m+2}^{0}

2.4 The Isomorphism Problem for Torsion-Free Abelian Groups

The class of torsion-free Abelian groups has been important to the study of classification problems in descriptive set theory. Friedman and Stanley proved that the isomorphism relation on finite rank countable torsion-free Abelian groups is Borel (and thus not Borel complete) [25]. They also conjectured that isomorphism for arbitrary countable torsion-free Abelian groups was Borel complete. This conjecture has so far resisted proof, although partial results showing that it is not Borel have been achieved by Hjorth [37].

2.4.1 Finite Rank

In general, even finite rank torsion-free Abelian groups can have quite complicated structure. A group is of rank at least n if and only if there are at least n ℤ-linearly independent elements (so in particular there are groups of finite rank that are not finitely generated; for example, the additive group of rationals has rank 1). Friedman and Stanley showed that the restriction of the isomorphism relation to the set of countable torsion-free Abelian groups of finite rank is not Borel complete [25]. There is a well-known classification for the case of rank 1, but none for any larger rank. Thomas has recently shown that the isomorphism relation on torsionfree Abelian groups of rank n is strictly simpler than on those of rank n + 1 (in the sense of the ordering ≤_{B}; see Definition 4.2.1) [70]. As the Friedman-Stanley result suggests, though, these groups are not altogether intractable. It is helpful to note the following “normal form” result for these groups.

Lemma 2.4.1. If G is a torsion-free Abelian group of rank n < ω, then G ≤ ℚ^{n}.

Proof. There is an embedding of G into G_{ℤ^{∗}} = \{[\frac{1}{a}g]|a ∈ ℤ^{∗}, g ∈ G\}, where the brackets denote classes of the natural equivalence relation. This group has the structure of a (necessarily free) ℚ-module, given by \frac{m}{n}g = [\frac{1}{n}mg]. It is easy to show that G_{ℤ^{∗}} has rank at most n.

There is a known classification, due to Baer [6], of countable rank 1 torsion-free Abelian groups. The account here will generally follow that in the book by Fuchs [27]. Given such a group G, for any prime p, we define a function h_{p} : G → ℕ by setting h_{p}(a) equal to the largest natural number k such that there is some b ∈ G with p^{k}b = a. If no such k exists, we say h_{p}(a) = ∞. Now define the characteristic of a to be the sequence χ_{G}(a) = (h_{p_{1}}(a), h_{p_{2}}(a), …), where (p_{i})_{i∈ω} is a list of all prime numbers. Where no confusion about the group involved is likely, we will write χ(a).

In some torsion-free Abelian groups (think of (ℚ, +)), it is the case that all nonzero elements have the same characteristic. In these groups, we would need to look no further for invariants. However, in some others (for example, (ℤ, +)) the characteristics of the various elements are essentially the same, but not identical. We say that two characteristics are equivalent if they are equal except in a finite number of places and in all places where they differ, both are finite. An equivalence class of characteristics under this relation is called a type. If χ_{G}(a) belongs to a type t, then we say that t_{G}(a) = t, and that a is of type t. A group G in which any two non-zero elements have the same type t is said to be homogeneous, and we say that t(G) = t is the type of G. In particular, we note that any torsion-free Abelian group of rank 1 is homogeneous. Proposition 2.4.2 (Baer [6]). If G and H are torsion-free Abelian groups of rank 1, then G ≃ H if and only if t(G) = t(H).

Proof. Suppose g ∈ G and h ∈ H are both nonzero. Write χ(g) = (m_{1}, m_{2}, m_{3}, …) and χ(h) = (n_{1}, n_{2}, n_{3}, …). Now since, as we have observed, G and H are homogeneous, if they are of the same type, then these two sequences differ at only finitely many places (say i_{1}, …, i_{t}), and both sequences are finite at all of these places. Now there is some g̃ ∈ G such that p_{i_{i}}p_{i_{2}} ⋯ p_{i_{t}} g̃ = g, and there is some h̃ ∈ H such that p_{i_{i}}p_{i_{2}} ⋯ p_{i_{t}} h̃ = h. Clearly χ(g̃) = χ(h̃). Thus, for any rational q, there is some x ∈ G with qg̃ = x if and only if there is some y ∈ H with qh̃ = y. Since such x and y are necessarily unique (because the groups are torsion-free), and since every member of G is a rational multiple of g̃ (respectively with H and h̃), we obtain a bijection which is an isomorphism.

A structure A is said to be computably categorical if for any two computable copies A_{1} ≃ A_{2} ≃ A, there is a computable function witnessing A_{1} ≃ A_{2}. It is well known that if G is a computable finite rank torsion-free Abelian group, then G is computably categorical (see, for instance, [21], [49], [58], [28]). To see this, note that if we have computable finite rank torsion-free Abelian groups G and H, a finite set \overline{g} spanning G, and h : G → H an isomorphism, then we can pass effectively from computable indices for (G, \overline{g}) and (H, h(\overline{g})) to an index for that same isomorphism as a computable function.

It is clear that if K is a class of computably categorical structures, then E(K) must be at worst Σ_{3}^{0} complete within K, since we can express “A_{a} and A_{b} are isomorphic” as “there exists an index for a computable function which is total, bijective, and respects the group operation,” which is clearly a Σ_{3}^{0} condition. Thus, we have a bound on the complexity of the isomorphism problem for finite rank torsion-free Abelian groups. This bound is sharp.

Theorem 2.4.3. If K is the class of torsion-free Abelian groups of any fixed finite rank r, then E(K) is Σ_{3}^{0} complete within K.

Proof. We have already shown that E(K) is Σ_{3}^{0} within K. We can reduce the completeness to a problem on computably enumerable sets. I am grateful to C. Jockusch for suggesting the proof of the following lemma.

Lemma 2.4.4. If S is a Σ_{3}^{0} set, then there exist sequences (A_{n})_{n∈ω} and (B_{n})_{n∈ω}, uniformly computably enumerable, such that A_{n}△B_{n} is finite if and only if n ∈ S.

Proof. It is well known that the set Cof = {e|W_{e} is cofinite} is Σ_{3}^{0} complete (see, for instance, [68]). We could take A_{n} = ω and B_{n} = W_{n} for all n. Then A_{n}△B_{n} is finite just in case ω \ B_{n} = \overline{W_{n}} is finite, which happens exactly when n ∈ Cof.

Now from a computably enumerable set A we will pass effectively to G(A), a computable torsion-free Abelian group of rank 1, in such a way that G(A) ≃ G(B) if and only if A△B is finite. This will be done by making the characteristic of 1 in G(A) (understood as a subgroup of ℚ) equal to the characteristic function of A. If we can do this, then χ_{G(A)}(1) will differ from χ_{G(B)}(1) only in places indexed by members of A△B, and in every place they are both finite.

Given an index for a computably enumerable set A, we can enumerate the set C(A) = \{\frac{1}{p_{e}} |e ∈ A\}, and thus we can also enumerate the subgroup of the rationals generated by C(A). We can pad to pass to a computable copy of this same group, and we call the resulting group G(A). Now (G(A_{n}))_{n∈ω} and (G(B_{n}))_{n∈ω} are uniformly computable sequences of groups such that G(A_{n}) ≃ G(B_{n}) exactly when n ∈ S.

2.4.2 Infinite Rank

The situation for infinite rank groups is somewhat more difficult. An analogue of Lemma 2.4.1 holds in this context, but these groups are not computably categorical. We will follow reasoning essentially due to Hjorth [37] to show that the isomorphism problem for this class is not hyperarithmetical, and so is properly Σ_{1}^{1}. However, there are many properly Σ_{1}^{1} m-degrees which are not Σ_{1}^{1} complete (the study of these degrees dates back at least to [23]; see [29] for more recent work), so it is not yet clear that the isomorphism problem for this class is Σ_{1}^{1} complete.

The argument of Hjorth coded hereditarily countable sets (ranked in a natural way, so as to correspond to the various classes Π_{α}) into a certain kind of labeled graph, and then coded these graphs into the groups. Hjorth’s method of encoding was almost exactly what is given here. The principal differences are in the substitution of the trees from Lemma 2.4.6 for hereditarily countable sets, and in a new proof of injectivity for the encoding, to replace Hjorth’s more difficult proof. In place of hereditarily countable sets, we will use trees. It is not clear yet that all trees can be encoded in these groups. However, a certain class of trees can be encoded.

We will first make the following definition: Definition 2.4.5. Let x be a node in a tree. We define the rank of x, denoted Rk(x) as follows:

1. We say that Rk(x) = 0 if and only if x is terminal.

2. We say that Rk(x) = β > 0 if and only if β is the supremum of the ranks of all successors of x.

The important features of these trees is that each of them is well-founded and has computable rank function (i.e. a computable function assigning to each node x the computable ordinal Rk(x)), that each E_{α}, A_{α}, and L^{α}, as well as the T_{n}’s approximating them, has rank α, and the trees E_{α} (respectively, A_{α} or L_{∞}^{α}) have index sets which are m-complete Σ_{α}^{0} (respectively, Π_{α}^{0}) within the class of trees produced. Proposition 2.4.6. For any computable successor ordinal α, there exist computable trees E_{α}, A_{α}, and for any computable limit ordinal α, there exist computable trees L_{∞}^{α}, and a sequence of trees (L_{k}^{α})_{k∈ω} such that if S is a Π_{α}^{0} set, 1. If α is a successor ordinal, there is a uniformly computable sequence of trees

with computable rank function (T_{n})_{n∈ω} such that for all n,

T_{n} ≃ \{ \begin{matrix}A_{α} & if n ∈ S \\ E_{α} & otherwise \end{matrix}

2. If α is a limit ordinal, there is a uniformly computable sequence of trees (T_{n})_{n∈ω} with computable rank function such that for all n,

T_{n} ≃ \{ \begin{matrix}L_{∞}^{α} & if n ∈ S \\ L_{k}^{α} & for some k otherwise \end{matrix}

The proof given here is due to Hirschfeldt and White [35], although the result was certainly known before them. For instance, the result was known to Ash [4] and to Goncharov, and probably many others. The proof by Hirschfeldt and White is used here because the trees produced are easy to work with. In this proof, we work below some (large) computable ordinal, and identify computable ordinals with their notations.

Proof. We will first describe the trees A_{α}, E_{α}, L_{∞}^{α}, and L_{n}^{α}, and then indicate how to construct T_{n} to reflect some α, some n, and some Π_{α}^{0} predicate. First, take A_{1} to be the tree consisting of a root with a single successor, and E_{1} to be a root with infinitely many successors. We can define the rest of the trees inductively. For α = β + 2, we will define A_{α} to be a root node with infinitely many copies of E_{α+1} attached, and E_{α+2} to be a root node with infinitely many copies of each of E_{α+1} and A_{α+1} attached.

For a limit ordinal α, let (γ_{n})_{n∈ω} be a fundamental sequence for α consisting only of successor ordinals. Since we will define A_{λ+1} and E_{λ+1} only in terms of trees for lower ordinals, there is no danger of circularity. We define L_{∞}^{α} to be a root with a copy of A_{γ_{n}} attached for each n. The tree L_{k}^{α} will be the tree consisting of a root with a copy of A_{γ_{n}} attached for each n ≤ k and a copy of E_{γ_{n}} for each n > k.

Finally, we define the trees for α = λ + 1 where λ is a limit ordinal. The tree A_{α} consists of a root with infinitely many copies of L_{n}^{λ} attached for each n ∈ ω. The tree E_{α} is a root with infinitely many copies of L_{n}^{λ} for each n ∈ ω and infinitely many copies of L_{∞}^{λ} attached.

We will now show that there are sequences (T_{n})_{n∈ω} as claimed. We will proceed by induction on α. For α = 1, suppose S ∈ Π_{α}^{0} is defined by ∀xR(x, n). Then the tree T_{n,0} will consist of a root labeled with 1, with one successor labeled with 0. At later stages, T_{n,s} will consist of T_{n,s−1} with one successor with label 0 to the root added for each stage t < s such that ∃x < tR(x, n). Define T̃_{n} = ⋃_{s∈ω} T_{n,s}, and as usual apply padding to get a structure T_{n} with a computable universe. If n ∈ S, it is clear that we will never add a second successor to the root, and if n ∉ S, we will have seen the counterexample by some stage ŝ and will add more new successors in each stage thereafter.

For α = β + 2, say that S is defined by ∀xR(x, n) where R is a Σ_{β+1}^{0} predicate. Now its complement, \overline{R}(x, n) is a Π_{β+1}^{0} predicate, so by induction, there is a uniformly computable sequence of trees

U_{β+1,x,n} ≃ \{ \begin{matrix}A_{β+1} & if \overline{R}(x, n) \\ E_{β+1} & otherwise \end{matrix}

Note that the notation of β + 1 is merely for bookkeeping and does not effect the isomorphism type of the tree. Now the tree T_{n} will consist of a root node with infinitely many copies of E_{β+1} attached, as well as infinitely many copies of U_{β+1,x,n} for each x ∈ ω. Now if n ∈ S, then for no x will \overline{R}(x, n) hold, so T_{n} consists of a root with infinitely many successors, each isomorphic to E_{β+1}. If n ∉ S, then for some x̂ we have R(x, n), so all of the copies of U_{β+1,x,n} will be isomorphic to A_{β+1}, so T_{n} ≃ E_{α}

For α a limit ordinal, say that S is defined as a computably enumerable conjunction of all R_{k}(n) where R_{k} is a Π_{γ_{k}}^{0} predicate. Recall that γ_{k} was a successor ordinal for all k. We define the predicate

C(m, n) = ⋁_{k≤m} R_{k}(n)

and since this is a Π_{γ_{m}}^{0} predicate, we have, by induction, a sequence of trees

U_{γ_{m},m,n} ≃ \{ \begin{matrix}A_{γ_{m}} & if C(m, n) \\ E_{γ_{m}} & otherwise \end{matrix}

So we define T_{n} to be the tree consisting of a root node with a single copy of U_{γ_{m},m,n} attached for each m ∈ ω. Then if n ∈ S, then all of the R_{k}(n) hold, so all of the C(m, n) hold, and so T_{n} is isomorphic to L_{∞}^{α}. Otherwise, for some m̂, we have Rm̂(n) fails, so for all m > m̂ the predicate C(m, n) also fails, so T_{n} ≃ L_{m̂−1}^{α}.

Finally, we consider α = λ + 1 for some limit ordinal λ. Say S is defined by ∀xR(x, n) where R(x, n) is Σ_{λ}^{0}. Again we use \overline{R} to denote the complement. By induction, there is a uniformly computable sequence of trees

U_{λ,x,n} ≃ \{ \begin{matrix}L_{∞}^{λ} & if \overline{R}(x, n) \\ L_{k}^{λ} & for some k otherwise \end{matrix}

Now we let T_{n} be a tree consisting of a root labeled α+1 with infinitely many copies of L_{m}^{λ} attached for each m ∈ ω, as well as infinitely many copies of U_{λ,x,n} for each x ∈ ω. Again, the isomorphism type of T_{n} is as claimed.

With this result in hand, we can proceed to prove something about the complexity of the isomorphism problem for computable infinite rank torsion-free Abelian groups. Now for each computable ordinal α, and for each Π_{α}^{0} set S, there is a uniformly computable sequence of trees (T_{n})_{n∈ω} with uniformly computable rank functions, which witness that E_{α}, A_{α}, and L_{∞}^{α} have the appropriate index set complexity.

Proposition 2.4.7. If K is the class of computable infinite rank torsion-free Abelian groups, then there is no computable ordinal α such that E(K) is Π_{α}^{0} within K.

Proof. For each of the trees T we have just constructed, we will produce a corresponding computable group G(T). This construction of G(T) is entirely due to Hjorth. Fix a computable ordinal α, and fix computable sequences of primes, all distinct, {p_{β}}_{0≤β≤α}, {q̂_{γ,β}}_{γ<β≤α}, and {p̂_{γ,β}}_{γ<β≤α}. Let S be a Π_{α}^{0} set, and fix (T_{n})_{n∈ω} with their rank functions as in Proposition 2.4.6.

Given a computable tree T, we will now form the labeled graph (V_{T} , E_{T} , f_{T}). We will suppress the dependence on T in the notation unless confusion is likely. Let V consist of all finite sequences ⟨A_{1}, …, A_{m}⟩ such that A_{i} is a node in T and rk(A_{i}) < rk(A_{i+1}). These are the vertices of the graph. Define the edge set, E_{n}, to consist of all unordered pairs {⟨A_{1}, …, A_{m}⟩, ⟨A_{1}, …, A_{m}, A_{m+1}⟩} where both members of the pair are in V. Now we will color both the vertices and the edges of the graph with primes. Define the function f so that

f(⟨A_{1}, …, A_{m}⟩) = p_{β} where rk(A_{m}) = β

and so that

f(\{⟨A_{1}, …, A_{m}⟩, ⟨A_{1}, …, A_{m}, A_{m+1}⟩\}) = \{ \begin{matrix}q̂_{γ,β} & if rk(A_{m}) = β, \\ & rk(A_{m+1}) = γ, \\ & and A_{m+1} is a \\ & successor of A_{m} \\ p̂_{γ,β} & if rk(A_{m}) = β, \\ & rk(A_{m+1}) = γ, \\ & and A_{m+1} is not a \\ & successor of A_{m} \end{matrix}

From this graph, we can now produce a group, G(T). Consider first the set of all finite formal sums ∑_{v∈V^{0}} q_{v}v where V^{0} ⊆ V and q_{v} ∈ ℚ. This is clearly a torsion-free Abelian group of infinite rank, with the obvious addition. We define G(T) to be the subgroup consisting of all elements of the form

∑_{v∈V^{0}} \frac{k_{v}v}{f(v)^{l_{v}}} + ∑_{\{v,w\}∈E^{0}} \frac{n_{\{v,w\}}(v + w)}{f(\{v, w\})^{m_{\{v,w\}}}}

where V^{0} ⊂ V and E^{0} ⊂ E are both finite, k_{v}, n_{{v,w}} ∈ ℤ, and l_{v}, m_{{v,w}} ∈ ℕ.

Roughly, the member of the group which consists of 1v where v is a vertex of the graph will represent that vertex, (v + w) will represent the edge {v, w}, and we can calculate f by measuring the powers of various primes by which elements are divisible. This is the reason for including both p̂ and q̂ in the definition of the graph, so that we can identify when there is an edge, even if it does not represent a successor.

Since all of these constructions are computable from an index for the tree with its rank function, we can produce a uniformly computable sequence of groups G_{n} = G(T_{n}). We will now show that if α is a successor ordinal, G_{n} ≃ G(A_{α}) if and only if n ∈ S, and if α is a limit ordinal, G_{n} ≃ G(L_{α}^{∞}) if and only if n ∈ S. For this purpose, it suffices to establish the following lemma.

Lemma 2.4.8. Let T^{1} and T^{2} be trees. Then T^{1} ≃ T^{2} if and only if G(T^{1}) ≃ G(T^{2}).

Proof. Clearly an isomorphism of trees amounts to a renaming of the nodes of the tree, and thus to a renaming of the elements of vertices of the graph, and induces an isomorphism of labeled graphs. This in turn induces an isomorphism of groups.

The converse, as usual, is more difficult. We will prove it by constructing (not necessarily effectively) a reasonably canonical function π which will recover the tree from the group. In the definition that follows, we will define the term “β-good” just as Hjorth did, to refer roughly to elements in the group which will play the role of nodes in the reconstructed tree, and the function π, which will reconstruct the original tree.

Definition 2.4.9. We define the notion of β-good and the function

π : {x ∈ G(T)|x is β-good for some β} → Labeled T rees

by induction on β.

1. An element g ∈ G(T) is said to be 0-good if and only if it is divisible by all powers of p_{0}. For any 0-good g, we define π(g) to be the labeled tree consisting of one node with a marker r_{g}.

2. An element g is said to be β-good for β > 0 if and only if g is divisible by all powers of p_{β} and for any γ < β and for any γ-good element h, there is h′ ∈ G(T) such that π(h) ≃ π(h′) (as unlabeled trees) and one of the following holds:

(a) (g + h′) is divisible by all powers of q̂_{γ,β}

(b) (g + h′) is divisible by all powers of p̂_{γ,β}

For any β-good g, we define π(g) to be a tree consisting of a node labeled with r_{g} having, for each γ < β and each γ-good element h with (h + g) divisible by all powers of q̂_{γ,β}, a successor which is the root (labeled r_{h}) of the tree π(h). By this we mean that the entire tree π(h) is included, with its root attached at the right place.

The remainder of the section will prove that from the isomorphism type of G(T) we can recover the tree T. This part of the argument will be different from Hjorth’s. The following statement is the correct form of the correspondence between tree nodes and β-good elements which makes the definition worthwhile.

Lemma 2.4.10. An element g ∈ G(T) is β-good if and only if there is

v = ⟨A_{1}, …, A_{m}⟩ ∈ V ⊆ G(T)

and s ∈ ℚ such that g = sv and such that rk(A_{m}) = β.

Proof. For β = 0, this follows clearly from the definitions of the group and of β-good. Suppose that the lemma is established for γ < β. Suppose there are s and v as stated. Then clearly, by the definition of the group, g is divisible by all powers of p_{β}. Also, if γ < β and h is γ-good, then there are s_{1}, v_{1} such that s_{1} ∈ ℚ and v_{1} = ⟨B_{1}, …, B_{m_{1}}⟩ such that h = s_{1}v_{1} and rk(B_{m_{1}}) = γ. Now clearly v_{0} = ⟨A_{1}, … A_{m}, B_{m_{1}}⟩ is a member of V, since γ < β. Note that π(v_{0}) = π(v_{1}). Also, sv + sv_{0} is divisible by all powers of q̂_{γ,β} or p̂_{γ,β} according to whether B_{m+1} is a successor of A_{m}. Thus, g is β-good.

Conversely, suppose g is β-good. Then g is divisible by all powers of p_{β}. But by the definition of the group, the only such elements are the rational multiples of the vertices ending in nodes of rank β.

Thus, given a group isomorphic to G(T), we can recover something like the nodes of the tree purely from the group structure. Now an easy corollary allows us to find the element on which π will tell us the whole tree T. Corollary 2.4.11. Suppose all elements of T, including the root, are of rank at most α. Let x and y be α-good elements of G(T). Then there is a rational number s such that x = sy.

Proof. Apply the lemma to x and y to get x = s_{1}v_{1} and y = s_{2}v_{2}. There is only one vertex ending in a node of rank α — namely the root — so we have v_{1} = v_{2}.

We will now prove that the function π does what was claimed. Lemma 2.4.12. Let x ∈ G(T) be β-good, with x = sv = s⟨A_{1}, …, A_{m}⟩, as in Lemma 2.4.10. Then π(x) is isomorphic to the substructure of T consisting only of nodes which extend A_{m}.

Proof. We proceed by induction on β. For β = 0, the result is obvious. Suppose that the lemma is established for γ < β. Let {B^{i}}_{i∈I} be the successors of A_{m} in T, with rk(B^{i}) = γ_{i} < β, and define w_{i} = ⟨A_{1}, …, A_{m}, B^{i}⟩. Now clearly v + w_{i} is divisible by all powers of q̂_{γ_{i},β}, and so is sv + sw_{i}. By the inductive assumption, π(sw_{i}) is isomorphic to the substructure consisting only of nodes which extend B^{i}, so π(x) contains an isomorphic copy of the tree below A_{m} in T.

To finish, it suffices to show that if r_{h} is a successor of r_{x} in π(x), then h = sw_{i} for some i. From the definition of π, we see that h is γ-good for some γ < β. We apply Lemma 2.4.10 to see h = s_{1}z for s_{1} ∈ ℚ and z ∈ V. Since (h + x) is divisible by all powers of q̂_{γ,β}, we know that {v, z} ∈ E and that if z =< C_{1}, …, C_{m_{1}} > then m_{1} = m + 1, that for all i ≤ m we have C_{i} = A_{i}, and that C_{m_{1}} is a successor of A_{m} in T. Let C_{m_{1}} = Bî. Then h = s_{1}w_{i}, as desired.

Now it is clear that taking β = α in this lemma, we have established Lemma 2.4.8.

Since we can complete this construction for any computable ordinal α, to show that E(K) is not Π_{α}^{0} in K, it suffices to show that for some α_{1} > α we can compute any Π_{α_{1}}^{0} set from E(K).

If the Friedman–Stanley conjecture is true, it seems likely that if K is the class of torsion-free Abelian groups of infinite rank, then E(K) is m-complete Σ_{1}^{1}. If this completeness statement is true, then there must be a torsion-free Abelian group of non-computable Scott rank. Since for each computable ordinal α there is a computable L_{ω_{1}ω} sentence which is true exactly of torsion-free Abelian groups of Scott rank at least α, we may conclude from Proposition 2.4.7, by Barwise compactness, that there is such a group with non-computable Scott rank. This fact may be thus be taken as evidence in favor of the Friedman-Stanley conjecture.

ALGEBRAIC AND ALGORITHMIC PROPERTIES OF FIELDS

Some of the first work in computable model theory centered on computable fields. Notable advances were the work of Frölich and Sheperdson [26], Rabin [60] and Metakides and Nerode [52]. In more recent years, much of the work in computable structure theory has been devoted to developing general theory, and the easier examples with which to do this have tended to be graphs, linear orderings, Boolean algebras, vector spaces, and Abelian groups.

Today, model theory proper — as opposed to computable model theory — studies various classes of fields as some of its most productive examples (see, for instance, [34]), largely due to important applications of model theory to algebraic geometry and number theory. At the same time, algebraic geometers have taken an increasing interest in algorithmic aspects of the subject (see, for instance, [19]). Some recent work in the computable model theory of rings and fields — centered mainly on the existence of algorithms for ideal membership, splitting, and similar properties — is surveyed in a paper of Stoltenberg-Hansen and Tucker [69].

In this chapter, we will apply some of the techniques of the previous section to certain classes of fields. We will demonstrate the existence of fields of arbitrary Turing degree, and of fields with no Turing degree. We will show that the isomorphism problem for arbitrary fields of any fixed characteristic, and for real closed fields, is Σ_{1}^{1} complete. We will also calculate the complexity of the isomorphism problem for Archimedean real closed fields or the models of each of a certain class of strongly minimal theories, and the corresponding index sets.

The results of Section 3.1 are a part of a joint paper of the present author with Harizanov and Shlapentokh [17]. Those of Sections 3.3, and 3.5 are reported in [12].

3.1 Degrees of Fields

The isomorphism type of a field has something to say about what sorts of algorithmic structure it will admit. That is, the isomorphism type of a field A determines a set of Turing degrees DI(A) in which A has copies.

One straightforward way in which to associate computability-theoretic information with algebraic information is to find a Turing degree that corresponds in some natural way to the isomorphism type of a given structure. A first attempt at this, suggested by Jochusch and explored by Richter [63], was to say that the degree of A is the least Turing degree in which A has some copy. However, Richter showed that not every structure has a degree in this sense. Theorem 3.1.1 (Richter [63]). For any Turing degree d, there is an Abelian torsion group of degree d. Moreover, there is an Abelian torsion group with no degree.

A second approach, also suggested by Jockusch, is the so-called jump degree of a structure. For the αth jump degree of a structure A, we take the least element among the αth jumps of degrees of copies of A. Again, it is not certain that a given structure will have αth jump degree. Theorem 3.1.2 (Oates [59]). For any α ≤ ω, there is an Abelian p-group G^{α} such that G^{α} has αth jump degree, but does not have βth jump degree for any β < α.

As we have seen, then, there are certain deficiencies to associating a particular degree to a structure. It is often more informative to associate a set of degrees with a structure. For a fixed countable structure A, we write DI(A) for the set of Turing degrees d such that A has a copy of degree d. Knight showed that in all cases except the well-understood “trivial” case, this set must be closed upwards [42]. Richter’s results stated above indicate that for some A, the set DI(A) does not have a least element. A general survey of properties of DI(A) may be found in a paper by Knight [43]. In the present paper, examples will be given of particular kinds of structures A in which DI(A) has prescribed properties.

After proving the results of this section, the present author became aware of other work by Harizanov and Shlapentokh which proves the same results, in addition to some others. The united project will be reported in [17].

Theorem 3.1.3. Let S ⊆ ω. Then there exists a field A_{S} such that DI(A_{S}) is exactly the set of degrees that compute enumerations of S.

Proof. The proof will generally follow the method of Richter [63]. Let C_{n} designate the nth cyclotomic polynomial, and let ζ_{n} be a computable sequence such that ζ_{n} is a primitive p_{n}th root of unity, where p_{n} is the nth prime. Let A be the field ℚ({ζ_{n}|n ∈ S}). Clearly, any copy of A_{S} computes an enumeration of S by simply looking to see which of the relevant roots appears.

Lemma 3.1.4. Let U ⊆ ω, such that S is c.e. in U. Then there is F ≃ A_{S} such that F ≤_{T} U.

Proof. Let A^{∗} be a computable prime algebraically closed field of characteristic 0. The set {ζ_{n}|n ∈ S} is a U-c.e. subset of A^{∗}, and so is the least subfield of A^{∗} containing this set. We can use padding to produce a computable copy of this structure.

Lemma 3.1.5. The field A_{S} is not trivial.

Proof. The result is obvious, but a proof is included here for completeness. Let U be a finite subset of A_{S}. If it is empty, take f : ω → ω to be the permutation which exchanges 1_{A_{S}} and 0_{A_{S}} and fixes all other elements. Otherwise, consider some x ∈ U. Now U can contain only finitely many of x, x + x, x + x + x, …, so let x̃ be the first such element which is not contained in U. Let f be the permutation of ω which exchanges x̃ + x and x̃ and fixes all other elements. In either case, f is a permutation fixing all elements of U which is not an automorphism of A_{S}.

Corollary 3.1.6. For any set S ⊆ ω, there is a field A_{S}^{!} such that

DI(A_{S}^{!}) = {d|S ≤_{T} d}.

Proof. Let A_{S}^{!} = A_{S⊕S̄}. The result follows.

3.2 The Isomorphism Problem for Computable Fields

Intuition and experience tell us that the class of computable fields is quite complicated, perhaps so much that no classification could ever capture it. Previous work by Kudinov focused on existence of a computable “Friedberg enumeration”.

Definition 3.2.1. A Friedberg enumeration of K up to isomorphism is a list of numbers, each of which is an index for a member of K, such that each isomorphism type from K occurs exactly once in the list. The enumeration is said to be computable (or hyperarithmetical), when this list is.

Goncharov and Knight had asked whether there was a computable Friedberg enumeration up to isomorphism of computable fields of fixed characteristic. Kudinov announced the following result:

Theorem 3.2.2 (Kudinov). There is no computable Friedberg enumeration of the computable fields of characteristic 0.

Knowing the complexity of the isomorphism problem for a class can tell us about the existence of Friedberg enumerations. The following is in [31]:

Proposition 3.2.3 (Goncharov-Knight). If I(K) is hyperarithmetical and there is a hyperarithmetical Friedberg enumeration of computable members of K up to isomorphism, then E(K) is hyperarithmetical.

The idea of the proof is that if E(K) is Σ_{1}^{1} (which it must always be) and there is a hyperarithmetical Friedberg enumeration of K up to isomorphism, then E(K) is also Π_{1}^{1}.

We can prove the following:

Theorem 3.2.4. When K is the class of computable fields of some fixed characteristic, E(K) is m-complete Σ_{1}^{1} within K.

Then we have the following strengthening of Kudinov’s result:

Corollary 3.2.5. For any p, prime or zero, there is no hyperarithmetical Friedberg enumeration up to isomorphism of computable fields of characteristic p.

The proof of Theorem 3.2.4 is by encoding graphs in fields. Friedman and Stanley [25] gave a method for doing this in a way which is well-defined and one-to-one on isomorphism types. What is needed beyond this is to show that if we start with a computable graph, we get a computable field. It is well known that the isomorphism problem for undirected graphs is Σ_{1}^{1} complete (see [54], [57], or [61] for a proof.

Actually, Theorem 3.3.1 implies the characteristic 0 case of Theorem 3.2.4. This proof is certainly simpler. However, the proof in this section — including some points not fully described here — covers positive characteristic and stresses the relationship with Borel complexity. Also, it offers an opportunity to simplify, at least for characteristic 0, the difficult argument of the Friedman–Stanley paper.

3.2.1 Borel Completeness for Fields: The Friedman-Stanley Embedding

In 1989, Friedman and Stanley [25] showed that the class of countable fields of characteristic 0 is Borel complete, the maximal level of complexity in their sense. They proved this by constructing a Borel embedding from graphs into fields (a Borel embedding is a Borel measurable function which is well-defined and injective on isomorphism types).

Friedman and Stanley assume that they are given a graph whose connectedness relation is R. From this they construct a field. We will use \overline{F} to indicate the algebraic closure of F, and (S) for the smallest field containing S.

Consider {e_{i}}_{i∈ω}, algebraically independent over ℚ. Let F_{0} be the composite of all of the \overline{(ℚ(e_{i}))}, and define the extension

L(R) = F_{0}(\{\sqrt{e_{i} + e_{j}}|iRj\})

To deal with positive characteristic, we could replace ℚ with 𝔽_{p} and the square root with some qth root where q is relatively prime to p, both in this construction and throughout the following argument. This function L : Graphs → F ields is both a Borel measurable function under the usual product topology [36], and well-defined on isomorphism classes. The difficulty is in showing that Proposition 3.2.6. L is injective on isomorphism classes.

Proof. In particular, it is difficult to show that \sqrt{e_{m} + e_{n}} cannot be expressed as a rational function of the various e_{i} and \sqrt{e_{j} + e_{k}} where \{j, k\} ≠ \{m, n\}. I will give here only the argument for characteristic 0, and will refer the reader to Shapiro’s paper [65] for the more general argument. The main difficulties appear when we consider only the composite of \overline{(ℚ(e_{i}))} and \overline{(ℚ(e_{j}))} (where i ≠ j), and ask whether it contains \sqrt{e_{i} + e_{j}}. I am grateful to W. Dwyer for the proof of the following lemma. A different proof is given in the paper by Friedman and Stanley [25], and there are others still by Abhyankar [1] and Shapiro [65]. In any case, proving the following lemma in positive characteristic is quite difficult.

Lemma 3.2.7. \sqrt{e_{i} + e_{j}} ∉ (\overline{ℚ(e_{i})} ∪ \overline{ℚ(e_{j})}), where i ≠ j.

Proof. A polynomial p of degree n in \overline{(ℚ(e_{i}))} gives a branched n-sheeted covering where the fiber over any point a in \overline{(ℚ(e_{i}))} is the set of roots of p = a, and branch points represent the multiple roots (a Riemann surface). A continuous function to find the roots of the polynomial may be defined on this covering with branch points deleted, but not in any neighborhood including the branch points themselves. We first consider the possibility

\sqrt{e_{i} + e_{j}} = ∑_{k=1}^{n} a_{k}b_{k}

where a_{k} is algebraic over ℚ(e_{i}), and b_{k} is algebraic over ℚ(e_{j}). That is, ∑_{k=1}^{n} a_{k}b_{k} gives one of the square roots.

Now for simplicity we can say that there is a single polynomial p_{i}(Z) over ℚ(e_{i}) of which all the a_{k} are roots, and similarly one p_{j} over ℚ(e_{j}) of which all the b_{k} are roots. We can view the composite field (\overline{ℚ(e_{i})} ∪ \overline{ℚ(e_{j})}) as \overline{ℚ(e_{i})} × \overline{ℚ(e_{j})}. Since p_{i} and p_{j} will each have only finitely many multiple roots and at most finitely many points at which the coefficients are not defined, we can define continuous functions giving a_{k} and b_{k} on the relevant covering spaces of

\overline{ℚ(e_{i})} \ \{these finitely many “bad points” of p_{i}, say b_{t}\}

and

\overline{ℚ(e_{t})} \ \{finitely many “bad points” of p_{j}, say f_{t}\}

Thus the expression ∑_{k=1}^{n} a_{k}b_{k} can be continuously defined on the relevant covering space of \overline{ℚ(e_{i})} \ \{b_{t}\} × \overline{ℚ(e_{j})} \ \{f_{t}\}). We can view this as a plane with finitely many vertical and horizontal lines deleted. Since the multiple roots of Z^{2} = e_{i}+e_{j} lie along the antidiagonal e_{i} + e_{j} = 0, there is clearly a neighborhood in which we can define ∑_{k=1}^{n} a_{k}b_{k} as a continuous function, but which contains points of the antidiagonal, so we cannot define \sqrt{e_{i} + e_{j}} as a continuous function. Thus the two cannot be equal. To make the difference more transparent, we could say that anywhere on this neighborhood we stay on the same branch of the right-hand side, but move from one branch to another on the left-hand side.

In the more general case that

\sqrt{e_{i} + e_{j}} = \frac{∑_{k=1}^{n} a_{k}b_{k}}{∑_{k=1}^{n} c_{k}d_{k}}

we could simply write

(\sqrt{e_{i} + e_{j}})(∑_{k=1}^{n} c_{k}d_{k}) = ∑_{k=1}^{n} a_{k}b_{k}

and again the right-hand side can be defined continuously where the left-hand side cannot.

There does not seem to be a way to modify this proof to cover the positive characteristic case. There is no apparent topology to replace the metric topology on the affine space, which we used here in declaring functions continuous or not. Also, while we could talk about the number of values of the “root function” and the right-hand-side “function,” there are points in the proof at which it is not obvious that values will not collapse.

If we simply add more e_{i}, then more dimensions are added to the picture, but nothing really changes, since the diagonal for \sqrt{e_{i} + e_{j}} is still in the same plane, and we can still find a neighborhood containing some point of it which contains no point of any line parallel to an axis. The next real problem comes up when we allow some square roots to be added. To simplify the task of visualization, and also to simplify the notation necessary, we will restrict the geometrical argument to a space whose F_{0}-dimension is the least possible to account for all e_{i} used in the expression. This allows us to refer to codimension, allowing an economical way to describe the higher-dimensional generalizations of the fact that lines intersect in points, planes intersect in lines, and so forth. Lemma 3.2.8. Let F_{0} be as above. Then

\sqrt{e_{i} + e_{j}} ∉ F_{0}(\sqrt{e_{j} + e_{k}})

where i, j, and k are distinct.

Proof. Suppose not. First we will suppose again the simpler case where

\sqrt{e_{i} + e_{j}} = ∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}

where each a_{st} is algebraic over a single e_{q} or is f_{st}\sqrt{e_{j} + e_{k}} for some f_{st} ∈ F_{0}. Since there are only a finite number of such e_{q} involved in the expression, let us collect, as before, polynomials p_{q}, one to account for all a_{st} algebraic over a single e_{q}. The multiple roots of p_{q} may be collected, as before, as {b_{qγ}}. Those used in the composition of f_{st} may be collected as {d_{stγ}}. The multiple roots corresponding to \sqrt{e_{i} + e_{j}} still form the diagonal (now a hyperplane, i.e. an algebraic surface of codimension 1) e_{i}+e_{j} = 0. Let x̂ be a point of e_{i}+e_{j} = 0, and let N be a ball around it of positive radius. Use M_{δ} to denote the (finitely many) hyperplanes X_{q} = b_{qγ}, e_{t} = d_{stγ}, and e_{j} + e_{k} = 0. Now M_{δ}^{c} (the complement of M_{δ}) is open, so N ∩ (⋂_{δ} M_{δ}) is a neighborhood containing a point of e_{i} + e_{j} = 0 and no point of any M_{δ}. Thus, there is a neighborhood in which we stay on a single branch of the right-hand side of the supposed equation, but cross a branch point of the left hand side.

Just as before, the extension to the more general case,

\sqrt{e_{i} + e_{j}} = \frac{∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}}{∑_{s=1}^{n} ∏_{t=1}^{m_{s}} b_{st}}

is quite easy. We clear the denominator and still have regions which are entirely fine for the right side of the equation but that the left finds unmanageable.

Alternately, we could consider a homomorphism

F_{0}(\sqrt{e_{j} + e_{k}}) → F_{0}(\sqrt{e_{j} + e_{k}})

which sends e_{k} ↦ 0 but which is the identity on ℚ∪{e_{ℓ}}_{ℓ≠k}. If the lemma failed, this homomorphism would show that \sqrt{e_{i} + e_{j}} ∈ F_{0}, contrary to the previous lemma. A similar alternate proof is possible for the following lemma.

Similarly, one can establish Lemma 3.2.9. Let F_{0} be as above. Then \sqrt{e_{i} + e_{j}} ∉ F_{0}(\{\sqrt{e_{m} + e_{n}}|\{m, n\} ≠ \{i, j\}\}).

Proof. Suppose that the lemma fails. Then we suppose

\sqrt{e_{i} + e_{j}} = ∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}

where each a_{st} is algebraic over a single e_{q} or is f_{st}\sqrt{e_{n} + e_{m}} for some f_{st} ∈ F_{0} and some {m, n} ≠ {i, j}. Acting just as before, we denote by p_{q} the polynomial accounting for all a_{st} which are roots of some polynomial over e_{q}. The left-hand side of the equation still gives us multiple roots along the hyperplane e_{i} + e_{j} = 0, the roots of the p_{q} still form hyperplanes parallel to the axes, just as before. The only difference from the previous case is that there are more hyperplanes of diagonal type (e_{m} + e_{n} = 0), but there is still a neighborhood in which the right side of the equation works, and the left does not. By this point, the usual extension to the more general form of a member of

F_{0}(\{\sqrt{e_{m} + e_{n}}|\{m, n\} ≠ \{i, j\}\})

is obvious.

We will need an additional fact. If two fields of this kind are isomorphic, the isomorphism will move e_{i} to something interalgebraic with some e_{j}, since they are the elements whose algebraic closure is included. The change of e_{i} to e_{j} is clearly tolerable, since it merely corresponds to a permutation of the names of the vertices of a graph. However, we need to verify that the isomorphism does not foul up information on the connectedness relation.

Lemma 3.2.10. Let A ∼ B if and only if \overline{ℚ(A)} = \overline{ℚ(B)}. If e ∼ e_{i} and c ∼ e_{j} then \sqrt{e + c} ∉ (\overline{ℚ(e_{i})} ∪ \overline{ℚ(e_{j})}).

Proof. The proof of this lemma is trivial. If \sqrt{e + c} ∈ (\overline{ℚ(e_{i})} ∪ \overline{ℚ(e_{j})}), then it is also in the (exactly equal) set (\overline{ℚ(e)}∪\overline{ℚ(c)}), in contradiction to the previous lemma.

Lemma 3.2.11. If c_{i} ∼ e_{i} for all i, then

\sqrt{c_{i} + c_{j}} ∉ F_{0}(\{\sqrt{e_{m} + e_{n}}|\{m, n\} ≠ \{i, j\}\})

Proof. This proof is an almost equally obvious extension of earlier results. Let F_{1} denote the composite field of all the \overline{ℚ(c_{i})}. The field

F_{0}(\{\sqrt{e_{m} + e_{n}}|\{m, n\} ≠ \{i, j\}\})

is equal to the field

F_{1}(\{\sqrt{e_{m} + e_{n}}|\{m, n\} ≠ \{i, j\}\})

We should note that each e_{i} is the root of some polynomial over c_{i}. Now suppose

\sqrt{c_{i} + c_{j}} = ∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}

where each a_{st} is algebraic over a single c_{i} or is f_{st}\sqrt{e_{m} + e_{n}} for some f_{st} ∈ F_{1} and some {m, n} ≠ {i, j}. Let p_{q} again denote the polynomial accounting for all a_{st} algebraic over c_{q}. The left-hand side still gives the same diagonal hyperplane c_{i} + c_{j} = 0. On the right-hand side, we have a finite union of hyperplanes parallel to the axes (the multiple roots of p_{q}), and also some more exotic hypersurfaces. These hypersurfaces are those of the form e_{m} + e_{n} = 0. However, these are not equal to c_{i} + c_{j} = 0, so for each such hypersurface P (of only finitely many) there is some neighborhood containing a point of c_{i} + c_{j} = 0 but no point of P. Thus, we can still find the necessary neighborhood in which the right-hand side of the equation is continuous and the left-hand side is not. The more general element works as always.

We can now prove Proposition 3.2.6. Suppose that R and S are two graphs, and that L(R) ≃ L(S). Now by this isomorphism, each e_{i} ∈ L(R) is mapped to some c_{i} ∼ e_{j} ∈ L(S). Certainly if nRm then \sqrt{e_{n} + e_{m}} ∈ L(R) and thus \sqrt{c_{n} + c_{m}} ∈ L(S). By the last lemma, if c_{n} ∼ e_{p} and c_{M} ∼ e_{q}, the last statement implies that \sqrt{e_{p} + e_{q}} ∈ L(S), so by the previous lemma pSq (since \sqrt{e_{p} + e_{q}} ∉ F_{0}(\{\sqrt{e_{m} + e_{n}}|\{m, n\} ≠ \{i, j\}\}) (that is, e_{p} + e_{q} only had a square root if we put one in to account for a connection of p and q in S). Similarly, we can argue that if nSm, then the corresponding elements are connected in R. Thus R ≃ S.

3.2.2 Computable Construction of the Friedman-Stanley Embedding

It will turn out that a similar embedding produces computable fields from computable graphs, amounting to a reduction E(Graphs) ≤_{1} E(Fields). This will complete the proof. The only real modification necessary is to guarantee that if we start with a computable graph, we end up with a computable field.

We should note that since the class of fields of given characteristic has ∏_{2}^{0} axioms (stating that it is a commutative ring, plus the condition that for any element there exists a multiplicative inverse), I(K) is ∏_{2}^{0}. Given a computable directed graph with connectedness relation R, consider {e_{i}}_{i∈ω}, algebraically independent over ℚ. Let G_{0} be a computable field isomorphic to the composite of all of the \overline{ℚ(e_{i})}, and let M(R) be the extension G_{0}(\{\sqrt{e_{i} + e_{j}}|iRj\}). It remains to verify

Proposition 3.2.12. Given a graph R we get a field F (G) computable relative to G.

Proof. Consider the language of fields, plus countably many constants e_{i}, with the theory of algebraically closed fields of characteristic 0 and the sentences stating that the e_{i} are algebraically independent. This theory is complete and decidable (since the theory of algebraically closed fields alone proves quantifier elimination), and so it has a computable model. Call this computable model G.

Once we have G, there is a c.e. G_{0}^{∗} ⊆ G which contains exactly those members of G which are algebraic over a single e_{i}. Further, there is a c.e. R^{∗} ⊆ G consisting of exactly \{\sqrt{e_{i} + e_{j}}|iRj\}. With these two sets, we can enumerate the elements of the smallest subfield containing G_{0}^{∗} ∪ R^{∗}, and we will call this F^{∗} ⊆ G. Note that F^{∗} has c.e. universe. Let idx(R) be the index of the function with which we enumerate D(F^{∗}), and note that we can find it effectively in a uniform way from an index for D(R). Now by padding, we can replace the c.e. field F^{∗} by a field whose universe is computable. It is also clear that an index for the function with which we enumerate this field is effectively obtained from idx(R) in a uniform way. This completes the proof both of the proposition and of Theorem 3.2.4 in the case of characteristic zero.

3.3 The Isomorphism Problem for Computable Real Closed Fields

Arbitrary fields, then, are quite complicated. On the other hand, many natural classes of fields are more tangible, and might give better hope of classification. K. Manders suggested the example of real closed fields, whose model theory is reasonably well-behaved, but which is unstable. Recall that a real closed ordered field is an ordered field satisfying the additional condition that each odd-degree polynomial has a root. When we add positive infinite elements we have a great deal of freedom in the structure of the field.

Theorem 3.3.1. If K is the class of real closed ordered fields, then E(K) is Σ_{1}^{1} complete within K.

Proof. We will say that a ⪯ b exactly when a ≤ b^{n} for some n ∈ ω. We say that a ≈ b (a is comparable to b) if a ⪯ b and b ⪯ a. Notice that the ∼-classes of positive elements form intervals. We will write a ≺ b if a ⪯ b but it is not the case that b ⪯ a. The proof will depend on realizing an arbitrary computable linear order as the order type of the comparability classes of infinite elements.

Lemma 3.3.2. Given a computable linear order L, there is a computable structure R(L)^{∗} = (R̄, +, ·, 0, 1, ≤, {e_{i}}_{i∈L}), an expansion of a real closed field, in which e_{i} ⪯ e_{j} if and only if i ≤ j. Moreover, an index for R(L)^{∗} is computable from an index for L.

Consider the language of ordered fields, plus infinitely many constants e_{i}, with the theory of real closed fields, and the sentences for each i stating that e_{i} is greater than any polynomial in {e_{j}|j <_{L} i}, and that all are greater than polynomials in 1. This is a complete, decidable theory, and thus has a computable model G. There is a c.e. subset R̃ ⊆ G containing exactly the elements algebraic over {e_{i}}_{i∈ω}. From an index for L, we can effectively find an index i(L) for the function enumerating R̃. Again we can pad to find an isomorphic structure R(L)^{∗} with computable universe, as claimed. Let R(L) denote the reduct of R(L)^{∗} to the language of ordered fields.

We have encoded arbitrary linear orders into real closed fields, and all that remains is to make sure that this operation is well-defined and injective on isomorphism types. The well-definedness is clear, since an isomorphism of linear orders would just amount to a permutation of the labels for the e_{j}. It is also clear that if h is an isomorphism h : R(L_{1}) → R(L_{2}), then for a, b ∈ R(L_{1}), a ⪯ b if and only if h(a) ⪯ h(b), but it requires some verification to see that for a in the comparability class of some e_{i}, h(a) must be in the comparability class of some e_{j}. Once this is shown, h will induce an isomorphism of orders h̃, where if h maps the class of e_{i} to that of e_{j}, then h̃ : i ↦ j. I am grateful to L. van den Dries for suggesting the proof of the following lemma.

Lemma 3.3.3. Let F be R(L) for some linear order L. Let C be a positive infinite comparability class of elements of F. Then C is the comparability class of one of the e_{i}.

Proof. Suppose we have a real closed field K, and we add a single positive infinite element x > K. Let K((e^{ℚ})) denote the set of formal series f = ∑_{q∈ℚ}a_{q}e^{q}, where a_{q} ∈ K and a_{q} = 0 except for q in some well-ordered set. There is an isomorphism rcl(K(x)) ≃ K((e^{ℚ})) mapping x ↦ e^{−1}. Now suppose that y ∈ K((e^{ℚ})), and y = ∑_{q∈ℚ}b_{q}e^{q}. Further, suppose that for all x ∈ K, we have y > x (that is, y is an infinite element over K). Let q̂ be the least such that bq̂ ≠ 0. We know that q̂ < 0, since if q̂ ≥ 0, then y ≤ b_{0} + 1, but b_{0} + 1 ∈ K, giving a contradiction. Now e^{q̂−1} > y; that is, (e^{−1})^{1−q̂} > y, so y ≈ t^{−1}. Thus, rcl(K(x)) has exactly one more comparability class than K.

Given this, the lemma is relatively easy. Using the previous paragraph as an induction step, it is easy to show that for L a finite linear order, the lemma holds. Further, since any element in R(L) is algebraic over finitely many e_{i}, R(L) = ⋃_{I} rcl(R({e_{i}}_{i∈I})) where I is a finite subset of L. This completes the proof of both the lemma and the theorem.

Corollary 3.3.4. If K is the class of countable real closed ordered fields and K′ is a class of countable structures, then K′ ≤_{B} K (see Definition 4.2.1)

It is also worthwhile to note that Theorem 3.3.1 implies the characteristic 0 case of Theorem 3.2.4.

3.4 The Isomorphism Problem and Index Sets for Computable Models of Certain Strongly Minimal Theories

In a recent paper of Goncharov, Harizanov, Laskowski, Lempp, and McCoy [30], it was shown that in a certain sense it is impossible to code complicated sets into countable models of certain uncountably categorical theories. The authors were interested in coding the information into an individual model, and proved that this was impossible for trivial strongly minimal theories (specifically, any model has a ∅′′- decidable copy). The current section asks a similar question, but in a much different sense. Inspired by the results of the previous section, we will demonstrate a sense in which complicated information cannot be encoded in the class of computable models.

Much depends on the work of Baldwin and Lachlan [8], Morley [53], and Marsh [51]. Morley showed that any theory categorical in a single uncountable cardinal was categorical in all uncountable cardinals. Baldwin and Lachlan showed that such a theory must have either one or ℵ_{0} countable models, and Harrington [32] and Khisamiev [40], working independently, showed that if the theory is decidable, then all of its models have decidable copies.

Here we focus on the simplest such theories, the strongly minimal ones. A theory is said to be strongly minimal if every subset of the model which is definable (with parameters) is either finite or co-finite. We will seek to show that such theories not only have tight control over their countable models, but also over the computable ones. Marker’s book [50] is a helpful reference for much of the needed modeltheoretic background.

The isomorphism problem result of this section is a more general statement of analogous theorems for vector spaces and algebraically closed fields proved in [12]. The index set results are generalized from analogous results for vector spaces in joint work of the present author with Harizanov, Knight, and S. Miller [16].

If we have an indexed set {a_{i}}_{i∈ω} and R ⊆ ω, then we will write ā_{R} for {a_{i}|i ∈ R}. We will also write P (S) for the algebraic closure of the set S. Theorem 3.4.1. Let T be a strongly minimal theory with effective elimination of quantifiers and some computable model, where acl(∅) is infinite. Suppose K is the class of computable models of T. Then E(K) is m-complete Π_{3}^{0} within I(K).

Proof. It suffices that we can define the relation “dim(A_{i}) = dim(A_{j})” by a Π_{3}^{0} statement. In what follows, when we have a sequence v_{1}, …, v_{n}, we will write v̂_{i} for the sequence with v_{i} omitted, and if ϕ is a formula, we will understand ϕ(v̂_{i}, z) to mean ϕ(v_{1}, …, v_{i−1}, z, v_{i+1}, …, v_{n}). If M is a model of T, we can write that b_{1}, …, b_{n} are independent members of M as the formula

⋀_{i=1}^{n} ⋀ ; \begin{matrix}ψ(\overline{v}, x) \\ m ∈ ω \end{matrix} ⋀ ([∃x_{1}, …, x_{m}∀y [ψ(b̂_{i}, y) → ⋁_{j=1}^{m} x_{j} = y]] → ¬ψ(b̂_{i}, b_{i})) .

We will call this conjunction I_{n}(b_{1}, …, b_{n}). Note that because of the effective quantifier elimination, this is equivalent to a computable Π_{1} sentence.

Now to write that a model has dimension at least n, we would write the sentence

D_{n} = ∃x_{1}, …, x_{n}I(x_{1}, …, x_{n})

which is Σ_{2}^{0}. To define the isomorphism relation within K, we need only write

⋀_{n∈ω} ⋀ A_{a} ⊧ D_{n} ⟺ A_{b} ⊧ D_{n}

This condition is clearly Π_{3}^{0}, and its restriction to the set of ordered pairs of indices for models of T is clearly E(K), since it says that φ(\overline{a}, A_{a}) and φ(\overline{a}, A_{b}) have the same dimension.

Toward completeness, note that cof = {e|W_{e} is cofinite} is m-complete Σ_{3}^{0}. We will produce a uniformly computable sequence of models (A_{n})_{n∈ω} such that A_{n} has dimension equal to |\overline{W}_{n}|. When this is accomplished, we will have reduced the complement of cof to the index set of the infinite dimensional model of T. Let B be a copy of ω on which we will build the structure A_{n}, and let f_{−1} = D_{−1} = ∅. We will build A_{n} by giving a function mapping B to some substructure of A^{∗}, an infinitedimensional model with distinguished computable basis {a_{i}|i ∈ ω}. In particular, A_{n} will be isomorphic via f to the substructure of A^{∗} with basis {a_{i}|i ∉ W_{n}}.

We begin by defining our estimates for S = ω − W_{n}. Let S_{0} = ∅. At stage s, if S_{s−1} ⊆ ω − W_{n,s−1}, then we find the furst element x outside W_{n,s} and let S_{s} = S_{s−1} ∪ {x}. On the other hand, if S_{s−1} ⊈ ω − W_{n,s−1}, then we find the least r ∈ S_{s} ∩ W_{n,s} and set S_{s} = S_{s−1} ∩ {q|q < r}. Now to build A_{n}, we will proceed as follows.

At each stage s where S_{s−1} ⊈ S_{s}, we will have to collapse to a smaller model. There are some elements in ran(f_{s−1}) which should not be in ran(f). Let t be the last stage less than s such that S_{t} ⊆ S_{s}. Now f_{s−1} maps some elements d̄ of B into P (ā_{S_{t}})_{s}, and some other elements c_{1}, …, c_{j} to P (ā_{S_{s}})_{s}−P (ā_{S_{t}})_{s}. Let δ_{s}(d̄, c_{1}, …, c_{j}) be the conjunction of all elements of D_{s−1}. Now P (ā_{S_{s−1}}) ⊧ ∃x̄ δ_{s}(d̄, x̄), and so we also have P (ā_{S_{s}}) ⊧ ∃x̄ δ_{s}(d̄, x̄). We run the enumeration until we see the witnesses c̃_{1}, …, c̃_{j} such that P (ā_{S_{s}}) ⊧ δ_{s}(d̄, c̃_{1}, …, c̃_{j}). We now define f_{s} so that f_{s} ⊇ f_{t}, so that f_{s}(c_{i}) = c̃_{i}, and so that dom(f_{s}) includes the first s elements of B and ran(f_{s}) includes the first s elements of P (ā_{S_{s}}).

Otherwise, no such collapse is necessary. We simply extend f_{s−1} to f_{s} so that dom(f_{s}) includes the first s elements of B and ran(f_{s}) includes the first s elements of P (ā_{S_{s}}).

In any case, we also extend D_{s−1} to D_{s} by finding the first atomic sentence λ such that neither λ nor ¬λ is in D_{s−1} but all constants used in λ are in dom(f_{s}), computing its truth value via f_{s}, and recording the result in D_{s}.

A true stage is a stage s such that S_{s} ⊆ ω − W_{n}.

Lemma 3.4.2. There are infinitely many true stages.

Proof. Consider some non-true stage s. Suppose that r^{∗} is the least element of S_{s} which is not in ω − W_{n}. There is some least stage t ≥ s at which r^{∗} ∈ W_{n,t}. Now t + 1 will be a true stage.

Let A_{n} be the structure with atomic diagram ⋃_{s∈ω} D_{s}, and universe B. Let T be the set of all true stages, and let f = ⋃_{s∈T} f_{s}. Now A_{n} is isomorphic to a substructure of A^{∗} via f.

This has actually proved a first index set result.

Corollary 3.4.3. Let T be a strongly minimal theory with effective elimination of quantifiers and a computable model, where acl(∅) is infinite, and let M be its infinite dimensional computable model. Then if K is the class of computable models of T, then I(M) is m-complete Π_{3}^{0} within K.

We can also compute the complexities of the index sets for the other computable models of T.

Theorem 3.4.4. Let T be a strongly minimal theory with effective elimination of quantifiers and a computable prime model, where acl(∅) is infinite, and let M_{0} be the prime model of T. If K_{f} is the class of computable finite-dimensional models of T, then I(M_{0}) is m-complete Π_{2}^{0} within K_{f}.

Proof. The complexity may be bounded using the methods of Theorem 3.4.1. In particular, the copies of M_{0} are those models of T that satisfy the sentence

∀x_{1}, x_{2} ¬I_{2}(x_{1}, x_{2}).

Toward completeness, let M_{0} ≺ M_{1} where M_{1} has dimension 1. Consider an arbitrary Π_{2}^{0} set S = {n|∃^{∞}x R(n, x)}. We will build a uniformly computable sequence of structures (A_{n})_{n∈ω} such that

A_{n} ≃ \{ \begin{matrix}M_{0} & if n ∈ S \\ M_{1} & otherwise \end{matrix}

We write n ∈ S_{s} if R(n, s) holds. In particular, n ∈ S if and only if there are infinitely many stages s such that n ∈ S_{s}. We begin, as before, with B = ω, and with f_{−1} = D_{−1} = ∅.

At stage s we will adjust the function f to conform to our changing beliefs about whether n ∈ S. If we have n ∉ S_{s}, then we extend f_{s−1} so that dom(f_{s}) includes the first s elements of B and ran(f_{s}) includes the first s elements of M_{1}.

On the other hand, if we have n ∈ S_{s}, then we want to collapse the dimension of the model we are building. Let t be the latest stage before s such that either t = 0 or n ∉ S_{t}. Now f_{s−1} maps some elements d̄ of B into P (∅)_{s}, and some other elements c_{1}, …, c_{j} to P (a_{0})_{s} − P (∅)_{s}. Let δ_{s}(d̄, c_{1}, …, c_{j}) be the conjunction of all elements of D_{s−1}. Now M_{1} ⊧ ∃x̄ δ_{s}(d̄, x̄), and so we also have M_{0} ⊧ ∃x̄ δ_{s}(d̄, x̄). Let c̃_{1}, …, c̃_{j} be such that M_{0} ⊧ δ_{s}(d̄, c̃_{1}, …, c̃_{j}). We can now adjust the map f so that

f_{s}(x) = \{ \begin{matrix}c̃_{i} & if x = c_{i} \\ f_{t}(x) & otherwise \end{matrix}

so that f_{s} extends f_{t}.

In any case, we also find the first atomic sentence λ such that neither λ nor its negation is in D_{s−1}, but all constants appearing in λ are in dom(f_{s}). We compute its truth value via f_{s}, and add the result to D_{s−1} to form D_{s}.

A true stage s is one in which if n ∈ S then n ∈ S_{s} and if n ∉ S then for any t ≥ s we have n ∉ S_{t}. Note that if s ≤ s′ are true stages, then f_{s} ⊆ f_{s′}. We define T to be the set of all true stages, and f = ⋃_{s∈T} f_{s}, and let A_{n} be the structure with universe B whose atomic diagram is given by ⋃_{s∈ω} D_{s}.

Now if n ∈ S, we will infinitely often see n ∈ S_{s}, so that A_{n} ≃_{f} M_{0}. On the other hand, if n ∉ S, then after some stage f_{s} will always be copying M_{1} and f : A_{n} ≃ M_{1}.

Theorem 3.4.5. Let T be a strongly minimal theory with effective elimination of quantifiers and a computable model, where acl(∅) is infinite, and let M be a computable model of T which has finite dimension m > 0. If K_{f} is the class of finite dimensional models of T, then I(M) is m-complete d-Σ_{2}^{0} within K_{f}.

Proof. Let M_{m−1} ≺ M_{m} ≺ M_{m+1}, where M_{k} has dimension k. Again, the bound comes from the methods of Theorem 3.4.1. The copies of M are those models of T which satisfy the sentence D_{m} ∧ ¬D_{m+1}.

Toward completeness, let S = S_{1} − S_{2}, where S_{i} = ∃^{<∞}x R_{i}(n, x) are arbitrary Σ_{2}^{0} sets. We will construct a uniformly computable sequence of models (A_{n})_{n∈ω} so that

A_{n} ≃ \{ \begin{matrix}M_{m} & if n ∈ S \\ M_{m−1} & if n ∉ S_{1} \\ M_{m+1} & if n ∈ S_{1} ∩ S_{2} \end{matrix}

We begin, as usual, with B = ω and with f_{−1} = D_{−1} = ∅. We also set q_{−1} = m − 1.

We say that n ∈ S_{i,s} if and only if we have ¬R_{i}(n, s). In particular, n ∈ S_{i} if and only if for sufficiently large s we have n ∈ S_{i,s}.

At stage s, we will first define the target dimension d_{s}. We set

d_{s} = \{ \begin{matrix}m & if n ∈ S_{1,s} − S_{2,s} \\ m − 1 & if n ∉ S_{1,s} \\ m + 1 & if n ∈ S_{1,s} ∩ S_{2,s} \end{matrix} .

If d_{s−1} > d_{s}, then we will collapse the dimension back to d_{s}. Let t be the last stage before s such that d_{t} = d_{s} and such that for all z between t and s, we have d_{z} ≥ d_{t}. Now f_{s−1} maps some elements d̄ of B into P (ā_{{i|i<d_{s}−1}})_{s}, and some other elements c_{1}, …, c_{j} to P (ā_{{i|i<m+1}})_{s} − P (ā_{{i|i<d_{s}−1}})_{s}. Let δ_{s}(d̄, c_{1}, …, c_{j}) be the conjunction of all elements of D_{s−1}. Now M_{m+1} ⊧ ∃x̄ δ_{s}(d̄, x̄), and so we also have M_{d_{s}} ⊧ ∃x̄ δ_{s}(d̄, x̄). Let c̃_{1}, …, c̃_{j} be such that M_{m−1} ⊧ δ_{s}(d̄, c̃_{1}, …, c̃_{j}). We can now adjust the map f so that

f_{s}(x) = \{ \begin{matrix}c̃_{i} & if x = c_{i} \\ f_{t}(x) & otherwise \end{matrix}

and so that dom(f_{s}) contains the first s elements of B and ran(f_{s}) contains the first s elements of M_{d_{s}}. Thus, we will have f_{s} ⊇ f_{t}. Also, we find the first atomic sentence λ such that neither λ nor its negation is in D_{s−1}, but all constants appearing in λ are in dom(f_{s}). We compute its truth value via f_{s}, and add the result to D_{s−1} to form D_{s}.

We say that a stage s is a true stage if and only if for all t > s we will never have d_{t} < d_{s}.

Lemma 3.4.6. There are infinitely many true stages.

Proof. Suppose n ∈ S_{1} ∩ S_{2}. Then there is some t_{0} such that for t > t_{0} we will have n ∈ S_{1,t} ∩ S_{2,t}, so that d_{t} = m + 1. Consequently, every t > t_{0} is a true stage.

If n ∉ S_{1}, then for infinitely many s we will have n ∉ S_{1,s}, so that for all such s we will have d_{s} = m − 1. Since d_{t} ≥ m − 1 for all t, these s are true stages.

Finally, if n ∈ S, then there is some t_{1} such that for t > t_{1} we have n ∈ S_{1,t}, but there are infinitely many s such that n ∉ S_{2,s}. Take t such that n ∉ S_{2,t} but t > t_{1}. Now d_{t} = m, and for s > t we will always have either d_{s} = m or d_{s} = m + 1, so that t is a true stage.

Let A_{n} be the structure with universe B and with atomic diagram ⋃_{s∈ω} D_{s}. It is isomorphic to a substructure of M_{m+1} via f = ⋃_{s∈T} f_{s}, where T is the set of all true stages. It is clear that dim(A_{n}) will be what was claimed.

3.5 The Isomorphism Problem for Computable Archimedean Real Closed Fields

Since the proof of Theorem 3.3.1 used the non-Archimedean elements in a central way, it is worthwhile to consider what happens when this possibility is removed. In fact, things become much simpler.

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

Proof. The class of real closed fields can be axiomatized by a computable infinitary Π_{2} sentence, as can the class of Archimedean real closed fields (by adding the sentence that for each element x, some finite multiple of 1 is greater than x). Archimedean real closed fields are classified simply by the cuts that are filled, so the statement

∀x ∃x̂ ⋀_{q∈ℚ} ⋀[(A_{a} ⊧ q ≤ x ⇔ A_{b} ⊧ q ≤ x̂)]∧

∀z ∃ẑ ⋀_{q∈ℚ} ⋀[(A_{b} ⊧ q ≤ z ⇔ A_{a} ⊧ q ≤ ẑ)]

defines the relation A_{a} ≃ A_{b}, showing that it is, at worst, Π_{3}^{0}.

Lemma 3.5.2. There exists a uniformly computable sequence (a_{i})_{i∈ω} of real numbers which are algebraically independent.

Proof. Lindemann’s theorem states (in one form) that if λ_{1}, λ_{2}, …, λ_{k} are algebraic numbers linearly independent over the rationals, then e^{λ_{1}}, …, e^{λ_{k}} are algebraically independent [7]. Further, it is well known that the set \{\sqrt{2}, \sqrt{3}, \sqrt{5}, … \} is linearly independent (a proof may be found in [11]). Alternately, we could bypass this technology and simply build the sequence by a priority argument.

Now consider the language (+, ·, 0, 1, (a_{i})_{i∈ω}), and the theory consisting of the axioms of real closed fields and the further axioms q < a_{i} and q > a_{i}. This is a complete decidable theory, and so has a computable model A^{∗}. The set of elements of A^{∗} algebraic over the set of a_{i} is c.e. and by padding we can find a computable structure M = (M, +, ·, 0, 1, ≤, (a_{i})_{i∈ω}) where M is the real closure of (a_{i})_{i∈ω}.

Toward the completeness part of the theorem, we will produce a uniformly computable sequence (A_{n})_{n∈ω} such that A_{n} ≃ A^{∗} if and only if n ∉ cof. Let D_{−1} = T_{−1} = f_{0} = ∅, and let B be an infinite computable set. If C ⊆ ω, then we write RCF^{C} for the theory of real closed fields with constants for {a_{i}|i < |C|}, and P_{C} the computable prime model of RCF_{C} within A^{∗}.

We begin by defining our estimates for S = ω − W_{n}. Let S_{0} = ∅. At stage s, if S_{s−1} ⊆ ω − W_{n,s−1}, then we find the furst element x outside W_{n,s} and let S_{s} = S_{s−1} ∪ {x}. On the other hand, if S_{s−1} ⊈ ω − W_{n,s−1}, then we find the least r ∈ S_{s} ∩ W_{n,s} and set S_{s} = S_{s−1} ∩ {q|q < r}. Now to build A_{n}, we will proceed as follows.

At each stage s where S_{s−1} ⊆ S_{s}, extend f_{s−1} to f_{s} so that its domain includes the first s members of B and so that its range includes the first s members of P_{S_{s}}.

At each stage s where S_{s−1} ⊈ S_{s}, we will have to collapse to a smaller model. There are some elements in ran(f_{s−1}) which should not be in ran(f). Let t be the last stage less than s such that S_{t} ⊆ S_{s}. Now f_{s−1} maps some elements d̄ of B into P_{S_{t},s}, and some other elements c_{1}, …, c_{j} to P_{S_{s},s} − P_{S_{t},s}. Let δ_{s}(d̄, c_{1}, …, c_{j}) be the conjunction of all elements of D_{s−1}. Now P_{S_{s}} ⊧ ∃x̄ δ_{s}(d̄, x̄), and so we also have P_{S_{t}} ⊧ ∃x̄ δ_{s}(d̄, x̄). We run the enumeration until we see the witnesses c̃_{1}, …, c̃_{j} such that P_{S_{t}} ⊧ δ_{s}(d̄, c̃_{1}, …, c̃_{j}). We now define f_{s} so that f_{s} ⊇ f_{t}, so that f_{s}(c_{i}) = c̃_{i}, and so that dom(f_{s}) includes the first s elements of B and ran(f_{s}) includes the first s elements of P_{S_{s}}.

Otherwise no such collpapse is necessary. We then simply extend f_{s−1} to f_{s} so that dom(f_{s}) includes the first s elements of B and ran(f_{s}) includes the first s elements of P_{S_{s}}.

In any case, we also extend D_{s−1} to D_{s} as follows. We find the first atomic sentence λ such that neither λ nor ¬λ is in D_{s−1} but all constants used in λ are in dom(f_{s}), compute its truth value via f_{s}, and record the result in D_{s}.

A true stage is a stage s such that S_{s} ⊆ ω − W_{n}.

Lemma 3.5.3. There are infinitely many true stages.

Proof. Consider some non-true stage s. Suppose that r^{∗} is the least element of S_{s} which is not in ω − W_{n}. There is some least stage t ≥ s at which r^{∗} ∈ W_{n,t}. Now t + 1 will be a true stage.

Let A_{n} be the structure with atomic diagram ⋃_{s∈ω} D_{s}, and universe B. Let f = ⋃_{s∈T} f_{s}, where T is the set of all true stages. Now A_{n} is isomorphic to a substructure of A^{∗} via f.

Now A_{n} is isomorphic to the substructure of A^{∗} which is the real closure of āW̄_{n}. Thus, A_{n} has elements filling the same cuts as the first |W̄_{n}| elements of {a_{i}|i ∈ ω}. Consequently, A_{n} ≃ A^{∗} if and only if W_{n} is co-infinite.

3.6 Index Sets for Computable Archimedean Real Closed Fields

For previous classes of fields, it seems out of reach to completely describe the complexity of the index sets of all possible models. On the other hand, we have an idea of the structure of Archimedean real closed fields which is sufficient to give such a treatment.

The proof of Theorem 3.5.1 suggests that infinite transcendence degree is an important aspect of the index set having maximal complexity. It remains to ask whether any Archimedean real closed field with infinite transcendence degree behaves similarly, or whether the result is only true in some special fields that have sequences like those guaranteed in Lemma 3.5.2. The results of the present section are preliminary work of the present author with Harizanov, Knight, and S. Miller which will be more fully reported in [16]

As it turns out, given an Archimedean ordered field A of infinite transcendence degree and a Π_{3}^{0} set S, we can construct a uniformly computable sequence of Archimedean real closed fields (A_{n})_{n∈ω} such that A_{n} ≃ A if and only if n ∈ S by treating all cuts alike — real algebraic or not. Some will necessarily get filled and others will be filled or not according to whether n ∈ ω, but we do not need to know which is which.

Theorem 3.6.1. Let K be the class of computable Archimedean ordered fields, and let A be a member of K. Assume A_{0} is a purely transcendental extension of ℚ and that A is either a finite extension of A_{0} or its real closure.

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

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

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

Question 3.6.2. Let A be a computable Archimedean ordered field of infinite transcendence degree. Is there a uniformly computable sequence of algebraically independent elements of A?

Question 3.6.3. Suppose that A is an Archimedean ordered field which is not real closed and is an infinite algebraic extension of A_{0}, where A_{0} is as in Theorem 3.6.1. What is the m-degree of I(A)?

FINITE STRUCTURES AND COMPARISONS

So far our attention has been restricted to infinite structures, and this is not without reason. Since it is difficult to find anything about a finite structure that is very far from being computable, it at first appears that computability theory is too blunt a tool for any meaningful analysis of such structures.

In the first section of this chapter, we will give evidence in favor of this obvious prejudice. Afterwards, though, we will see a method first proposed in joint work of the present author with Cummins, Knight, and S. Miller [15], by which meaningful and non-trivial comparisons can be made between classes of finite structures. Moreover, the method is also interesting when applied to classes of infinite structures, and will find important application in Chapter 5 for calculating Scott ranks.

4.1 Index Sets of Finite Structures

It is well-known that any finite structure is determined up to isomorphism by a relatively simple first-order sentence. The next theorem could be considered an optimality result for that sentence. On the other hand, it is an analogue of the index set results of Section 3.4, with finite sizes corresponding to finite dimensions. In that sense, this result relates results like those of Section 3.4 to their “lower end.” Theorem 4.1.1 (C.–Harizanov–Knight–S. Miller [16]). Let A be a finite structure for a language L, and let K be the class of finite structures for that language.

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

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

4.2 Comparing Classes of Structures

While the internal complexity of a single finite structure is rather severely bounded, the external complexity — its situation within a class of similar structures — can still be quite complex. No one would say, for instance, that the class of finite graphs is “simple.” In an earlier chapter, allusion was made to a method of comparing classes of structures, which originated in a paper of Friedman and Stanley. Definition 4.2.1 (Friedman–Stanley [25]). View the set of structures in a fixed language and with universe ω as a topological space via the product topology. Let K_{1} and K_{2} be classes of countable structures with the subspace topology. Then we say K_{1} ≤_{B} K_{2} if there is a Borel measurable function Φ : K_{1} → K_{2} which is well-defined and 1-1 on isomorphism types.

Clearly if the classes of structures involved are countable, this definition is completely useless, since any function between countable sets is Borel measurable. This fails to account, though, for the unreasonable effectiveness of proofs that K_{1} ≤_{B} K_{2} in proving theorems about isomorphism problems for classes of computable structures, such as Theorems 3.2.4 and 3.3.1.

In an effort to explain this, the present author, Cummins, Knight, and S. Miller proposed a definition of a different ordering, analogous to ≤_{B} but based on enumeration reducibility which does give some information about these classes. This definition is by no means the only reasonable analogy. However, it is a definition that fairly reflects the situation of finite structures, and about which we can prove interesting results.

Definition 4.2.2 (C.–Cummins–Knight–S. Miller [15]). Let K_{1} and K_{2} be classes of structures, and let Φ be a c.e. set of pairs (α, φ), where α is a subset of the atomic diagram of a finite structure for the language of K_{1}, and φ is an atomic sentence, or the negation of one, in the language of K_{2}.

1. We say that Φ is a computable transformation from K_{1} to K_{2} if for all A ∈ K_{1}, the set Φ(D(A)) has the form D(B), for some B ∈ K_{2}. We may write Φ(A) = B (identifying the structures with their atomic diagrams).

2. We say that K_{1} ≤_{c} K_{2} if there is a computable transformation Φ from K_{1} to K_{2}, which, when viewed as a function Φ : K_{1} → K_{2}, is well-defined and 1-1 on isomorphism types.

The encoding used in the proof of Theorem 3.2.4 is an example of a computable transformation witnessing that if UG is the class of undirected graphs and F is the class of fields, then UG ≤_{c} F. Cummins used an argument from Friedman and Stanley [25] that if LO is the class of linear orders and DG is the class of directed graphs then DG ≤_{B} LO to show that DG ≤_{c} LO [20]. An important general property of computable transformations is the following proposition.

Proposition 4.2.3 (C.–Cummins–Knight–S. Miller [15]). Let K_{1} and K_{2} be classes of structures, and let Φ be a computable transformation from K_{1} to K_{2}. If A, A′ ∈ K_{1}, where A ⊆ A′, then Φ(A) ⊆ Φ(A′).

This apparently minor fact turns out to be very important in proving results of the form K_{1} ≰_{c} K_{2}, which is the harder part of almost any comparison of classes using ≤_{c}. For the remainder of this section we will adopt the following operational definition.

Definition 4.2.4. We will use the following names for some important classes of structures.

G  = Graphs
V S = Vector Spaces
F V S = Finite-dimensional Vector Spaces
F G = Finite Graphs
CG = Cyclic graphs

4.2.1 Basic Properties of the Order ≤_{c}

The natural classes just named are conveniently situated as landmarks throughout the partial order of all classes of countable structures under ≤_{c}. Theorem 4.2.5 (C.–Cummins–Knight–S. Miller [15]). Among the classes listed above, we have the following relations:

CG <_{c} F G <_{c} F V S <_{c} V S <_{c} G

We say that two classes K_{1} and K_{2} are c-equivalent (written K_{1} ≡_{c} K_{2}, and often just expressed by “equivalent” if no confusion is likely) if both K_{1} ≤_{c} K_{2} and K_{2} ≤_{c} K_{1}. It turns out that most natural classes of structures are equivalent to one of these classes. Theorem 4.2.6 (C.–Cummins–Knight–S. Miller [15]). We have the following equivalences

1. The following classes are c-equivalent: (a) CG

(b) Finite prime fields

2. The following classes are c-equivalent: (a) Finite graphs

(b) Finite groups

(c) Finite simple groups (d) Finite cyclic groups

(e) Finite linear orders

(f) Arbitrary finite structures

As might be expected, all classes of finite structures fall below F G and all classes of countable structures fall below G. While most natural classes of structures tend to fall into the linearly ordered segment described in Theorem 4.2.5, there are many other equivalence classes. One important method of constructing them is based on immunity.

Definition 4.2.7 (C.–Cummins–Knight–S. Miller [15]). Let X ⊆ ω. We say that sets A, B ⊆ ω are X bi-immune if for any X-computable function f with infinite range, there is some a ∈ A such that f(a) ∉ B, and there is some b ∈ B such that f(b) ∉ A. We say that A and B are bi-immune if they are X bi-immune for computable X.

If A and B are bi-immune, and if K_{A} is the class of cyclic graphs of size n for n ∈ A and K_{B} for n ∈ B, then neither K_{A} ≤_{c} K_{B} nor K_{B} ≤_{c} K_{A}.

Proposition 4.2.8 (C.–Cummins–Knight–S. Miller [15]). For any set X, there exists a family (A_{f})_{f∈2^{ω}} such that for any distinct f, g ∈ 2^{ω}, A_{f} and A_{g} are X bi-immune.

Thus, there are continuum many classes of computable structures which are ≤_{c} incomparable, and which are ≤_{c}-below the class of finite cyclic graphs. Many similar results are possible, and the partial ordering given by ≤_{c} is quite complicated.

Theorem 4.2.9 (Knight [44]). There are classes K_{1} and K_{2} of structures such that K_{1} and K_{2} have neither least upper bound nor greatest upper bound. Thus, ≤_{c} is not a lattice.

4.2.2 Applications to Infinite Structures

The ordering ≤_{c} was originally developed to investigate classes of finite structures. However, it gives some important information, too, about infinite structures. A first taste of this is a byproduct of the immunity investigations.

An important question about isomorphism problems is exactly which m-degrees can occur as the degree of the isomorphism problem for some class of computable structures. It is generally believed that far more degrees are possible than we have actually seen. A major milestone, though, is producing two such degrees that are incomparable.

Theorem 4.2.10. There are incomparable m-degrees each of which is the degree of the isomorphism problem for some class of computable structures.

Proof. Let A and B be Δ_{4}^{0} bi-immune sets of natural numbers. Let K_{A} be the set of computable ℚ-vector spaces of dimensions from A, and let K_{B} be defined symmetrically. Then E(K_{A}) and E(K_{B}) are incomparable.

More applications that come directly from computable transformations and the relation ≤_{c} are being seen in work currently in progress. Much of the effectiveness of these concepts comes from the following theorem of Knight.

Theorem 4.2.11 (Knight [44]). Let Φ witness that K_{1} ≤_{c} K_{2}. For any computable infinitary sentence φ in the language of K_{2}, we can find a computable infinitary sentence φ^{∗} in the language of K_{1} such that for all A ∈ K_{1} we have Φ(A) ⊧ φ if and only if A ⊧ φ^{∗}. Moreover, if φ is of class Σ_{α}^{0}, then φ^{∗} may also be chosen to be of class Σ_{α}^{0}.

COMPUTABLE STRUCTURES AND HIGH SCOTT RANK

We have already seen examples of highly complicated structures. For instance, the way in which a class of computable structures with Σ_{1}^{1} complete isomorphism problem are proved to be at that level is typically that it has some member whose index set is of the greatest possible complexity.

With the exception of the background information in Section 5.1, all of the material in the present chapter is of a preliminary nature. This chapter is meant to give the reader a sense of the state of a very important and promising direction for future inquiry in the subject of this thesis, however incomplete the work on this direction may be.

5.1 Scott Rank

Question 5.1.1. What gives a structure high index set complexity?

One measure of the internal complexity of a structure is the Scott rank. This rank is one good candidate for an answer to the question. There are several reasonable definitions of the Scott rank of a structure in the literature, and all are nearly equivalent (most differ only finitely, and many agree on limit ordinals; see [5] for more details). The following definition allows for reasonable calculations, and makes fine distinctions at the top of the range. We first define the Scott rank of a tuple of elements.

Definition 5.1.2.

1. ā ∼_{0} b̄ if they satisfy all the same atomic formulas.

2. ā ∼_{α+1} b̄ if for every d there is a c such that b̄d ∼_{α} āc.

3. ā ∼_{γ} b̄ for limit γ if ā ∼_{α} b̄ for all α < γ.

4. sr(ā) is the least ordinal α such that b̄ ∼_{α} implies b̄ ≃ ā.

With this definition in hand, we proceed to define the Scott rank of a structure. Definition 5.1.3. Given a structure A, we define the Scott rank of A, denoted SR(A) to be the least ordinal greater than sr(ā) for all finite ā ⊆ A.

Nadel [55] showed that if A is a computable structure, then SR(A) ≤ ω_{1}^{CK} + 1. A computable linear ordering of type ω_{1}^{CK}(1 + η) (Harrison showed that such an ordering exists [33]), where η is the order type of the rationals, has Scott rank ω_{1}^{CK} + 1, since, for instance, the orbit of the first element in a copy of ω_{1}^{CK} other than the first, is not hyperarithmetical. If A is a computable infinite dimensional ℚ-vector space, then SR(A) = 1.

It will be helpful to have on hand a few additional easy properties of Scott rank: Theorem 5.1.4 (Classical). Let A be a computable structure.

1. We have SR(A) < ω_{1}^{CK} if and only if the structure A has a computable infinitary Scott sentence.

2. We have SR(A) = ω_{1}^{CK} + 1 if and only if there is some element x ∈ A such that sr(x) = ω_{1}^{CK}.

The possibility of a relationship of Scott rank to index set complexity is expressed in a question of Goncharov and Knight.

Question 5.1.5 (Goncharov–Knight [31]). If I(A) is hyperarithmetical, must SR(A) be computable?

It is not at all clear what the answer to this question will be. Much of the work discussed in this chapter arises from attempts to build intuition and techniques in the general vicinity of this problem, but we are not yet prepared to mount a full frontal assault on it.

Rather, this chapter will document joint work of the present author with several others, first on the construction of various examples of structures with Scott rank ω_{1}^{CK} exactly, and then on the complexity of the set of indices for all structures with non-computable Scott rank.

5.2 Examples of Structures of High Scott Rank

As has already been noted, there are many examples of computable structures A where either SR(A) is computable or SR(A) = ω_{1}^{CK} + 1. There are no examples in which SR(A) > ω_{1}^{CK} + 1. It is natural, then, to look at the gap: Question 5.2.1. Is there a computable structure A where SR(A) = ω_{1}^{CK}?

It is important to note that some other definitions of Scott rank collapse ranks ω_{1}^{CK} and ω_{1}^{CK} + 1. Nadel’s paper [55], for instance, calculates the maximum Scott rank (in the sense of the definition of Barwise [10]) of a computable structure to be ω_{1}^{CK}, so that the problem is trivial. In our definition, though, the distinction exists.

It at first seemed that structures of Scott rank ω_{1}^{CK} should at least be rare and unnatural. The earliest examples were. Theorem 5.2.2 (Makkai [48]). There is an arithmetical structure A such that SR(A) = ω_{1}^{CK}. Theorem 5.2.3 (Knight–Young [45]). There is a computable structure A such that SR(A) = ω_{1}^{CK}.

These structures were not of any type to which we are accustomed, which presented difficulties in understanding them. To produce these structures, one would start with a tree, define certain group structures in the level of the tree, and use the result to produce a new structure which included neither the original tree nor any of the group operations. The purpose of introducing the group structure is to impose a property of “homogeneity” on the structure (this is not the usual model-theoretic notion of homogeneity), so that tuples that appear to be automorphic actually are automorphic.

The present author, along with Knight and Young, noticed that this homogeneity could be imposed from the beginning, allowing an example to be given which is simply a tree.

Definition 5.2.4 (C.–Knight–Young [18]). We say that a tree T is rank homogeneous if for every n ∈ ω and every x ∈ T at level n, the following are satisfied:

1. For every α < tr(x), if there is y ∈ T at level n + 1 such that tr(y) = α, then there is an infinite set of nodes {y_{i}}_{i∈ω} ⊆ T, each of which is at level n + 1, each of which is a successor of x, and each of which has rank α.

2. If tr(x) = ∞, then x has infinitely many successors of rank ∞.

The most important thing about this class of trees is that if T is a rank homogeneous tree, then we can calculate the Scott ranks of elements in T. In particular, if x̄ is a finite subset of T and for each x ∈ x̄ we have tr(x) computable, then sr(x̄) is computable. Further, if x, y ∈ T at level n, and tr(x) = tr(y) = ∞, then x and y are automorphic. It follows that if for each level n there is a computable ordinal α_{n} bounding the tree ranks of elements x at level n which have tr(x) < ∞, then all tuples in T have computable Scott rank. On the other hand, if for any computable ordinal α there exists x ∈ T with α < tr(x) < ∞, then there is no computable bound on the Scott ranks of tuples, so that SR(T) ≥ ω_{1}^{CK}. We can now summarize the additional property we need in our tree. Definition 5.2.5. We say that a tree T is thin if for every level n there is a computable ordinal α_{n} bounding the nodes at level n with ordinal rank, but for any computable ordinal α there exists x ∈ T with α < tr(x) < ∞.

What is needed, then, is a thin, rank homogeneous tree. We can do exactly that. Theorem 5.2.6 (Knight–Young [45]). There is a computable thin tree. Theorem 5.2.7 (C.–Knight–Young [18]). From an index for a computable tree T we can pass effectively to an index for a computable rank homogeneous tree T̃ such that the ranks that occur at level n in T̃ are exactly the ones that occur at level n in T. Theorem 5.2.8 (C.–Knight–Young [18]). If T is a computable thin rank homogeneous tree, then SR(T) = ω_{1}^{CK}.

Since we have a tree of Scott rank ω_{1}^{CK}, it becomes believable that there are examples in other interesting classes of structures. Work in progress, summarized by the following two theorems, gives such examples. Theorem 5.2.9 (C.–Goncharov–Knight). Let K be any of the following classes. Then there is a computable structure A ∈ K such that SR(A) = ω_{1}^{CK}.

1. Undirected graphs

2. Linear orders

3. Fields of characteristic 0 It appears, then, that structures of rank ω_{1}^{CK} are not as exotic as was once

believed. We might reasonably expect to encounter them in more classes, or in problems in which we did not set out to find them. On the other hand, there are some contexts in which we can exclude the possibility of such a structure.

Theorem 5.2.10 (C.–Goncharov–Knight). Let K be any of the following classes. Then if A is a computable member of K and SR(A) ≥ ω_{1}^{CK}, then SR(A) = ω_{1}^{CK} + 1.

1. Abelian p-groups

2. Models of the computable infinitary theory of well-orderings

3. Models of the computable infinitary theory of superatomic Boolean algebras

5.3 Index Sets for High Scott Rank

In examples we have explored in earlier sections of this thesis, a calculation of the complexity of the index set of a structure requires some deep understanding of the structure itself, and in turn gives some insight on what sort of information the structure contains. It is reasonable to think that this would happen not only for structures, but also for classes of structures — for instance, the class K_{HR} of computable structures of noncomputable Scott rank. We will also examine I(K_{α}) where K_{α} is the class of computable structures of Scott rank α and where α ∈ {ω_{1}^{CK}, ω_{1}^{CK} + 1}. In this section, we will see the results of work in progress, which has an eventual goal of resolving the following question, which is currently open.

Question 5.3.1. What are the m-degrees of the following?

1. I(K_{HR})

2. I(K_{ω_{1}^{CK}})

3. I(K_{ω_{1}^{CK}+1})

Naive ways to write the definition L_{ω_{1}ω} with second order quantifiers give the following bounds.

Proposition 5.3.2 (C.–Goncharov–Knight–Kudinov–Morozov–Puzarenko).

1. I(K_{HR}) is Σ_{1}^{1}.

2. I(K_{ω_{1}^{CK}}) has a definition of the form ∀∃(d-Σ_{1}^{1}).

3. I(K_{ω_{1}^{CK}+1}) has a definition of the form ∃∀(Σ_{1}^{1} ∨ Π_{1}^{1}).

Of course, for the first item, we have much more exact information, since if K is the class of orderings isomorphic to either a computable ordinal or to ω_{1}^{CK}(1 + η), then I(K ∩ K_{HR}) is m-complete Σ_{1}^{1} within K.

Proposition 5.3.3 (C.–Goncharov–Knight–Kudinov–Morozov–Puzarenko). I(K_{HR}) is m-complete Σ_{1}^{1}.

Completeness in the other two cases remains open. If S is a Π_{1}^{1} set, we can show that S ≤_{m} I(K_{ω_{1}^{CK}+1}) within K_{HR} using a method of “hiding” a copy of the Harrison ordering. We will construct a uniformly computable sequence of structures (A_{n})_{n∈ω} such that A_{n} is of Scott rank ω_{1}^{CK} We begin with a Harrison ordering, and to each pair of elements we connect an infinite set. For each n, we will give each of these sets the structure of a tree.

Lemma 5.3.4. Let S ∈ Π_{1}^{1}, and let T be the computable tree of Scott rank ω_{1}^{CK} constructed in Theorems 5.2.6, 5.2.7, and 5.2.8. There is a uniformly computable sequence of trees (C_{n})_{n∈ω} such that C_{n} ≃ T if and only if n ∉ S, and such that if n ∈ S we have SR(C_{n}) < ω_{1}^{CK}.

Now if (a, b) is a pair in the ordering, the structure attached to the pair (a, b) will be the structure C_{n} if a < b and T otherwise. The structure A_{n} will be the reduct in which the original ordering is forgotten and we retain only the structures attached to the various pairs. In the case that n ∈ §, the structure C_{n} will have a computable infinitary Scott sentence, and so we can recover the Harrison ordering, giving some tuples Scott rank ω_{1}^{CK} and making SR(A_{n}) = ω_{1}^{CK} + 1. On the other hand, if n ∉ S, we will have SR(A_{n}) = ω_{1}^{CK}. Lemma 5.3.4 was a major motivation for proving Theorems 5.2.7 and 5.2.8, since it was not clear that an analogous result would hold for previous examples of structures with Scott rank ω_{1}^{CK}.

The method just described, along with the fact that if K is the class of orderings isomorphic to either a computable ordinal or to ω_{1}^{CK}(1 + η), then I(K ∩ K_{HR}) is m-complete Σ_{1}^{1} within K, are the principal methods needed to get the strongest known completeness results. We state these results here.

Proposition 5.3.5 (C.–Goncharov–Knight–Kudinov–Morozov–Puzarenko). We have the following bounds:

1. For any set S with a definition of the form ∃(d-Σ_{1}^{1}), we have S ≤_{m} I(K_{ω_{1}^{CK}+1}).

2. For any set S with a definition of the form ∀(Σ_{1}^{1}∨Π_{1}^{1}), we have S ≤_{m} I(K_{ω_{1}^{CK}+1}).

BIBLIOGRAPHY

[1] S. Abhyankar. On the compositum of algebraically closed subfields. Proceedings of the American Mathematical Society, 7:905–907, 1956.

[2] C. J. Ash. Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. Transactions of the American Mathematical Society, 298:497–514, 1986. Corrections: Ibid, vol. 300 (1988) p. 851.

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

[4] C. J. Ash. Generalizations of enumeration reducibility using recursive infinitary propositional sentences. Annals of Pure and Applied Logic, 58:173–184, 1992.

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

[6] R. Baer. Abelian groups without elements of finite order. Duke Mathematical Journal, 3:68–122, 1937.

[7] A. Baker. Transcendental number theory. Cambridge University Press, 1975.

[8] J. T. Baldwin and A. H. Lachlan. On strongly minimal sets. Journal of Symbolic Logic, 36:79–96, 1971.

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

[10] J. Barwise. Admissible sets and structures. Perspectives in Mathematical Logic. Springer-Verlag, 1975.

[11] A. S. Besicovitch. On the linear independence of fractional powers of integers. Journal of the London Mathematical Society, 15:3–6, 1940.

[12] W. Calvert. The isomorphism problem for classes of computable fields. Archive for Mathematical Logic, 43:327–336, 2004.

[13] W. Calvert. The isomorphism problem for computable Abelian p-groups of bounded length. accepted for publication in Journal of Symbolic Logic, 2005.

[14] W. Calvert, D. Cenzer, V. Harizanov, and A. Morozov. Δ_{2}^{0}-categoricity of Abelian p-groups. in preparation.

[15] W. Calvert, D. Cummins, J. F. Knight, and S. Miller. Comparing classes of finite structures. Algebra and Logic, 43:374–392, 2004.

[16] W. Calvert, V. Harizanov, J. F. Knight, and S. Miller. Index sets of computable structures. in preparation.

[17] W. Calvert, V. Harizanov, and A. Shlapentokh. Turing degrees of isomorphism types of algebraic objects. preprint, 2005.

[18] W. Calvert, J. F. Knight, and J. M. Young. Rank homogeneity and some consequenses. in preparation.

[19] D. A. Cox, J. B. Little, and D. B. O’Shea. Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics. Springer Verlag, 1998.

[20] D. Cummins. Homogeneous embeddings. Senior Thesis, University of Notre Dame, 2003.

[21] R. G. Downey. On presentations of algebraic structures. In Complexity, logic, and recursion theory, volume 187 of Lecture Notes in Pure and Applied Mathematics, pages 157–205. Marcel Dekker, 1997.

[22] S. Feferman. Impredicativity of the existence of the largest divisible subgroup of an Abelian p-group. In Model Theory and Algebra: A memorial tribute to Abraham Robinson, number 498 in Lecture Notes in Mathematics, pages 117– 130. Springer, 1975.

[23] S. Feferman and C. Spector. Incompleteness along paths in progressions of theories. Journal of Symbolic Logic, 27:383–390, 1962.

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

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

[26] A. Frolich and J. C. Sheperdson. Effective procedures in field theory. Philosophical Transactions of the Royal Society of London, Series A, 248:407–432, 1956.

[27] L. Fuchs. Infinite Abelian groups, volume 2. Academic Press, 1973.

[28] S. S. Goncharov. Autostability of models and Abelian groups. Algebra and Logic, 19:13–27, 1980.

[29] S. S. Goncharov, V. S. Harizanov, J. F. Knight, and R. A. Shore. Π_{1}^{1} relations and paths through O. Journal of Symbolic Logic, 69:585–611, 2004.

[30] S. S. Goncharov, V. S. Harizanov, M. C. Laskowski, S. Lempp, and C. F. D. McCoy. Trivial, strongly minimal theories are model complete after naming constants. Proceedings of the American Mathematical Society, 131:3901–3912, 2003.

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

[32] L. Harrington. Recursively presentable prime models. The Journal of Symbolic Logic, 39:305–309, 1974.

[33] J. Harrison. Recursive pseudo-well-orderings. Transactions of the American Mathematical Society, 131:526–543, 1968.

[34] D. Haskell, A. Pillay, and C. Steinhorn. Model theory, algebra, and geometry. Cambridge University Press, 2000.

[35] D. R. Hirschfeldt and W. M. White. Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures. Notre Dame Journal of Formal Logic, 43:51–64, 2002.

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

[37] G. Hjorth. The isomorphism relation on countable torsion free Abelian groups. Fundamenta Mathematicae, 175:241–257, 2002.

[38] G. Hjorth and A. S. Kechris. Analytic equivalence relations and Ulm-type classifications. Journal of Symbolic Logic, 60:1273–1300, 1995.

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

[40] N. G. Khisamiev. Strongly constructive models of a decidable theory. Izvestija Akademii Nauk KazahskoĭSSR. Serija Fiziko-Matematičeskaja, pages 83–84, 94, 1974.

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

[42] J. F. Knight. Degrees coded in jumps of orderings. The Journal of Symbolic Logic, 51:1034–1042, 1986.

[43] J. F. Knight. Degrees of models. In Handbook of Recursive Mathematics, volume 1, pages 289–309. Elsevier, 1998.

[44] J. F. Knight. Effective transfer of invariants. preprint, 2005.

[45] J. F. Knight and J. M. Young. Computable structures of rank ω_{1}^{CK}. preprint, 2005.

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

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

[48] M. Makkai. An example concerning Scott heights. The Journal of Symbolic Logic, 46:301–318, 1981.

[49] A. I. Mal’cev. On recursive Abelian groups. Dokl. Akad. Nauk SSSR, 146:1009– 1012, 1962.

[50] D. Marker. Model theory: an introduction. Springer-Verlag, 2002.

[51] W. E. Marsh. On ω_{1}-categorical but not ω-categorical theories. PhD thesis, Dartmouth College, 1966.

[52] G. Metakides and A. Nerode. Effective content of field theory. Annals of Mathematical Logic, 17:289–320, 1979.

[53] M. Morley. Categoricity in power. Transactions of the American Mathematical Society, 114:514–538, 1965.

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

[55] M. E. Nadel. Scott sentences and admissible sets. Annals of Mathematical Logic, 7:267–294, 1974.

[56] M. E. Nadel. Scott heights of Abelian groups. The Journal of Symbolic Logic, 59:1351–1359, 1994.

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

[58] A. Nurtazin. Strong and weak constructivizations and computable families. Algebra and Logic, 13:177–184, 1974.

[59] S. E. Oates. Jump degrees of groups. PhD thesis, University of Notre Dame, 1989.

[60] M. O. Rabin. Computable algebra, general theory and theory of computable fields. Transactions of the American Mathematical Society, 95:341–360, 1960.

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

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

[63] L. J. Richter. Degrees of structures. The Journal of Symbolic Logic, 46:723–731, 1981.

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

[65] D. B. Shapiro. Composites of algebraically closed fields. Journal of Algebra, 130:176–190, 1990.

[66] S. Shelah. Classification theory and the number of non-isomorphic models. North Holland, 1990.

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

[68] R. I. Soare. Recursively enumerable sets and degrees. Springer-Verlag, 1987.

[69] V. Stoltenberg-Hansen and J. V. Tucker. Computable rings and fields. In E. R. Griffor, editor, Handbook of Computability Theory, pages 363–447. Elsevier, 1999.

[70] S. Thomas. The classification problem for torsion-free Abelian groups of finite rank. Journal of the American Mathematical Society, 16, 2003.