Degree Spectra and Computable Dimensions in Algebraic Structures

Denis R. Hirschfeldt^{∗}

Department of Mathematics, Cornell University, Ithaca NY 14853, U.S.A.

Bakhadyr Khoussainov

Department of Computer Science, University of Auckland,

Private Bag 92019, Auckland, New Zealand

Richard A. Shore^{∗∗}

Department of Mathematics, Cornell University, Ithaca NY 14853, U.S.A.

Arkadii M. Slinko

Department of Mathematics, University of Auckland,

Private Bag 92019, Auckland, New Zealand

December 5, 2000

Abstract

Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given class in a way that is effective enough to preserve the property in which we are interested. In this paper, we show how to transfer a number of computability-theoretic properties from directed graphs to structures in the following classes: symmetric, irreflexive graphs; partial orderings; lattices; rings (with zero-divisors); integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups. This allows us to show that several theorems about degree spectra of relations on computable structures, nonpreservation of computable categoricity, and degree spectra of structures remain true when we restrict our attention to structures in any of the classes on this list. The codings we present are general enough to be viewed as establishing that the theories mentioned above are computably complete in the sense that, for a wide range of computability-theoretic nonstructure type properties, if there are any examples of structures with such properties then there are such examples that are models of each of these theories.

∗Partially supported by an Alfred P. Sloan Doctoral Dissertation Fellowship. Current address:

Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago IL 60637, U.S.A..

∗∗Partially supported by NSF Grants DMS-9503503, DMS-9802843, and INT-9602579.

1 Introduction

With the formalization of the notions of algorithm and computable function in the first half of the twentieth century, and the subsequent development of computability theory, there has been increasing interest in recent decades in investigating the effective content of mathematics. In this paper, we are concerned with the connection between two branches of this effective mathematics program: computable model theory and computable algebra. We assume the reader is familiar with basic concepts of computability theory, model theory, and algebra; standard references are [40], [21], and [28], respectively.

One of the main concerns of computable model theory is the study of computabilitytheoretic properties of countable structures. We will always assume we are working with computable languages. We will denote the domain of a structure A by |A|. (We will not always use calligraphic letters for structures, so A may denote a different structure, usually one isomorphic to A.) Let us for the moment focus on computable structures.

1.1. Definition. A structure A is computable if both |A| and the atomic diagram of (A, a)_{a∈|A|} are computable. If, in addition, the n-quantifier diagram of (A, a)_{a∈|A|} is computable then A is n-decidable, while if the full first-order diagram of (A, a)_{a∈|A|} is computable then A is decidable.

An isomorphism from a structure M to a computable structure is called a computable presentation of M. We often abuse terminology and refer to the image of a computable presentation as a computable presentation. If M has a computable presentation then it is computably presentable.

Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within wellknown classes of algebraic structures, such as groups, rings, lattices, and so forth. As an example, let us consider the computable dimension of computable structures, which is a special case of the following definition. (Here and below, degree means Turing degree.)

1.2. Definition. Given a degree d, the d-computable dimension of a computably presentable structure M is the number of computable presentations of M up to d-com-putable isomorphism. If M has d-computable dimension 1 then it is d-computably categorical.

For an ordinal α, 0^{α}-computably categorical structures are usually called Δ_{α+1}^{0}- categorical structures. An equivalent definition of Δ_{β}^{0}-categoricity, which also works for limit ordinals β, is that a computably presentable structure is Δ_{β}^{0}-categorical if any two of its computable presentations are isomorphic via a Δ_{β}^{0} isomorphism.

It is easy to construct computable structures with computable dimension 1 or ω. Indeed, most familiar structures, and even all members of many familiar classes of structures, have computable dimension 1 or ω. For example, Nurtazin [34] showed that all decidable structures fall into this category. Goncharov [8] later extended this result to 1-decidable structures, and there have been several other well-known algebraic classes of structures for which similar results have been proved.

1.3. Theorem (Goncharov; Goncharov and Dzgoev; Metakides and Nerode; Nurtazin; LaRoche; Remmel). All structures in each of the following classes have computable dimension 1 or ω: algebraically closed fields, real closed fields, Abelian groups, linear orderings, Boolean algebras, and Δ_{2}^{0}-categorical structures.

The result for algebraically closed and real closed fields is implied by the results in [34]; the result for algebraically closed fields was also independently proved in [32]. The result for Abelian groups appears in [10], that for linear orderings independently in [13] and [37], and that for Δ_{2}^{0}-categorical structures in [11]. The result for Boolean algebras appears in full in [12], though it is implicit in earlier work of Goncharov and, independently, in [29].

In most cases, these results were proved via structure theorems, that is, theorems that connect computability-theoretic properties of structures in the relevant classes to their structural properties. For example, a linear ordering with finitely many pairs of adjacent elements is computably categorical, while one with infinitely many such pairs has infinite computable dimension. The methods in this paper can be seen as the development of a nonstructure theory for computable model theory, in the same sense that, for instance, the study of Borel completeness provides such a theory for descriptive set theory. We will comment on this further below.

In light of results such as those mentioned above, an important question early in the development of computable model theory was whether there exist computable structures with finite computable dimension greater than 1. This question was answered positively by Goncharov [9].

1.4. Theorem (Goncharov). For each n > 0 there is a computable structure with computable dimension n.

Further investigation led to examples of computable structures with finite computable dimension greater than 1 in several classes of algebraic structures. In each case, the proof consisted of coding families of computably enumerable (c.e.) sets with a finite number of computable enumerations (up to a suitable notion of computable equivalence of enumerations) in a sufficiently effective way.

1.5. Theorem (Goncharov; Goncharov, Molokov, and Romanovskii; Kudinov). For each n > 0 there are structures with computable dimension n in each of the following classes: graphs, lattices, partial orderings, 2-step nilpotent groups, and integral domains.

The results for partial orderings and (implicitly) graphs appear in [9], and the result for lattices is an easy consequence of the results in that paper. The result for 2-step nilpotent groups (which improves a result in [10]) appears in [15], and that for integral domains in [27].

We now turn to the other computability-theoretic properties of structures with which this paper is concerned, and give examples of the kinds of results we would like to show remain true when we restrict our attention to certain classes of algebraic structures. For more thorough treatments of these and related results, see [24] or the articles in [6].

One way to understand the differences between noncomputably isomorphic computable presentations of a structure M is to compare (from a computability-theoretic point of view) the images in these presentations of additional relations on the domain of M, that is, relations that are not the interpretation in M of relation symbols in the language of M. The study of relations on computable structures began with the work of Ash and Nerode [2], who were concerned with relations that maintain some degree of effectiveness in different computable presentations of a structure.

1.6. Definition. Let U be a relation on the domain of a computable structure A and let ℭ be a class of relations. We say that U is intrinsically ℭ on A if the image of U in any computable presentation of A is in ℭ.

A different way to approach the study of relations on computable structures, introduced by Harizanov and Millar, is to look at the degrees of the images of a relation in different computable presentations of a structure.

1.7. Definition. Let U be a relation on the domain of a computable structure A. The degree spectrum of U on A, which is denoted by DgSp_{A}(U), is the set of degrees of the images of U in all computable presentations of A.

It is easy to give examples of relations on computable structures whose degree spectra are singletons or infinite. Harizanov [16] was the first to give an example of an intrinsically Δ_{2}^{0} relation with a two-element degree spectrum that includes 0. This was improved by Khoussainov and Shore [23] as follows.

1.8. Theorem (Khoussainov and Shore). For each n > 0 there exists an intrinsically c.e. relation U on the domain of a computable structure A of computable dimension n such that DgSp_{A}(U) consists of n distinct c.e. degrees, including 0.

The n = 2 case of the above theorem is also due to Goncharov and Khoussainov [14]. The following result was also proved in [23].

1.9. Theorem (Khoussainov and Shore). For each computable partial ordering P there exists an intrinsically c.e. relation U on the domain of a computable structure A such that (DgSp_{A}(U), ⩽_{T}) ≅ P. If P has a least element then we can pick A and U so that 0 ∈ DgSp_{A}(U).

Later, Hirschfeldt [18] and Khoussainov and Shore [25] independently obtained the following strengthenings of the previous two theorems.

1.10. Theorem (Hirschfeldt; Khoussainov and Shore). Let a_{0}, …, a_{n−1} be c.e. degrees. There exists an intrinsically c.e. relation U on the domain of a computable structure A of computable dimension n such that DgSp_{A}(U) = {a_{0}, …, a_{n−1}}.

1.11. Theorem (Hirschfeldt). Let {A_{i}}_{i∈ω} be a uniformly c.e. collection of c.e. sets. There exists an intrinsically c.e. relation U on the domain of a computable structure A such that DgSp_{A}(U) = {deg(A_{i}) : i ∈ ω}.

A related issue is the question of what happens to the computable dimension of a computably categorical structure when it is expanded by finitely many constants. Millar [33] showed that, with a relatively small additional amount of decidability, computable categoricity is preserved under expansion by finitely many constants.

1.12. Theorem (Millar). If A is computably categorical and 1-decidable then any expansion of A by finitely many constants remains computably categorical.

However, preservation of categoricity does not hold in general, as was shown by Cholak, Goncharov, Khoussainov, and Shore [4].

1.13. Theorem (Cholak, Goncharov, Khoussainov, and Shore). For each k > 0 there exist a computably categorical structure A and an a ∈ |A| such that (A, a) has computable dimension k.

In fact, as shown by Hirschfeldt, Khoussainov, and Shore [19], not even finiteness of computable dimensionality is always preserved under expansion by a constant.

1.14. Theorem (Hirschfeldt, Khoussainov, and Shore). There are a computably categorical structure A and an a ∈ |A| such that (A, a) has computable dimension ω.

Another important topic in computable model theory is studying the complexity of the isomorphisms between different computable presentations of a structure. We say that a computable structure is strictly Δ_{α}^{0}-categorical if it is Δ_{α}^{0}-categorical but not Δ_{β}^{0}-categorical for any β < α. The following result was proved by Ash in [1].

1.15. Theorem (Ash). For each computable limit ordinal δ (including δ = 0) and each n ∈ ω, there is a strictly Δ_{δ+2n}^{0}-categorical well-ordering.

The work of computable model theory is not restricted to computable structures, of course. When a countable structure is not computably presentable, it is of interest to find out just how far from being computably presentable it is. One way to measure this is to look at the degrees of presentations of the structure.

1.16. Definition. Let d be a degree. A structure A with computable domain is dcomputable if the atomic diagram of (A, a)_{a∈|A|} is d-computable. The degree of A, denoted by deg(A), is the least degree d (which always exists) such that A is d-computable.

An isomorphism from a structure M to a (d-computable) structure with computable domain is called a (d-computable) presentation of M. We often abuse terminology and refer to the image of a (d-computable) presentation as a (d-computable) presentation. In particular, when we refer to the degree of a presentation, we always mean the degree of the image, rather than that of the isomorphism. If M has a d-computable presentation then it is d-computably presentable.

A countable structure M is relatively computably categorical if any two presentations M, M′ of M are isomorphic via a (deg(M) ∨ deg(M′))-computable isomorphism.

Every countable structure is isomorphic to a structure with computable domain. Therefore, whenever we mention a countable structure we assume that it has computable domain, so that it may be thought of as a presentation of itself.

1.17. Definition. The degree spectrum of a countable structure A, which is denoted by DgSp(A), is the set of degrees of presentations of A.

As shown by Knight [26], in all nontrivial cases, the degree spectrum of a countable structure is closed upwards.

1.18. Definition. A countable structure A is trivial if for some finite set S of elements of |A|, every permutation of |A| that keeps the elements of S fixed is an automorphism of A.

1.19. Theorem (Knight). If A is a nontrivial countable structure then DgSp(A) is closed upwards.

Trivial structures are not very interesting from the point of view of computable model theory, and obviously cannot occur within certain classes of structures, such as rings of characteristic 0. Thus we will restrict our attention to nontrivial structures.

Any set that is computable in every nonzero degree is in fact computable, but as shown independently by Slaman [39] and Wehner [41], the analogous fact is not true of structures.

1.20. Theorem (Slaman; Wehner). There is a structure A that has presentations of every degree except 0. (In other words, DgSp(A) = D − {0}, where D is the set of all degrees.)

In the original proofs of Theorems 1.8–1.11, 1.13, and 1.14, the structures in question were directed graphs, and the relations mentioned in Theorems 1.8–1.11 were unary. The structures in the proofs of Theorem 1.20 had more complicated signatures, but could easily be modified to be directed graphs (for instance, by the method outlined in Appendix A). It is natural to ask, in the spirit of what was done for structures of finite computable dimension, for which theories these theorems remain true if we require that A be a model of the given theory. Our main result gives a partial answer to this question.

The following condition on a theory T is clearly sufficient for the theorems mentioned in the previous paragraph, as well as other similar results, to remain true when we restrict our attention to models of T.

1.21. Definition. A theory T is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations if for every nontrivial countable graph G there is a nontrivial A ⊨ T with the following properties.

1. DgSp(A) = DgSp(G).

2. If G is computably presentable then the following hold.

(a) For any degree d, A has the same d-computable dimension as G.

(b) If x ∈ |G| then there exists an a ∈ |A| such that (A, a) has the same computable dimension as (G, x).

(c) If S ⊆ |G| then there exists a U ⊆ |A| such that DgSp_{A}(U) = DgSp_{G}(S) and if S is intrinsically c.e. then so is U.

The terminology adopted in Definition 1.21 suggests that a theory satisfying this definition should still satisfy it if “every nontrivial countable graph G” is replaced by “every nontrivial countable structure G”. This is indeed the case, since it is not hard to code a countable structure into a countable graph in a highly effective way. We give such a coding in Appendix A.

We can now state our main result.

1.22. Theorem. Let T be any of the following theories: symmetric, irreflexive graphs; partial orderings; lattices; rings (with zero-divisors); integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups. Then T is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A ⊨ T. Furthermore, Theorems 1.8–1.11 remain true if we also require that U be a submodel of A.

Notice that, by Theorem 1.3, this result cannot be extended from partial orderings to linear orderings, from lattices to Boolean algebras, or from commutative semigroups and 2-step nilpotent groups to Abelian groups. A natural open question is what is the situation for fields. It is not even known whether there exist fields of finite computable dimension greater than 1. Of course, some of the theorems mentioned in our main result do not involve finite computable dimension, and thus could in principle still hold for some of the classes mentioned in Theorem 1.3. For instance, in the case of linear orderings, Hirschfeldt [17] has shown that Theorem 1.8 does not hold, but whether Theorem 1.20 holds is still an open question (see [5] for a discussion of this question).

The rest of this paper is dedicated to the proof of Theorem 1.22. Most of the cases are handled by coding graphs with the desired properties into models of the given theories in a way that is effective enough to preserve these properties. This approach is much simpler and more general than attempting to adapt the original proofs of the relevant theorems. Furthermore, our codings are sufficiently effective to make similar results that might be proved for graphs in the future carry over to the classes of structures mentioned in Theorem 1.22 without additional work.

As mentioned above, our results fit into a framework that has become important in several areas of mathematical logic and theoretical computer science, namely the study of dichotomies between structure theory, represented here by results such as Theorem 1.3, and nonstructure theorems, the latter often proved by coding structures that are known to be “as complicated as possible” into the particular structures being studied. In model theory, interpretations of various kinds have long been used to transfer model-theoretic properties from classes of structures in which they are easy to determine to other classes in which they are less obvious. One example is Mekler [31]. In descriptive set theory, the study of Borel reducibilities and Borel completeness has received much attention in recent years, for example in Friedman and Stanley [7], Hjorth and Kechris [20], and Camerlo and Gao [3]. A recent survey is Kechris [22]. Another example of the use of codings to show that certain phenomena that can occur in general already occur in what would seem to be a much more restricted setting is the work of Peretyat’kin [35] on finitely axiomatizable theories, which touches on both classical and computable model theory. Probably best-known of all, of course, is the use of highly effective reducibilities in complexity theory to show that certain problems are complete for various complexity classes, which is modeled on the use of reducibilities to prove index set results in computability theory.

In all the examples mentioned above, uncovering the correct notions of reducibility is essential. In Sections 2 and 4, we present sufficient conditions for a coding of a graph into a structure to be effective enough for our purposes. These conditions will be useful in all cases except that of nilpotent groups, in which, instead of coding graphs, we code rings into nilpotent groups. Even in this case, the properties of the coding that must be verified are very similar to those in our general conditions.

Section 3 deals with undirected graphs, partial orderings, and lattices, Section 4 with rings, Section 5 with integral domains and commutative semigroups, and Section 6 with 2-step nilpotent groups.

2 A Sufficient Condition

In this section, we give a sufficient condition for a coding of a graph into a structure to be effective enough for our purposes. This condition is far from being the most general one we could give, but it is sufficient for our needs. It corresponds to an especially effective version of interpretations of theories (in the standard model-theoretic sense) in which equality is interpreted as equality. In Section 4, we will present a generalization of this condition which corresponds to interpretations in which equality is interpreted as an equivalence relation. (See chapter 5 of [21] for more on interpretations of theories.) We begin with a few definitions.

2.1. Definition. A relation U on a structure M is invariant if for every automorphism f : M ≅ M we have f(U) = U.

2.2. Definition. Let d be a degree. A d-computable defining family for a structure M is a d-computable set of existential formulas φ_{0}(a⃗, x), φ_{1}(a⃗, x), … such that a⃗ is a tuple of elements of |M|, each x ∈ |M| satisfies some φ_{i}, and no two elements of |M| satisfy the same φ_{i}.

Because we will be dealing with arbitrary presentations, rather than only computable ones, we will need to consider the relativized version of the notion of intrinsic computability.

2.3. Definition. A relation U on the domain of a structure A is relatively intrinsically computable if for every presentation f : A ≅ A, the image f(U) is computable in deg(A).

Now let G be a nontrivial, countable directed graph with edge relation E and let A be a countable structure. Assume that there exist relatively intrinsically computable, invariant relations D(x) and R(x, y) on the domain of A and a map G ↦ A_{G} from the set of presentations of G to the set of presentations of A with the following properties. (We will use the notation D(A_{G}) instead of D^{A_{G}} to emphasize that we think of D(A_{G}) as a subset of |A_{G}|.)

(P0) For every presentation G of G, the structure A_{G} is deg(G)-computable.

(P1) For every presentation G of G there is a deg(G)-computable map g_{G} : D(A_{G}) ⟶_{onto}^{1–1} |G| such that R^{A_{G}}(x, y) ⇔ E^{G}(g_{G}(x), g_{G}(y)) for every x, y ∈ D(A_{G}).

(P2) If f : D(A) ⟶_{onto}^{1–1} D(A) is such that R(x, y) ⇔ R(f(x), f(y)) then f can be extended to an automorphism of A.

(P3) For every presentation G of G there exists a deg(G)-computable defining family for (A_{G}, b)_{b∈D(A_{G})}, that is, a deg(G)-computable set of existential formulas φ_{0}(a⃗, b⃗_{0}, x), φ_{1}(a⃗, b⃗_{1}, x), … such that a⃗ is a tuple of elements of |A_{G}|, each b⃗_{i} is a tuple of elements of D(A_{G}), each x ∈ |A_{G}| satisfies some φ_{i}, and no two elements of |A_{G}| satisfy the same φ_{i}.

We wish to show that the following hold.

1. DgSp(A) = DgSp(G).

2. If G is computably presentable then

(a) for any degree d, A has the same d-computable dimension as G;

(b) if x ∈ |G| then there exists an a ∈ D(A) such that (A, a) has the same computable dimension as (G, x); and

(c) if S ⊆ |G| then there exists a U ⊆ D(A) such that DgSp_{A}(U) = DgSp_{G}(S) and if S is intrinsically c.e. then so is U.

Remark. We will use condition (P3) only for computable presentations, but all our examples below satisfy (P3) as stated, and this fact could be useful for future results.

We begin with a series of lemmas.

2.4. Lemma. Let A and G be computable presentations of A and G, respectively, and let f : A ≅ A_{G}. Then f is deg(f ↾ D(A))-computable.

Proof. It is enough to show that f^{−1} is deg(f ↾ D(A))-computable. Given x ∈ |A_{G}|, find an i ∈ ω such that A_{G} ⊨ φ_{i}(a⃗, b⃗_{i}, x), where φ_{i}(a⃗, b⃗_{i}, x) is as in (P3). By definition, x is the only element of |A_{G}| that satisfies φ_{i}. Thus there exists a unique y ∈ |A| such that A ⊨ φ_{i}(f^{−1}(a⃗), f^{−1}(b⃗_{i}), y), and f^{−1}(x) = y. Since both A_{G} and A are computable, f^{−1} is deg(f ↾ D(A))-computable.

2.5. Lemma. Let A and G be computable presentations of A and G, respectively. Suppose that there exists a map f : D(A) ⟶_{onto}^{1–1} D(A_{G}) such that R^{A}(x, y) ⇔ R^{A_{G}}(f(x), f(y)) for each x, y ∈ D(A). Then f can be extended to a deg(f)-computable isomorphism f̂: A ≅ A_{G}.

Proof. Since A and A_{G} are both presentations of A, there exists an isomorphism h : A ≅ A_{G}. Let k = h ↾ D(A). Then c = f ∘k^{−1} is a one-to-one map from D(A_{G}) onto itself such that R^{A_{G}}(x, y) ⇔ R^{A_{G}}(c(x), c(y)) for each x, y ∈ D(A_{G}). So, by (P2), c can be extended to ĉ: A_{G} ≅ A_{G}. Now let f̂ = ĉ ∘ h. Then f̂: A ≅ A_{G} and f̂ ↾ D(A) = f ∘ k^{−1} ∘ k = f. Lemma 2.4 implies that f̂ is deg(f)-computable.

2.6. Lemma. If G and G′ are computable presentations of G and h : G ≅ G′ is an isomorphism then there exists a deg(h)-computable isomorphism f̂ : A_{G} ≅ A_{G′} such that f̂ ↾ D(A_{G}) = g_{G′}^{−1} ∘ h ∘ g_{G}.

Proof. Let f : D(A_{G}) ⟶_{onto}^{1–1} D(A_{G′}) be defined by f = g_{G′}^{−1} ∘ h ∘ g_{G}. Clearly, f is deg(h)-computable. Furthermore, for each x, y ∈ D(A_{G}) we have R^{A_{G}}(x, y) ⇔ E^{G}(g_{G}(x), g_{G}(y)) ⇔ E^{G′}((h∘g_{G})(x), (h∘g_{G})(y)) ⇔ R^{A_{G′}}(f(x), f(y)). So, by Lemma 2.5, there exists a deg(h)-computable isomorphism f̂: A_{G} ≅ A_{G′} extending f.

For any presentation A of A, let G̃_{A} be the graph whose domain is D(A), with an edge between x and y if and only if R^{A}(x, y). Clearly, there exist a deg(A)-computable map h_{A} and a deg(A)-computable graph G_{A} such that h_{A} : G̃_{A} → G_{A} is a deg(A)- computable presentation of G̃_{A}. If A is computable then we take G_{A} = G̃_{A} and let h_{A} be the identity. In any case, it is easy to check that G_{A} is a deg(A)-computable presentation of G.

2.7. Lemma. If A and A′ are computable presentations of A and f : A ≅ A′ is an isomorphism then f ↾ D(A) is a deg(f)-computable isomorphism from G_{A} to G_{A′}.

Proof. We have E^{G_{A}}(x, y) ⇔ R^{A}(x, y) ⇔ R^{A′}(f(x), f(y)) ⇔ E^{G_{A′}}(f(x), f(y)). Since |G_{A}| = D(A) and |G_{A′}| = D(A′), it follows that f ↾ D(A) is an isomorphism from G_{A} to G_{A′}.

2.8. Lemma. If G is a computable presentation of G then g_{G} is a computable isomorphism from G_{A_{G}} to G.

Proof. If x, y ∈ |G_{A_{G}}| then E^{G_{A_{G}}}(x, y) ⇔ R^{A_{G}}(x, y) ⇔ E^{G}(g_{G}(x), g_{G}(y)). Thus g_{G} is a computable isomorphism from G_{A_{G}} to G.

2.9. Lemma. If A is a computable presentation of A then there exists a computable isomorphism f : A ≅ A_{G_{A}} such that f ↾ D(A) = g_{G_{A}}^{−1} ∘ h_{A}.

Proof. The map g_{G_{A}}^{−1} ∘ h_{A} is computable, and for each x, y ∈ D(A) we have R^{A}(x, y) ⇔ E^{G_{A}}(x, y) ⇔ R^{A_{G_{A}}}((g_{G_{A}}^{−1} ∘ h_{A})(x), (g_{G_{A}}^{−1} ∘ h_{A})(y)). So, by Lemma 2.5, g_{G_{A}}^{−1} ∘ h_{A} can be extended to a computable isomorphism from A to A_{G_{A}}.

We are now ready to show that 1 and 2.a–c above hold.

2.10. Proposition. DgSp(A) = DgSp(G).

Proof. First note that, since G is nontrivial, (P1) implies that A is nontrivial. For any presentation G of G, (P0) implies that deg(A_{G}) ⩽ deg(G), so, by Theorem 1.19, there is a presentation A of A such that deg(A) = deg(G). Thus DgSp(G) ⊆ DgSp(A).

On the other hand, for any presentation A of A, it follows from the definition of G_{A} that deg(G_{A}) ⩽ deg(A), so, by Theorem 1.19, there is a presentation G of G such that deg(G) = deg(A). Thus DgSp(A) ⊆ DgSp(G).

Now assume that G is computably presentable.

2.11. Proposition. For any degree d, A has the same d-computable dimension as G.

Proof. Let G and G′ be computable presentations of G that are not d-computably isomorphic. By Lemma 2.8, G_{A_{G}} and G_{A_{G′}} are not d-computably isomorphic. Thus, by Lemma 2.7, A_{G} and A_{G′} are not d-computably isomorphic. So the d-computable dimension of A is greater than or equal to that of G.

Now let A and A′ be computable presentations of A that are not computably isomorphic. By Lemma 2.9, A_{G_{A}} and A_{G_{A′}} are not d-computably isomorphic. Thus, by Lemma 2.6, G_{A} and G_{A′} are not d-computably isomorphic. So the d-computable dimension of G is greater than or equal to that of A.

2.12. Proposition. Let x ∈ |G|. There exists an a ∈ D(A) such that (A, a) has the same computable dimension as (G, x).

Proof. Let f : G ≅ G be a computable presentation of G, let h : A ≅ A_{G} be an isomorphism, and let a = (h^{−1} ∘ g_{G}^{−1} ∘ f)(x). By Lemma 2.6, for every computable presentation f′ : G ≅ G′ of G there exists an isomorphism k : A ≅ A_{G′} such that a = (k^{−1} ∘ g_{G′}^{−1} ∘ f′)(x). The rest of the proof is similar to the proof of Proposition 2.11.

Let (G, x^{G}) and (G′, x^{G′}) be computable presentations of (G, x) that are not computably isomorphic. By Lemma 2.8, (G_{A_{G}}, g_{G}^{−1}(x^{G})) and (G_{A_{G′}}, g_{G′}^{−1}(x^{G′})) are not computably isomorphic. Thus, by Lemma 2.7, (A_{G}, g_{G}^{−1}(x^{G})) and (A_{G′}, g_{G′}^{−1}(x^{G′})) are not computably isomorphic. So the computable dimension of (A, a) is greater than or equal to that of (G, x).

Now let (A, a^{A}) and (A′, a^{A′}) be computable presentations of (A, a) that are not computably isomorphic. By Lemma 2.9, (A_{G_{A}}, g_{G_{A}}^{−1}(a^{A})) and (A_{G_{A′}}, g_{G_{A′}}^{−1}(a^{A′})) are not computably isomorphic. Thus, by Lemma 2.6, (G_{A}, a^{A}) and (G_{A′}, a^{A′}) are not computably isomorphic. So the computable dimension of (G, x) is greater than or equal to that of (A, a).

2.13. Proposition. Let S ⊆ |G|. There exists a U ⊆ D(A) such that DgSp_{A}(U) = DgSp_{G}(S) and if S is intrinsically c.e. then so is U.

Proof. Let f : G ≅ G be a computable presentation of G, let h : A ≅ A_{G} be an isomorphism, and let U = (h^{−1} ∘ g_{G}^{−1} ∘ f)(S).

Let f′ : G ≅ G′ be a computable presentation of G. By Lemma 2.6, there exists an isomorphism k : A ≅ A_{G′} such that U = (k^{−1} ∘ g_{G′}^{−1} ∘ f′)(S). Since g_{G′} is computable, deg(f′(S)) = deg(k(U)) ∈ DgSp_{A}(U). So DgSp_{G}(S) ⊆ DgSp_{A}(U).

Now let k : A ≅ A be a computable presentation of A. We claim that there exists an isomorphism m : G ≅ G_{A} such that S = (m^{−1} ∘ k)(U). Indeed, let f, G, and h be as above. Then S = (f^{−1} ∘ g_{G} ∘ h)(U), so if we let m = k ∘ h^{−1} ∘ g_{G}^{−1} ∘ f then (m^{−1} ∘ k)(U) = (f^{−1} ∘ g_{G} ∘ h ∘ k^{−1} ∘ k)(U) = (f^{−1} ∘ g_{G} ∘ h)(U) = S. Furthermore, it is not hard to check that m : G ≅ G_{A}. This establishes our claim, which implies that deg(k(U)) = deg(m(S)) ∈ DgSp_{G}(S) and that if m(S) is c.e. then so is k(U). So DgSp_{A}(U) ⊆ DgSp_{G}(S), and if S is intrinsically c.e. then so is U.

We conclude from the previous four propositions that, given a theory T, if for every nontrivial, countable directed graph G we can find A ⊨ T and relations D and R satisfying properties (P0)–(P3), then T is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. But it is not actually necessary that we be able to code every nontrivial countable graph into a model of T, as long as we can code enough such graphs.

2.14. Proposition. Let T be a theory and let C be a theory of directed graphs that is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. If for every nontrivial countable G ⊨ C we can find A ⊨ T and relatively intrinsically computable, invariant relations D and R satisfying properties (P0)–(P3) then T is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations.

3 Simple Codings

Coding symmetric, irreflexive graphs into structures is usually easier than coding arbitrary directed graphs. Thus we begin this section by showing that the theory of symmetric, irreflexive graphs is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. We then show how to apply this result to partial orderings and lattices.

3.1 Undirected Graphs

Let G be a countably infinite directed graph with edge relation E. The deg(G)- computably presentable symmetric, irreflexive graph H_{G} = (|H_{G}|, F) is defined as follows. (Recall that it makes sense to talk of deg(G) because we think of any countable structure as a presentation of itself.)

1. |H_{G}| = {a, â, b} ∪ {c_{i}, d_{i}, e_{i} : i ∈ |G|}.

2. F (x, y) holds only in the following cases.

(a) F (a, â) and F (â, a).

(b) For all i ∈ |G|,

i. F (a, c_{i}) and F (c_{i}, a),
ii. F (b, e_{i}) and F (e_{i}, b),
iii. F (c_{i}, d_{i}) and F (d_{i}, c_{i}),
iv. F (d_{i}, e_{i}) and F (e_{i}, d_{i}).

(c) If E(i, j) then F (c_{i}, e_{j}) and F (e_{j}, c_{i}).

As an example, Figure 1 shows a portion of the graph H_{G} in the case in which E(0, 1), E(1, 0), E(1, 2), E(2, 2), ¬E(0, 0), ¬E(0, 2), ¬E(1, 1), ¬E(2, 0), and ¬E(2, 1). On the left is H_{G} itself; on the right is a picture highlighting the edges (and missing edges) that are used to code E: edges that code positive facts about E are pictured as solid lines, missing edges that code negative facts about E are pictured as dotted lines, and all other edges are pictured as dashed lines.

[figure: a; â; c_{0}; c_{1}; c_{2}; d_{0}; d_{1}; d_{2}; e_{0}; e_{1}; e_{2}; b; a; â; c_{0}; c_{1}; c_{2}; d_{0}; d_{1}; d_{2}; e_{0}; e_{1}; e_{2}; b]

Figure 1: A portion of H_{G}

Let a, â, b, and c_{i} be as in the definition of H_{G} and define

D(x) = {x ∈ |H_{G}| : x ≠ â ∧ F (a, x)} = {c_{i} : i ∈ |G|}

and

R(x, y) = {(x, y) : D(x) ∧ D(y) ∧ ∃d, e(F (b, e) ∧ F (y, d) ∧ F (d, e) ∧ F (x, e))}.

Clearly, D is relatively intrinsically computable, and so is R, since, for x, y ∈ D(H_{G}),

∃d, e(F (b, e) ∧ F (y, d) ∧ F (d, e) ∧ F (x, e)) ⇔ ¬∃d, e(F (b, e) ∧ F (y, d) ∧ F (d, e) ∧ ¬F (x, e)).

To see that D and R are invariant, it is enough to notice that x = a is the only element of H_{G} that satisfies the formula

∃^{∞}y(F (x, y)) ∧ ∃z(F (x, z) ∧ ∀w(F (w, z) → w = x)),

x = â is the only element of H_{G} that satisfies

F (x, a) ∧ ∀y(F (x, y) → y = a),

and x = b is the only element of H_{G} that satisfies

∃^{∞}y(F (x, y)) ∧ ¬F (a, x) ∧ ¬∃z(F (a, z) ∧ F (x, z)).

Fix a deg(G)-computable presentation of H_{G} for which the map g_{G} : c_{i} ↦ i is deg(G)-computable and identify H_{G} with this presentation.

Let G′ be a presentation of G. The deg(G′)-computable symmetric, irreflexive graph H_{G′} and the deg(G′)-computable map g_{G′} are defined in an analogous way.

Clearly, H_{G′} ≅ H_{G}, so H_{G′} is a deg(G′)-computable presentation of H_{G}. Furthermore, it is easy to check that D(H_{G′}) = dom(g_{G′}) and R^{H_{G′}}(x, y) ⇔ E^{G′}(g_{G′}(x), g_{G′}(y)).

If f : D(H_{G}) ⟶_{onto}^{1–1} D(H_{G}) is such that R(x, y) ⇔ R(f(x), f(y)) then we can extend f as follows. Let a, â, b, d_{i}, and e_{i} be as in the definition of H_{G}. Let f(a) = a, f(â) = â, f(b) = b, f(d_{i}) = d_{(g_{G}∘f)(c_{i})}, and f(e_{i}) = e_{(g_{G}∘f)(c_{i})}. It can be easily verified that this extended map is an automorphism of H_{G}.

Finally, let a, â, and b be as in the definition of H_{G} and consider the deg(G)- computable set of formulas

{x = a, x = â, x = b} ∪ {x = c : c ∈ D(H_{G})} ∪

{x ≠ a ∧ F (c, x) ∧ ¬F (b, x) : c ∈ D(H_{G})} ∪ {F (b, x) ∧ ∃d(F (c, d) ∧ F (d, x)) : c ∈ D(H_{G})}.

Clearly, every x ∈ |H_{G}| satisfies some formula in this set, with no two elements satisfying the same formula, so this set is a deg(G)-computable defining family for (H_{G}, z)_{z∈D(H_{G})}.

For any presentation G′ of G, a deg(G′)-computable defining family for (H_{G′}, z)_{z∈D(H_{G′})} can be defined in an analogous way.

Theorem 1.22 in the case of symmetric, irreflexive graphs now follows from Proposition 2.14.

3.1. Theorem. The theory of symmetric, irreflexive graphs is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A be a symmetric, irreflexive graph.

Thus we may take the theory C in Proposition 2.14 to be the theory of symmetric, irreflexive graphs.

3.2 Partial Orderings

Let G be a symmetric, irreflexive, countably infinite computable graph with edge relation E. The deg(G)-computably presentable partial ordering P_{G} = (|P_{G}|, ≺) is defined as follows.

1. |P_{G}| = {a, b} ∪ {c_{i} : i ∈ |G|} ∪ {d_{i,j} : i < j ∧ i, j ∈ |G|}.

2. The relation ≺ is the smallest transitive relation on |P_{G}| satisfying the following conditions.

(a) a ≺ c_{i} ≺ b for all i ∈ |G|.

(b) If i < j and E(i, j) then d_{i,j} ≺ c_{i}, c_{j}.

(c) If i, j ∈ |G|, i < j, and ¬E(i, j), then c_{i}, c_{j} ≺ d_{i,j}.

As an example, Figure 2 shows a portion of the partial ordering P_{G} in the case in which E(0, 1), E(1, 2), and ¬E(0, 2). An arrow from x to y represents the fact that x ≺ y. The solid arrows represent facts used to code E.

Let a, b, and c_{i} be as in the definition of P_{G} and define

D(x) = {x ∈ |P_{G}| : a ≺ x ≺ b} = {c_{i} : i ∈ |G|}

and

R(x, y) = {(x, y) : x ≠ y ∧ D(x) ∧ D(y) ∧ ∃z ≠ a(z ≺ x, y)}.

[figure: b; d_{0,2}; c_{0}; c_{1}; c_{2}; d_{0,1}; a; d_{1,2}]

Figure 2: A portion of P_{G}

Clearly, D is relatively intrinsically computable and invariant, and so is R, since

∃z ≠ a(z ≺ x, y) ⇔ ¬∃z ≠ b(x, y ≺ z).

(Invariance follows from the fact that a is the only element of P_{G} with infinitely many elements above it and b is the only element of P_{G} with infinitely many elements below it.)

Fix a deg(G)-computable presentation of P_{G} for which the map g_{G} : c_{i} ↦ i is deg(G)-computable and identify P_{G} with this presentation.

Let G′ be a presentation of G. The deg(G′)-computable partial ordering P_{G′} and the deg(G′)-computable map g_{G′} are defined in an analogous way.

Clearly, P_{G′} ≅ P_{G}, so P_{G′} is a deg(G′)-computable presentation of P_{G}. Furthermore, it is easy to check that D(P_{G′}) = dom(g_{G′}) and R^{P_{G′}}(x, y) ⇔ E^{G′}(g_{G′}(x), g_{G′}(y)).

If f : D(P_{G}) ⟶_{onto}^{1–1} D(P_{G}) is such that R(x, y) ⇔ R(f(x), f(y)) then we can extend f as follows. Let a, b, and d_{i,j} be as in the definition of P_{G}. Let f(a) = a, f(b) = b, and

f(d_{i,j}) = \begin{cases}d_{(g_{G}∘f)(c_{i}),(g_{G}∘f)(c_{j})} & if (g_{G} ∘ f)(c_{i}) < (g_{G} ∘ f)(c_{j}), \\ d_{(g_{G}∘f)(c_{j}),(g_{G}∘f)(c_{i})} & otherwise. \end{cases}

It can be easily verified that this extended map is an automorphism of P_{G}.

Finally, let a and b be as in the definition of P_{G} and consider the deg(G)-computable set of formulas

{x = a, x = b} ∪ {x = c : c ∈ D(P_{G})} ∪ {((x ≺ c, c′) ∨ (c, c′ ≺ x)) ∧ x ≠ a ∧ x ≠ b : c ≠ c′ ∧ c, c′ ∈ D(P_{G})}.

Clearly, every x ∈ |P_{G′}| satisfies some formula in this set, with no two elements satisfying the same formula, so this set is a deg(G)-computable defining family for (P_{G}, z)_{z∈D(P_{G})}.

For any presentation G′ of G, a deg(G′)-computable defining family for (P_{G′}, z)_{z∈D(P_{G′})} can be defined in an analogous way.

Theorem 1.22 in the case of partial orderings now follows from Proposition 2.14, with the theory C mentioned in that proposition being the theory of symmetric, irreflexive graphs.

3.2. Theorem. The theory of partial orderings is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A be a partial ordering.

3.3 Lattices

Let G be a symmetric, irreflexive, countably infinite graph with edge relation E. We may assume that G has at least one node that is not connected to any other node, since the theory of graphs with this property is clearly complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations.

The deg(G)-computably presentable lattice L_{G} = (|L_{G}|, ⋏, ⋎) is the unique lattice satisfying the following conditions.

1. |L_{G}| = {a, b, k} ∪ {c_{i}, m_{i} : i ∈ |G|} ∪ {d_{i,j} : i < j ∧ E(i, j)}.

2. For all x, y ∈ |L_{G}|, if x ≠ y then x ⋎ y = a and x ⋏ y = b, except as required to satisfy the following conditions.

(a) If i < j and E(i, j) then c_{i} ⋎ c_{j} = d_{i,j}.

(b) If i ∈ |G| then k ⋎ c_{i} = m_{i}.

As an example, Figure 3 shows a portion of the lattice L_{G} in the case in which E(0, 1), E(1, 2), and ¬E(0, 2). To simplify the picture, we omit the top element a and the bottom element b of the lattice. The coding of E is done on the left side of the picture, where d_{0,1} and d_{1,2} are. Remark. It is interesting to note that L_{G} has height 4. Clearly, any lattice of height less than 4 is relatively computably categorical.

[figure: d_{0,1}; d_{1,2}; m_{0}; m_{1}; m_{2}; c_{0}; c_{1}; c_{2}; k]

Figure 3: A portion of L_{G}

Let a, b, k, and c_{i} be as in the definition of L_{G} and define

D(x) = {x ∈ |L_{G}| : (k ⋎ x ≠ a) ∧ (k ⋎ x ≠ x)} = {c_{i} : i ∈ |G|}

and

R(x, y) = {(x, y) : (x ≠ y) ∧ D(x) ∧ D(y) ∧ (x ⋎ y ≠ a)}.

Clearly, D and R are relatively intrinsically computable. To see that they are also invariant, it is enough to notice that, because of our assumption that G has an isolated node, k is the only element of L_{G} whose join with any level-2 element of L_{G} is not a.

Fix a deg(G)-computable presentation of L_{G} for which the map g_{G} : c_{i} ↦ i is deg(G)-computable and identify L_{G} with this presentation.

Let G′ be a presentation of G. The deg(G′)-computable lattice L_{G′} and the deg(G′)- computable map g_{G′} are defined in an analogous way.

Clearly, L_{G′} ≅ L_{G}, so L_{G′} is a deg(G′)-computable presentation of L_{G}. Furthermore, it is easy to check that D(L_{G′}) = dom(g_{G′}) and R^{L_{G′}}(x, y) ⇔ E^{G′}(g_{G′}(x), g_{G′}(y)).

If f : D(L_{G}) ⟶_{onto}^{1–1} D(L_{G}) is such that R(x, y) ⇔ R(f(x), f(y)) then we can extend f as follows. Let a, b, k, m_{i}, and d_{i,j} be as in the definition of L_{G}. Let f(a) = a, f(b) = b, f(k) = k, f(m_{i}) = m_{(g_{G}∘f)(c_{i})}, and

f(d_{i,j}) = \begin{cases}d_{(g_{G}∘f)(c_{i}),(g_{G}∘f)(c_{j})} & if (g_{G} ∘ f)(c_{i}) < (g_{G} ∘ f)(c_{j}), \\ d_{(g_{G}∘f)(c_{j}),(g_{G}∘f)(c_{i})} & otherwise. \end{cases}

It can be easily verified that this extended map is an automorphism of L_{G}.

Finally, let a, b, and k be as in the definition of L_{G} and consider the deg(G)- computable set of formulas

{x = a, x = b, x = k} ∪ {x = c : c ∈ D(L_{G})} ∪ {c ⋎ c′ = x : (c, c′) ∈ R^{L_{G}}} ∪ {k ⋎ c = x : c ∈ D(L_{G})}.

Clearly, every x ∈ |L_{G}| satisfies some formula in this set, with no two elements satisfying the same formula, so this set is a deg(G)-computable defining family for (L_{G}, z)_{z∈D(L_{G})}. For any presentation G′ of G, a deg(G′)-computable defining family for (L_{G′}, z)_{z∈D(L_{G′})} can be defined in an analogous way.

Since, for any computable presentation L of L_{G}, the sublattice of L generated by any subset S of D(L) has the same degree as S, and is c.e. if S is c.e., Theorem 1.22 in the case of lattices now follows from Proposition 2.14, with the theory C mentioned in that proposition being the theory of symmetric, irreflexive graphs with at least one isolated node.

3.3. Theorem. The theory of lattices is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A be a lattice. Furthermore, Theorems 1.8–1.11 remain true if we also require that U be a sublattice of A.

4 A Weaker Sufficient Condition and Its Application to Rings

In this section we give a strengthening of Proposition 2.14 which will be used in the next section, as well as an example of its application to rings. If Q is an equivalence relation on a set D then by a set of Q-representatives we mean a set of elements of D containing exactly one member of each Q-equivalence class.

4.1. Proposition. Let T be a theory and let C be a theory of directed graphs that is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. Suppose that for every nontrivial countable G ⊨ C we can find an A ⊨ T; relatively intrinsically computable, invariant relations D(x), Q(x, y), and R(x, y) on |A|; and a map G ↦ A_{G} from the set of presentations of G to the set of presentations of A with the following properties.

(P0) For every presentation G of G, the structure A_{G} is deg(G)-computable.

(P1′) For every presentation G of G there is a deg(G)-computable map g_{G} : D(A_{G}) ⟶^{onto} |G| such that, for all x, y ∈ D(A_{G}), we have R^{A_{G}}(x, y) ⇔ E^{G}(g_{G}(x), g_{G}(y)) and Q^{A_{G}}(x, y) ⇔ (g_{G}(x) = g_{G}(y)). (Note that this implies that Q is an equivalence

relation and that if Q(x, x′) and Q(y, y′) then R(x, y) ⇔ R(x′, y′).)

(P2′) For every pair S, S′ of sets of Q-representatives, if f : S ⟶_{onto}^{1–1} S′ is such that R(x, y) ⇔ R(f(x), f(y)) for every x, y ∈ S then f can be extended to an automorphism of A.

(P3′) If G is a presentation of G and S is a deg(G)-computable set of Q^{A_{G}}-represen-tatives then there exists a deg(G)-computable defining family for (A_{G}, a)_{a∈S}.

Then T is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. Furthermore, in each of Theorems 1.8–1.11 with the extra requirement that A ⊨ T, the relation U can be chosen so that U ⊆ D(A) and Q(x, y) ⇒ (U(x) ⇔ U(y)).

Proof. It is enough to show that if the nontrivial countable graph G ⊨ C and the model A ⊨ T satisfy (P0) and (P1′)–(P3′) then Propositions 2.10–2.13 hold of G and A and, in Proposition 2.13, U can be chosen so that Q(x, y) ⇒ (U(x) ⇔ U(y)). The argument is similar to what was done in Section 2, so we present only the necessary changes. We begin with two remarks.

4.2. Remark. If G is a presentation of G and S is a set of Q^{A_{G}}-representatives then g_{G} ↾ S is one-to-one.

4.3. Remark. If S and S′ are sets of Q-representatives and f : S ⟶_{onto}^{1–1} S′ is such that Q(x, f(x)) for every x ∈ S then (P1′) implies that R(x, y) ⇔ R(f(x), f(y)) for every x, y ∈ S, so that, by (P2′), f can be extended to an automorphism of A.

We now need new versions of Lemmas 2.4 and 2.5.

4.4. Lemma. Let A and G be computable presentations of A and G, respectively, let S be a computable set of Q^{A}-representatives, and let f : A ≅ A_{G}. Then f is deg(f ↾ S)- computable.

4.5. Lemma. Let A and G be computable presentations of A and G, respectively. Let S be a computable set of Q^{A}-representatives and let S′ be a computable set of Q^{A_{G}}- representatives. Suppose that there exists a map f : S ⟶_{onto}^{1–1} S′ such that R^{A}(x, y) ⇔ R^{A_{G}}(f(x), f(y)) for each x, y ∈ S. Then f can be extended to a deg(f)-computable isomorphism f̂: A ≅ A_{G}.

The proof of Lemma 4.4 is the same as that of Lemma 2.4, using (P3′) in place of (P3). The proof of Lemma 4.5 is essentially the same as that of Lemma 2.5, with D(A) replaced by S and D(A_{G}) by S′, and using (P2′) in place of (P2) and Lemma 4.4 in place of Lemma 2.4. The only other change is that the isomorphism h : A ≅ A_{G} must be such that h(S) = S′. The existence of such an isomorphism is an immediate consequence of Remark 4.3.

We now need a few definitions. Let A be a presentation of A. Let

D̂(A) = {x ∈ D(A) : y < x ⇒ ¬Q^{A}(x, y)},

where < is the natural ordering on ω. Notice that D̂(A) is a deg(A)-computable set of Q^{A}-representatives. Let G̃_{A} be the graph whose domain is D̂(A), with an edge between x and y if and only if R^{A}(x, y). Clearly, there exist a deg(A)-computable map h_{A} and a deg(A)-computable graph G_{A} such that h_{A} : G̃_{A} → G_{A} is a deg(A)-computable presentation of G̃_{A}. If A is computable then we take G_{A} = G̃_{A} and let h_{A} be the identity. For any presentation G of G, let ĝ_{G} = g_{G} ↾ D̂(A_{G}). Note that, by Remark 4.2, ĝ_{G} is one-to-one and hence invertible.

The following are the new versions of Lemmas 2.6–2.9.

4.6. Lemma. If G and G′ are computable presentations of G and h : G ≅ G′ is an isomorphism then there exists a deg(h)-computable isomorphism f̂ : A_{G} ≅ A_{G′} such that f̂ ↾ D̂(A_{G}) = ĝ_{G′}^{−1} ∘ h ∘ ĝ_{G}.

4.7. Lemma. If A and A′ are computable presentations of A and f : A ≅ A′ is an isomorphism then there exists a map h : f(D̂(A)) ⟶_{onto}^{1–1} D̂(A′) such that h ∘ (f ↾ D̂(A)) is a deg(f)-computable isomorphism from G_{A} to G_{A′}.

4.8. Lemma. If G is a computable presentation of G then ĝ_{G} is a computable isomorphism from G_{A_{G}} to G.

4.9. Lemma. If A is a computable presentation of A then there exists a computable isomorphism f : A ≅ A_{G_{A}} such that f ↾ D̂(A) = ĝ_{G_{A}}^{−1} ∘ h_{A}.

In most cases, the proofs of these lemmas are essentially the same as those of the corresponding lemmas in Section 2, with a few obvious modifications. The only exception is Lemma 4.7, which can be proved as follows. For x ∈ f(D̂(A)), let h(x) be the unique y ∈ D̂(A′) such that Q^{A′}(x, y). Then E^{G_{A}}(x, y) ⇔ R^{A}(x, y) ⇔ R^{A′}(f(x), f(y)) ⇔ R^{A′}((h ∘ f)(x), (h ∘ f)(y)) ⇔ E^{G_{A′}}((h ∘ f)(x), (h ∘ f)(y)). Thus h ∘ (f ↾ D̂(A)) is a deg(f)-computable isomorphism from G_{A} to G_{A′}.

We can now prove Propositions 2.10–2.13 in much the same way as before, using Lemmas 4.6–4.9 in place of Lemmas 2.6–2.9. The other necessary changes to the proofs of these propositions are described below.

No other changes to the proofs of Propositions 2.10 and 2.11 are needed.

In establishing Proposition 2.12, the proof that the computable dimension of (A, a) is at least the same as that of (G, x) is as before, with g_{G} and g_{G′} replaced by ĝ_{G} and ĝ_{G′}, respectively.

For the other direction, if (B, a^{B}) and (B′, a^{B′}) are computable presentations of (A, a) that are not computably isomorphic then, by Lemma 4.5, there exist computable presentations (A, a^{A}) and (A′, a^{A′}) of (A, a) such that (A, a^{A}) is computably isomorphic to (B, a^{B}), (A′, a^{A′}) is computably isomorphic to (B′, a^{B′}), a^{A} ∈ D̂(A), and a^{A′} ∈ D̂(A′). Now the proof proceeds as before, with g_{G_{A}} and g_{G_{A′}} replaced by ĝ_{G_{A}} and ĝ_{G_{A′}}, respectively.

For the proof of Proposition 2.13, let f, G, and h be as in that proof and redefine U = {x ∈ D : ∃y[Q(x, y)∧y ∈ (h^{−1}∘ĝ_{G}^{−1}∘f)(S)]}. Notice that this definition guarantees that Q(x, y) ⇒ (U(x) ⇔ U(y)).

Now, by Lemma 4.6, for every computable presentation f′ : G ≅ G′ of G there exists an isomorphism k : A ≅ A_{G′} such that

k(U) = {x ∈ D(A_{G′}) : ∃y[Q^{A_{G′}}(x, y) ∧ y ∈ (ĝ_{G′}^{−1} ∘ f′)(S)]} = {x ∈ D(A_{G′}) : ¬∃y[Q^{A_{G′}}(x, y) ∧ y ∈ (ĝ_{G′}^{−1} ∘ f′)(|G| − S)]},

which implies that DgSp_{G}(S) ⊆ DgSp_{A}(U).

On the other hand, for every computable presentation k : A ≅ A of A, Remark 4.3 implies that there exists an automorphism p : A ≅ A such that (p ∘ h^{−1})(D̂(A_{G})) = k^{−1}(D̂(A)). It is not hard to check that m = k∘p∘h^{−1}∘ĝ_{G}^{−1}∘f is an isomorphism from G to G_{A}, and that m(S) = k(U ↾ k^{−1}(D̂(A))). This implies that DgSp_{A}(U) ⊆ DgSp_{G}(S) and that if S is intrinsically c.e. then so is U.

We now give a relatively simple example of the application of Proposition 4.1 to rings, via a coding based on one due to Rabin and Scott [36].

Let G be a symmetric, irreflexive, countably infinite graph with edge relation E. We may assume that there exist x, y, z ∈ G such that E(x, y), E(x, z), and E(y, z), since the theory of graphs with this property is clearly complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations.

To simplify our notation, we will assume without loss of generality that |G| = ω. (We can do this because every infinite d-computable structure is computably isomorphic to a d-computable structure with domain ω.) The deg(G)-computably presentable ring A_{G} is defined as follows.

1. A_{G} is generated by elements a, b, d, e, and c_{i}, i ∈ ω.

2. Multiplication is commutative.

3. A_{G} has characteristic 0.

4. a^{2} = b^{2} = ab = ad = bd = ae = be = 0, e^{2} = a, and de = d^{3} = b.

5. For all i ∈ ω, c_{i}^{2} = a, ac_{i} = bc_{i} = dc_{i} = 0, and ec_{i} = b.

6. For all i, j ∈ ω, if E(i, j) then c_{i}c_{j} = b. (Notice that if E(i, j) then i ≠ j.)

7. For all i, j ∈ ω, if i ≠ j and ¬E(i, j) then c_{i}c_{j} = 0. It is easy to check that A_{G} satisfies the ring axioms, using the fact that each of its elements is of the form

n_{0} + n_{1}a + n_{2}b + n_{3}d + n_{4}d^{2} + n_{5}e + ∑_{i=0}^{p} n_{i+6}c_{i},  (4.1)

where p ∈ ω and n_{0}, …, n_{p+6} ∈ ℤ.

Let a, b, d, and e be as in the definition of A_{G} and define

D(x) = {x ∈ |A_{G}| : x^{2} = a ∧ dx = 0 ∧ ex = b},

R(x, y) = {(x, y) : D(x) ∧ D(y) ∧ xy = b},

and

Q(x, y) = {(x, y) : D(x) ∧ D(y) ∧ xy = a}.

Clearly, D, R, and Q are relatively intrinsically computable. We claim they are also invariant. To see this, fix an automorphism f of A_{G}. Let P = {x ∈ |A_{G}| : x^{4} = 0} and P^{2} = {y ∈ |A_{G}| : ∃x ∈ P (x^{2} = y)}.

Let x be of the form (4.1). Since x^{4} is a sum of n_{0}^{4} and terms involving a, b, d, e, or some c_{i}, it follows that if x ∈ P then n_{0} = 0. Conversely, if n_{0} = 0 then

x^{2} = (n_{5}^{2} + ∑_{i=0}^{p} n_{i+6}^{2})a + 2(n_{3}n_{4} + n_{3}n_{5} +

n_{5} ∑_{i=0}^{p} n_{i+6} + ∑_{i=0}^{p}(∑ {j ⩽ p : E^{G′}(i, j)} n_{i+6}n_{j+6}))b + n_{3}^{2}d^{2}, (4.2)

and hence x^{4} = 0, so x ∈ P if and only if n_{0} = 0. It will be clear from this fact that all the elements that we consider below are in P.

We will need to consider several elements with square equal to a. It follows easily from (4.2) that these are all of one of the forms n_{1}a+n_{2}b+n_{4}d^{2}±c_{i} or n_{1}a+n_{2}b+n_{4}d^{2}±e. Note in particular that this means that if x^{2} = a then x^{3} = 0.

Equation (4.2) also shows that every element of P^{2} is of the form ka + lb + md^{2}, where k, m ∈ ω and l ∈ ℤ. Furthermore, if x ∈ P then x^{3} = n_{3}^{3}b, so f(b) = lb for some l ∈ ℤ. This is only possible if l = ±1. Since every element of P^{2} can be expressed as a sum of nonnegative integer multiples of a and d^{2} and an integer multiple of b, and P^{2} is invariant, it follows that every element of P^{2} can be expressed as a sum of nonnegative integer multiples of f(a) and f(d^{2}) and an integer multiple of f(b) = ±b. In particular, a and d^{2} can be so expressed. This means that if we write f(a) = ka + lb + md^{2} then k, m ⩽ 1.

We will now show that f(a) = a. Let x be any element of the form (4.1) such that x^{2} = f(a) = ka + lb + md^{2}, where k, m ⩽ 1. As mentioned above, for any y ∈ |A_{G}|, if y^{2} = a then y^{3} = 0, so it must be the case that x^{3} = 0. Now, k = n_{5}^{2} + ∑_{i=0}^{p} n_{i+6}^{2}, l = 2(n_{3}n_{4} +n_{3}n_{5} +n_{5} ∑_{i=0}^{p} n_{i+6} +∑_{i=0}^{p} ∑_{j⩽p:E^{G′}(i,j)} n_{i+6}n_{j+6}), and m = n_{3}^{2}. So if k = 0 then n_{i+6} = 0 for all i ⩽ p, which means that if at least one of l and m is nonzero then n_{3} ≠ 0, and hence x^{3} ≠ 0. If k = 1 then either n_{5} = ±1 and n_{i+6} = 0 for all i ⩽ p; or n_{5} = 0, n_{i+6} = ±1 for some i ⩽ m, and n_{j+6} = 0 for all j ≠ i. Again, if at least one of l and m is nonzero then n_{3} ≠ 0, and hence x^{3} ≠ 0. Since x^{3} = 0, this means that l = m = 0, which implies that k = 1. In other words, f(a) = a.

We will now show that f(b) = b. Take i_{0}, i_{1}, and i_{2} such that E(i_{0}, i_{1}), E(i_{0}, i_{2}), and E(i_{1}, i_{2}). For each j ⩽ 2, the fact that c_{i_{j}}^{2} = a implies that f(c_{i_{j}}) is of one of the forms n_{j,1}a + n_{j,2}b + n_{j,4}d^{2} + ε_{j}c_{i′_{j}} or n_{j,1}a + n_{j,2}b + n_{j,4}d^{2} + ε_{j}e, where ε_{j} = ±1. The second case cannot happen for two different j, k ⩽ 2, since then f(c_{i_{j}})f(c_{i_{k}}) = ±a ≠ ±b = f(b) = f(c_{i_{j}}c_{i_{k}}). So we can assume without loss of generality that f(c_{i_{j}}) is of the form n_{j,1}a + n_{j,2}b + n_{j,4}d^{2} + ε_{j}c_{i′_{j}} for j = 0, 1. Now, c_{i_{0}}c_{i_{1}} = c_{i_{0}}c_{i_{2}} = c_{i_{1}}c_{i_{2}}, so we must have f(c_{i_{0}})f(c_{i_{1}}) = f(c_{i_{0}})f(c_{i_{2}}) = f(c_{i_{1}})f(c_{i_{2}}), which implies that ε_{0} = ε_{1} = ε_{2}. This means that f(b) = f(c_{i_{0}})f(c_{i_{1}}) = c_{i′_{0}}c_{i′_{1}}. Since f(b) = ±b and c_{i′_{0}}c_{i′_{1}} ≠ −b, it follows that f(b) = b.

We will now show that D, R, and Q are invariant. As in the case of a, if we write f(d^{2}) = ka + lb + md^{2} then k, m ⩽ 1. But, since f(a) = a and f(b) = b, it follows that k must equal 0, since otherwise we could not express d^{2} as a sum of nonnegative integer multiples of f(a) and f(d^{2}) and an integer multiple of f(b). This implies that m = 1. If x^{2} = d^{2} + lb then x is of the form n_{1}a + n_{2}b ± d + n_{4}d^{2}, so f(d) is of this form. But f(d)^{3} = b, so f(d) is of the form n_{1}a + n_{2}b + d + n_{4}d^{2}. From this fact it follows easily that f(d)x = dx for all x ∈ |A_{G}| such that x^{2} = a. Furthermore, e^{2} = a and de = b, so f(e) must be of the form n_{1}a + n_{2}b + n_{4}d^{2} + e, from which it follows that f(e)x = ex for all x ∈ |A_{G}| such that x^{2} = a. This is enough to show that D, R, and Q are invariant.

Fix a deg(G)-computable presentation of A_{G} for which the map g_{G} that sends ma + nb + c_{i} to i, for each m, n ∈ ℤ and i ∈ ω, is deg(G)-computable, and identify A_{G} with this presentation.

Let G′ be a presentation of G. The deg(G′)-computable ring A_{G′} and the deg(G′)- computable map g_{G′} are defined in an analogous way.

Clearly, A_{G′} ≅ A_{G}, so A_{G′} is a deg(G′)-computable presentation of A_{G}. We claim that D(A_{G′}) = dom(g_{G′}), R^{A_{G′}}(x, y) ⇔ E^{G′}(g_{G′}(x), g_{G′}(y)), and Q^{A_{G′}}(x, y) ⇔ g_{G′}(x) = g_{G′}(y).

To avoid notational confusion, we verify this claim for G; the proof for G′ is analogous. Let a, b, d, e, and c_{i} be as in the definition of A_{G}. It is easy to check that dom(g_{G}) ⊆ D(A_{G}). Now let x ∈ D(A_{G}). As mentioned above, the fact that x^{2} = a implies that x is of one of the forms n_{1}a + n_{2}b + n_{4}d^{2} ± c_{i} or n_{1}a + n_{2}b + n_{4}d^{2} ± e. The second case cannot happen, because e(n_{1}a + n_{2}b + n_{4}d^{2} ± e) = ±e^{2} = ±a ≠ b, so x = n_{1}a + n_{2}b + n_{4}d^{2} ± c_{i}. Since d(n_{1}a + n_{2}b + n_{4}d^{2} ± c_{i}) = n_{4}b, it follows that n_{4} = 0. Since ex = b, it follows that x = n_{1}a + n_{2}b + c_{i}. This shows that D(A_{G}) = dom(g_{G}).

Now suppose that x, y ∈ D(A_{G}). Then, as we have seen in the previous paragraph, for some i, j ∈ ω and m, n, m′, n′ ∈ ℤ, we have x = ma + nb + c_{i} and y = m′a + n′ + c_{j}, and hence xy = c_{i}c_{j}. Thus R^{A_{G}}(x, y) ⇔ xy = b ⇔ E(g_{G}(x), g_{G}(y)) and Q^{A_{G}}(x, y) ⇔ xy = a ⇔ i = j ⇔ g_{G}(x) = g_{G}(y).

To apply Proposition 4.1, we are left with showing that properties (P2′) and (P3′) in the statement of that proposition are satisfied.

Let S and S′ be sets of Q-representatives and let f : S ⟶_{onto}^{1–1} S′ be such that R(x, y) ⇔ R(f(x), f(y)). We can extend f as follows. Let a, b, d, e, and c_{i} be as in the definition of A_{G}. Clearly, S = {m_{0}a+n_{0}b+c_{0}, m_{1}a+n_{1}b+c_{1}, … } for some m_{0}, m_{1}, …, n_{0}, n_{1}, … ∈ ℤ, so given x ∈ |A_{G}|, we have x = k_{0} + k_{1}a + k_{2}b + k_{3}d + k_{4}d^{2} + k_{5}e + ∑_{i=0}^{p} k_{i+6}s_{i} for some p ∈ ω, k_{0}, …, k_{p+6} ∈ ℤ, and s_{0}, …, s_{p} ∈ S. Let

f(x) = k_{0} + k_{1}a + k_{2}b + k_{3}d + k_{4}d^{2} + k_{5}e + ∑_{i=0}^{p} k_{i+6}f(s_{i}).

It can be easily verified that this extended map is an automorphism of A_{G}.

Finally, given a deg(G)-computable set S of Q^{A_{G}}-representatives, let a, b, d, and e be as in the definition of A_{G} and let t_{0}, t_{1}, … be a deg(G)-computable list of all terms generated by applying addition and multiplication to a, b, d, e, 1, −1, and the elements of S. Consider the deg(G)-computable set of formulas {x = t_{i} : i ∈ ω}. Every x ∈ |A_{G}| satisfies some formula in this set, with no two elements satisfying the same formula, so this set is a deg(G)-computable defining family for (A_{G}, z)_{z∈D(A_{G})}. For any presentation G′ of G, a deg(G′)-computable defining family for (A_{G′}, z)_{z∈D(A_{G′})} can be defined in an analogous way.

It is straightforward to check that, for any computable presentation A of A_{G}, if U is a subset of D(A) such that Q(x, y) ⇒ (U(x) ⇔ U(y)) then the subring of A generated by U has the same degree as U, and is c.e. if U is c.e.. Thus Theorem 1.22 in the case of rings of characteristic 0 follows from Proposition 4.1, with the theory C mentioned in that proposition being the theory of symmetric, irreflexive graphs containing at least one triangle.

4.10. Theorem. The theory of rings of characteristic 0 is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A be a ring of characteristic 0. Furthermore, Theorems 1.8–1.11 remain true if we also require that U be a subring of A.

5 Integral Domains and Commutative Semigroups

In this section we present a coding of a graph into an integral domain inspired by Kudinov’s coding [27] of a family of c.e. sets into an integral domain of characteristic 0, and show how this leads to a proof of Theorem 1.22 in the case of integral domains of arbitrary characteristic. Because our coding will not make use of the additive structure of the domain, we will simultaneously handle the case of commutative semigroups.

Let p be either 0 or a prime. We adopt the convention that ℤ_{0} = ℤ. If p = 0 then let 𝔽 = ℚ; otherwise, let 𝔽 = ℤ_{p}. Let I be the set of invertible elements of ℤ_{p}. Note that I is finite.

The graphs constructed in Subsection 3.1 have the following property: for every finite set of nodes S there exist nodes x, y ∉ S that are connected by an edge. Thus the theory of such graphs is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations.

Let G be a symmetric, irreflexive, countably infinite graph with edge relation E, having the property mentioned in the previous paragraph. As in the previous section, we assume without loss of generality that |G| = ω.

The deg(G)-computably presentable integral domain A_{G} is defined to be

ℤ_{p} [x_{i} : i ∈ ω] [\frac{y}{x_{i}x_{j}} : E(i, j)] [\frac{z}{x_{i}x_{j}} : ¬E(i, j)] [\frac{y}{x_{i}^{n}} : i, n ∈ ω] .

Note that, since G is irreflexive, \frac{z}{x_{i}^{2}} is included as a generator for each i ∈ ω.

It is easy to see that A_{G} is deg(G)-computably presentable. In fact, if we fix a computable presentation P of the ring 𝔽(x_{i} : i ∈ ω)[y, z] then A_{G} has an obvious deg(G)-computable presentation induced from that of P. (Just take as the domain of this presentation a deg(G)-computable copy of the set of all elements of P that can be generated from the generators of A_{G}.) In what follows, we will identify A_{G} with this presentation. We will also assume that we have chosen P so that the map g_{G} : ax_{i} ↦ i, a ∈ I, is deg(G)-computable.

Let G′ be a presentation of G. The deg(G′)-computable integral domain A_{G′} and the deg(G′)-computable map g_{G′} are defined in an analogous way. Clearly, A_{G′} ≅ A_{G}.

Let y and z be as in the definition of A_{G} and define

D(x) = {x ∈ |A_{G}| : x ∉ I ∧ ∃r(x^{2}r = z)},
Q(x, x′) = {(x, ax) : D(x) ∧ a ∈ I},

and

R(x, x′) = {(x, x′) : D(x) ∧ D(x′) ∧ ¬Q(x, x′) ∧ ∃r(rxx′ = y)}.

We will show that D, Q, and R are relatively intrinsically computable and invariant, and satisfy properties (P1′)–(P3′) in the statement of Proposition 4.1.

Since A_{G} is a subring of 𝔽(x_{i} : i ∈ ω)[y, z], it makes sense to talk of the degree in y or z (in the algebraic sense) of an element r of A_{G}. We will denote these by deg_{y}(r) and deg_{z}(r), respectively. Let

Gen = \{±1\} ∪ \{x_{i} : i ∈ ω\} ∪ \{\frac{y}{x_{i}x_{j}} : E(i, j)\} ∪ \{\frac{z}{x_{i}x_{j}} : ¬E(i, j)\} ∪ \{\frac{y}{x_{i}^{n}} : i, n ∈ ω\} .

It will be useful to think of elements of A_{G} as sums of products of elements of Gen. (Of course, such representations are not unique, but this will not matter for our purposes.)

Whenever we mention another ring B, such as ℤ_{p}[x_{i}, \frac{1}{x_{i}} : i ∈ ω][y, z] or ℤ_{p}[x_{i} : i ∈ ω], for example, we will think of A_{G} as a subring of B or of B as a subring of A_{G}, as appropriate. The relationships between such rings should be clear. For instance, if deg_{y}(r) = deg_{z}(r) = 0 then r can be expressed as a sum of products of the generators x_{i}, i ∈ ω, so that r is in the subring ℤ_{p}[x_{i} : i ∈ ω] of A_{G}. In this case, it makes sense to talk of the degree in x_{i} of r, denoted by deg_{x_{i}}(r), for any i ∈ ω. We will make frequent use of these and similar facts. One ring that will be mentioned often is

M = ℤ_{p} [x_{i}, \frac{1}{x_{i}} : i ∈ ω] [y, z].

5.1. Lemma. The only invertible elements of A_{G} are the elements of I.

Proof. If rs = 1 then deg_{y}(r) = deg_{z}(r) = 0, and hence r ∈ ℤ_{p}[x_{i} : i ∈ ω]. Clearly, the only invertible elements of ℤ_{p}[x_{i} : i ∈ ω] are the invertible elements of ℤ_{p}.

5.2. Lemma. Let r, s ∈ |A_{G}|. Suppose that r^{2}s = z and r ∉ I. Then r = ax_{i} for some i ∈ ω and a ∈ I.

Proof. Clearly, deg_{y}(r) = deg_{z}(r) = 0. Since r ∉ I, it must be the case that r = x_{i}r_{0}+r_{1} for some i ∈ ω, r_{0} ∈ ℤ_{p}[x_{k} : k ∈ ω], r_{0} ≠ 0, and r_{1} ∈ ℤ_{p}[x_{k} : k ≠ i].

Now, deg_{y}(s) = 0 and deg_{z}(s) = 1, so that, working in M, we can write s = \frac{z}{x_{i}^{2}} s_{0} + \frac{z}{x_{i}} s_{1} + s_{2}, where s_{0} ∈ ℤ_{p}[x_{j} : j ≠ i], s_{1} ∈ ℤ_{p}[x_{j}, \frac{1}{x_{j}} : j ≠ i], and s_{2} ∈ ℤ_{p}[x_{j} : j ∈ ω][\frac{1}{x_{j}} : j ≠ i][z].

We first show that r_{1} = 0. Assume for a contradiction that r_{1} ≠ 0. It is easy to check that

x_{i}^{2}z = x_{i}^{2}r^{2}s = zr_{1}^{2}s_{0} + x_{i}(2zr_{0}r_{1}s_{0} + zr_{1}^{2}s_{1}) + x_{i}^{2}t

for some t ∈ ℤ_{p}[x_{j} : j ∈ ω][\frac{1}{x_{j}} : j ≠ i][z], and hence that zr_{1}^{2}s_{0} = x_{i}u for some u ∈ ℤ_{p}[x_{j} : j ∈ ω][\frac{1}{x_{j}} : j ≠ i][z]. Since deg_{x_{i}}(zr_{1}^{2}s_{0}) = 0, it must be the case that s_{0} = 0.

Now x_{i}(zr_{1}^{2}s_{1}) = x_{i}^{2}(z − t). Since deg_{x_{i}}(zr_{1}^{2}s_{1}) = 0, it follows from this fact that s_{1} = 0. But then s_{2} ≠ 0 and

x_{i}^{2}r_{0}^{2}s_{2} = (x_{i}r_{0} + r_{1})^{2}s_{2} − (2x_{i}r_{0}r_{1} + r_{1}^{2})s_{2} = z − (2x_{i}r_{0}r_{1} + r_{1}^{2})s_{2}.

Since now

deg_{x_{i}}(x_{i}^{2}r_{0}^{2}s_{2}) = 2 deg_{x_{i}}(r_{0}) + deg_{x_{i}}(s_{2}) + 2 > deg_{x_{i}}(r_{0}) + deg_{x_{i}}(s_{2}) + 1 ⩾ deg_{x_{i}}(z − (2x_{i}r_{0}r_{1} + r_{1}^{2})s_{2}),

this is a contradiction. So in fact r_{1} = 0, and hence r = x_{i}r_{0}.

We now show that r_{0} ∈ I. We have

x_{i}^{2}r_{0}^{2}s_{2} = x_{i}^{2}r_{0}^{2}s − (r_{0}^{2}s_{0}z + x_{i}r_{0}^{2}s_{1}z) = z − (r_{0}^{2}s_{0}z + x_{i}r_{0}^{2}s_{1}z).

Since s_{2} ≠ 0 implies that

deg_{x_{i}}(x_{i}^{2}r_{0}^{2}s_{2}) = 2 deg_{x_{i}}(r_{0}) + deg_{x_{i}}(s_{2}) + 2 > 2 deg_{x_{i}}(r_{0}) + 1 ⩾ deg_{x_{i}}(z − (r_{0}^{2}s_{0}z + x_{i}r_{0}^{2}s_{1}z)),

it must be the case that s_{2} = 0. Now x_{i}r_{0}^{2}s_{1}z = z − r_{0}^{2}s_{0}z. Since s_{1} ≠ 0 implies that

deg_{x_{i}}(x_{i}r_{0}^{2}s_{1}z) = 2 deg_{x_{i}}(r_{0}) + 1 > 2 deg_{x_{i}}(r_{0}) ⩾ deg_{x_{i}}(z − r_{0}^{2}s_{0}z),

it must be the case that s_{1} = 0. Thus s = \frac{z}{x_{i}^{2}} s_{0}. So z = x_{i}^{2}r_{0}^{2} \frac{z}{x_{i}^{2}} s_{0} = r_{0}^{2}s_{0}z, and hence r_{0} ∈ I.

5.3. Corollary. If we let G′ be a presentation of G and let x′_{i} be the image of x_{i} in A_{G′} then D(A_{G′}) = {ax′_{i} : i ∈ ω ∧ a ∈ I}. Furthermore, D and Q are relatively intrinsically computable.

Proof. The first statement follows immediately from Lemma 5.2; we prove the second. It is enough to show that D is relatively intrinsically computable.

Let A be a presentation of A_{G}. We want to show that D(A) is deg(A)-computable. Abusing notation, we refer to the images of y and z in A as y and z, respectively. Let D̂(A) be as in Section 4. Since I is finite and x ∈ D(A) ⇔ ∃a ∈ I(ax ∈ D̂(A)), it is enough to show that D̂(A) is deg(A)-computable.

Clearly, D̂(A) is deg(A)-c.e., and hence so is the set

Gen_{A} = D̂(A) ∪ {r ∈ |A| : ∃x, x′ ∈ D̂(A)(∃n ∈ ω(xx′r = y ∨ xx′r = z ∨ x^{n}r = y))}.

Given x ∈ |A|, we can write x as a sum of products of elements of Gen_{A}, and hence deg(A)-computably determine deg_{y}(x) and deg_{z}(x). If it is not the case that deg_{y}(x) = deg_{z}(x) = 0 then x ∉ D̂(A). Otherwise, x is a polynomial over the elements of D̂(A) with coefficients in ℤ_{p}, and checking whether a polynomial over a linearly independent deg(A)-c.e. set is an element of that set can be done deg(A)-computably.

5.4. Lemma. If i ≠ j and ¬E(i, j) then there is no r ∈ |A_{G}| such that rx_{i}x_{j} = y. Similarly, if E(i, j) then there is no r ∈ |A_{G}| such that rx_{i}x_{j} = z.

Proof. The proofs of both statements are similar; we prove the first.

Assume for a contradiction that, for some i ≠ j ∈ ω and r ∈ |A_{G}|, we have ¬E(i, j) and x_{i}x_{j}r = y. We work in the ring M. Since deg_{y}(r) = 1 and deg_{z}(r) = 0, thinking of r as a sum of products of elements of Gen, we see that we can write r = \frac{y}{x_{i}} r_{0} + \frac{y}{x_{j}} r_{1} + r_{2}, where r_{0} ∈ ℤ_{p}[x_{k} : k ≠ i][\frac{1}{x_{k}} : k ≠ j], r_{1} ∈ ℤ_{p}[x_{k} : k ≠ j][\frac{1}{x_{k}} : k ≠ i], and r_{2} ∈ ℤ_{p}[x_{k} : k ∈ ω][\frac{1}{x_{k}} : k ≠ i, j][y].

Let n ∈ ω be such that x_{i}^{n}r_{0}, x_{j}^{n}r_{2} ∈ ℤ_{p}[x_{k} : k ∈ ω][\frac{1}{x_{k}} : k ≠ i, j]. Then

(x_{i}x_{j})^{n+1}r_{2} = (x_{i}x_{j})^{n}y − (x_{i}^{n}x_{j}^{n+1}r_{0}y + x_{i}^{n+1}x_{j}^{n}r_{1}y).

Since deg_{x_{i}}(x_{i}^{n}x_{j}^{n+1}r_{0}y), deg_{x_{j}}(x_{i}^{n+1}x_{j}^{n}r_{1}y), and deg_{x_{i}}((x_{i}x_{j})^{n}y) are all less than or equal to n, and r_{2} ∈ ℤ_{p}[x_{k} : k ∈ ω][\frac{1}{x_{k}} : k ≠ i, j][y], it must be the case that r_{2} = 0.

Now

(x_{i}x_{j})^{n}y = x_{i}^{n}x_{j}^{n+1}r_{0}y + x_{i}^{n+1}x_{j}^{n}r_{1}y.

But

r_{0} ≠ 0 ⇒ deg_{x_{i}}(x_{i}^{n}x_{j}^{n+1}r_{0}y) ⩽ n ∧ deg_{x_{j}}(x_{i}^{n}x_{j}^{n+1}r_{0}y) > n

and

r_{1} ≠ 0 ⇒ deg_{x_{i}}(x_{i}^{n+1}x_{j}^{n}r_{1}y) > n ∧ deg_{x_{j}}(x_{i}^{n+1}x_{j}^{n}r_{1}y) ⩽ n.

Since we cannot have r_{0} = r_{1} = 0, this means that at least one of deg_{x_{i}}(x_{i}^{n}x_{j}^{n+1}r_{0}y + x_{i}^{n+1}x_{j}^{n}r_{1}y) and deg_{x_{j}}(x_{i}^{n}x_{j}^{n+1}r_{0}y + x_{i}^{n+1}x_{j}^{n}r_{1}y) is greater than n. But deg_{x_{i}}((x_{i}x_{j})^{n}y) = deg_{x_{j}}((x_{i}x_{j})^{n}y) = n, so this is a contradiction.

5.5. Corollary. We have

R = {(x, x̂) : D(x) ∧ D(x̂) ∧ ¬Q(x, x̂) ∧ ∃r(rxx̂ = y)} = {(x, x̂) : D(x) ∧ D(x̂) ∧ ¬∃r(rxx̂ = z)}, and hence R is relatively intrinsically computable. Furthermore, if we let G′ be a presentation of G and let x′_{i} be the image of x_{i} in A_{G′} then

R^{A_{G′}} = {(ax′_{i}, bx′_{j}) : E^{G′}(i, j) ∧ a, b ∈ I}.

We now need to show that D, Q, and R are invariant. Fix an automorphism f : A_{G} ≅ A_{G}. We will show that f(D) = D, f(Q) = Q, and f(R) = R.

5.6. Lemma. Suppose that i ∈ ω and f(x_{i}) = rs for some r, s ∈ |A_{G}|. Then either r ∈ I or s ∈ I.

Proof. Since f(I) = I and x_{i} = f^{−1}(r)f^{−1}(s), it is enough to show that if x_{i} = r′s′ for some r′, s′ ∈ |A_{G}| then either r′ ∈ I or s′ ∈ I. But this follows easily from the fact that if x_{i} = r′s′ then deg_{y}(r′) = deg_{z}(r′) = deg_{y}(s′) = deg_{z}(s′) = 0, so that r′, s′ ∈ ℤ_{p}[x_{j} : j ∈ ω].

5.7. Lemma. We have f(D) = D, which implies that f(Q) = Q.

Proof. It is enough to show that f(D) ⊆ D. Since f is an arbitrary automorphism of A_{G}, the same proof will show that f^{−1}(D) ⊆ D, and hence that D ⊆ f(D).

Let i ∈ ω. Let n = deg_{y}(f(y)) and let r = f(\frac{y}{x_{i}^{n+1}} ). Then f(x_{i})^{n+1}r = f(y), and hence n = deg_{y}(f(y)) ⩾ deg_{y}(f(x_{i})^{n+1}) = (n + 1) deg_{y}(f(x_{i})). Thus it must be the case that deg_{y}(f(x_{i})) = 0. A similar argument shows that deg_{z}(f(x_{i})) = 0. Since f(x_{i}) ∉ I, this means that f(x_{i}) = x_{j}s_{0} + s_{1} for some j ∈ ω, s_{0} ∈ ℤ_{p}[x_{l} : l ∈ ω], s_{0} ≠ 0, and s_{1} ∈ ℤ_{p}[x_{l} : l ≠ j].

Let k be such that x_{j}^{k}f(y) ∈ ℤ_{p}[x_{l} : l ∈ ω][\frac{1}{x_{l}} : l ≠ j][y, z] and let n = deg_{x_{j}}(x_{j}^{k}f(y))+ 1. For some r ∈ |A_{G}|, we have x_{j}^{k}f(x_{i})^{n}r = x_{j}^{k}f(y). Working in M, we can write

r = \frac{1}{x_{j}^{k+1}} r_{0} + \frac{1}{x_{j}^{k}} r_{1} + ⋯ + r_{k+1},

where r_{0} ∈ ℤ_{p}[x_{l} : l ≠ j][\frac{1}{x_{l}} : l ∈ ω][y, z], r_{1}, …, r_{k} ∈ ℤ_{p}[x_{l}, \frac{1}{x_{l}} : l ≠ j][y, z], and r_{k+1} ∈ ℤ_{p}[x_{l} : l ∈ ω][\frac{1}{x_{l}} : l ≠ j][y, z].

Now

x_{j}^{k}(x_{j}s_{0} + s_{1})^{n}r_{k+1} = x_{j}^{k}(x_{j}s_{0} + s_{1})^{n}r − x_{j}^{k}(x_{j}s_{0} + s_{1})^{n}(r − r_{k+1}) =

x_{j}^{k}f(y) − (x_{j}^{k}(x_{j}s_{0} + s_{1})^{n} (\frac{1}{x_{j}^{k+1}} r_{0} + \frac{1}{x_{j}^{k}} r_{1} + ⋯ + \frac{1}{x_{j}} r_{k})) .

But it is easy to check that if r_{k+1} ≠ 0 then

deg_{x_{j}}(x_{j}^{k}(x_{j}s_{0}+s_{1})^{n}r_{k+1}) = n deg_{x_{j}}(s_{0})+deg_{x_{j}}(r_{k+1})+k+n > n deg_{x_{j}}(s_{0})+k+n−1 ⩾

deg_{x_{j}} (x_{j}^{k}f(y) − (x_{j}^{k}(x_{j}s_{0} + s_{1})^{n} (\frac{1}{x_{j}^{k+1}} r_{0} + \frac{1}{x_{j}^{k}} r_{1} + ⋯ + \frac{1}{x_{j}} r_{k}))) .

It follows that r_{k+1} = 0.

It is not hard to see that we may now repeat the above argument with k in place of k + 1 (assuming k > 0). Proceeding in this fashion, we see that r_{1} = ⋯ = r_{k+1} = 0.

So

\frac{s_{1}^{n}r_{0}}{x_{j}} = x_{j}^{k}(x_{j}s_{0} + s_{1})^{n} \frac{1}{x_{j}^{k+1}} r_{0} − x_{j}^{k}((x_{j}s_{0} + s_{1})^{n} − s_{1}^{n})\frac{1}{x_{j}^{k+1}} r_{0} =

x_{j}^{k}f(y) − ((x_{j}s_{0} + s_{1})^{n} − s_{1}^{n})\frac{1}{x_{j}} r_{0}.

But s_{1}^{n}r_{0} ∈ ℤ_{p}[x_{l} : l ≠ j][\frac{1}{x_{l}} : l ∈ ω][y, z], which implies that either s_{1}^{n}r_{0} = 0 or \frac{s_{1}^{n}r_{0}}{x_{j}} ∉ ℤ_{p}[x_{l} : l ∈ ω][\frac{1}{x_{l}} : l ≠ j][y, z]. Since

x_{j}^{k}f(y) − ((x_{j}s_{0} + s_{1})^{n} − s_{1}^{n})\frac{1}{x_{j}} r_{0} ∈ ℤ_{p}[x_{l} : l ∈ ω] [\frac{1}{x_{l}} : l ≠ j] [y, z],

it must be the case that s_{1}^{n}r_{0} = 0. Since r ≠ 0, we conclude that s_{1} = 0.

Thus f(x_{i}) = s_{0}x_{j}. By Lemma 5.6, s_{0} ∈ I.

5.8. Corollary. f(ℤ_{p}[x_{i} : i ∈ ω]) = ℤ_{p}[x_{i} : i ∈ ω].

5.9. Lemma. Let r ∈ |A_{G}| be such that r ≠ 0, deg_{y}(r) = 0, and deg_{z}(r) ⩽ n. For all i ∈ ω, we have x_{i}^{2n+1}r ∉ ℤ_{p}[x_{j}, \frac{1}{x_{j}} : j ≠ i][y, z].

Proof. We work in the ring M. Let i ∈ ω. We think of r as a sum of products of elements of Gen. Each term t in this sum can be written as \frac{z^{m}}{x_{i}^{2m}} s, where m ⩽ n and s ∈ ℤ_{p}[x_{j} : j ∈ ω][\frac{1}{x_{j}} : j ≠ i]. So x_{i}^{2n+1}t = x_{i}u for some u ∈ ℤ_{p}[x_{j} : j ∈ ω][\frac{1}{x_{j}} : j ≠ i][z]. Thus x_{i}^{2n+1}r = x_{i}v for some v ∈ ℤ_{p}[x_{j} : j ∈ ω][\frac{1}{x_{j}} : j ≠ i][z], and hence x_{i}^{2n+1}r ∉ ℤ_{p}[x_{j}, \frac{1}{x_{j}} : j ≠ i][y, z].

5.10. Lemma. deg_{y}(f(y)) = 1 and deg_{z}(f(y)) = 0.

Proof. Let i ∈ ω be such that f(y) ∈ ℤ_{p}[x_{j}, \frac{1}{x_{j}} : j ≠ i][y, z]. Working in M, we can write f(y) = ys_{0} + s_{1}, where s_{0} ∈ |M|, s_{1} ∈ |A_{G}|, and deg_{y}(s_{1}) = 0. Let n = deg_{z}(s_{1}).

By Lemma 5.7, there exists an r ∈ |A_{G}| such that x_{i}^{2n+1}r = f(y) = ys_{0} + s_{1}. We can write r = yr_{0} + r_{1}, where r_{0} ∈ |M|, r_{1} ∈ |A_{G}|, and deg_{y}(r_{1}) = 0. Now x_{i}^{2n+1}r_{1} = s_{1}. Since deg_{z}(r_{1}) = deg_{z}(s_{1}) = n, it follows from Lemma 5.9 that either r_{1} = 0 or s_{1} ∉ ℤ_{p}[x_{j}, \frac{1}{x_{j}} : j ≠ i][y, z]. But the latter possibility would imply that f(y) ∉ ℤ_{p}[x_{j}, \frac{1}{x_{j}} : j ≠ i][y, z], contradicting our choice of i. So r_{1} = 0, and hence s_{1} = 0.

Thus f(y) = ys_{0}. A similar argument shows that deg_{y}(f^{−1}(y)) ⩾ 1. We now need to show that deg_{y}(s_{0}) = deg_{z}(s_{0}) = 0.

Let t ∈ ℤ_{p}[x_{j} : j ∈ ω] be such that ts_{0} ∈ ℤ_{p}[x_{j} : j ∈ ω][y, z]. Then

f^{−1}(t)y = f^{−1}(tf(y)) = f^{−1}(ts_{0}y) = f^{−1}(ts_{0})f^{−1}(y).

By Corollary 5.8, f^{−1}(t) ∈ ℤ_{p}[x_{j} : j ∈ ω], which means that deg_{y}(f^{−1}(t)y) = 1 and deg_{z}(f^{−1}(t)y) = 0. Since deg_{y}(f^{−1}(y)) ⩾ 1, this means that f^{−1}(ts_{0}) ∈ ℤ_{p}[x_{j} : j ∈ ω]. By Corollary 5.8, ts_{0} ∈ ℤ_{p}[x_{j} : j ∈ ω]. So deg_{y}(s_{0}) = deg_{z}(s_{0}) = 0.

5.11. Lemma. f(y) = ty for some t ∈ |A_{G}|.

Proof. Let i, j, i′, j′ ∈ ω be such that i ≠ j, f(x_{i′}) = ax_{i} and f(x_{j′}) = bx_{j} for some a, b ∈ I, f(y) ∈ ℤ_{p}[x_{k}, \frac{1}{x_{k}} : k ≠ i, j][y, z], and E(i′, j′). Such numbers exist by Lemma 5.7 and the assumption about G that we made at the beginning of this section.

Let r = f(\frac{aby}{x′_{i}x′_{j}}). Then x_{i}x_{j}r = f(y). By Lemma 5.10, deg_{y}(f(y)) = 1 and deg_{z}(f(y)) = 0, and hence deg_{y}(r) = 1 and deg_{z}(r) = 0. Working in M and thinking of r as a sum of products of elements of Gen, we see that we can write

r = yr_{0} + \frac{y}{x_{i}} r_{1} + \frac{y}{x_{j}} r_{2} + \frac{y}{x_{i}x_{j}} r_{3} + r_{4},

where r_{0} ∈ ℤ_{p}[x_{k} : k ∈ ω][\frac{1}{x_{k}} : k ≠ i, j], r_{1} ∈ ℤ_{p}[x_{k} : k ≠ i][\frac{1}{x_{k}} : k ≠ j], r_{2} ∈ ℤ_{p}[x_{k} : k ≠ j][\frac{1}{x_{k}} : k ≠ i], and r_{3}, r_{4} ∈ ℤ_{p}[x_{k} : k ≠ i, j].

Let n ∈ ω be such that x_{i}^{n}r_{1}, x_{j}^{n}r_{2} ∈ ℤ_{p}[x_{k} : k ∈ ω][\frac{1}{x_{k}} : k ≠ i, j]. Then

(x_{i}x_{j})^{n+1}r_{0}y + (x_{i}x_{j})^{n+1}r_{4} = (x_{i}x_{j})^{n}f(y) − (x_{i}^{n}x_{j}^{n+1}r_{1}y + x_{i}^{n+1}x_{j}^{n}r_{2}y + (x_{i}x_{j})^{n}r_{3}y).

Now, deg_{x_{i}}(x_{i}^{n}x_{j}^{n+1}r_{1}y), deg_{x_{j}}(x_{i}^{n+1}x_{j}^{n}r_{2}y), deg_{x_{i}}((x_{i}x_{j})^{n}r_{3}y), and deg_{x_{i}}((x_{i}x_{j})^{n}f(y)) are all less than or equal to n. Furthermore, r_{0}, r_{4} ∈ ℤ_{p}[x_{k} : k ∈ ω][\frac{1}{x_{k}} : k ≠ i, j] and deg_{y}((x_{i}x_{j})^{n+1}r_{4}) = 0. So it must be the case that r_{0} = r_{4} = 0.

Now

(x_{i}x_{j})^{n}f(y) − (x_{i}x_{j})^{n}r_{3}y = x_{i}^{n}x_{j}^{n+1}r_{1}y + x_{i}^{n+1}x_{j}^{n}r_{2}y.

But

r_{1} ≠ 0 ⇒ deg_{x_{i}}(x_{i}^{n}x_{j}^{n+1}r_{1}y) ⩽ n ∧ deg_{x_{j}}(x_{i}^{n}x_{j}^{n+1}r_{1}y) > n

and

r_{2} ≠ 0 ⇒ deg_{x_{i}}(x_{i}^{n+1}x_{j}^{n}r_{2}y) > n ∧ deg_{x_{j}}(x_{i}^{n+1}x_{j}^{n}r_{2}y) ⩽ n,

which means that either r_{1} = r_{2} = 0 or at least one of deg_{x_{i}}(x_{i}^{n}x_{j}^{n+1}r_{1}y + x_{i}^{n+1}x_{j}^{n}r_{2}y) and deg_{x_{j}}(x_{i}^{n}x_{j}^{n+1}r_{1}y + x_{i}^{n+1}x_{j}^{n}r_{2}y) is greater than n. Since

deg_{x_{i}}((x_{i}x_{j})^{n}f(y) − (x_{i}x_{j})^{n}r_{3}y), deg_{x_{j}}((x_{i}x_{j})^{n}f(y) − (x_{i}x_{j})^{n}r_{3}y) ⩽ n,

it must be the case that r_{1} = r_{2} = 0. Thus f(y) = x_{i}x_{j} \frac{y}{x_{i}x_{j}} r_{3} = yr_{3}. Since r_{3} ∈ |A_{G}|, we are done.

5.12. Corollary. If ∃r(x_{i}x_{j}r = y) then ∃r(x_{i}x_{j}r = f(y)).

5.13. Lemma. f(R) = R.

Proof. It is enough to show that R ⊆ f(R). Since f is an arbitrary automorphism of A_{G}, the same proof will show that R ⊆ f^{−1}(R), and hence that f(R) ⊆ R.

By Corollaries 5.5 and 5.12, R(x_{i}, x_{j}) ⇒ ∃r(x_{i}x_{j}r = y) ⇒ ∃r(x_{i}x_{j}r = f(y)) ⇒ R(f(x_{i}), f(x_{j})).

Since f is an arbitrary automorphism of A_{G}, Lemmas 5.7 and 5.13 imply the following result.

5.14. Lemma. The relations D, Q, and R are invariant.

To apply Proposition 4.1, we are left with showing that properties (P2′) and (P3′) in the statement of that proposition are satisfied.

5.15. Lemma. For every pair S, S′ of sets of Q-representatives, if f : S ⟶_{onto}^{1–1} S′ is such that R(x, y) ⇔ R(f(x), f(y)) for every x, y ∈ S then f can be extended to an automorphism of A_{G}.

Proof. Let y, z, and x_{i} be as in the definition of A_{G}. A set of Q-representatives contains one element of the form ax_{i}, a ∈ I, for each i ∈ ω, and it contains no other elements. So there exist sequences a_{0}, a_{1}, … ∈ I and b_{0}, b_{1}, … ∈ I such that S = {a_{0}x_{0}, a_{1}x_{1}, … } and S′ = {b_{0}x_{0}, b_{1}x_{1}, … }. Thus, for some permutation π of ω, f : a_{i}x_{i} ↦ b_{π(i)}x_{π(i)}.

Now R(x_{i}, x_{j}) ⇔ R(x_{π(i)}, x_{π(j)}) for all i, j ∈ ω. So it is clear from what we have previously done that the map x_{i} ↦ x_{π(i)} can be extended to an automorphism of A_{G}.

Thus it is enough to show that the map a_{i}x_{i} ↦ b_{π(i)}x_{i}, or equivalently, the map h : x_{i} ↦ \frac{b_{π(i)}}{a_{i}} x_{i}, can be extended to an automorphism of A_{G}. But h can clearly be extended to an automorphism of 𝔽(x_{i} : i ∈ ω)[y, z] that fixes y and z. Since \frac{b_{π(i)}}{a_{i}} ∈ I, this automorphism restricts to an automorphism of A_{G}.

5.16. Lemma. For every presentation G′ of G and every deg(G′)-computable set S of Q^{A_{G′}}-representatives, there exists a deg(G′)-computable defining family for (A_{G′}, a)_{a∈S}.

Proof. We let S be a deg(G)-computable set of Q^{A_{G}}-representatives and construct a deg(G)-computable defining family for (A_{G}, a)_{a∈S}. An analogous construction can be performed for G′.

Let y, z, and x_{i} be as in the definition of A_{G}. As mentioned in the proof of the previous lemma, S = {a_{0}x_{0}, a_{1}x_{1}, … } for some sequence a_{0}, a_{1}, … ∈ I. Let s_{i} = a_{i}x_{i} and consider the sets

Gen′ = \{±1\} ∪ \{s_{i} : i ∈ ω\} ∪ \{\frac{y}{s_{i}s_{j}} : E(i, j)\} ∪ \{\frac{z}{s_{i}s_{j}} : ¬E(i, j)\} ∪ \{\frac{y}{s_{i}^{n}} : i, n ∈ ω\}

and

Gen′_{k} = \{±1\} ∪ \{s_{i} : i ⩽ k\} ∪ \{\frac{y}{s_{i}s_{j}} : E(i, j) ∧ i, j ⩽ k\} ∪

\{\frac{z}{s_{i}s_{j}} : ¬E(i, j) ∧ i, j ⩽ k\} ∪ \{\frac{y}{s_{i}^{n}} : i, n ⩽ k\} .

For each i, j, n ∈ ω, let the formula φ_{i,j,n} over the language of rings with additional constants y, z, s_{0}, s_{1}, … be defined by

φ_{i,j,n} = \begin{cases}s_{i}s_{j}u_{i,j} = y ∧ s_{i}^{n}v_{i,n} = y & if E(i, j), \\ s_{i}s_{j}u_{i,j} = z ∧ s_{i}^{n}v_{i,n} = y & if ¬E(i, j). \end{cases}

(Here u_{i,j} and v_{i,n} are the free variables of φ_{i,j,n}.) For each sum t of products of elements of Gen′, let t′ be the result of substituting all occurrences of \frac{y}{s_{i}s_{j}} or \frac{z}{s_{i}s_{j}} in t by u_{i,j}, and all occurrences of \frac{y}{s_{i}^{n}} by v_{i,n}. Let k be the least number such that t is a sum of products of elements of Gen′_{k} and let t̂ be the formula

∃u_{0,0}, v_{0,0}, …, u_{0,k}, v_{0,k}, …, u_{k,0}, v_{k,0}, …, u_{k,k}, v_{k,k}(t′ ∧ ⋀_{i,j,n⩽k} φ_{i,j,n}).

Let t_{0}, t_{1}, … be a deg(G)-computable list of all sums of products of elements of Gen′. Since each s_{i} is a product of x_{i} with an element of I, each element of A_{G} is equal to t_{i} for some i ∈ ω. It follows easily that {t̂_{i} : i ∈ ω} is a defining family for (A_{G}, a)_{a∈S}.

Lemmas 5.3, 5.14, 5.15, and 5.16 and Corollary 5.5 are enough to enable us to apply Proposition 4.1. It is straightforward to check that, for any computable presentation A of A_{G}, if U is a subset of D(A) such that Q(x, y) ⇒ (U(x) ⇔ U(y)) then the subring of A generated by U has the same degree as U, and is c.e. if U is c.e.. This establishes Theorem 1.22 in the case of integral domains of arbitrary characteristic.

5.17. Theorem. Let p be either 0 or a prime. The theory of integral domains of characteristic p is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A be an integral domains of characteristic p. Furthermore, Theorems 1.8–1.11 remain true if we also require that U be a subring of A.

Now consider the commutative semigroup generated (multiplicatively) by the elements of Gen. Let

D(x) = {x ∈ |A_{G}| : ∃r(x^{2}r = z)},
Q(x, x′) = {(x, x) : D(x)},

and

R(x, x′) = {(x, x′) : D(x) ∧ D(x′) ∧ x ≠ x′ ∧ ∃r(rxx′ = y)}.

It is not hard to check that Proposition 4.1 applies in this case, with essentially the same proof as above. (Though, of course, many of the details could be simplified in this case.) This establishes Theorem 1.22 in the case of commutative semigroups.

5.18. Theorem. The theory of commutative semigroups is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A be a commutative semigroup. Furthermore, Theorems 1.8–1.11 remain true if we also require that U be a subsemigroup of A.

6 Nilpotent Groups

In this section, we prove Theorem 1.22 in the case of 2-step nilpotent groups. Much of the proof consists of verifying the effectiveness of a coding of rings into groups due to Mal’cev [30]. Combined with the results of Section 5, this will enable us to provide analogs of Lemmas 2.6–2.9, which can then be used to establish analogs of Propositions 2.10–2.13.

We recall the following definitions from the theory of groups.

6.1. Definition. Let G be a group. The center of G is the set {x ∈ |G| : ∀y ∈ |G|(xy = yx)}. The commutator [x, y] of x, y ∈ |G| is the element xyx^{−1}y^{−1}. The group G is 2-step nilpotent if [x, y] is in the center of G for every pair of elements x, y ∈ |G|. (A group is 1-step nilpotent if and only if it is Abelian. For the more general definition of n-step nilpotent groups, see any standard textbook on group theory, such as [38].)

Let R = (|R|, +, ·, 0, 1) be a countably infinite ring with unit of characteristic p > 2. The deg(R)-computably presentable group G_{R} is defined to be the set of all triples (a, b, c), a, b, c ∈ |R|, with multiplication given by the formula

(a, b, c)(x, y, z) = (a + x, b + y, b · x + c + z).

It is easy to check that this multiplication is associative, that the triple e = (0, 0, 0) is the identity element for it, and that (a, b, c)^{−1} = (−a, −b, b · a − c). Note that the center of G_{R} consists of all elements of the form (0, 0, c).

Fix a deg(R)-computable presentation of G_{R} for which the map g_{R} : (0, 0, c) ↦ c is deg(R)-computable and identify G_{R} with this presentation. For any presentation R′ of R, the deg(R′)-computable group G_{R′} and the deg(R′)-computable map g_{R′} are defined in an analogous way. Remark. The above definition also works for nonassociative rings. When R is associative, G_{R} can be represented as the group of upper triangular 3 × 3 matrices via the isomorphism

(a, b, c) ↦ (\begin{matrix}1 & b & c \\ 0 & 1 & a \\ 0 & 0 & 1 \end{matrix}) ,

a, b, c ∈ |R|, in which form G_{R} is known as the Heisenberg group of R.

We begin by establishing an analog of Lemma 2.6. Let the relation D on |G_{R}| be defined by

D(x) ⇔ x is in the center of G_{R}.

6.2. Lemma. If h : R ≅ R′ is an isomorphism then there exists a deg(h)-computable isomorphism f : G_{R} ≅ G_{R′} such that f ↾ D(G_{R}) = g_{R′}^{−1} ∘ h ∘ g_{R}.

Proof. It is easy to check that f((a, b, c)) = (h(a), h(b), h(c)) is the desired isomorphism.

Let us now consider the following properties of an expanded group (G, a_{1}, a_{2}), introduced in [30].

(G1) G is 2-step nilpotent.

(G2) The subsets

C_{i} = {x ∈ |G| : xa_{i} = a_{i}x}, i = 1, 2,

are Abelian subgroups of G.

(G3) The intersection of C_{1} and C_{2} is exactly the center Z of G.

(G4) For each pair z_{1}, z_{2} ∈ Z there exists an h(z_{1}, z_{2}) ∈ |G| such that

[a_{1}, h(z_{1}, z_{2})] = z_{1} and [a_{2}, h(z_{1}, z_{2})] = z_{2}.

(G5) There exist isomorphisms f_{i} : Z ≅ C_{i}, i = 1, 2, such that f_{1}([a_{2}, a_{1}]) = a_{1}, f_{2}([a_{2}, a_{1}]) = a_{2}^{−1}, and [a_{2}, f_{1}(z)] = [a_{1}, f_{2}(z)] = z for all z ∈ Z.

Let

a_{1} = (1, 0, 0) ∈ |G_{R}|,
a_{2} = (0, 1, 0) ∈ |G_{R}|.

6.3. Lemma. (G_{R}, a_{1}, a_{2}) satisfies (G1)–(G4).

Proof. Let Z be the center of G_{R} and let C_{i} = {x ∈ |G_{R}| : xa_{i} = a_{i}x}, i = 1, 2.

Direct computation shows that C_{1} consists of all triples of the form (a, 0, c), C_{2} consists of all triples of the form (0, b, c), and Z consists of all triples of the form (0, 0, c), so G_{R} satisfies (G3).

Since

(a, b, c)(x, y, z)(a, b, c)^{−1}(x, y, z)^{−1} = (0, 0, b · x − y · a) ∈ Z,

G_{R} satisfies (G1).

It can be easily checked that for all a, b, c, x, y, z ∈ |R| we have (a, 0, c)(x, 0, y) = (x, 0, y)(a, 0, c) and (0, b, c)(0, y, z) = (0, y, z)(0, b, c), so G_{R} satisfies (G2).

Finally, letting h((0, 0, c), (0, 0, c′)) = (c′, −c, 0), we see that G_{R} satisfies (G4).

6.4. Lemma. Let m : G_{R} → G be an isomorphism and let b_{1} = m(a_{1}) and b_{2} = m(a_{2}). Then (G, b_{1}, b_{2}) satisfies (G1)–(G5). Moreover, the functions f_{1} and f_{2} in (G5) can be chosen to be deg(G)-computable.

Proof. It is easy to check that, since (G_{R}, a_{1}, a_{2}) satisfies (G1)–(G4), so does (G, b_{1}, b_{2}).

Let Z be the center of G and let C_{i} = {x ∈ |G| : xb_{i} = b_{i}x}, i = 1, 2. To prove that a deg(G)-computable isomorphism f_{1} as in (G5) exists, we first note that the mapping λ : C_{1} → Z defined by λ(x) = [b_{2}, x] is a homomorphism of C_{1} onto Z. Indeed,

[b_{2}, xy] = b_{2}xyb_{2}^{−1}y^{−1}x^{−1} = b_{2}xb_{2}^{−1}b_{2}yb_{2}^{−1}y^{−1}x^{−1} = b_{2}xb_{2}^{−1}[b_{2}, y]x^{−1} = [b_{2}, x][b_{2}, y],

since [b_{2}, y] ∈ Z, and λ is onto because of (G4).

Now, any element of Z is equal to m((0, 0, c)) for some c ∈ |R|, and the fact that R has characteristic p implies that (0, 0, c)^{p} = (0, 0, pc) = (0, 0, 0) for every c ∈ |R|. So Z is an Abelian group satisfying the identity x^{p} = e, and can thus be thought of as a vector space over ℤ_{p} via kz = z^{k}, k ∈ ℤ_{p}. Since ℤ_{p} is finite, there exists a deg(G)- computable basis {z_{i} : i ∈ ω} for Z as a vector space with z_{0} = [b_{2}, b_{1}]. Furthermore, the set {c_{i} : i ∈ ω} of elements of C_{1} such that λ(c_{i}) = z_{i} is also deg(G)-computable. Note that c_{0} = b_{1}.

Given z ∈ Z, there is a unique way to express z as ∏_{i=1}^{n} z_{i}^{k_{i}} with 0 < k_{1}, …, k_{n} < p. Define f_{1}(z) = ∏_{i=1}^{n} c_{i}^{k_{i}}. Then

b_{2}f_{1}(z)b_{2}^{−1}f_{1}(z)^{−1} = [b_{2}, f_{1}(z)] = λ(f_{1}(z)) = λ (∏_{i=1}^{n} c_{i}^{k_{i}}) = ∏_{i=1}^{n} z_{i}^{k_{i}} = z.

Furthermore, f_{1}([b_{2}, b_{1}]) = f_{1}(z_{0}) = c_{0} = b_{1}.

A deg(G)-computable isomorphism f_{2} as in (G5) can be constructed in a similar way.

Let the relations P and M on |G_{R}| be defined by

P (x, y, z) ⇔ xy = z

and

M(x, y, z) ⇔ ∃w, w′([a_{1}, w] = x ∧ [a_{2}, w′] = y ∧ [a_{2}, w] = [a_{1}, w′] = e ∧ [w′, w] = z).

As we will see, P and M code + and ·, respectively.

6.5. Lemma. Let G be a computable presentation of G_{R}. Let m : G_{R} → G be an isomorphism and let b_{1} = m(a_{1}) and b_{2} = m(a_{2}). Suppose that x_{1}, x_{2}, y_{1}, y_{2} ∈ |G| are such that [b_{i}, x_{j}] = [b_{i}, y_{j}] for i, j ∈ {1, 2}. Then [x_{1}, x_{2}] = [y_{1}, y_{2}].

Proof. Let C_{1}, C_{2}, and Z be as in the proof of Lemma 6.4.

For i, j ∈ {1, 2}, the fact that [b_{i}, x_{j}] = [b_{i}, y_{j}] implies that b_{i}x_{j}^{−1}y_{j} = x_{j}^{−1}y_{j}b_{i}. So x_{j}^{−1}y_{j} ∈ C_{1} ∩ C_{2} = Z for j = 1, 2. Thus we have

x_{1}x_{2}x_{1}^{−1}x_{2}^{−1} = y_{1}y_{1}^{−1}x_{1}y_{2}y_{2}^{−1}x_{2}x_{1}^{−1}x_{2}^{−1} = y_{1}y_{2}y_{1}^{−1}x_{1}x_{1}^{−1}y_{2}^{−1}x_{2}x_{2}^{−1} = y_{1}y_{2}y_{1}^{−1}y_{2}^{−1}.

6.6. Lemma. The relations D, M, and P are relatively intrinsically computable. The relations D and P are invariant, while M is mapped to itself by any automorphism of G_{R} that fixes a_{1} and a_{2}. Let R′ be a presentation of R. Then D(G_{R′}) = dom(g_{R′}), and for x, y, z ∈ D(G_{R′}),

P^{G_{R′}}(x, y, z) ⇔ (g_{R′}(x) + g_{R′}(y) = g_{R′}(z))

and

M^{G_{R′}}(x, y, z) ⇔ (g_{R′}(x) · g_{R′}(y) = g_{R′}(z)).

Proof. The relations D and P are algebraic, and hence invariant, while M is algebraic over {a_{1}, a_{2}}, and hence is mapped to itself by any automorphism of G_{R} that fixes a_{1} and a_{2}.

The relation P is obviously relatively intrinsically computable, and the fact that every presentation of G_{R} satisfies (G3) implies that so is D. It is also obvious that for each x, y ∈ D(G_{R′}) there is at most one z such that P^{G_{R′}}(x, y, z).

Let b_{1}, b_{2} ∈ |G_{R′}| be defined by b_{1} = (1, 0, 0), b_{2} = (0, 1, 0). By Lemma 6.5,

∃w, w′([b_{1}, w] = x ∧ [b_{2}, w′] = y ∧ [b_{2}, w] = [b_{1}, w′] = e ∧ [w′, w] = z) ⇔ ∀w, w′(([b_{1}, w] = x ∧ [b_{2}, w′] = y ∧ [b_{2}, w] = [b_{1}, w′] = e) → [w′, w] = z).

This implies that M is relatively intrinsically computable. It also implies that for each x, y ∈ D(G_{R′}) there is at most one z such that M^{G_{R′}}(x, y, z).

Now let r, s ∈ |R′|. We are left with showing that P^{G_{R′}}((0, 0, r), (0, 0, s), (0, 0, r + s)) and M^{G_{R′}}((0, 0, r), (0, 0, s), (0, 0, r · s)).

By the definition of multiplication in G_{R′}, we have (0, 0, r)(0, 0, s) = (0, 0, r + s), so indeed P^{G_{R′}}((0, 0, r), (0, 0, s), (0, 0, r + s)).

Let w = (0, −r, 0) and w′ = (s, 0, 0). Direct computation shows that [b_{1}, w] = (0, 0, r), [b_{2}, w′] = (0, 0, s), [b_{2}, w] = [b_{1}, w′] = e, and [w′, w] = (0, 0, r · s), which implies that M^{G_{R′}}((0, 0, r), (0, 0, s), (0, 0, r · s)).

For any presentation G of G_{R}, let R̃_{G} be the ring whose domain is D(G), with addition defined by x + y = z ⇔ P^{G}(x, y, z) and multiplication defined by x · y = z ⇔ M^{G}(x, y, z). Clearly, there exist a deg(G)-computable map h_{G} and a deg(G)-computable ring R_{G} such that h_{G} : R̃_{G} → R_{G} is a deg(G)-computable presentation of R̃_{G}. If G is computable then we take R_{G} = R̃_{G} and let h_{G} be the identity. In any case, Lemma 6.6 implies that R_{G} is a deg(G)-computable presentation of R.

The following lemma, which is an analog of Lemma 2.8, can be easily checked.

6.7. Lemma. Let R′ be a computable presentation of R. Then g_{R′} is a computable isomorphism from R_{G_{R′}} to R′.

We now establish an analog of Lemma 2.9.

6.8. Lemma. Let G be a computable presentation of G_{R}. Then G is computably isomorphic to G_{R_{G}} via a map whose restriction to D(G) is equal to g_{R_{G}}^{−1} ∘ h_{G}.

Proof. Let f_{1} and f_{2} be computable functions as in (G5). On pages 225–226 of [30], property (G5) is used to show that the mapping

z = (z_{1}, z_{2}, z_{3}) ↦ τ(z) = f_{1}(h_{G}^{−1}(z_{1}))f_{2}(h_{G}^{−1}(z_{2}))^{−1}h_{G}^{−1}(z_{3})

is an isomorphism from G_{R_{G}} to G. (Of course, in [30] h_{G} is not present, since there it is not important that R_{G} have computable domain.) Since f_{1}, f_{2}, and h_{G}^{−1} are computable, so is τ. Finally, if x ∈ D(G) then τ^{−1}(x) = (0, 0, h_{G}(x)) = (g_{R_{G}}^{−1} ∘ h_{G})(x).

We now come to the analog of Lemma 2.7. The fact that M is not invariant creates a difficulty, but this can be remedied by showing that, for any computable presentation G of G_{R} and any automorphism h of G, there exists a computable automorphism g of G such that g(a_{i}^{G}) = h(a_{i}^{G}) for i = 1, 2. (See Lemma 6.14. The situation is similar to what we encountered in Section 4 in connection with Lemma 4.7.)

All the results obtained so far in this section are true for any ring R with unit of characteristic p. To prove the statement in the previous paragraph we need to impose the following additional conditions on R.

1. R is an integral domain.

2. The only invertible elements of R are 1, …, p − 1.

Note that, by Lemma 5.1, the integral domains of characteristic p constructed in Section 5 satisfy Condition 2. Since the result we wish to prove is of interest only in the case in which R is computably presentable, we will assume for the remainder of this argument that R is computable.

Let h : G_{R} ≅ G_{R} be an automorphism. Let b_{1} = (a, b, c), b_{2} = (a′, b′, c′) ∈ |G_{R}| be such that h(a_{i}) = b_{i}, i = 1, 2.

Let r = a·b′−b·a′. Note that r ≠ 0, since h((0, 0, 1)) = h([a_{1}, a_{2}]) = [b_{1}, b_{2}] = (0, 0, r). Let R̃ = R [\frac{1}{r}]. Since we are assuming that R is computable, we can take R̃ to be a computable ring. We think of G_{R} as a subgroup of GR̃.

Let g : GR̃ → GR̃ be defined by

g((x, y, z)) = (a · x + a′ · y , b · x + b′ · y , b · a′x · y + \frac{p + 1}{2} · a · b · (x^{2} − x)+

\frac{p + 1}{2} · a′ · b′ · (y^{2} − y) + c · x + c′ · y + (a · b′ − b · a′) · z) .

6.9. Lemma. The function g is a computable automorphism of GR̃ such that g(a_{i}) = b_{i}, i = 1, 2.

Proof. It is clear that g is computable and that g((1, 0, 0)) = (a, b, c) and g((0, 1, 0)) = (a′, b′, c′).

Let (x, y, z), (x′, y′, z′) ∈ |GR̃|. Straightforward but tedious expansion and matching of terms shows that g((x, y, z)(x′, y′, z′)) = g((x, y, z))g((x′, y′, z′)). (Recall that p+1 = 1 in R̃.)

We now need to show that g is surjective and injective. To show that g is surjective, pick an arbitrary element (x, y, z) of GR̃. Let d_{0} = (\frac{1}{r} · b′ · x, −\frac{1}{r} · b · x, 0) and d_{1} = (−\frac{1}{r} · a′ · y, \frac{1}{r} · a · y, 0). It is straightforward to check that, for some z_{0}, z_{1} ∈ |R̃|, we have g(d_{0}) = (x, 0, z_{0}) and g(d_{1}) = (0, y, z_{1}). Let d_{2} = (0, 0, \frac{1}{r} · (z − z_{0} − z_{1})). Then g(d_{2}) = (0, 0, z − z_{0} − z_{1}), and hence g(d_{0}d_{1}d_{2}) = (x, 0, z_{0})(0, y, z_{1})(0, 0, z − z_{0} − z_{1}) = (x, y, z).

To see that g is injective, suppose that g((x, y, z)) = (0, 0, 0). Then a · x + a′ · y = b · x + b′ · y = 0. Thus, working in the field of fractions of R̃, we have \frac{a′}{a} · y = \frac{b′}{b} · y, so that, unless y = 0, we have r = a · b′ − b · a′ = 0, which is a contradiction. So y = 0, which implies that x = 0. Now g((x, y, z)) = (0, 0, r · z), so that r · z = 0, which implies that z = 0.

6.10. Lemma. Let f : G_{R} → GR̃ be a group homomorphism such that f(a_{i}) = a_{i}, i = 1, 2. Let u, v, w ∈ D(G_{R}) be such that M^{GR̃}(f(u), f(v), f(w)). Then M^{G_{R}}(u, v, w).

Proof. There exists a w′ ∈ D(G_{R}) such that M^{G_{R}}(u, v, w′), and it is clear from the definition of M that M^{GR̃}(f(u), f(v), f(w′)). But this means that f(w′) = f(w), so w′ = w.

6.11. Lemma. R = R̃.

Proof. It is enough to show that r is invertible in R. Let s and t be such that h((0, 0, s)) = (0, 0, 1) and h((0, 0, t)) = (0, 0, r^{2}). Recall that h((0, 0, 1)) = (0, 0, r). Let i : G_{R} → GR̃ be the inclusion map and define f = g^{−1} ∘ i ∘ h. Now f is a group homomorphism from G_{R} into GR̃.

It is easy to check that f(a_{1}) = a_{1}, f(a_{2}) = a_{2}, f((0, 0, 1)) = (0, 0, 1), f((0, 0, s)) = (0, 0, \frac{1}{r}), and f((0, 0, t)) = (0, 0, r). Since M^{GR̃}((0, 0, \frac{1}{r}), (0, 0, r), (0, 0, 1)), it follows from Lemma 6.10 that M^{G_{R}}((0, 0, s), (0, 0, t), (0, 0, 1)), so that s · t = 1.

Thus s is invertible in R. By our assumption on R, this means that s = k for some 1 ⩽ k ⩽ p − 1. Let n < p be such that kn = 1 mod p. It follows that (0, 0, r) = h((0, 0, 1)) = h((0, 0, k)^{n}) = (h((0, 0, k)))^{n} = (0, 0, 1)^{n} = (0, 0, n), so r is invertible in R.

The above argument obviously holds for any computable presentation R′ of R in place of R. With R′ = R_{G}, the following lemma follows from Lemma 6.8.

6.12. Lemma. Let G be a computable presentation of G_{R} and let h be an automorphism of G. There exists a computable automorphism g of G such that g(a_{i}^{G}) = h(a_{i}^{G}), i = 1, 2.

6.13. Corollary. If G and G′ are computable presentations of G_{R} and f : G ≅ G′ is an isomorphism then there exists an automorphism g of G′ such that g ∘ f is a deg(f)- computable isomorphism and (g ∘ f)(M^{G}) = M^{G′}.

Proof. Since G and G′ are presentations of G_{R} and f is an isomorphism, there is an automorphism h of G′ such that (h ∘ f)(a_{i}^{G}) = a_{i}^{G′} for i = 1, 2. By Lemma 6.12, there is a computable automorphism g of G′ such that (g ∘ f)(a_{i}^{G}) = a_{i}^{G′} for i = 1, 2. By Lemma 6.6, (g ∘ f)(M^{G}) = M^{G′}.

The following analog of Lemma 2.7 follows easily from Corollary 6.13.

6.14. Lemma. If G and G′ are computable presentations of G_{R} and f : G ≅ G′ is an isomorphism then there exists an automorphism g of G′ such that (g ∘ f) ↾ D(G) is a deg(f)-computable isomorphism from R_{G} to R_{G′}.

Using Lemmas 6.2, 6.14, 6.7, and 6.8 in place of Lemmas 2.6, 2.7, 2.8, and 2.9, respectively, we can establish the following result by essentially the same arguments as were used in the proofs of Propositions 2.10–2.13.

6.15. Proposition. Let R = (|R|, +, ·, 0, 1) be a countably infinite integral domain of characteristic p > 2 whose only invertible elements are 1, …, p − 1. Let G_{R} be the group whose domain is the set of all triples (a, b, c), a, b, c ∈ |R|, and whose group operation is given by the formula

(a, b, c)(x, y, z) = (a + x, b + y, b · x + c + z).

Then DgSp(G_{R}) = DgSp(R), and if R is computably presentable then the following hold.

1. For any degree d, G_{R} has the same d-computable dimension as R.

2. Let x ∈ |R|. There exists an a ∈ D(G_{R}) such that (G_{R}, a) has the same computable dimension as (R, x).

3. Let S be a subring of R. There exists a subgroup U of G_{R} such that DgSp_{G_{R}}(U) = DgSp_{R}(S) and if S is intrinsically c.e. then so is U.

(The fact that U can be taken to be a subgroup in part 3 of Proposition 6.15 follows from the fact that if S is a subring of R then g_{R}^{−1}(S) is a subgroup of G_{R}.)

It follows from Proposition 6.15 and the results of Section 5 that Theorem 1.22 holds in the case of 2-step nilpotent groups.

6.16. Theorem. The theory of 2-step nilpotent groups is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, Theorems 1.8–1.11, 1.13–1.15, and 1.20 remain true if we require that A be a 2-step nilpotent group. Furthermore, Theorems 1.8–1.11 remain true if we also require that U be a subgroup of A.

A The Universality of Directed Graphs

In this appendix, we justify the terminology adopted in Definition 1.21 by giving a sufficiently effective coding of a given countable structure into a countable graph, thus showing that if a theory satisfies Definition 1.21 then it still satisfies it if “every nontrivial countable graph G” is replaced by “every nontrivial countable structure G”.

Let A be a nontrivial countable structure in a computable language with (possibly finitely many) constants c_{0}, c_{1}, …, function symbols f_{0}, f_{1}, …, and relation symbols R_{0}, R_{1}, . . .. Let k_{i} be the arity of f_{i} and let l_{i} be the arity of R_{i}.

The nontrivial directed graph G consists of the following nodes and edges.

1. A node x with an edge from x to itself.

2. A node x_{i} for each i ∈ |A|, with an edge from x to each x_{i}.

3. For each constant c_{i}, a cycle of length 4i + 2 with an edge from x_{j} to one of the elements of this cycle, where j = c_{i}^{A}.

4. For each function f_{i} and each tuple (j_{0}, …, j_{k_{i}−1}) ∈ |A|, a cycle O of length 4i+3; a chain of elements y_{0}, …, y_{k_{i}}, where y_{0} is an element of O, with an edge from y_{n} to y_{n+1} for each n < k_{i}; an edge from x_{j_{n}} to y_{n} for each n < k_{i}; and an edge from y_{k_{i}} to x_{j}, where j = f_{i}^{A}(j_{0}, …, j_{k_{i}−1}).

5. For each relation R_{i} and each tuple (j_{0}, …, j_{l_{i}−1}) ∈ |A| such that R_{i}^{A}(j_{0}, …, j_{l_{i}−1}) holds, a cycle O of length 4i + 4; a chain of elements y_{0}, …, y_{l_{i}−1}, where y_{0} is an element of O, with an edge from y_{n} to y_{n+1} for each n < l_{i} − 1; and an edge from x_{j_{n}} to y_{n} for each n < l_{i}.

6. For each relation R_{i} and each tuple (j_{0}, …, j_{l_{i}−1}) ∈ |A| such that R_{i}^{A}(j_{0}, …, j_{l_{i}−1}) does not hold, a cycle O of length 4i + 5; a chain of elements y_{0}, …, y_{l_{i}−1}, where y_{0} is an element of O, with an edge from y_{n} to y_{n+1} for each n < l_{i} − 1; and an edge from x_{j_{n}} to y_{n} for each n < l_{i}.

As an example, Figure 4 shows a portion of G in the case in which the language of A has one constant c_{0}, one unary function symbol f_{0}, and one binary relation symbol R_{0}; c_{0}^{A} = 0; f_{0}^{A}(0) = 0; f_{0}^{A}(1) = 0; and the only ordered pairs of numbers less than 2 of which R_{0}^{A} holds are (0, 0) and (1, 0). The expressions under each cycle show which fact is being coded by that cycle and its connections.

[figure: x; x_{0}; x_{1}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; c_{0}^{A} = 0; •; •; •; •; •; •; f_{0}^{A}(0) = 0; f_{0}^{A}(1) = 0; •; •; •; •; R_{0}^{A}(0, 0); R_{0}^{A}(1, 0); •; •; ¬R_{0}^{A}(0, 1); ¬R_{0}^{A}(1, 1)]

Figure 4: A portion of G

It is not hard to check, using methods similar to those of Section 2, that G has the following properties.

1. DgSp(G) = DgSp(A).

2. If A is computably presentable then the following hold.

(a) For any degree d, G has the same d-computable dimension as A.

(b) if a ∈ |A| then there exists an x ∈ |G| such that (G, x) has the same computable dimension as (A, a).

(c) if S ⊆ |A| then there exists a U ⊆ |G| such that DgSp_{G}(U) = DgSp_{A}(S) and if S is intrinsically c.e. then so is U.

References

[1] C. J. Ash, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. Amer. Math. Soc. 298 (1986) 497–514.

[2] C. J. Ash and A. Nerode, Intrinsically recursive relations, in J. N. Crossley (ed.), Aspects of Effective Algebra (Clayton, 1979) (Upside Down A Book Co., Yarra Glen, Australia, 1981) 26–41.

[3] R. Camerlo and S. Gao, The completeness of the isomorphism relation for countable Boolean algebras, to appear in Trans. Amer. Math. Soc.

[4] P. Cholak, S. S. Goncharov, B. Khoussainov, and R. A. Shore, Computably categorical structures and expansions by constants, J. Symbolic Logic 64 (1999) 13–37.

[5] R. Downey and J. B. Remmel, Questions in computable algebra and combinatorics, in P. A. Cholak, S. Lempp, M. Lerman, and R. A. Shore (eds.), Computability Theory and Its Applications (Boulder, CO, 1999), vol. 257 of Contemp. Math. (Amer. Math. Soc., Providence, RI, 2000) 95–125.

[6] Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel (eds.), Handbook of Recursive Mathematics, vol. 138–139 of Studies in Logic and the Foundations of Mathematics (Elsevier Science, Amsterdam, 1998).

[7] H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic 54 (1989) 894–914.

[8] S. S. Goncharov, The quantity of nonautoequivalent constructivizations, Algebra and Logic 16 (1977) 169–185.

[9] S. S. Goncharov, Problem of the number of non-self-equivalent constructivizations, Algebra and Logic 19 (1980) 401–414.

[10] S. S. Goncharov, Groups with a finite number of constructivizations, Soviet Math. Dokl. 23 (1981) 58–61.

[11] S. S. Goncharov, Limit equivalent constructivizations, in Mathematical Logic and the Theory of Algorithms, vol. 2 of Trudy Inst. Mat. (“Nauka” Sibirsk. Otdel., Novosibirsk, 1982) 4–12, in Russian.

[12] S. S. Goncharov, Countable Boolean Algebras and Decidability, Siberian School of Algebra and Logic (Consultants Bureau, New York, 1997).

[13] S. S. Goncharov and V. D. Dzgoev, Autostability of models, Algebra and Logic 19 (1980) 28–37.

[14] S. S. Goncharov and B. Khoussainov, On the spectrum of degrees of decidable relations, Doklady Math. 55 (1997) 55–57, research announcement.

[15] S. S. Goncharov, A. V. Molokov, and N. S. Romanovskii, Nilpotent groups of finite algorithmic dimension, Siberian Math. J. 30 (1989) 63–68.

[16] V. S. Harizanov, The possible Turing degree of the nonzero member in a two element degree spectrum, Ann. Pure Appl. Logic 60 (1993) 1–30.

[17] D. R. Hirschfeldt, Degree spectra of relations on computable structures in the presence of Δ_{2}^{0} isomorphisms, to appear.

[18] D. R. Hirschfeldt, Degree spectra of relations on structures of finite computable dimension, to appear.

[19] D. R. Hirschfeldt, B. Khoussainov, and R. A. Shore, From computable categoricity to infinite computable dimension by expansion by a constant, to appear.

[20] G. Hjorth and A. S. Kechris, Borel equivalence relations and classifications of countable models, Ann. Pure Appl. Logic 82 (1996) 221–272.

[21] W. Hodges, Model Theory, vol. 42 of Encyclopedia Math. Appl. (Cambridge University Press, Cambridge, 1993).

[22] A. S. Kechris, New directions in descriptive set theory, Bull. Symbolic Logic 5 (1999) 161–174.

[23] B. Khoussainov and R. A. Shore, Computable isomorphisms, degree spectra of relations, and Scott families, Ann. Pure Appl. Logic 93 (1998) 153–193.

[24] B. Khoussainov and R. A. Shore, Effective model theory: the number of models and their complexity, in S. B. Cooper and J. K. Truss (eds.), Models and Computability, vol. 259 of London Mathematical Society Lecture Note Series (Cambridge University Press, Cambridge, 1999) 193–239.

[25] B. Khoussainov and R. A. Shore, Solution of the Goncharov-Ash problem and the spectrum problem in the theory of computable models, Doklady Math. 61 (2000) 178–179, research announcement (Russian version in Dokl. Akad. Nauk 371 (2000) 30–31).

[26] J. F. Knight, Degrees coded into jumps of orderings, J. Symbolic Logic 51 (1986) 1034–1042.

[27] O. Kudinov, An integral domain with finite algorithmic dimension, personal communication.

[28] S. Lang, Algebra, 3rd ed. (Addison–Wesley Publishing Co., Reading, MA, 1993).

[29] P. LaRoche, Recursively represented Boolean algebras, Notices Amer. Math. Soc. 24 (1977) A–552, research announcement.

[30] A. Mal’cev, On a correspondence between rings and groups, Amer. Math. Soc. Translations (series 2) 45 (1965) 221–232.

[31] A. H. Mekler, Stability of nilpotent groups of class 2 and prime exponent, J. Symbolic Logic 46 (1981) 781–788.

[32] G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979) 289–320.

[33] T. Millar, Recursive categoricity and persistence, J. Symbolic Logic 51 (1986) 430– 434.

[34] A. T. Nurtazin, Strong and weak constructivizations and enumerable families, Algebra and Logic 13 (1974) 177–184.

[35] M. G. Peretyat’kin, Finitely Axiomatizable Theories, Siberian School of Algebra and Logic (Consultants Bureau, New York, 1997).

[36] M. Rabin and D. Scott, The undecidability of some simple theories, unpublished.

[37] J. B. Remmel, Recursively categorical linear orderings, Proc. Amer. Math. Soc. 83 (1981) 387–391.

[38] J. J. Rotman, An Introduction to the Theory of Groups, vol. 148 of Graduate Texts in Mathematics, 4th ed. (Springer-Verlag, New York, 1995).

[39] T. A. Slaman, Relative to any nonrecursive set, Proc. Amer. Math. Soc. 126 (1998) 2117–2122.

[40] R. I. Soare, Recursively Enumerable Sets and Degrees, Perspect. Math. Logic (Springer–Verlag, Heidelberg, 1987).

[41] S. Wehner, Enumerations, countable structures, and Turing degrees, Proc. Amer. Math. Soc. 126 (1998) 2131–2139.