Degree Spectra of Relations on Computable Structures in the Presence of Δ_{2}^{0} Isomorphisms

Denis R. Hirschfeldt School of Mathematical and Computing Sciences Victoria University of Wellington, New Zealand

September 27, 2000

Abstract

We give some new examples of possible degree spectra of invariant relations on Δ_{2}^{0}-categorical computable structures that demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the kinds of sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ_{2}^{0}-categorical computable structure is either intrinsically computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses [22] to establish the same result for computable relations on computable linear orderings.

We also place our results in the context of the study of which kinds of degreetheoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of Δ_{2}^{0}-categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode [3] to extend results of Harizanov [12].

Most of the results in this paper are part of the author’s doctoral dissertation, written at Cornell University under the supervision of Richard A. Shore. The author thanks Professor Shore for many useful comments and suggestions. The author was partially supported by an Alfred P. Sloan Doctoral Dissertation Fellowship.

1 Introduction

The study of properties of computable structures has formed an important and fertile branch of computable model theory. (A valuable reference is the handbook [8]. In particular, the introduction and the articles by Ershov and Goncharov [7] and Harizanov [13] give useful overviews, while the articles by Ash [1] and Goncharov [10] cover material related to the topic of this paper. Another relevant survey article is [20].) One direction this study has taken, beginning with the work of Ash and Nerode [3] in the early 1980’s, concerns the question of what can be said about the images of an additional relation U on the domain of a computable structure M (that is, one that is not the interpretation in M of a relation in the language of M) in different computable copies of M.

For example, if L is a linear ordering of type ω and S is the successor relation on L then there is a computable copy of L in which the image of S is computable, namely ω with its standard ordering. But there are also computable copies of L in which the images of S are not computable (see, for instance, [5]). In fact, for every computably enumerable (c.e.) degree a, we can construct a computable linear ordering of type ω in which the successor relation has degree a. On the other hand, the successor relation on any linear ordering is always co-c.e., so this is the most we can do.

In the previous example we see two ways of approaching the question of what happens to a relation in different copies of a structure. One, taken in [3], is to begin with a relation U on a computable structure A that is in some particular class of relations, such as computable relations or c.e. relations, and ask when is it the case that the image of U in different computable copies of A always remains in the given class.

A different approach, which was first taken by Harizanov [11] (although there are portents of this approach in earlier work such as [23]), is to look at the collection of (Turing) degrees of the images of a relation in different computable copies of a structure, which is known as the degree spectrum of the relation.

The question of which sets of degrees can be realized as degree spectra of relations on computable structures, both in the general case and with certain restrictions imposed on the relation or the structure, has received increasing attention from a number of researchers. (References can be found in the aforementioned articles in [8], as well as in [20].) Several natural classes of degrees can be so realized, for example the α-c.e. degrees for any computable ordinal α (see Section 3) and the Σ_{n}^{0} and Δ_{n}^{0} degrees for any n ∈ ω (see [16]). However, not all degree spectra of relations are natural classes of degrees. For instance, in [15] it is shown that, for every uniformly c.e. collection 𝔖 of sets of natural numbers, there is an invariant relation on a computable structure whose degree spectrum coincides with the degrees of elements of 𝔖.

In [17] it is shown for various classes of structures such as nilpotent groups and integral domains, that there are no more restrictions on the possible degree spectra of relations on structures belonging to these classes than there are in the general case. In this paper, we discuss classes of structures of which this is not true. Our main focus is on Δ_{2}^{0}-categorical structures, that is, structures for which any two computable copies are isomorphic via a Δ_{2}^{0} map. This class of structures includes several natural classes of structures, such as algebraically closed fields, graphs in which all connected components are finite, and structures in relational languages all of whose relations are unary. We show, for example, that every invariant computable relation on a Δ_{2}^{0}-categorical computable structure is either intrinsically computable (that is, computable in every computable copy of the structure) or has infinite degree spectrum. This is in contrast to the general case, since invariant computable relations with degree spectra of finite cardinality greater than 1 have been known to exist since the work of Harizanov [11].

A different approach, which was first taken by Harizanov [11] (although there are portents of this approach in earlier work such as [23]), is to look at the collection of (Turing) degrees of the images of a relation in different computable copies of a structure, which is known as the degree spectrum of the relation. First, however, in Section 3, we give some new examples of possible degree spectra of invariant relations on Δ_{2}^{0}- categorical computable structures. In Section 4, we establish results that, besides their independent interest, which will be discussed below, can be used to give a sufficient condition for a relation to have infinite degree spectrum. This condition is given in Section 5, and is applied to Δ_{2}^{0}-categorical structures and linear orderings, in the last case making use of the proof of a result of Moses [22].

There is a sense in which the study of degree spectra of relations on computable structures is as a generalization of the classical study of the degrees, since the degrees can be seen as the degree spectrum of an infinite and coinfinite relation (of any arity) on the domain of a computable structure in the empty language. (The view of the study of relations on structures as a form of generalized computability theory, and of the study of relations on computable structures as an effective version of this approach, is well-known in abstract computability theory (see [21] or [25], for instance), but the focus there has been principally on questions of definability and computability-theoretic hierarchies, rather than on degrees. Of course, it is only in the effective case that concentrating on degrees becomes natural.) From this point of view, it is interesting to consider the question of which of the constructions that have been developed in the context of the degrees as a whole (or, more to the point, the c.e. degrees, since we are dealing with computable structures and thus with issues of effectivity that do not arise in the case of the degrees as a whole) are still possible in subcases of this more general setting.

Of course, in general, nothing is possible, since there are relations whose degree spectra are singletons, and, even if we ignore this case, the existence of structures of finite computable dimension shows that not much can be done in the most general case. However, when restrictions on the relation or the structure are imposed, certain constructions become possible. Results that give sufficient conditions for the degree spectrum of a relation to contain all degrees in a given natural class of degrees (see [2] or [14], for example) can be thought of as examples of this approach, but a study of degree spectra along the lines suggested above can be carried out even when no such conditions hold.

In the case of invariant computable relations on Δ_{2}^{0}-categorical computable structures whose degree spectra are not singletons, the results of Section 4 will show that techniques for constructing infinite sets of pairwise incomparable c.e. degrees and for avoiding the cone of degrees above a given degree are always applicable. (We will show that this is also the case for computable relations on linear orderings and for relations satisfying certain decidability conditions from [3].) On the other hand, the results of Section 3 will imply that the same is not true of techniques for building noncomputable sets below a given (c.e.) degree.

2 Basic Definitions and Notation

For basic notions of computability theory and model theory, the reader is referred to [24] and [18], respectively. By degree, we will mean Turing degree unless otherwise specified. We will denote the join of degrees a and b by a ∪ b.

Since α-c.e. sets and degrees for arbitrary computable ordinals α may not be familiar to all readers, we define them here. The definition of α-c.e. sets and degrees depends on the choice of ordinal notation system; see [6] for details. When we talk about α-c.e. sets and degrees, where α is a computable ordinal, we assume that we have fixed a univalent, computably related ordinal notation system with a notation for α (and hence for all ordinals less than α).

It is slightly cumbersome to give a definition of α-c.e. sets that works for both α < ω (where we want to agree with the definition of n-c.e. sets, n ∈ ω, given by the difference hierarchy) and α ⩾ ω. The following (slightly nonstandard) definition works well for our purposes, and is easily seen to be equivalent to standard definitions of n-c.e. and α-c.e. sets and degrees (as in [6]).

2.1. Definition. Let α be a computable ordinal and assume we have fixed a univalent, computably related ordinal notation system with a notation for α. Let ⌜β⌝ denote the unique notation for β ⩽ α in this system.

A set A is α-c.e. if there exists a partial computable binary function Ψ satisfying the following conditions for all x ∈ ω. (We will say that Ψ witnesses the fact that A is α-c.e..)

1. Ψ(⌜α⌝, x)↓= 0.

2. If α ⩾ ω then there exists a β < α such that Ψ(⌜β⌝, x)↓.

3. For the least β ⩽ α such that Ψ(⌜β⌝, x)↓, Ψ(⌜β⌝, x) = A(x).

A degree is α-c.e. if it contains an α-c.e. set.

Whenever we mention a c.e. set X, we assume we have fixed some computable enumeration of X and let X[s] denote the part of X enumerated after s + 1 many steps. Similarly, whenever we mention a Δ_{2}^{0} set Y, we assume we have fixed some computable approximation of Y and let Y [s] denote the result of performing s + 1 many steps of this approximation.

When we mention a fresh large number in one of our constructions, we mean a number larger than any appearing in the construction up to that point.

For any set X, let X ↾ m = X ∩ {0, …, m − 1}.

The e^{th} partial computable function with oracle X is denoted by Φ_{e}^{X}. The evaluation of Φ_{e}^{X[s]} at stage s is denoted by Φ_{e}^{X}[s] and its value at x by Φ_{e}^{X}(x)[s]. The use of the computations Φ_{e}^{X}(x) and Φ_{e}^{X}(x)[s] are denoted by φ_{e}^{X}(x) and φ_{e}^{X}(x)[s], respectively.

Fix a one-to-one function from ω×ω onto ω and let ⟨a, b⟩ denote the image under this function of the ordered pair consisting of a ∈ ω and b ∈ ω. We will write ⟨a, b, c⟩ instead of ⟨a, ⟨b, c⟩⟩, and similarly for longer sequences of natural numbers. Let π_{1}(⟨a, b⟩) = a.

If x⃗ = (x_{0}, …, x_{m}) and y⃗ = (y_{0}, …, y_{n}) are sequences of natural numbers then x⃗(i) = x_{i}, max(x⃗) = max{x_{i} | i < k}. and x^{⌢}y⃗ is the sequence (x_{0}, …, x_{m}, y_{0}, …, y_{n}). We will write x^{⌢}z instead of x^{⌢}(z), where (z) is the sequence consisting of the single element z. If f is a function on ω then we will write f(x⃗) to mean (f(x_{0}), …, f(x_{m})).

If z ∈ ω then we will write x⃗ < z to mean that max(x⃗) < z. The notations x⃗ ⩽ z and z ⩽ x⃗ are defined analogously.

One of the central notions of computable model theory is that of a computable structure. We will always assume we are working with computable languages.

2.2. Definition. A structure A is computable if both its domain |A| and the atomic diagram of ⟨A, a⟩_{a∈|A|} are computable.

If, in addition, the existential diagram of ⟨A, a⟩_{a∈|A|} is computable then A is 1decidable.

It will be more convenient to treat equality in computable structures as actual equality rather than as a relation. This is not an important distinction, however, since every computable structure is computably isomorphic to some computable structure B such that if a ≠ b ∈ |B| then B ⊨ a ≠ b.

Of course, there are often many different ways of making a given structure computable. From the point of view of computable model theory, two computably isomorphic computable copies of a structure are the same, since they share all computable properties. However, two noncomputably isomorphic computable copies of a structure can have very different computable properties. This leads naturally to the following definitions.

2.3. Definition. 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.

2.4. Definition. The computable dimension of a computably presentable structure M is the number of computable presentations of M up to computable isomorphism.

A structure of computable dimension 1 is said to be computably categorical.

The main focus of this paper is on structures that, while perhaps not computably categorical, do have relatively simple isomorphisms between their various computable presentations.

2.5. Definition. A computably presentable structure is Δ_{2}^{0}-categorical if any two of its presentations are isomorphic via a Δ_{2}^{0} map.

As we have mentioned above, the study of additional relations on computable structures began with the work of Ash and Nerode [3], who were concerned with relations that maintain some degree of effectiveness in different computable presentations of a structure.

2.6. Definition. Let U be a relation on the domain of a computably presentable structure M and let ℭ be a class of relations. U is intrinsically ℭ on M if the image of U in any computable presentation of M is in ℭ.

An important class of relations is that of invariant relations.

2.7. Definition. A relation U on the domain of a structure M is invariant if, for every automorphism f : M ≅ M, f(U) = U.

The following definition is due to Harizanov [11].

2.8. Definition. Let U be a relation on the domain of a computably presentable structure M. The degree spectrum of U on M, DgSp_{M}(U), is the set of degrees of the images of U in all computable presentations of M.

It is also interesting to consider degree spectra of relations with respect to other reducibilities.

2.9. Definition. Let r be a reducibility, such as many-one reducibility (m-reducibility) or weak truth-table reducibility (wtt-reducibility). Let U be a relation on the domain of a computably presentable structure M. The r-degree spectrum of U on M, DgSp_{M}^{r}(U), is the set of r-degrees of the images of U in all computable presentations of M.

3 Examples of Degree Spectra of Relations on Δ_{2}^{0}- Categorical Structures

We begin with a simple observation. Let U and V be k-ary relations on the domains of computable graphs A = ⟨|A| , E⟩ and B = ⟨|B| , F ⟩, respectively. Let C = ⟨|C| , R, Q⟩ be the computable structure in the language with one binary and one unary relation defined by

|C| = {2x | x ∈ |A|} ∪ {2x + 1 | x ∈ |B|},
R = {(2x, 2y) | E(x, y)} ∪ {(2x + 1, 2y + 1) | F (x, y)},

and

Q = {2x | x ∈ |A|}.

Let

W = {(2x_{0}, …, 2x_{k−1}) | (x_{0}, …, x_{k−1}) ∈ U} ∪ {(2x_{0} + 1, …, 2x_{k−1} + 1) | (x_{0}, …, x_{k−1}) ∈ V }.

It is easy to check that

DgSp_{C}(W) = {c | ∃a, b(a ∈ DgSp_{A}(U) ∧ b ∈ DgSp_{B}(V) ∧ c = a ∪ b)}.

Furthermore, if A and B are Δ_{2}^{0}-categorical then so is C, if U and V are invariant then so is W, and, for any class of relations ℭ closed under m-equivalence and finite disjoint unions, if U and V are intrinsically ℭ then so is W.

It is not hard to modify this construction to handle the case in which U and V do not necessarily have the same arity and A and B are arbitrary computable structures, and hence establish the following result.

3.1. Proposition. Let A and B be sets of degrees and let ℭ be a class of relations closed under m-equivalence and finite disjoint unions. Let C = {c | ∃a, b(a ∈ A ∧ b ∈ B ∧ c = a ∪ b)}. If both A and B can be realized as degree spectra of intrinsically ℭ invariant relations on the domains of Δ_{2}^{0}-categorical computable structures then so can C.

Now let C_{0} be the directed graph consisting of a single node and no edges and let C_{1} be the directed graph consisting of two nodes x and y with an edge from x to y. Consider the directed graph G = ⟨|G| , E⟩ that is the disjoint union of infinitely many copies of each of C_{0} and C_{1}. Let U be the unary relation on the domain of G that holds of x if and only if there is a y such that E(x, y). Since U is defined by an existential formula in the language of directed graphs, U is intrinsically c.e.. We claim that DgSp_{G}(U) consists of all c.e. degrees. (In fact, DgSp_{G}^{m}(U) consists of all c.e. m-degrees other than the m-degrees of ∅ and ω.)

Indeed, let A be an infinite and coinfinite c.e. set and let a_{0}, a_{1}, … be a computable enumeration of A. Define a directed graph G with edge relation F as follows. Let |G| = ω and, for x, y ∈ ω, let F (x, y) hold if and only if, for some k ∈ ω, x = 2a_{k} and y = 2k + 1. It is easy to check that G is a computable presentation of G. Furthermore, U^{G}(x) ⇔ x = 2a ∧ a ∈ A, and hence U^{G} ≡_{m} A.

By modifying this example, it is possible to construct, for each n > 0, an intrinsically n-c.e. invariant relation on a Δ_{2}^{0}-categorical computable structure whose degree spectrum consists of all n-c.e. degrees. A little more work can get us a similar result with α-c.e. in place of n-c.e. for any computable ordinal α.

In this section, we show that, in fact, for any c.e. degree a and any computable ordinal α, there is an intrinsically α-c.e. invariant relation on a Δ_{2}^{0}-categorical computable structure whose degree spectrum consists of all α-c.e. degrees less than or equal to a, and we extend this result to certain other nonprincipal ideals of Δ_{2}^{0} degrees. We begin with a theorem that has a similar but simpler proof.

3.2. Theorem. Let a be a c.e. degree. There exists an invariant relation U on the domain of a Δ_{2}^{0}-categorical computably presentable structure M such that DgSp_{M}(U) consists of all degrees less than or equal to a.

Proof. The structure M will be a directed graph. We begin by defining our basic building blocks.

3.3. Definition. Let n ∈ ω. The directed graph [n] consists of n + 3 many nodes x_{0}, x_{1}, …, x_{n+2} with an edge from x_{0} to itself, an edge from x_{n+2} to x_{0} and an edge from x_{i} to x_{i+1} for each i ⩽ n + 1. We call x_{0} the top of [n].

Figure 3.1 shows [2] as an example.

[figure: •; top; •; •; •; •]

Figure 3.1: [2]

3.4. Definition. Let m⃗ = (m_{0}, m_{1}, …, m_{k}) ∈ ω^{k+1} and S ⊆ {0, 1, …, k}. The directed graph [m⃗, S] consists of the following nodes and edges.

1. k + 1 many nodes x_{0}, x_{1}, x_{2}, …, x_{k} with an edge from x_{i} to x_{i+1} for each i < k.

2. For each i ∈ S, a copy of [2m_{i} + 1] with x_{i} as its top.

3. For each i ∈ {0, 1, …, k} − S, a copy of [2m_{i}] with x_{i} as its top.

We call x_{0} the principal node of [m⃗, S]. The height of [m⃗, S] is defined to be \left|{ \atop m}\right| and its length is defined to be max{|σ_{m}| | m ∈ m⃗}.

Figure 3.2 shows [(1, 2, 3), {2}] as an example.

[figure: •; principal; node; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

Figure 3.2: [(1, 2, 3), {2}]

Let A be a c.e. set in a and let σ_{0}, σ_{1}, … be a computable list of all finite binary strings. The idea behind Definition 3.4 is that the [m⃗, S] can be used to represent computations in which we are computably approximating a Δ_{2}^{0} oracle, with the strings σ_{m}, m ∈ m⃗, representing initial segments of approximations of the oracle and the elements of S representing stages at which the computation changes its mind about its output at a particular input. Of course, we are only interested in the case in which the oracle is A. This leads to the following definition.

3.5. Definition. We say that [m⃗, S], m⃗ = (m_{0}, m_{1}, …, m_{k}), S ⊆ {0, 1, …, k}, is Aacceptable if it satisfies both of the following conditions.

1. A ↾ |σ_{m_{k}}| = σ_{m_{k}}.

2. If i < k then σ_{m_{i}} ≠ A ↾ |σ_{m_{i}}| and, for every j < |σ_{m_{i}}|, σ_{m_{i}}(j) = 1 ⇒ A(j) = 1.

We define A[s]-acceptability analogously.

Note that, if we think of an A-acceptable [m⃗, S] as an approximation of some computation relative to A in the manner described above then condition 2 in Definition 3.5 makes sense because A is c.e.. This condition is important for two reasons. As we will see, together with condition 1 it ensures that, given a copy of an A-acceptable [m⃗, S] in some computable graph, we can A-computably determine m⃗ and S. Furthermore, it guarantees that if [m⃗, S] is A[s]-acceptable, n⃗ is a proper initial segment of m⃗, and T ⊆ \{0, …, \left|{ \atop n}\right| − 1\}, then [n⃗, T] is not A[t]-acceptable for any t ⩾ s, and hence is not A-acceptable.

We now define M and U.

3.6. Definition. Let M′ be the disjoint union of infinitely many copies of each Aacceptable [m⃗, S], m⃗ ∈ ω^{k+1}, S ⊆ {0, 1, …, k}, k ∈ ω. Let T be the set of principal nodes of these copies.

The directed graph M consists of M′ and one additional root node x, with an edge from x to each element of T. We call the connected components of M′ the components of M. For any computable presentation M of M, we call the image of x in M the root node of M.

The unary relation U on the domain of M is the set of all elements of T that are principal nodes of components of M of the form [m⃗, S], |S| odd.

We need to show that U and M have the desired properties. Let [m⃗, S] have length l. The following facts, which will be used below without explicit mention, follow easily from the definitions.

1. For any s ∈ ω such that A[s] ↾ l = A ↾ l, [m⃗, S] is A-acceptable if and only if it is A[s]-acceptable.

2. If [m⃗, S] is A[s]-acceptable, A[s + 1] ↾ l ≠ A[s] ↾ l, and m is such that σ_{m} = A[s + 1] ↾ l, then [m^{⌢}m, S] is A[s + 1]-acceptable.

3. For any m ∈ ω and T = S or T = S ∪ \{\left|{ \atop m}\right|\}, [m⃗, S] can be extended to [m^{⌢}m, T] by adding new nodes and edges.

3.7. Lemma. M is Δ_{2}^{0}-categorical.

Proof. This follows from the fact that each connected component of M′ is finite.

3.8. Lemma. If M is a computable presentation of M then U^{M} ⩽_{T} A.

Proof. Let T be set of all nodes y of M such that there is an edge from y to itself. Let y ∈ T. Then y is the top of a copy of [k] for some k ∈ ω. Let m be such that k = 2m or k = 2m + 1. Define σ(y) = σ_{m} and c(y) = k − 2m. Note that T is computable, and so are the maps taking y ∈ T to σ(y) and c(y).

To A-computably determine whether x ∈ U^{M}, we can proceed as follows. First, check whether there is an edge from the root node of M to x. If not then x ∉ U^{M}. Otherwise, x is the principal node of a copy of some [m⃗, S]. In this case, by the definition of M, there is a unique list x_{0}, …, x_{n} of elements of T such that x = x_{0}, for all i < n there is an edge from x_{i} to x_{i+1}, and σ(x_{n}) = A ↾ |σ(x_{n})|. Clearly, we can A-computably find x_{0}, …, x_{n}, and hence A-computably determine c = ∑_{i=0}^{n} c(x_{i}). By the definition of U, x ∈ U^{M} if and only if c is odd.

To complete the proof of the theorem, given a set B = Φ_{e}^{A}, we need to build a computable presentation M of M such that U^{M} ≡_{T} B. (In fact, we will build M so that U^{M} ≡_{m} B.) We take advantage of the fact that M contains infinitely many copies of each of its components and proceed as follows. We first construct a computable presentation N of M such that U^{N} is computable. We then add to this presentation A-acceptable components C_{n}, n ∈ ω, such that the principal node of C_{n} is in U^{M} if and only if n ∈ B.

At each stage s + 1 in the construction of M, we will have approximations C_{n}[s + 1] for each n such that Φ_{e}^{A}(n)[t] ↓ for some t ⩽ s. Each such C_{n}[s + 1] will be a copy of some [m⃗, S] such that, for the last element m of m⃗ and the largest t ⩽ s such that Φ_{e}^{A}(n)[t]↓, σ_{m} = A[t] ↾ φ_{e}^{A}(n)[t] and |S| ≡ Φ_{e}^{A}(n)[t] mod 2.

Every time the computation Φ_{e}^{A}(n) changes, we change the approximation of C_{n} to reflect this. Since Φ_{e}^{A}(n) is total, this will guarantee that C_{n} = lim_{s} C_{n}[s] is A-acceptable and is a copy of some [m⃗, S] such that |S| ≡ Φ_{e}^{A}(n) mod 2.

3.9. Lemma. There exists a computable presentation N of M such that U^{N} is computable.

Proof. We build N in stages. By the beginning of each stage s + 1, we will have built components C_{0}[s], …, C_{k_{s}−1}[s] for some k_{s} ∈ ω, where each C_{i}[s] will be a copy of some A[s]-acceptable [m⃗_{i}[s], S_{i}]. For each i, m⃗_{i}[s] will have a limit m⃗_{i}, and thus C_{i}[s] will have a limit C_{i}.

stage 0. Choose 0 as the root node of N. Let k_{0} = 0.

stage s + 1. We break the stage up into two phases.

1. Define k_{s+1}, m⃗_{i}[s + 1], and S_{i}, k_{s} ⩽ i < k_{s+1}, so that the set {[m⃗_{i}[s + 1], S_{i}] | k_{s} ⩽ i < k_{s+1}} contains every A[s + 1]-acceptable [m⃗, S] whose height and length are less than or equal to s. For each k_{s} ⩽ i < k_{s+1}, build a new copy C_{i}[s + 1] of [m⃗_{i}[s + 1], S_{i}] using fresh large numbers and add an edge from 0 to the principal node of C_{i}[s + 1].

2. For each C_{i}[s], i < k_{s}, if C_{i}[s] is not A[s+1]-acceptable then proceed as follows. Let m be such that σ_{m} = A[s + 1] ↾ l, where l is the length of C_{i}[s]. Let m⃗_{i}[s + 1] = m⃗_{i}[s]^{⌢}m. Extend C_{i}[s] to a copy C_{i}[s + 1] of [m⃗_{i}[s + 1], S_{i}] using fresh large numbers. Note that, since C_{i}[s] is A[s]-acceptable but not C_{i}[s + 1]-acceptable, C_{i}[s + 1] is A[s + 1]-acceptable.

On the other hand, if C_{i}[s] is A[s + 1]-acceptable then let m⃗_{i}[s + 1] = m⃗_{i}[s] and C_{i}[s + 1] = C_{i}[s].

Let i ∈ ω and let s be such that C_{i}[s] is defined. It is easy to check that, for any t ⩾ s, C_{i}[t] is A[t] acceptable and has the same length as C_{i}[s]. Thus there exists a t ⩾ s such that, for all u ⩾ t, C_{i}[u] = C_{i}[t], and hence C_{i} = lim_{u} C_{i}[u] is well-defined and A-acceptable. So every C_{i} is a copy of some component of M.

Now suppose that [m⃗, S] is A-acceptable and has length l and let s ⩾ l be such that A[s + 1] ↾ l = A ↾ l. Then for every t ⩾ s there exists k_{t−1} ⩽ i < k_{t} such that C_{i}[t] is a copy of [m⃗, S] and, by the choice of s, C_{i} = C_{i}[t]. Thus each component of M has infinitely many copies in N. Together with the result of the previous paragraph, this shows that N is a computable presentation of M.

To determine whether x ∈ U^{N}, all we need to do is to look for a stage s in the construction during which numbers greater than x are used. Then x ∈ U^{N} if and only if it is the principal node of some [m⃗_{i}[s], S_{i}], i < k_{s}, with |S_{i}| odd.

3.10. Lemma. Let B ⩽_{T} A. There is a computable presentation M = ⟨|M| , E⟩ of M such that U^{M} ≡_{m} B.

Proof. Let e be such that Φ_{e}^{A} = B. By Lemma 3.9, there is a computable presentation N of M such that U^{N} is computable. We can assume that D = ω − |N| is infinite.

We extend N to another computable presentation M of M in stages. When we make use of fresh numbers in the construction, we take them from D in order. We adopt the conventions that n ⩽ s ⇒ Φ_{e}^{A}(n)[s] ↑ and A[s + 1] ↾ φ_{e}^{A}(n)[s] ≠ A[s] ↾ φ_{e}^{A}(n)[s] ⇒ Φ_{e}^{A}(n)[s + 1]↑.

At the beginning of stage s+1, we have copies C_{n}[s] of graphs [m⃗_{n}[s], S_{n}[s]] for each n < s such that Φ_{e}^{A}(n)[t]↓ for some t < s. For each n ⩽ s, we proceed as follows.

If Φ_{e}^{A}(n)[s]↓ and Φ_{e}^{A}(n)[t]↑ for all t < s then let m be such that σ_{m} = A[s] ↾ φ_{e}^{A}(n)[s] and let m⃗_{n}[s + 1] = (m). If Φ_{e}^{A}(n)[s] = 0 then let S_{n}[s + 1] = ∅; otherwise, let S_{n}[s + 1] = {0}. Let C_{n}[s + 1] be a new copy of [m⃗_{n}[s + 1], S_{n}[s + 1]], formed using fresh numbers in D, and add an edge from the root node of N to the principal node of C_{n}[s + 1].

If C_{n}[s] is defined, Φ_{e}^{A}(n)[s] ↓, and Φ_{e}^{A}(n)[s − 1] ↑, then let m be such that σ_{m} = A[s] ↾ φ_{e}^{A}(n)[s] and let m⃗_{n}[s + 1] = m⃗_{n}[s]^{⌢}m. If Φ_{e}^{A}(n)[s] ≡ |S_{n}[s]| mod 2 then let S_{n}[s + 1] = S_{n}[s]; otherwise, let S_{n}[s + 1] = S_{n}[s] ∪ {|m⃗_{n}[s]|}. Extend C_{n}[s] to a copy C_{n}[s + 1] of [m⃗_{n}[s + 1], S_{n}[s + 1]], using fresh numbers in D.

If neither of the previous two cases holds then let m⃗_{n}[s+1] = m⃗_{n}[s], S_{n}[s+1] = S_{n}[s], and C_{n}[s + 1] = C_{n}[s].

It is easy to check that M is a computable presentation of M. In particular, the following facts hold.

1. Whenever C_{n}[s] changes, it is only to reflect the fact that a number has entered A below the use of the computation Φ_{e}^{A}(n).

2. C_{n}[s] will necessarily change to reflect the last change in this use.

Thus each C_{n}[s] comes to a limit C_{n}, and it is then a copy of an A-acceptable [m⃗_{n}, S_{n}].

Let x_{n} be the principal node of C_{n}. We wish to show that U^{M} ≡_{m} B. By our choice of N, U^{M} ∩ |N| is computable, so it suffices to show that n ∈ B ⇔ x_{n} ∈ U^{M}, that is, that ∀n ∈ ω(B(n) ≡ |S_{n}| mod 2).

Fix n and let s be the least number such that Φ_{e}^{A}(n)[t] ↓= Φ_{e}^{A}(n) for all t ⩾ s. By the minimality of s, Φ_{e}^{A}(n)[s − 1] ↑, and hence one of the first two cases in the description of the stage s + 1 action of the construction of M holds for n, so that B(n) = Φ_{e}^{A}(n) = Φ_{e}^{A}(n)[s] ≡ |S_{n}[s + 1]| mod 2. Furthermore, neither of these cases ever holds after stage s + 1, so that S_{n} = S_{n}[s + 1]. Thus B(n) ≡ |S_{n}| mod 2.

The theorem follows from Lemmas 3.7, 3.8, and 3.10. ■

The above theorem could have been proved by building, instead of a graph, a structure in the language consisting of infinitely many unary relations R_{0}, R_{1}, …, the basic idea being to substitute each graph [m⃗, S], m⃗ ∈ ω^{k+1}, S ⊆ {0, …, k}, by a point x_{m⃗,S,f} for each function f : {0, …, k} → ω, letting R_{n} hold of x_{m⃗,S,f} if and only if, for some i ⩽ k, either i ∉ S and n = ⟨2m⃗(i), f(i)⟩ or i ∈ S and n = ⟨2m⃗(i) + 1, f(i)⟩. This would probably make the proof less perspicuous, but it is interesting to note that the results of this section also hold in this seemingly simpler case.

We now show how to modify the proof of Theorem 3.2 in order to realize the set of all α-c.e. degrees below a given c.e. degree as the degree spectrum of an invariant relation on a Δ_{2}^{0}-categorical computable structure.

3.11. Theorem. Let a be a c.e. degree and let α be a computable ordinal. There exists an intrinsically α-c.e. invariant relation U on the domain of a Δ_{2}^{0}-categorical computably presentable structure M such that DgSp_{M}(U) consists of all α-c.e. degrees less than or equal to a.

Proof. This proof is similar to that of Theorem 3.2; we give the necessary changes. Unless otherwise noted, we use the same notation and conventions as in that proof.

Let A be a c.e. set in a. In the proof of Theorem 3.2, we had graphs [m⃗, S] that could be used to represent computations in which we computably approximate the oracle A. In this proof, we also want to be able to represent the nonincreasing sequences of ordinals less than or equal to α that can be associated to computable approximations of α-c.e. sets. This leads to the following definitions.

3.12. Definition. Let m⃗ = (m_{0}, m_{1}, …, m_{k}) ∈ ω^{k+1}, let S ⊆ {0, 1, …, k}, and let γ⃗ = (γ_{0}, γ_{1}, …, γ_{k}) ∈ (α + 1)^{k+1} be nonincreasing. The directed graph [m⃗, S, γ⃗] consists of the following nodes and edges.

1. k + 1 many nodes x_{0}, x_{1}, x_{2}, …, x_{k} with an edge from x_{i} to x_{i+1} for each i < k.

2. For each i ∈ S, a copy of [⟨m_{i}, ⌜γ_{i}⌝, 1⟩] with x_{i} as its top.

3. For each i ∈ {0, 1, …, k} − S, a copy of [⟨m_{i}, ⌜γ_{i}⌝, 0⟩] with x_{i} as its top.

As before, we call x_{0} the principal node of [m⃗, S, γ⃗]. The height of [m⃗, S, γ⃗] is defined to be \left|{ \atop m}\right|, its length is defined to be max\{|σ_{m}| | m ∈ m⃗\}, and its range is defined to be max{⌜γ_{i}⌝ | i ⩽ k}.

3.13. Definition. Let m⃗ = (m_{0}, m_{1}, …, m_{k}) ∈ ω^{k+1}, let S ⊆ {0, 1, …, k}, and let γ⃗ = (γ_{0}, γ_{1}, …, γ_{k}) ∈ (α + 1)^{k+1} be nonincreasing. We say that [m⃗, S, γ⃗] is A-acceptable if it satisfies all of the following conditions.

1. A ↾ |σ_{m_{k}}| = σ_{m_{k}}.

2. For i < k, σ_{m_{i}} ≠ A ↾ |σ_{m_{i}}| and, for every j < |σ_{m_{i}}|, σ_{m_{i}}(j) = 1 ⇒ A(j) = 1.

3. For i > 0, if i ∈ S then γ_{i} ≠ γ_{i−1}.

4. If α ⩾ ω or 0 ∈ S then γ_{0} < α.

We define A[s]-acceptability analogously.

Now M and U are defined much as before.

3.14. Definition. Let M′ be the disjoint union of infinitely many copies of each Aacceptable [m⃗, S, γ⃗], where, for some k ∈ ω, m⃗ ∈ ω^{k+1}, S ⊆ {0, 1, …, k}, and γ⃗ = (γ_{0}, γ_{1}, …, γ_{k}) ∈ (α + 1)^{k+1} is nonincreasing. Let T be the set of principal nodes of these copies.

The directed graph M consists of M′ and one additional root node x, with an edge from x to each element of T.

The unary relation U on the domain of M is the set of all elements of T that are principal nodes of connected components of M′ of the form [m⃗, S, γ⃗], |S| odd.

The following lemmas hold for the same reasons as the corresponding ones in the proof of Theorem 3.2.

3.15. Lemma. M is Δ_{2}^{0}-categorical.

3.16. Lemma. If M is a computable presentation of M then U^{M} ⩽_{T} A.

We also need to check that U is intrinsically α-c.e..

3.17. Lemma. If M is a computable presentation of M then U^{M} is α-c.e..

Proof. Let S be the set of all nodes y of M such that there is an edge from the root node of M to y. Let T be set of all nodes y of M such that there is an edge from y to itself. Let y ∈ T. Then y is the top of a copy of [k] for some k ∈ ω. Let m ∈ ω, β ⩽ α, and i ⩽ 1 be such that k = ⟨m, ⌜β⌝, i⟩. Define σ(y) = σ_{m}, β(y) = β, and c(y) = i. Note that T is computable, and so are the maps taking y ∈ T to σ(y), β(y), and c(y).

Define the partial computable binary function Ψ as follows.

stage 0. For all x ∈ ω, Ψ(⌜α⌝, x) = 0. If x ∉ S then Ψ(⌜β⌝, x) = 0 for all β < α. If x ∈ S then Ψ(⌜β(x)⌝, x) = c(x).

stage s + 1. For all x ∈ S, proceed as follows. Let x_{0}, …, x_{n} be the longest chain of elements of T ↾ s ∪ {x} such that x = x_{0} and for all i < n there is an edge from x_{i} to x_{i+1}. Let c = |{i < n | c(x_{i}) ≠ c(x_{i+1})}|. If Ψ(⌜β(x_{n})⌝, x) has not yet been defined then Ψ(⌜β(x_{n})⌝, x) = c.

It is not hard to check that the fact that each x ∈ S is the principal node of an A-acceptable component of M implies that Ψ witnesses that U^{M} is α-c.e. in the sense of Definition 2.1.

As before, in order to show that DgSp_{M}(U) contains every α-c.e. degree less than or equal to a, we begin by showing that it contains 0.

3.18. Lemma. There exists a computable presentation N of M such that U^{N} is computable.

Proof. We build N in stages in much the same way as before.

stage 0. Choose 0 as the root node of N. Let k_{0} = 0. stage s + 1. We break the stage up into two phases.

1. Define k_{s+1}, m⃗_{i}[s + 1], S_{i}, and γ⃗_{i}[s + 1], k_{s} ⩽ i < k_{s+1}, so that the set {[m⃗_{i}[s + 1], S_{i}, γ⃗_{i}[s + 1]] | k_{s} ⩽ i < k_{s+1}} contains every A[s + 1]-acceptable [m⃗, S, γ⃗] of height, length, and range less than or equal to s. For each k_{s} ⩽ i < k_{s+1}, build a new copy C_{i}[s + 1] of [m⃗_{i}[s + 1], S_{i}, γ⃗_{i}[s + 1]] using fresh large numbers and add an edge from 0 to the principal node of C_{i}[s + 1].

2. For each C_{i}[s], i < k_{s}, if C_{i}[s] is not A[s + 1]-acceptable then proceed as follows. Let m be such that σ_{m} = A[s + 1] ↾ l, where l is the length of C_{i}[s]. Let k be the height of C_{i}[s]. Let m⃗_{i}[s + 1] = m⃗_{i}[s]^{⌢}m and γ⃗_{i}[s + 1] = γ⃗_{i}[s]^{⌢}γ⃗_{i}(k − 1). Extend C_{i}[s] to a copy C_{i}[s + 1] of [m⃗_{i}[s + 1], S_{i}, γ⃗_{i}[s + 1]] using fresh large numbers. On the other hand, if C_{i}[s] is A[s + 1]-acceptable then let m⃗_{i}[s + 1] = m⃗_{i}[s], γ⃗_{i}[s + 1] = γ⃗_{i}[s], and C_{i}[s + 1] = C_{i}[s].

It is easy to check, as in the proof of Lemma 3.9, that for every i ∈ ω, C_{i} = lim_{s} C_{i}[s] is well-defined and A-acceptable. So every C_{i} is a copy of some component of M. Moreover, by the same argument as before, each component of M has infinitely many copies in N. Thus N is a computable presentation of M.

As before, to determine whether x ∈ U^{N}, all we need to do is to look for a stage s in the construction during which numbers greater than x are used. Then x ∈ U^{N} if and only if it is the principal node of some [m⃗_{i}[s], S_{i}, γ⃗_{i}[s]], i < k_{s}, with |S_{i}| odd.

3.19. Lemma. Let B ⩽_{T} A be α-c.e.. There exists a computable presentation M = ⟨|M| , E⟩ of M such that U^{M} ≡_{m} B.

Proof. This proof is much the same as that of Lemma 3.10; we give the necessary changes.

Let Ψ be a partial computable binary function witnessing the fact that B is α-c.e.. It is not hard to see that there exists an e ∈ ω with the following properties.

1. Φ_{e}^{A} = B.

2. If Φ_{e}^{A}(n)[s] ↓ then Ψ(⌜α⌝, n)[s] ↓ and, for the least β ⩽ α such that Ψ(⌜β⌝, n)[s] ↓, Φ_{e}^{A}(n)[s] = Ψ(⌜β⌝, n).

3. For the least number s such that Φ_{e}^{A}(n)[s]↓, if either α ⩾ ω or Φ_{e}^{A}(n)[s] = 1 then Ψ(⌜β⌝, n)[s]↓ for some β < α.

By Lemma 3.18, there is a computable presentation N of M such that U^{N} is computable. We can assume that D = ω − |N| is infinite. We extend N to another computable presentation M of M in stages. When we make use of fresh numbers in the construction, we take them from D in order.

At the beginning of stage s + 1, we have copies C_{n}[s] of graphs [m⃗_{n}[s], S_{n}[s], γ⃗_{n}[s]] for each n < s such that Φ_{e}^{A}(n)[t] ↓ for some t < s. For each n ⩽ s, we proceed as follows.

If Φ_{e}^{A}(n)[s]↓ and Φ_{e}^{A}(n)[t]↑ for all t < s then let m be such that σ_{m} = A[s] ↾ φ_{e}^{A}(n)[s] and let m⃗_{n}[s + 1] = (m). If Φ_{e}^{A}(n)[s] = 0 then let S_{n}[s + 1] = ∅; otherwise, let S_{n}[s + 1] = {0}. Let β ⩽ α be the least ordinal such that Ψ(⌜β⌝, n)[s] ↓ and let γ⃗_{n}[s + 1] = (β). Let C_{n}[s + 1] be a new copy of [m⃗_{n}[s + 1], S_{n}[s + 1], γ⃗_{n}[s + 1]], formed using fresh numbers in D, and add an edge from the root node of N to the principal node of C_{n}[s + 1].

If C_{n}[s] is defined, Φ_{e}^{A}(n)[s] ↓, and Φ_{e}^{A}(n)[s − 1] ↑, then let m be such that σ_{m} = A[s] ↾ φ_{e}^{A}(n)[s] and let m⃗_{n}[s + 1] = m⃗_{n}[s]^{⌢}m. If Φ_{e}^{A}(n)[s] ≡ |S_{n}[s]| mod 2 then let S_{n}[s + 1] = S_{n}[s]; otherwise, let S_{n}[s + 1] = S_{n}[s] ∪ {|m⃗_{n}[s]|}. Let β ⩽ α be the least ordinal such that Ψ(⌜β⌝, n)[s] ↓ and let γ⃗_{n}[s + 1] = γ⃗_{n}[s]^{⌢}β. Extend C_{n}[s] to a copy C_{n}[s + 1] of [m⃗_{n}[s + 1], S_{n}[s + 1], γ⃗_{n}[s + 1]], using fresh numbers in D.

If neither of the previous two cases holds then let m⃗_{n}[s+1] = m⃗_{n}[s], S_{n}[s+1] = S_{n}[s], γ⃗_{n}[s + 1] = γ⃗_{n}[s], and C_{n}[s + 1] = C_{n}[s].

It is easy to check that M is a computable presentation of M, and the proof that U^{M} ≡_{m} B is the same as before.

The theorem follows from Lemmas 3.15, 3.16, 3.17, and 3.19. ■

It is not hard to replace the single c.e. degree of the previous results by any finite set of degrees.

3.20. Theorem. Let a_{0}, …, a_{n} be c.e. degrees and let α be a computable ordinal.

1. There exists an invariant relation U on the domain of a Δ_{2}^{0}-categorical computably presentable structure M such that DgSp_{M}(U) consists of all degrees b such that b ⩽ a_{i} for all i ⩽ n.

2. There exists an intrinsically α-c.e. invariant relation V on the domain of a Δ_{2}^{0}- categorical computably presentable structure N such that DgSp_{N} (V) consists of all α-c.e. degrees b such that b ⩽ a_{i} for all i ⩽ n.

Proof sketch. The proof of this theorem is very similar to those of Theorems 3.2 and 3.11. We will restrict ourselves to defining M and U. It should be clear how to define N and V and complete the proof along the lines of the proofs of Theorems 3.2 and 3.11.

Let A_{0}, …, A_{n} be c.e. sets in a_{0}, …, a_{n}, respectively. Define the graphs [m⃗, S] and the concept of A_{i}-acceptability of such graphs as before. For m⃗_{0}, …, m⃗_{n} ∈ ω^{k+1} and S_{0}, …, S_{n} ⊆ {0, …, k}, the directed graph [m⃗_{0}, …, m⃗_{n}; S_{0}, …, S_{n}] consists of the following nodes and edges.

1. A coding node x and n + 1 many nodes x_{0}, …, x_{n} with an edge from x to x_{i} for each i ⩽ n.

2. For each i ⩽ n, a copy of [i] with x_{i} as its top.

3. For each i ⩽ n, a node y_{i} with an edge from x_{i} to y_{i}.

4. For each i ⩽ n, a copy of [m⃗_{i}, S_{i}] with y_{i} as its principal node.

We say that [m⃗_{0}, …, m⃗_{n}; S_{0}, …, S_{n}] is acceptable if each [m⃗_{i}, S_{i}] is A_{i}-acceptable and all |S_{i}| have the same parity. The idea, of course, is that an acceptable component can be used to represent n + 1 many simultaneous computations, each using a different A_{i} as an oracle, and all arriving at the same result. Part 2 of the definition of [m⃗_{0}, …, m⃗_{n}; S_{0}, …, S_{n}] guarantees that we can tell which representation corresponds to a given A_{i}.

Now let M′ be the disjoint union of infinitely many copies of each acceptable [m⃗_{0}, …, m⃗_{n}; S_{0}, …, S_{n}]. Let T be the set of coding nodes of these copies. The directed graph M consists of M′ and one additional node z, with an edge from z to each element of T. The unary relation U on the domain of M is the set of all elements of T that are coding nodes of components of M of the form [m⃗_{0}, …, m⃗_{n}; S_{0}, …, S_{n}], |S_{0}| odd (equivalently, |S_{i}| odd for all i ⩽ n).

For any degree a, it is easy to give an example of an invariant relation on the domain of a computably categorical structure whose degree spectrum is {a}. Thus, combining Theorem 3.2 with Proposition 3.1, we see that if a < b are degrees and b is c.e. then there exists an invariant relation U on the domain of a Δ_{2}^{0}-categorical computable structure A such that DgSp_{A}(U) consists of all degrees in the interval [a, b]. Similarly, for each computable ordinal α, there exists an intrinsically α-c.e. invariant relation U on the domain of a Δ_{2}^{0}-categorical computable structure A such that DgSp_{A}(U) consists of all α-c.e. degrees in the interval [a, b], and similar results can be obtained by combining Theorem 3.20 with Proposition 3.1.

Suppose that we add to Definition 3.5 the condition that |σ_{m_{0}}| = |σ_{m_{1}}| = ⋯ = |σ_{m_{k}}| and define M and U as in Definition 3.6. Then, given a computable presentation M of M, we can compute as a function of x the use of the A-computable procedure given in the proof of Lemma 3.8 for determining whether x ∈ U^{M}, and hence U^{M} ⩽_{wtt} A. Furthermore, Lemma 3.9 can be proved as before, as can Lemma 3.10 for B ⩽_{wtt} A. (In the proof, we need to pick e so that there is a computable bound f on the use of Φ_{e}^{A} and then adopt the convention that φ_{e}^{A}(n)[s] = f(n) for all n, s ∈ ω.) Similar changes can be made to the proofs of Theorems 3.11 and 3.20. Thus we have the following result, where we restrict ourselves to α-c.e. wtt-degrees, α ∈ ω ∪ {ω}, because every wtt-degree less than or equal to a c.e. wtt-degree is ω-c.e..

3.21. Theorem. Let a_{0}, …, a_{n} be c.e. wtt-degrees and let α ∈ ω∪{ω}. There exists an intrinsically α-c.e. invariant relation U on the domain of a Δ_{2}^{0}-categorical computably presentable structure M such that DgSp_{M}^{wtt}(U) consists of all α-c.e. wtt-degrees b such that b ⩽ a_{i} for all i ⩽ n.

The following is a natural question in light of the above results.

3.22. Question. How far can Theorems 3.2 and 3.11 be extended to the case where a is not c.e.?

By the results of Section 5, these theorems cannot hold if a is a minimal degree, and hence c.e. cannot be replaced by Δ_{2}^{0}, or even by ω-c.e., in their statements. Similarly, the existence of a minimal c.e. tt-degree implies that wtt cannot be replaced by tt, or by any stronger reducibility, in the statement of Theorem 3.21. As shown in [15], the situation is quite different if the requirement that M be Δ_{2}^{0}-categorical is dropped. For instance, for each ω-c.e. degree a > 0 there is an invariant relation on a computable structure whose degree spectrum is {0, a}, and this remains true if degree is replaced by m-degree.

As we will see in Section 5, no finite set of degrees containing 0 can be the degree spectrum of an invariant relation on the domain of a Δ_{2}^{0}-categorical computable structure. However, it is not hard to give an example of an intrinsically d.c.e. invariant relation on the domain of a Δ_{2}^{0}-categorical structure with a two-element degree spectrum, but one that does not include 0.

Indeed, let d be a maximal incomplete d.c.e. degree, as constructed in [4]. (That is, d ≠ 0′ is d.c.e. and there are no d.c.e. degrees in (d, 0′).) It is easy to construct invariant, intrinsically d.c.e. relations U and V on the domains of Δ_{2}^{0}-categorical computable structures A and B, respectively, so that the degree spectra of U and V are the singleton {d} and the set of all d.c.e. degrees, respectively. By Proposition 3.1, there exists an intrinsically d.c.e. invariant relation W on the domain of a Δ_{2}^{0}-categorical computable structure C whose degree spectrum is

{c | ∃a, b(a ∈ DgSp_{A}(U) ∧ b ∈ DgSp_{B}(V) ∧ c = a ∪ b)} = {c | d ⩽ c and c is d.c.e.} = {d, 0′}.

3.23. Question. Can the degree spectrum of an intrinsically c.e. invariant relation on a Δ_{2}^{0}-categorical computable structure have finite cardinality greater than 1?

4 Restrictions on Degree Spectra in the Presence of Δ_{2}^{0} Isomorphisms

In this section, we show that, for a computable relation U on a computable structure A such that the image of U in some Δ_{2}^{0}-isomorphic copy of A is not computable, both upper cone avoidance and the building of infinitely many pairwise incomparable degrees are possible within DgSp_{A}(U). We will give the full proof of the possibility of cone avoidance and then comment on the modifications necessary to build infinitely many pairwise incomparable degrees.

We will need some notation to talk about finite portions of a computable structure A of (possibly infinite) signature L. Let S ⊂ ω be finite. Define L_{S} to be the language obtained by restricting L to its first |S| symbols, substituting all j-ary function symbols by (j + 1)-ary relation symbols in the obvious way, and dropping any constant whose interpretation in A is not in S. Define A ↾ S to be the finite structure obtained from A by restricting the domain to |A| ∩ S and restricting the language to L_{S}.

4.1. Theorem. Let k ∈ ω. Let U^{0} and U^{1} be k-ary relations on the domains of computable structures A^{0} and A^{1}, respectively, and let B_{0}, B_{1}, … be a uniformly Δ_{2}^{0} sequence of noncomputable subsets of ω^{k}. Suppose that U^{0} is not computable, U^{1} is computable, and there exists a Δ_{2}^{0} isomorphism f : A^{0} → A^{1} such that f(U^{0}) = U^{1}. Then there exists a Δ_{2}^{0} function h : |A^{0}| → ω such that h(A^{0}) is a computable structure, h(U^{0}) is not computable, and for all n ∈ ω, B_{n} ⩽̸_{T} h(U^{0}). Proof. Let Φ_{e} be the e^{th} k-ary Turing functional. We will build the Δ_{2}^{0} function h : |A^{0}| ⟶_{onto}^{1–1} ω to satisfy the requirements

Q_{e} : Φ_{e} ≠ h(U^{0})

and

R_{⟨i,j⟩} : Φ_{i}^{h(U^{0})} ≠ B_{j}

for each e, i, j ∈ ω, while in addition guaranteeing that h(A^{0}) is a computable structure.

Since f is Δ_{2}^{0}, there exist sequences S_{0}^{i}, S_{1}^{i}, …, i = 0, 1, of subsets of ω and a computable sequence f_{0}, f_{1}, … of maps such that, for each s ∈ ω, f_{s} : A^{0} ↾ S_{s}^{0} ≅ A^{1} ↾ S_{s}^{1}, S_{0}^{i} ⊂ S_{1}^{i} ⊂ ⋯, ⋃_{s∈ω} S_{s}^{i} = |A^{i}|, and, for each x ∈ |A^{0}|, f(x) = lim_{s} f_{s}(x). For each s ∈ ω, we will denote f_{s}^{−1}(U^{1} ∩ (S_{s}^{1})^{k}) by U^{0}[s].

Our construction will be similar to the standard finite injury argument that would be used to satisfy the above requirements with a Δ_{2}^{0} set A in place of h(U^{0}). Of course, when building a Δ_{2}^{0} set, we can decide at any stage whether we want the value of A at some given element to remain the same or change. In our construction, the only thing we control is h.

At each stage s + 1, we will define the approximation h_{s+1} of h to extend either h_{s} or h_{s} ∘ f_{s}^{−1} ∘ f_{s+1}. If h_{s+1} extends h_{s} ∘ f_{s}^{−1} ∘ f_{s+1} then, for all x⃗ in the range of h_{s}, U^{0}(h_{s+1}^{−1}(x⃗))[s + 1] = U^{0}(h_{s}^{−1}(x⃗))[s], which means that h(U^{0}) remains unaltered at this stage. On the other hand, if U^{0}(h_{s}^{−1}(x⃗))[s + 1] ≠ U^{0}(h_{s}^{−1}(x⃗))[s] then we can change the value of h(U^{0}) at x⃗ by letting h_{s+1} extend h_{s}. The fact that f is Δ_{2}^{0} means that, for each x⃗ ∈ ω^{k}, there is a stage s such that, for all t ⩾ s, f_{t}^{−1} ∘ f_{t+1}(x⃗) = x⃗, which will imply that h_{t+1} extends h_{t}. This is what will allow us to ensure that lim_{s} h_{s} exists.

We now proceed with the construction. To simplify our notation, we assume without loss of generality that |A| = ω. We can do this because every infinite computable structure is computably isomorphic to one with domain ω.

stage 0. Let h_{0} = ∅. stage s + 1. For each e < s + 1, let i and j be such that ⟨i, j⟩ = e and define

q_{e,s} = \{ \begin{matrix}max(f_{s}^{−1}(z⃗)) & Q_{e} is currently satisfied \\ & through z⃗ (defined below) \\ max\{y | ∀z⃗ < y(Φ_{e}(z⃗)[s]↓)\} & otherwise, \end{matrix}

l_{e,s} = max {y | ∀z⃗ < y (Φ_{i}^{h_{s}(U^{0}[s])}(z⃗)[s]↓= B_{j}(z⃗)[s])} ,
m_{e,s} = max{l_{e,t} | t ⩽ s},

and

r_{e,s} = max {φ_{i}^{h_{s}(U^{0}[s])}(z⃗)[s] | z⃗ ⩽ m_{e,s}} .

In order to define h_{s+1}, we will begin by defining an auxiliary function g. Let e < s+1 be the least number such that

1. f_{s+1}(y) = f_{s}(y) for all y such that either y ⩽ e or h_{s}(y) ⩽ e and

2. one of the following holds.

(a) Q_{e} is not satisfied and, for some x⃗ ∈ dom(h_{s}), U^{0}(x⃗)[s + 1] ≠ U^{0}(x⃗)[s] and Φ_{e}(h_{s}(x⃗))[s]↓.

(b) Not 2.a and for some y ⩽ q_{e,s}, f_{s+1}(y) ≠ f_{s}(y).

(c) Not 2.a or 2.b, and for some y such that h_{s}(y) ⩽ r_{e,s}, f_{s+1}(y) ≠ f_{s}(y).

If no such number exists then let g = h_{s}.

If condition 2.a holds then proceed as follows. If Φ_{e}(h_{s}(x⃗)) = U^{0}(x⃗)[s] then let g = h_{s}; otherwise, let g = h_{s} ∘ f_{s}^{−1} ∘ f_{s+1}. In either case, declare Q_{e} to be satisfied through f_{s}(x⃗). We say that Q_{e} is active at stage s + 1.

If condition 2.b holds then proceed as follows. If Q_{e} is not satisfied then let g = h_{s}; otherwise, let g = h_{s} ∘ f_{s}^{−1} ∘ f_{s+1}. In either case, we say that Q_{e} is active at stage s + 1.

If condition 2.c holds then let g = h_{s} ∘ f_{s}^{−1} ∘ f_{s+1}. We say that R_{e} is active at stage s + 1.

If either Q_{e} or R_{e} is active at stage s+1 then declare each Q_{i}, i > e, to be unsatisfied. Now define h_{s+1} as follows. For y ∈ dom(g), let h_{s+1}(y) = g(y). Let y_{0} < ⋯ < y_{m}

be the elements of S_{s+1} − dom(g) and let z_{0} < ⋯ < z_{m} be the m + 1 least numbers not in rng(g). For i ⩽ m, let h_{s+1}(y_{i}) = z_{i}.

This completes the construction. We now need to show that h = lim_{s} h_{s} and h^{−1} = lim_{s} h_{s}^{−1} are well-defined, all requirements are met, and h(A^{0}) is a computable structure. We begin by showing by induction that h and h^{−1} are well-defined; each requirement is active only finitely often; for each e ∈ ω, q_{e,s} and r_{e,s} have finite limits; and for each e ∈ ω, if Φ_{e} is total then Q_{e} is eventually permanently satisfied.

For the following lemmas, fix e ∈ ω and assume by induction that, for all i < e, the requirements Q_{i} and R_{i} are active only finitely often and lim_{s} h_{s}^{−1}(i) is well-defined.

4.2. Lemma. Both h^{−1}(e) = lim_{s} h_{s}^{−1}(e) and h(e) = lim_{s} h_{s}(e) are well-defined.

Proof. Let s be a stage such that no requirement Q_{i} or R_{i}, i < e, is active after stage s. By construction, for all t ∈ ω, h_{t+1} extends either h_{t} or h_{t} ∘ f_{t}^{−1} ∘ f_{t+1}. One of the conditions for a requirement Q_{j} or R_{j}, j ⩾ e, to be active at stage t+1 is that f_{t+1}(e) = f_{t}(e) and f_{t+1}(h_{t}^{−1}(e)) = f_{t}(h_{t}^{−1}(e)). So, for all t ⩾ s, if f_{t+1}(e) ≠ f_{t}(e) or f_{t+1}(h_{t}^{−1}(e)) ≠ f_{t}(h_{t}^{−1}(e)) then no requirement is active at stage t + 1, and hence h_{t+1} extends h_{t}. Thus h_{t}(e) = h_{s}(e) and h_{t}^{−1}(e) = h_{s}^{−1}(e) for all t > s.

Let s_{0} > e be such that no requirement Q_{i} or R_{i}, i < e, is active after stage s_{0}, h_{t}^{−1}(i) = h^{−1}(i) for all t ⩾ s_{0} and i ⩽ e, and f_{t}(y) = f(y) for all t ⩾ s_{0} and all y such that either y ⩽ e or h^{−1}(i) = y for some i ⩽ e.

4.3. Lemma. If Φ_{e} is total then Q_{e} is eventually permanently satisfied.

Proof. It is enough to show that if Φ_{e} is total then Q_{e} is satisfied at some stage t > s_{0}. Suppose otherwise. We claim that we can compute U^{0}, which contradicts the hypothesis that U^{0} is not computable. Let x⃗ ∈ ω^{k}. Since Φ_{e} is total and Q_{e} is never satisfied after stage s_{0}, lim_{t} q_{e,t} = ∞. Let t > s_{0} be such that x⃗ < q_{e,t} and x⃗ ∈ (dom(h_{t}))^{k}. As mentioned above, for all u ∈ ω, h_{u+1} extends either h_{u} or h_{u} ∘ f_{u}^{−1} ∘ f_{u+1}. Furthermore, for all u ⩾ t, if f_{u+1}(x⃗) ≠ f_{u}(x⃗) then h_{u+1} extends h_{u}. So h_{u}(x⃗) = h_{t}(x⃗) for all u > t. Now let u ⩾ t be such that Φ_{e}(h_{t}(x⃗))[u] ↓. If U^{0}(x⃗)[v + 1] ≠ U^{0}(x⃗)[v] for some v ⩾ u then Q_{e} is satisfied at stage v + 1. Therefore, x⃗ ∈ U^{0} ⇔ x⃗ ∈ U^{0}[u].

4.4. Lemma. lim_{s} q_{e,s} < ∞ and Q_{e} is active only finitely often.

Proof. If Q_{e} is satisfied through z⃗ after stage s_{0} then lim_{s} q_{e,s} = max(f^{−1}(z⃗)). Otherwise, by the previous lemma, Φ_{e} is not total, and thus lim_{s} q_{e,s} is equal to the largest y such that Φ_{e}(x⃗) ↓ for all x⃗ < y. Now let t > s_{0} be such that either Q_{e} is satisfied at stage t or Q_{e} is never satisfied after stage t and, for all u > t and y ⩽ lim_{s} q_{e,s}, q_{e,u} = q_{e,t} and f_{u}(y) = f_{t}(y). Then Q_{e} is not active after stage t.

Let s_{1} ⩾ s_{0} be such that Q_{e} is not active after stage s_{1}. Let i and j be such that ⟨i, j⟩ = e.

4.5. Lemma. lim_{s} m_{e,s} < ∞.

Proof. Let t > s_{1}, x ⩽ r_{e,t}, and z = f_{t} ∘ h_{t}^{−1}(x). For any u ⩾ t, if f_{u+1}(x) ≠ f_{u}(x) then h_{u+1} extends h_{u} ∘ f_{u+1}^{−1} ∘ f_{u}. So for all u ⩾ t, f_{u} ∘ h_{u}^{−1}(x) = z. Therefore, for all u ⩾ t, h_{u}(U^{0}[u])(x) = U^{0}(h_{u}^{−1}(x))[u] = U^{1}(f_{u} ∘ h_{u}^{−1}(x)) = U^{1}(f_{t} ∘ h_{t}^{−1}(x)) = U^{0}(h_{t}^{−1}(x))[t] = h_{t}(U^{0}[t])(x).

Now assume for a contradiction that lim_{s} m_{e,s} = ∞. Then for each x⃗ ∈ ω^{k} there is a tx⃗ ∈ ω such that x⃗ < l_{e,tx⃗}. Since B_{j} is not computable and we can computably determine tx⃗ from x⃗, there exists an x⃗ ∈ ω^{k} such that B_{j}(x⃗) ≠ B_{j}(x⃗)[tx⃗]. Let u be such that, for all v > u, B_{j}(x⃗)[v] = B_{j}(x⃗)[u]. Using the result of the previous paragraph, we conclude that, for all v ⩾ u, Φ_{i}^{h_{v}(U^{0}[v])}(x⃗)[v]↓= Φ_{i}^{h_{tx⃗}(U^{0}[tx⃗])}(x⃗)[tx⃗]↓= B_{j}(x⃗)[tx⃗] ≠ B_{j}(x⃗)[v], which implies that l_{e,v} ⩽ x⃗, contradicting the assumption that lim_{s} m_{e,s} = ∞.

4.6. Lemma. lim_{s} r_{e,s} < ∞ and R_{e} is active only finitely often.

Proof. Let t > s_{1} be such that m_{e,u} = m_{e,t} for all u > t. As we have seen, h_{u}(U^{0}[u])(y⃗) = h_{t}(U^{0}[t])(y⃗) for all y⃗ ⩽ r_{e,t} and u > t. Thus, for all u > t and x⃗ ⩽ m_{e,t}, φ_{i}^{h_{u}(U^{0}[u])}(x⃗)[u] = φ_{i}^{h_{t}(U^{0}[t])}(x⃗)[t]. So r_{e} = lim_{s} r_{e,s} < ∞.

Now let t > s_{1} be such that, for all u > t, r_{e,u} = r_{e,t}. For m ⩽ r_{e}, let z_{m} = f_{t}∘h_{t}^{−1}(m). For all u > t and m ⩽ r_{e}, f_{u} ∘ h_{u}^{−1}(m) = z_{m}. Let u > t be such that, for all v > u and m ⩽ r_{e}, f_{v}^{−1}(z_{m}) = f_{u}^{−1}(z_{m}). For m ⩽ r_{e}, let y_{m} = h_{u}^{−1}(m). Now, for all v > u and m ⩽ r_{e}, h_{v}^{−1}(m) = y_{m} and f_{v}(y_{m}) = f_{u}(y_{m}). It follows that R_{e} is not active after stage u.

This completes the induction. We now show that all requirements are met and h(A^{0}) is a computable structure.

4.7. Lemma. For all e ∈ ω, Φ_{e} ≠ h(U^{0}).

Proof. If Φ_{e} is not total then there is nothing to show, so assume that Φ_{e} is total. By Lemma 4.3, for some z⃗ ∈ ω^{k} and t ∈ ω, Q_{e} is permanently satisfied through z⃗ at stage t + 1. Let y⃗ = h_{t} ∘ f_{t}^{−1}(z⃗). It is easy to check that, by the definition of h_{t+1}, Φ_{e}(y⃗) ≠ U^{1}(z⃗).

We claim that, for all u ⩾ t, h_{u+1} ∘ f_{u+1}^{−1}(z⃗) = y⃗. Indeed, let u ⩾ t and assume by induction that h_{u} ∘ f_{u}^{−1}(z⃗) = y⃗. There are two cases.

1. If f_{u+1}^{−1}(z⃗) = f_{u}^{−1}(z⃗) then, no matter which way h_{u+1} is defined, h_{u+1} ∘ f_{u+1}^{−1}(z⃗) = h_{u} ∘ f_{u}^{−1}(z⃗) = y⃗.

2. If f_{u+1}^{−1}(z⃗) ≠ f_{u}^{−1}(z⃗) then, since q_{e,u} = f_{u}^{−1}(z⃗), h_{u+1} extends h_{u} ∘ f_{u}^{−1} ∘ f_{u+1}, and hence h_{u+1} ∘ f_{u+1}^{−1}(z⃗) = h_{u} ∘ f_{u}^{−1} ∘ f_{u+1} ∘ f_{u+1}^{−1}(z⃗) = h_{u} ∘ f_{u}^{−1}(z⃗) = y⃗.

So, by induction, for all u ⩾ t, h_{u+1} ∘ f_{u+1}^{−1}(z⃗) = y⃗, and hence h ∘ f^{−1}(z⃗) = y⃗. Thus h(U^{0})(y⃗) = U^{0}(h^{−1}(y⃗)) = U^{0}(f^{−1}(z⃗)) = U^{1}(z⃗) ≠ Φ_{e}(y⃗).

4.8. Lemma. For all i ∈ ω and j < n, Φ_{i}^{h(U^{0})} ≠ B_{j}.

Proof. If Φ_{i}^{h(U^{0})} = B_{j} then lim_{s} m_{⟨i,j⟩,s} = ∞, which we have already shown not to be the case.

4.9. Lemma. h(A^{0}) is a computable structure.

Proof. For all s ∈ ω, rng(h_{s+1}) ⊃ rng(h_{s}) and h_{s+1}^{−1} ∘ h_{s} is either the identity or is equal to f_{s+1}^{−1} ∘ f_{s}, and hence is an embedding from A^{0} ↾ S_{s} into A^{0} ↾ S_{s+1}, if we restrict the latter structure to the language L_{S_{s}}. Furthermore, ⋃_{s∈ω} rng(h_{s}) = ω. So the images of h_{s} form a chain whose limit h(A^{0}) is a computable structure.

The theorem follows from Lemmas 4.7, 4.8, and 4.9. ■

It is straightforward to modify the proof of Theorem 4.1 to build, instead of one Δ_{2}^{0} map h, infinitely many such maps h_{0}, h_{1}, …, to satisfy the requirements

Q_{e} : Φ_{e} ≠ h_{i}(U^{0})

and

R_{⟨e,i,j⟩} : Φ_{e}^{h_{i}(U^{0})} ≠ B_{j}

for each e, i, j ∈ ω and

S_{⟨e,i,j⟩} : Φ_{e}^{h_{i}(U^{0})} ≠ h_{j}(U^{0})

for each e, i, j ∈ ω, i ≠ j, while in addition guaranteeing that each h_{j}(A^{0}) is a computable structure. This shows that, as mentioned above, in the context of invariant computable (but not intrinsically computable) relations on Δ_{2}^{0}-categorical computable structures, techniques for upper cone avoidance and building of incomparable degrees developed for the c.e. degrees are applicable. We record below this stronger form of Theorem 4.1.

4.10. Theorem. Let U be a computable relation on the domain of a computable structure A. Let D be the set of degrees of a uniformly Δ_{2}^{0} collection of noncomputable sets. If there exists a Δ_{2}^{0} function f such that f(A) is a computable structure and f(U) is not computable then DgSp_{A}(U) contains an infinite set S of pairwise incomparable degrees such that, for each a ∈ D and b ∈ S, b ⩾̸ a.

In the next section, the role of these results in showing that certain kinds of relations always have infinite degree spectra will be explored. It should be noted, however, that they already show that there are limitations on the possible degree spectra of invariant relations on computably categorical structures that do not arise in the general case, even if we restrict ourselves to infinite degree spectra.

For instance, as mentioned in Section 1, it is shown in [15] that, for every uniformly c.e. collection 𝔖 of sets of natural numbers, there is an invariant relation on a computable structure whose degree spectrum coincides with the degrees of elements of 𝔖. An appropriate choice of 𝔖 shows that, for each c.e. degree a < 0′, there is an invariant computable relation on a computable structure whose degree spectrum is infinite and such that every nonzero member is above a. Similarly, there is an invariant computable relation on a computable structure whose degree spectrum is infinite but contains no pairwise incomparable elements. By Theorem 4.10, neither of these cases is possible if the structure is Δ_{2}^{0}-categorical.

On the other hand, the results of Section 3 imply that there are certain directions in which Theorem 4.1 cannot be extended. For instance, we might have hoped that some kind of permitting might be used to show that for any c.e. degree a, the degree spectrum of an invariant computable relation on a computably categorical structure that is not intrinsically computable has a noncomputable element below a. However, Theorem 3.11 shows that this is not possible. Indeed, let a and b be a minimal pair of c.e. degrees. By Theorem 3.11, there is an invariant relation U on a Δ_{2}^{0}-categorical computable structure A such that DgSp_{A}(U) consists of all c.e. degrees less than or equal to a. For any c ∈ DgSp_{A}(U), either c = 0 or c ⩽̸ b.

5 A Sufficient Condition for Infinite Degree Spectra

The results of the previous section (either Theorem 4.10 directly or Theorem 4.1 by repeated applications) have as an immediate consequence the following sufficient condition for a relation to have infinite degree spectrum.

5.1. Theorem. Let U be a computable relation on the domain of a computable structure A. If there exists a Δ_{2}^{0} function f such that f(A) is a computable structure and f(U) is not computable then DgSp_{A}(U) is infinite.

It should be noted that this result is an analog of the following theorem of Goncharov [9], which is very useful in showing that certain classes contain no structures of finite computable dimension greater than 1.

5.2. Theorem (Goncharov). If two computable structures are Δ_{2}^{0}-isomorphic but not computably isomorphic then their computable dimension is ω.

The following result follows immediately from Theorem 5.1.

5.3. Theorem. Let U be an invariant computable relation on the domain of a Δ_{2}^{0}- categorical computable structure A. Either U is intrinsically computable or DgSp_{A}(U) is infinite.

In Theorem 5.3, both conditions on U are necessary. In Section 3, we saw that there exists an invariant relation on the domain of a Δ_{2}^{0}-categorical computable structure whose degree spectrum consists of exactly two degrees, neither of them computable. Now let A^{0}, A^{1}, U^{0}, and U^{1} be the structures and relations built by Khoussainov and Shore to prove Theorem 2.1 of [19]. We can assume that |A^{0}| ∩ |A^{1}| = ∅. Let P be the predicate {(x, y) | x ∈ U^{0} ∧ y ∈ U^{1} ∧ there is an isomorphism from A^{0} to A^{1} that extends the map x ↦ y} and let E be the equivalence relation whose equivalence classes are |A^{0}| and |A^{1}|. In the proof of Theorem 4.2 of [19], it is shown that if B is the computable structure obtained by taking the union of A^{0} and A^{1} and expanding it by P and E then B is computably categorical. Since B has exactly one nontrivial automorphism, which sends U^{1} to U^{0}, DgSp_{B}(U^{1}) = {0, deg(U^{0})}.

Even when A is not necessarily Δ_{2}^{0}-categorical and U is not necessarily invariant, it is sometimes possible to use Theorem 5.1 to show that either U is intrinsically computable or DgSp_{A}(U) is infinite.

In [22], Moses showed that, for any computable relation U on a linear ordering L, either U is definable by a quantifier free formula in the language of L expanded by finitely many constants (in which case it is obviously intrinsically computable) or there is a function f such that f(L) is a computable structure and f(U) is not computable. It is clear from the proof of this result that, in the latter case, f can be chosen to be Δ_{2}^{0}. Theorem 5.1 can now be invoked to establish the following result.

5.4. Theorem. Let U be a computable relation on the domain of a computable linear ordering L. Either U is intrinsically computable or DgSp_{L}(U) is infinite.

5.5. Question. Another way of phrasing Theorem 5.4 is that the degree spectrum of a computable relation on the domain of a computable linear ordering is either a singleton or infinite. How far can this result be extended to the case where the relation is not computable? Is there any relation on a computable linear ordering whose degree spectrum is finite but not a singleton?

Of course, it also follows from the proof of Moses’s result that the comments following Theorem 4.1 are also applicable in the case of linear orderings. That is, upper cone avoidance and the building of infinitely many pairwise incomparable degrees are possible within the degree spectrum of any computable but not intrinsically computable relation on a computable linear ordering.

By the proof of a result of Ash and Nerode [3], the same is true for certain relations on 1-decidable structures. The key here is the following extra decidability condition.

5.6. Definition. Let U be a relation on a computable structure A. We say that U satisfies condition (∗) if there is a computable procedure for determining, given a_{0}, …, a_{n} ∈ |A| and an existential formula ψ(x⃗) in the language of A expanded by constants for a_{0}, …, a_{n}, whether ⟨A, U, a_{0}, …, a_{n}⟩ ⊨ ∀x⃗(ψ(x⃗) → U(x⃗)).

Notice that if U is a nonempty relation on a computable structure A satisfying condition (∗) then U is computable and A is 1-decidable. Notice also that a sufficient condition for both U and its complement to satisfy condition (∗) is that ⟨A, U⟩ be 1-decidable.

Two other notions introduced in [3] are those of formally c.e. and formally computable relations.

5.7. Definition. A k-ary relation U on a computable structure A is formally c.e. if there exists a c.e. sequence ψ_{0}, ψ_{1}, … of existential formulas in the language of A expanded by finitely many constants from A such that, for every x⃗ ∈ ω^{k}, U(x⃗) ⇔ ⋁_{n∈ω} ψ_{n}(x⃗).

A relation U on a computable structure is formally computable if both it and its complement are formally c.e..

In [3] the following result was established.

5.8. Theorem (Ash and Nerode). Let U be a relation on a computable structure satisfying condition (∗). Then U is formally c.e. if and only if it is intrinsically c.e..

The proof of Theorem 5.8 shows that if a relation U on a computable structure A satisfying condition (∗) is not formally c.e. then there is a Δ_{2}^{0} function f such that f(A) is a computable structure and f(U) is not c.e.. Given a computable relation U on a computable structure A such that both it and its complement satisfy condition (∗), we can apply this result to U and its complement to conclude that either U is formally computable (in which case it is intrinsically computable) or there is a Δ_{2}^{0} function f such that f(A) is a computable structure and f(U) is not computable.

Thus we have the following results, of which only the cone avoidance part is new, the other parts having been established by Harizanov [12]. For a c.e. but not intrinsically c.e. relation U on a computable structure satisfying condition (∗), both upper cone avoidance and the building of infinitely many pairwise incomparable degrees are possible within the degree spectrum of U, and the same is true of a computable but not intrinsically computable relation on a computable structure such that both it and its complement satisfy condition (∗). In particular, in both these cases the degree spectrum is infinite.

5.9. Question. It would be interesting to know whether condition (∗) can be replaced in the above results by the weaker condition that U be computable and A be 1-decidable. In particular, is there a computable but not intrinsically computable relation on a 1decidable structure whose degree spectrum is finite?

The results of this section suggest the following question.

5.10. Question. For what other natural classes of structures is it true that every (invariant) computable but not intrinsically computable relation on a computable structure from the given class has infinite degree spectrum?

The case of Boolean algebras has been handled by Downey, Goncharov, and Hirschfeldt (in preparation). Another strong possibility, in light of results about computable dimension and well-established structure theorems, is the class of Abelian groups. On the other hand, the results of [17] give several examples of classes of structures for which there do exist computable but not intrinsically computable relations on computable structures from the given class with finite degree spectra.

References

[1] C. J. Ash, Isomorphic recursive structures, in Ershov et al. [8] 167–182.

[2] C. J. Ash, P. Cholak, and J. F. Knight, Permitting, forcing, and copying of a given recursive relation, Ann. Pure Appl. Logic 86 (1997) 219–236.

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

[4] S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp, and R. I. Soare, The d.r.e. degrees are not dense, Ann. Pure Appl. Logic 55 (1991) 125–151.

[5] R. G. Downey, Computability theory and linear orderings, in Ershov et al. [8] 823– 976.

[6] R. L. Epstein, R. Haas, and R. L. Kramer, Hierarchies of sets and degrees below 0′, in M. Lerman, J. H. Schmerl, and R. I. Soare (eds.), Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80), vol. 859 of Lecture Notes in Mathematics (Springer–Verlag, Heidelberg, 1981) 32–48.

[7] Y. L. Ershov and S. S. Goncharov, Elementary theories and their constructive models, in Ershov et al. [8] 115–166.

[8] 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).

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

[10] S. S. Goncharov, Autostable models and algorithmic dimensions, in Ershov et al. [8] 261–288.

[11] V. S. Harizanov, Degree spectrum of a recursive relation on a recursive structure, PhD Thesis, University of Wisconsin, Madison, WI (1987).

[12] V. S. Harizanov, Some effects of Ash-Nerode and other decidability conditions on degree spectra, Ann. Pure Appl. Logic 55 (1991) 51–65.

[13] V. S. Harizanov, Pure computable model theory, in Ershov et al. [8] 3–114.

[14] V. S. Harizanov, Turing degrees of certain isomorphic images of computable relations, Ann. Pure Appl. Logic 93 (1998) 103–113.

[15] D. R. Hirschfeldt, Degree spectra of intrinsically c.e. relations, to appear in J. Symbolic Logic.

[16] D. R. Hirschfeldt, Degree spectra of relations on computable structures, PhD Thesis, Cornell University, Ithaca, NY (1999).

[17] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, and A. M. Slinko, Degree spectra and computable dimension in algebraic structures, to appear.

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

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

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

[21] Y. N. Moschovakis, Elementary induction on abstract structures, vol. 77 of Studies in Logic and the Foundations of Mathematics (North-Holland Publishing Company, Amsterdam-London, 1974).

[22] M. Moses, Relations intrinsically recursive in linear orders, Z. Math. Logik Grundlag. Math. 32 (1986) 467–472.

[23] J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981) 572–594.

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

[25] I. N. Soskov, Intrinsically hyperarithmetical sets, Math. Log. Quart. 42 (1996) 469– 480.