TURING DEGREES OF ISOMORPHISM TYPES OF ALGEBRAIC OBJECTS

VALENTINA HARIZANOV, WESLEY CALVERT, AND ALEXANDRA SHLAPENTOKH

Abstract. The Turing degree spectrum of a countable structure A is the set of all Turing degrees of isomorphic copies of A. The Turing degree of the isomorphism type of A, if it exists, is the least Turing degree in its degree spectrum. We show there are countable fields, rings, and torsion-free abelian groups of arbitrary rank, whose isomorphism types have arbitrary Turing degrees. We also show that there are structures in each of these classes whose isomorphism types do not have Turing degrees.

1. Introduction

One of the main goals of computable algebra is to understand how algebraic properties of structures interact with their computabilitytheoretic properties. While in algebra and model theory isomorphic structures are often identified, in computable model theory they can have very different algorithmic properties. Here, we study Turing degrees of algebraic structures from some well-known classes. We consider only countable structures for computable (usually finite) languages. The universe A of an infinite countable structure A can be identified with the set ω of all natural numbers. Furthermore, we often use the same symbol for the structure and its universe. (For the definition of a language and a structure see p. 8 of [21], and for a definition of a computable language see p. 509 of [22].)

2 VALENTINA HARIZANOV, WESLEY CALVERT, AND ALEXANDRA SHLAPENTOKH

Let {A_{j}, j ∈ ω} be a sequence of structures contained in a structure B. Then by ∏_{j∈ω} A_{j} we mean the smallest substructure of B containing A_{j} for all j. More specifically, we will be looking at products of number fields and function fields, and at products of rings contained in a number field. In the case of fields, we fix an algebraic closure of ℚ, a rational function field over a finite field of characteristic p > 0 or over ℚ as required, and we can set B to be this algebraic closure. In the case of subrings of a number field, the number field itself is a natural choice for B.

Calvert acknowledges partial support of the NSF grants DMS-0139626 and DMS-0353748. Harizanov gratefully acknowledges support of the Columbian Research Fellowship of the George Washington University. Shlapentokh acknowledges partial support of the NSF grant DMS-0354907.

When measuring complexity of structures, we identify them with their atomic diagrams. The atomic diagram of a structure A is the set of all quantifier-free sentences in the language of A expanded by adding a constant symbol for every a ∈ A, which are true in A. The Turing degree of A, deg(A), is the Turing degree of the atomic diagram of A. Hence, A is computable (recursive) iff deg(A) = 0. (Some authors call a structure computable if it is only isomorphic to a computable one.) We also say that a procedure is computable (effective), relative to B, also in B, if it is computable relative to the atomic diagram of B.

We use ≤_{T} for Turing reducibility and ≡_{T} for Turing equivalence of sets. We often abbreviate deg(A) ≤ deg(X) by A ≤_{T} X. (Detailed information about Turing degrees and their structure can be found in [27] and [29].)

The Turing degree spectrum of a countable structure A is

DgSp(A) = {deg(B) : B ≅ A}.

A countable structure A is automorphically trivial if there is a finite subset X of the domain A such that every permutation of A, whose restriction on X is the identity, is an automorphism of A. If a structure A is automorphically trivial, then all isomorphic copies of A have the same Turing degree. It was shown in [14] that if the language is finite, then that degree must be 0. On the other hand, Knight [19] proved that for an automorphically nontrivial structure A, we have that DgSp(A) is closed upwards, that is, if b ∈ DgSp(A) and d > b, then d ∈ DgSp(A). Hirschfeldt, Khoussainov, Shore, and Slinko established in [15] that for every automorphically nontrivial structure A, there is a symmetric irreflexive graph, a partial order, a lattice, a ring, an integral domain of arbitrary characteristic, a commutative semigroup, or a 2step nilpotent group whose degree spectrum coincides with DgSp(A).

The Turing degree of a structure is not invariant under isomorphisms. Thus, Jockusch and Richter introduced the following complexity measures of the isomorphism type of a structure.

Definition 1.1. (i) The Turing degree of the isomorphism type of A, if it exists, is the least Turing degree in DgSp(A).

(ii) Let α be a computable ordinal. The αth jump degree of a structure A is, if it exists, the least Turing degree in

{deg(B)^{(α)} : B ≅ A}.

Obviously, the notion of the 0th jump degree of A coincides with the notion of the degree of the isomorphism type of A. (A general discussion of the jump operator can be found in 13.1 of [27] and Chapter III of [29].)

In [26] Richter proved that if A is a structure without a computable copy and satisfies the effective extendability condition explained below, then the isomorphism type of A has no degree. Richter’s result uses a minimal pair construction. Distinct nonzero Turing degrees a and b form a minimal pair if

(c ≤ a, c ≤ b) ⇒ c = 0.

(See [29] for the minimal pair method.) A structure A satisfies the effective extendability condition if for every finite structure M isomorphic to a substructure of A, and every embedding σ of M into A, there is an algorithm that determines whether a given finite structure N extending M can be embedded into A by an embedding extending σ. In [26] Richter also showed that every linear order and every tree, as a partially ordered set, satisfy the effective extendability condition. Recently, Khisamiev in [18] showed that every abelian p-group, where p is a prime number, satisfies the effective extendability condition. Hence the isomorphism type of a countable linear order, a tree, or an abelian p-group, which is not isomorphic to a computable one, does not have a degree.

Recently, Csima in [6] proved that if A is a prime model of a complete decidable theory with no computable prime model, then the isomorphism type of A does not have a Turing degree, while for every n ≥ 1, the structure A has the nth jump degree 0^{(n)}. (See [13] for more information on computability of prime models.)

If A is a nonstandard model of Peano arithmetic, then the isomorphism type of A has no degree. On the other hand, Knight showed in [19] that for any Turing degree d, there is a nonstandard model of Peano Arithmetic with first jump degree d′. Knight also established that the only possible first jump degree for a linear order is 0′.

Ash, Jockusch, and Knight in [2], and Downey and Knight in [9] proved that for every computable ordinal α ≥ 1, and every Turing degree d such that d ≥ 0^{(α)}, there is a linear order L whose αth jump degree is d, and such that L does not have βth jump degree for any β < α. Jockusch and Soare proved in [17] that for a Turing degree d and n ∈ ω, if a Boolean algebra B has nth jump degree d, then d = 0^{(n)}. They also showed that if d ≥ 0^{(ω)}, then there is a Boolean algebra with ωth jump degree d. Oates in [23] proved that for every computable ordinal α ≥ 1, and every Turing degree d such that d > 0^{(α)}, there is an abelian group G whose αth jump degree is d, and G does not have βth jump degree for any β < α.

For additional background information on computability (recursion) theory, see [27] or [29]. For computable model theory, see [8], [13], [12], and [24]. In the sections that follow we will use some facts from algebra and number theory. The relevant algebraic material can be found in [1], [5], [10], [11], [16], [20], [25], or [28].

2. Turing degrees of the isomorphism types of structures

We would like to further investigate Turing degrees of the isomorphism types of abelian groups, rings, and fields. The following result is a modification of Richter’s Theorem 2.1 on p. 725 in [26]. Richter used her theorem to show that for every Turing degree d, there is an abelian torsion group whose isomorphism type has degree d.

Theorem 2.1. Let C be a class of countable structures in a finite language L, closed under isomorphisms. Assume that there is a computable sequence {A_{i}, i ∈ ω} of computable (possibly infinite) structures in C satisfying the following conditions.

• There exists a finitely generated structure A ∈ C such that for all i ∈ ω, we have that A ⊂ A_{i}.

• For any X ⊆ ω, there is a structure A_{X} in C such that A ⊂ A_{X}

and

A_{X} ≤_{T} X,

and for every i ∈ ω, there exists an embedding σ such that

σ : A_{i} ↪ A_{X}, σ_{|A} = id,

iff i ∈ X.

• Suppose a structure B is such that for some X ⊆ ω, we have that B ≃ A_{X} under isomorphism τ : A_{X} ⟷ B. Consider the set Λ of pairs (i, j) such that exactly one of the structures A_{i} and A_{j} is embeddable in B under an embedding σ such that (τ^{−1} ∘ σ)_{|A} = id. Then there is a procedure, computable in B (that is, in the atomic diagram of B), which decides for every (i, j) ∈ Λ, which of A_{i} and A_{j} embeds in B.

Then for every Turing degree d, there is a structure in C whose isomorphism type has degree d.

Proof. Let D ⊆ ω be such that deg(D) = d. As usual, let

D ⊕ \overline{D} =_{def} \{2n : n ∈ D\} ∪ \{2n + 1 : n ∉ D\}.

We will show that A_{D⊕\overline{D}} is a structure in C, whose isomorphism type has Turing degree d. Clearly, by assumption,

deg(A_{D⊕\overline{D}}) ≤ deg(D ⊕ \overline{D}) = d.

Now, let a structure B be such that there exists an isomorphism τ : A_{D⊕\overline{D}} ⟷ B. We then have, by the definition of D ⊕ \overline{D} and an assumption of the theorem, that for every j ∈ ω,

j ∈ D ⇔ (∃σ)[σ : A_{2j} ↪ B ∧ (τ^{−1} ∘ σ)_{|A} = id],

or, equivalently,

j ∉ D ⇔ (∃σ)[σ : A_{2j+1} ↪ B ∧ (τ^{−1} ∘ σ)_{|A} = id].

Thus, by an assumption of the theorem, we conclude that d ≤ deg(B). Hence deg(A_{D⊕\overline{D}}) = d. Moreover, the degree of the isomorphism type of A_{D⊕\overline{D}} is d. □

3. Fields whose isomorphism types have arbitrary Turing degrees

In this section we show that certain sequences of computable linearly disjoint fields satisfy conditions of Theorem 2.1. First we state two definitions to describe sequences we will consider.

Definition 3.1. Let F be any field. Let {L_{i}, i ∈ ω} be a sequence of finite extensions of F such that for any i ∈ ω, we have that L_{i} and ∏_{j∈ω\{i}} L_{j} are linearly disjoint over F, or, in other words,

[L_{i} : F] = [L : ∏_{j∈ω\{i}} L_{j}] > 1,

where L = ∏_{j∈ω} L_{j}. Then we will call the sequence {L_{i}, i ∈ ω} totally linearly disjoint over F.

Definition 3.2. Let F be any field. Let {L_{i}, i ∈ ω} be a sequence of algebraic extensions of F, and let L = ∏_{i∈ω} L_{i}. Suppose further that for any embedding σ : L ↪ F̃, where F̃ is the algebraic closure of F, such that σ_{|F} = id, for all i, we have either σ(L_{i}) = L_{i} or σ(L_{i}) ⊄ L. Then we will call the sequence {L_{i}, i ∈ ω} stable with respect to F. If F = ℚ or F is a finite field, then we will say that the sequence {L_{i}, i ∈ ω} is stable.

We are now ready to prove the main theorem involving these field sequences.

Theorem 3.3. Let K be any computable finitely generated field, and let K̃ be a computable algebraic closure of K. Let P = {f_{i}(T) ∈ K(T)} be a computable sequence of monic polynomials irreducible over K. Let α_{i} be a root of f_{i}, and let M_{i} = K(α_{i}). Assume further that the sequence {M_{i}, i ∈ ω} is totally linearly disjoint over K and is stable with respect to K. Let A = K. Let A_{i} = M_{i}, and for any X ⊂ ω, let A_{X} = M_{X}, where

M_{X} = ∏_{i∈X} M_{i}.

Then the conditions of Theorem 2.1 are satisfied.

Remark 3.4. Before we proceed with the details of the proof, we would like to note that every computable field has a computable algebraic closure, as shown in [24].

Proof. Let X ⊂ ω.

(1) We show that M_{i} is embeddable into M_{X} = ∏_{i∈X} M_{i} under any embedding σ keeping K fixed if and only if i ∈ X. Let σ : M_{i} ↪ M_{X} be such an embedding. Given our assumptions on the linear disjointness of the elements of the sequence, σ can be extended to σ̃ : M ↪ F̃, where M = ∏_{j∈ω} M_{j}. Thus, by our assumptions, we conclude that σ(M_{i}) = M_{i}, and therefore, M_{i} ⊂ M_{X}. However, by our assumptions again, this is possible iff i ∈ X.

(2) Next, we show that M_{X} ≤_{T} X. Let α_{i} be a root of f_{i}. Given our assumptions, M is a computable field, and there exists a computable function which, given an element of M, will produce its coordinates with respect to the basis

Ω = {∏_{i∈I} α_{i}^{a_{i}} : I ⊂ ω, |I| < ∞, 0 ≤ a_{i} < deg(f_{i})}.

Thus, given β ∈ M and X, we can determine, computably in X, whether β ∈ M_{X}. Consequently, M_{X} ≤_{T} X. (Since the reverse reducibility is obvious, we can actually show that M_{X} ≡_{T} X.)

(3) Finally, let τ : M_{X} ⟷ B be an isomorphism, and let i, j ∈ ω, i ≠ j, be such that for exactly one of k = i and k = j, there exists σ : M_{k} ↪ B satisfying the condition that τ^{−1} ∘ σ is an identity on K. Since K is finitely generated, we can compute in B the τ-images of f_{i} and f_{j}. Next we note that there exists an embedding σ : M_{i} ↪ B such that τ^{−1} ∘ σ is an identity on K if and only if τ(f_{i}) has a root in B. Indeed, suppose there exists γ ∈ B such that γ is a root of τ(f_{i}). Then β = τ^{−1}(γ) ∈ M_{X} and f_{i} has a root β ∈ M_{X}. We claim that

K(β) = K(α_{i}) = M_{i}.

Suppose otherwise. Then consider λ : K(α_{i}) → K(β) keeping K fixed, and its extension λ̃ to M. Since λ̃ fixes K, by our assumption on {M_{i}}, we conclude that either K(β) = K(α_{i}), or K(β) ⊄ M and, in particular, K(β) ⊄ M_{X}. Thus, i ∈ X and M_{i} ⊂ M_{X}, and we can set σ(M_{i}) = τ(M_{i}). Conversely, if the required σ exists, then τ^{−1} ∘ σ : M_{i} → M_{X}, and thus i ∈ X and τ(α_{i}) will satisfy τ(f_{i}). Therefore, we just need to check systematically all elements of B until we find a root for τ(f_{i}) or τ(f_{j}).

□

Example 3.5. Let K = ℚ, let {p_{i}, i ∈ ω} be the listing of rational primes. Let f_{i}(T) = T^{2} − p_{i}. It is clear that in this case the sequence \{M_{i}, i ∈ ω\}, where M_{i} = ℚ(\sqrt{p_{i}}), is stable and totally linearly disjoint over ℚ, and thus all the requirements of Theorem 3.3 are satisfied.

Example 3.6. Let K = ℚ(x), where x is not algebraic over ℚ. Let \{p_{i}, i ∈ ω\} be the listing of rational primes. Let M_{i} = ℚ(x, \sqrt[p_{i}]{x^{2} + 1}). Then the sequence {M_{i}, i ∈ ω} is linearly disjoint over ℚ(x) and is stable with respect to ℚ(x). Hence Theorem 3.3 applies again.

Example 3.7. Let 𝔽_{p} be a field of p elements for some rational prime p. Let {p_{i}, i ∈ ω} be a listing of rational primes as before. Let α_{i} be of degree p_{i} over 𝔽_{p}. Let M_{i} = 𝔽_{p}(α_{i}). Then {M_{i}, i ∈ ω} is a stable sequence totally linearly disjoint over 𝔽_{p}, and the Theorem 3.3 applies.

Example 3.8. Let 𝔾_{p} be a finite field. Let x be transcendental over 𝔾_{p}. Let {p_{i}, i ∈ ω} be a listing of rational primes as before. Let α_{i} be of degree p_{i} over 𝔾_{p}. Let M_{i} = 𝔾_{p}(α_{i}, x). Then {M_{i}, i ∈ ω} is totally linearly disjoint over 𝔾_{p}(x) and is stable with respect to 𝔾_{p}(x).

Example 3.9. Let K = ℚ(x) or K = 𝔽_{p}(x), where x is not algebraic over ℚ or 𝔽_{p}, respectively. Let M_{i} = ℚ(\sqrt{x^{2} + i}) or M = 𝔽_{p}(\sqrt{x^{2} + i}). Then {M_{i}, i ∈ ω} is totally linearly disjoint over ℚ(x) and 𝔽_{p}(x), respectively, and is stable with respect to ℚ(x) and 𝔽_{p}(x), respectively.

4. Rings whose isomorphism types have arbitrary Turing degrees

In this section we consider sequences of integrally closed subrings of product formula fields: number fields (finite extensions of ℚ), and finite extensions of rational function fields. In the case of a function field, we will let the constant field be an arbitrary computable field with a splitting algorithm. (For a discussion of fields with splitting algorithms see Section 17.1, 17.2 of [10].)

Let K be a product formula field. In the case of a function field, let C be the constant field, and let x ∈ K be a non-constant element. If characteristic p is such that p > 0, then assume x is not a pth power in K. Under our assumptions, K/ℚ in the case of a number field, or K/C(x) in the case of a function field is a finite and separable extension. Let R = ℤ in the case of a number field, and let R = C[x] in the case of a function field. Then all prime ideals of R correspond to prime numbers or irreducible monic polynomials. In the case of ℤ, these ideals also represent all non-archimedean valuations of ℚ, while in the case of C(x), a valuation corresponding to the degree of polynomials does not correspond to a prime ideal of C[x]. (It does, however, correspond to a prime ideal of C[\frac{1}{x}].) Now, let O_{K} be the integral closure of ℤ or C[x] in K. Then O_{K} is called the ring of algebraic integers or integral functions, depending on the choice of K. Now, the prime ideals of R do not necessarily remain prime in O_{K}, but every prime ideal of R will have finitely many factors in O_{K}. The set of all prime ideals of O_{K} (together with the factors of the degree valuation in the case of function fields) will constitute what is called the set of primes of K. If x ∈ (O_{K})^{∗} and p is a prime ideal in O_{K}, then we define ord_{p}z to be the largest nonnegative number such that z ∈ (p)^{n}. If w ∈ K, we write w = z_{1}/z_{2} for some z_{1}, z_{2} ∈ (O_{K})^{∗}, and we let ord_{p}w = ord_{p}z_{1} −ord_{p}z_{2}. Finally, we set ord_{p}0 = ∞. For more material on valuations and primes of number fields and function fields the reader is referred to [5], [16], [10], and [25].

Using the Strong Approximation Theorem (see p. 21 of [10] and p. 268 of [25]), it can be shown that any integrally closed subring of K, whose fraction field is K is of the form

O_{K,W} = {z ∈ K : (∀p ∉ W)[ord_{p}z ≥ 0]},

where W is an arbitrary set of (non-archimedean) primes of K. In the case W is finite, this ring is called a ring of W-integers. Unfortunately, there is no universally accepted name for these rings when W is infinite. Since R is a principal ideal domain, O_{K} is a free R-module. The basis of O_{K} as a free R-module is called an integral basis of K over R. Therefore, if we represent elements of K using their coordinates with respect to an integral basis, O_{K} is computable under such representation.

In what follows, we use an effective listing of primes of a product formula field, and basically identify the ith prime on the list with a natural number i (for the purpose of satisfying the requirements of Theorem 2.1). To carry out this plan, we need some way to represent the primes and to make sure that the order at a given prime is computable. There are several ways to do this. In the next lemma we describe one of them.

Lemma 4.1. Let K be a product formula field. Consider the pairs of K-elements representing the primes of K, as described below. Then, given an element x ∈ K presented by its coordinates with respect to some integral basis of K over its rational subfield, there is an effective procedure to determine which primes of K occur in the divisor of x, as well as the order of x at each of the primes occurring in its divisor.

Proof. Let p be a prime of K. First, by the Weak Approximation Theorem, there exists t_{p} ∈ O_{K} such that ord_{p}t_{p} = 1 and for any q ≠ p, conjugate to p over the rational field, ord_{q}t_{p} = 0. We will identify each prime of K with a pair (t_{p}, p), where p is the prime number or the monic irreducible polynomial below p in the rational field.

Since we assume that the constant field is computable and has a splitting algorithm, we can produce a computable sequence of all primes of the rational field. Then for all but finitely many primes p of the rational field, using Lemma 4.1 on p. 135 of [28], Lemma 17.5 on p. 232 of [10], and Proposition 25 on p. 27 of [20], we have an effective procedure for determining the number and relative degree of all Kfactors of p. Next, by a systematic search of O_{K}, using the rational norms of elements of O_{K}, we can locate t_{p} for each factor of a given rational prime p. Finally, for an arbitrary element x of K, by looking at its rational norm, we can determine a finite superset of the primes occurring in its divisor. Then, using the pairs for these potentially occurring primes, we can determine the actual divisor of x. □

Remark 4.2. For future use we also note here that for any K-prime p, by the Strong Approximation Theorem, there exists an element z_{p} ∈ K such that p is the only prime of K with ord_{p}z_{p} < 0. Furthermore, there exist a_{p}, b_{p} ∈ K such that z_{p} = \frac{a_{p}}{b_{p}} . Having constructed sequence {(p, t_{p})} for each prime of K, we can effectively locate z_{p}, a_{p}, and b_{p}.

We are now ready to state the main theorem of this section.

Theorem 4.3. Let K be a computable product formula field with a finite degree separable rational subfield F. (So either F = ℚ, or F = C(x) for some x ∈ K \ C.) In the case of a function field, assume that the constant field C is computable, finitely generated, and has a splitting algorithm. Let {p_{i}, i ∈ ω} be an effective listing of primes of F (i.e., prime numbers or monic irreducible polynomials in x over C). For each p_{i}, choose one K-factor p_{i}, and let {(p_{i}, t_{p_{i}})} be the listing of primes of K corresponding to {p_{i}, i ∈ ω}, where t_{p_{i}} has the least code in the set {t_{q} : q is a K-factor of p}. Let A = R (that is, A = ℤ if K is a number field, and A = C[x] if K is a function field). Let W = ∅ if K is a number field, and let W be the (finite) set of all K-poles of x if K is a function field. For any X ⊆ ω, let

W_{X} = W ∪ {p_{i} : i ∈ X}.

Let

A_{X} = O_{K,W_{X}}.

Then the sequence {A_{i}, i ∈ ω} satisfies the conditions of Theorem 2.1.

Proof. In the case of K being a function field, we observe that for all i ∈ ω, we have that p_{i} is not a pole of x in K. This is true since each p_{i} is a factor of a C(x)-prime corresponding to a polynomial in x. We next verify that all conditions of Theorem 2.1 hold.

(1) We show that O_{K,W_{X}} ≤_{T} X for any X ⊆ ω. Assuming we represent elements of K as n-tuples of their coordinates with respect to some integral basis of K over its rational subfield F, by Lemma 4.1, we can effectively compute the divisors of elements of K. Assuming the element is in O_{K,W_{ω}} to begin with, we can next determine for each pair (p_{i}, p_{i}) with p_{i} occurring in the norm, whether i ∈ X, and thus establish whether the element is in O_{K,W_{X}}. (Conversely, if we have the characteristic function of O_{K,W_{X}}, to determine whether i ∈ X, it is enough to determine whether z_{p_{i}} ∈ O_{K,W_{X}}. Hence we have O_{K,W_{X}} ≡_{T} X.)

(2) Let σ : O_{K,W_{i}} ↪ O_{K,W_{X}} for some i ∈ ω and X ⊂ ω with σ|_{C[x]} = id in the case K is a function field. We show that i ∈ X. First, observe that σ can be extended to an automorphism of K keeping C(x) fixed. Next, observe that σ(z_{p_{i}}) = σ(a_{p_{i}}/b_{p_{i}}) is an element that has negative order only at a prime σ(p_{i}). By the definition of O_{K,W_{X}}, we have that σ(p_{i}) ∈ W_{X} ⊂ W. However, W_{X} contains only one factor for each p_{i}. Therefore,

σ(p_{i}) = p_{i} ∈ W_{X} ⇔ i ∈ X.

The case of K being a number field is similar.

(3) Let τ : O_{K,W_{X}} ⟷ B be an isomorphism of rings. Let i, j ∈ ω, i ≠ j, be such that for exactly one of k = i and k = j, there exists an embedding σ : O_{K,W_{k}} ↪ B such that τ^{−1} ∘ σ|_{C[x]} = id in the case when K is a function field. We show that, relative to B, we can compute which of the rings O_{K,W_{i}} and O_{K,W_{j}} is embeddable into B in the prescribed manner. Since C is finitely generated and O_{K} has a basis over R, in B we can list τ(O_{K}) and effectively find τ(a_{p_{i}}), τ(b_{p_{i}}), τ(a_{p_{j}}), and τ(b_{p_{j}}). Finally, we systematically look for the solution in B of the equations τ(b_{p_{i}})Z = τ(a_{p_{i}}), and τ(b_{p_{j}})W = τ(a_{p_{j}}). It is clear that, by assumption, exactly one of these equations will have a solution. On the other hand, τ(b_{p_{k}})Z = τ(a_{p_{k}}) has a solution in B if and only if σ : O_{K,W_{k}} ↪ B as specified above exists.

□

In lieu of examples illustrating this theorem, which are pretty easy to generate, we offer a different version of Theorem 4.3. The proof of this version is very similar to the proof of Theorem 4.3.

Theorem 4.4. Let K be a computable product formula field with a finite degree separable rational subfield F. In the case of a function field, assume that the constant field C is computable, finitely generated, and has a splitting algorithm. Let {p_{i}, i ∈ ω} be an effective listing of primes of K, excluding in the function field case the poles of some nonconstant element x such that F = C(x). Let A = O_{K}. Let W = ∅ if K is a number field, and let W be the (finite) set of all K-poles of x. For any X ⊆ ω, let

W_{X} = ⋃_{i∈X}{p is a factor of p_{i}} ∪ W.

Let W_{i} = W ∪ {all K-factors of p_{i}}. Let

A_{X} = O_{K,W_{X}}.

Let A_{i} = O_{K,W_{i}}. Then the sequence {A_{i}, i ∈ ω} satisfies the conditions of Theorem 2.1.

5. Torsion-free abelian groups of arbitrary finite rank and of arbitrary Turing degree

Rank 1, torsion-free, abelian groups are isomorphic to subgroups of (ℚ, +). There is a known classification, due to Baer [4], of countable, rank 1, torsion-free, abelian groups. The account here will generally follow the one in a book by Fuchs [11], Volume 2. 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 set 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.

In some torsion-free abelian groups (for example, (ℚ, +)), 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 set t_{G}(a) = t, and say that a is of type t. A group G in which any two nonzero elements have the same type t is 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 5.1. (Baer [4]) If G and H are torsion-free abelian groups of rank 1, then G ≃ H if and only if t(G) = t(H).

Knight and Downey established that for an arbitrary Turing degree d, there exists a torsion-free abelian group of rank 1 and finite type, whose degree of the isomorphism type is d (see [8]). Downey and Jockusch showed in [8] that even rank 1 groups of finite type can fail to have degree. On the other hand, it follows from a computabilitytheoretic result of Coles, Downey, and Slaman, using a result by Downey, Jockusch, and Solomon, that every torsion-free abelian group of rank 1 has first jump degree (see [7]). Coles, Downey, and Slaman proved that for every set A ⊆ ω, there is a Turing degree that is the least degree of the jumps of all sets X for which A is computably enumerable in X. On the other hand, Richter [26] constructed a non-computably enumerable set that is computably enumerable in two sets that form a minimal pair. This construction implies that there is a set A such that the set of all X for which A is computably enumerable in X has no member of the least Turing degree.

Knight-Downey’s proof of the claim that for an arbitrary Turing degree d, there exists a torsion-free abelian group of rank 1 (and finite type) whose degree of the isomorphism type is d is as follows. Let a set D ⊆ ω be of degree d. Let G be a rank 1 group defined by the type sequence (a_{n})_{n∈ω} such that

a_{n} = \{ \begin{matrix}1 & if n ∈ D ⊕ D̄, \\ 0 & if n ∉ D ⊕ D̄. \end{matrix}

There is an isomorphic copy of G computable in D. Conversely, let H ≅ G. Then H has the type sequence (a_{n})_{n∈ω} (by Proposition 5.1).

The type sequence of H is computably enumerable in H, and hence D ⊕ D̄ is computably enumerable in H. Thus D ≤_{T} H.

On the other hand, the construction from Section 4 can be adapted to give examples of torsion-free abelian groups of finite rank satisfying conditions of Theorem 2.1, and thus produce torsion-free abelian groups of arbitrary rank and of arbitrary Turing degree d.

Theorem 5.2. Let k be a positive integer. Let C be the class of all subgroups of ℚ^{k}. Let {p_{i}, i ∈ ω} be a listing of rational primes. Let A = ℤ^{k}. For any X ⊆ ω, let V_{X} = {p_{i} : i ∈ X}. Let

A_{X} = (O_{ℚ,_{V_{X}}})^{k}.

For each i ∈ ω, let A_{i} = (O_{ℚ,{p_{i}}})^{k}. Then the sequence {A_{i}, i ∈ ω} satisfies the conditions of Theorem 2.1.

The proof of this theorem is almost identical to the proof of Theorem 4.3.

6. Algebraic structures whose isomorphism types have no Turing degrees

We now want to investigate structures whose isomorphism types have no Turing degrees. The enumeration reducibility will play an important role. First, we define the canonical index u of a finite set D_{u} ⊂ ω. Let D_{0} = ∅. For u > 0, let D_{u} = {n_{0}, …, n_{k−1}}, where n_{0} < … < n_{k−1} and u = 2^{n_{0}} + … + 2^{n_{k−1}}. For sets X, Y ⊆ ω, we say that Y is enumeration reducible to X, in symbols X ≤_{e} Y, if there is a computably enumerable binary relation E such that

(x ∈ X) ⇔ (∃u)[D_{u} ⊆ Y ∧ E(x, u)].

Equivalently, X ≤_{e} Y iff for every set S, if Y is computably enumerable relative to S, then X is computably enumerable relative to S. Richter showed that a modification of Theorem 2.1 on p. 725 in [26], obtained by replacing Turing reducibility in A_{X} ≤_{T} X by the enumeration reducibility A_{X} ≤_{e} X, yields a very different conclusion, Theorem 2.3 on p. 726 in [26] — that there is a set X such that the isomorphism type of A_{X} does not have a degree. Richter used this theorem to show that there is a torsion abelian group whose isomorphism type does not have a degree. The following result is a generalization of Richter’s Theorem 2.3. It should be noted that the hypotheses of this theorem are similar to those of Theorem 2.1.

Theorem 6.1. Let C be a class of countable structures in a finite language L, closed under isomorphisms. Assume that there is a computable sequence {A_{i}, i ∈ ω} of computable (possibly infinite) structures in C satisfying the following conditions.

• There exists a finitely generated structure A ∈ C such that for all i ∈ ω, we have that A ⊂ A_{i}.

• For any X ⊆ ω, there is a structure A_{X} in C such that A ⊂ A_{X}

and

A_{X} ≤_{e} X,

and for every i ∈ ω, there exists an embedding σ such that

σ : A_{i} ↪ A_{X}, σ_{|A} = id,

iff i ∈ X.

• Suppose a structure B is such that for some X ⊆ ω we have that B ≃ A_{X} under isomorphism τ : A_{X} ⟷ B. Then from any enumeration of B, we can effectively pass to an enumeration of the set of indices i such that A_{i} ↪ B under an embedding σ such that (τ^{−1} ∘ σ)_{|A} = id.

Then there is a structure in C whose isomorphism type has no Turing degree.

Proof. The proof follows from the following well-known lemma.

Lemma 6.2. There is a set X ⊆ ω such that the set of functions

{f : ran(f) = X}

has no least Turing degree.

We omit the proof of Lemma 6.2 here. The idea is to construct a set X, which is not computably enumerable, but the set of enumerations of X contains two enumerations whose Turing degrees form a minimal pair. A full proof may be found in [26].

Let X be as in Lemma 6.2, and, toward contradiction, let M be a copy of A_{X} with least Turing degree. Now, we will argue that M has a least enumeration. Let ν be an enumeration of M where deg(ν) = deg(M). Let g be another enumeration of M with ν ≰_{T} g. By padding (i.e. by passing to a structure whose elements are of the form (x, t), where x is enumerated into M at time t, and where the operations are the obvious ones), we can obtain an isomorphic copy of M with the same Turing degree as g, which is a contradiction. Hence, by the final assumption of the theorem, we can pass effectively from ν to an enumeration ν_{M} of X.

Let f be an enumeration of X, and we will show that ν_{M} ≤_{T} f. By assumption, we can pass effectively from f to an enumeration g of A_{X}, and, since A_{X} ≤_{e} X and M ≤_{T} A_{X} (because here we identify M with its atomic diagram), we can pass effectively from g to an enumeration g̃ of M. Now M ≤_{T} g̃, so we have ν_{M} ≤_{T} M ≤_{T} f, as was to be shown. This is a contradiction. □

Theorem 6.3. There are countable fields, rings, and torsion-free abelian groups of arbitrary finite rank, whose isomorphism types do not have Turing degrees.

Proof. Since the statements of Theorem 6.3 and Theorem 2.1 differ in the place where A_{X} ≤_{T} X is replaced with A_{X} ≤_{e} X, to prove the analogs of Theorems 3.3, 4.3, and 5.2, we need to show that the respective structures satisfy A_{X} ≤_{e} X.

We will start with the field case, where all the notation and assumptions are as in Theorem 3.3. We need to show that M_{X} ≤_{e} X. Let ϕ : ω ⟶ X be any listing of X. Then, using ϕ, we can list the sets {α_{ϕ(i)}} and {α_{ϕ(i_{1})}^{m(ϕ(i_{1}))} … α_{ϕ(i_{k})}^{m(ϕ(i_{k}))}}, where 0 ≤ m(ϕ(i_{l})) < deg(f_{ϕ(i_{l})}) and k ∈ ω. Thus we will be able to list the basis of M_{X} over K, and then M_{X} itself. (As in the case of Turing reducibility, it is not hard to see that X ≤_{e} M_{X} also, and therefore, we really have enumeration equivalence.)

We now proceed to the ring case. Here, all the notation and assumptions are as in Theorem 4.3. Let ϕ be as above, and note that, given ϕ, we can list the set {p_{ϕ(i)}, p_{ϕ(i)}}. The listing of primes will then allow the listing of O_{K,W_{X}}, where we would proceed by testing elements of K to see if the primes in the denominator of their divisors have appeared in the list already. This testing process is effective as discussed in Section 4. (As above, we also have here that X ≤ O_{K,W_{X}}.) The case of the abelian groups from Section 5 is again almost identical to the case of the rings.

For the condition on listing the i such that A_{i} is embeddable in a copy of A_{X}, the earlier proofs suffice. In each case, we proved the hypotheses for Theorem 2.1 by first establishing the hypotheses for this theorem. □

References

[1] E. Artin, Algebraic Numbers and Algebraic Functions, Gordon and Breach Science Publishers, New York, 1967.

[2] C. J. Ash, C. G. Jockusch, Jr., and J. F. Knight, Jumps of orderings, Transactions of the American Mathematical Society 319 (1990), pp. 573–599.

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

[4] R. Baer, Abelian groups without elements of finite order, Duke Mathematical Journal 3 (1937), pp. 68–122.

[5] C. Chevalley, Introduction to the Theory of Algebraic Functions of One Variable, Mathematical Surveys VI, American Mathematical Society, New York, 1951.

[6] B. Csima, Degree spectra of prime models, Journal of Symbolic Logic 69 (2004), pp. 430–442.

[7] R. J. Coles, R. G. Downey, and T. A. Slaman, Every set has a least jump enumeration, Journal of the London Mathematical Society 62 (2000), pp. 641–649.

[8] R. G. Downey, On presentations of algebraic structures, Complexity, Logic, and Recursion Theory (A. Sorbi, editor), Lecture Notes in Pure and Applied Mathematics 187, Marcel Dekker, New York, 1997, pp. 157–205.

[9] R. Downey and J. F. Knight, Orderings with αth jump degree 0^{(α)}, Proceedings of the American Mathematical Society 114 (1992), pp. 545– 552.

[10] M. D. Fried and M. Jarden, Field Arithmetic, first edition, Springer-Verlag, Berlin, 1986.

[11] L. Fuchs, Infinite Abelian Groups, Academic Press, New York, 1973.

[12] V. S. Harizanov, Computability-theoretic complexity of countable structures, Bulletin of Symbolic Logic 8 (2002), pp. 457–477.

[13] V. S. Harizanov, Pure computable model theory, Handbook of Recursive Mathematics, vol. 1 (Yu. L. Ershov, S. S. Goncharov, A. Nerode and J. B. Remmel, editors, V. W. Marek, assoc. editor), Elsevier, Amsterdam, 1998, pp. 3–114.

[14] V. Harizanov and R. Miller, Spectra of structures and relations, submitted.

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

[16] G. J. Janusz, Algebraic Number Fields, Pure and Applied Mathematics 55, Academic Press, New York, 1973.

[17] C. G. Jockusch, Jr. and R. I. Soare, Boolean algebras, Stone spaces, and the iterated Turing jump, Journal of Symbolic Logic 59 (1994), pp. 1121–1138.

[18] A. N. Khisamiev, On the upper semilattice L_{E}, Siberian Mathematical Journal 45 (2004), pp. 211–228 (in Russian); pp. 173–187 (English translation).

[19] J. F. Knight, Degrees coded in jumps of orderings, Journal of Symbolic Logic 51 (1986), pp. 1034–1042.

[20] S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, 1970.

[21] D. Marker, Model Theory, An Introduction, Springer-Verlag, New York, [22] T. S. Millar, Pure recursive model theory, Handbook of Computability

Theory (E. R. Griffor, editor), Elsevier, Amsterdam, 1999, pp. 507–532.

[23] S. Oates, Jump Degrees of Groups, PhD dissertation, University of Notre Dame, 1989.

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

[25] P. Ribenboim, The theory of classical valuations, Springer Monographs in Mathematics, Springer-Verlag, New York, 1999.

[26] L. J. Richter, Degrees of structures, Journal of Symbolic Logic 46 (1981), pp. 723–731.

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

[28] A. Shlapentokh, Hilbert’s Tenth Problem over number fields, a survey, Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry, (J. Denef, L. Lipshitz, T. Pheidas, and J. Van Geel, editors), Contemporary Mathematics 270, American Mathematical Society, Providence, 2000, pp. 107–137.

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

Department of Mathematics, George Washington University, Washington, DC 20052

E-mail address: harizanv@gwu.edu

Department of Mathematics & Statistics, Murray State University, Murray, KY 42071

E-mail address: wcalvert@sigmaxi.org

Department of Mathematics, East Carolina University, Greenville, NC 27858

E-mail address: shlapentokha@mail.ecu.edu