Degree Spectra of Relations on Boolean Algebras

Rod G. Downey^{1} Sergey S. Goncharov^{2} Denis R. Hirschfeldt^{1}

1 School of Mathematical and Computing Sciences, Victoria University of Wellington, New Zealand 2 Novosibirsk State University and Institute of Mathematics, Novosibirsk, Russia

November 11, 2002

Abstract We show that every computable relation on a computable Boolean algebra 𝔅 is either definable by a quantifier-free formula with constants from 𝔅 (in which case it is obviously intrinsically computable) or has infinite degree spectrum.

Computable mathematics has been the focus of a large amount of research in the past few decades. Computable model theory in particular has seen vigorous and varied activity, leading to the discovery and intensive investigation of a number of central recurring themes. Among these is the study of the computability-theoretic properties of the images of a relation on a structure in different computable copies of the structure.

In this paper, we investigate computable relations on Boolean algebras from this point of view. Boolean algebras are very interesting to computable model theorists because, like linear orderings, they are a natural, nontrivial, and well-studied class of structures that exhibits much more structure than is present in the general case. Thus, studying computable Boolean algebras can give us insight into the nature of computation under constraints.

We will define the relevant concepts from computable model theory below. A valuable recent reference covering a wide range of topics in computable mathematics is the handbook [4]. For basic notions of computability theory, model theory, and (computable) Boolean algebras, the reader is referred to [14], [10], and [5], respectively.

The first and second authors’ research was partially supported by the Marsden Fund of New Zealand.

Third author’s current address: Department of Mathematics, University of Chicago, U.S.A..

When doing computable mathematics, we must abandon the idea that isomorphic structures are essentially identical. For example, under the standard ordering of the natural numbers, the successor relation is computable, but it is not hard to construct a computable linear ordering of type ω in which the successor relation is not computable. From a computability-theoretic point of view, these two computable copies of the same structure are very different. This leads us to study structures up to computable isomorphism, and gives rise to the notion of a computable presentation. (We always assume we are working with computable languages.)

1 Definition. A structure A is computable if both its domain |A| and the atomic diagram of ⟨A, a⟩_{a∈|A|} are computable. (In other words, the domain, constants, functions, and relations of A are uniformly computable.)

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

One way in which we may hope to understand the differences between computable presentations of the same structure is to look at the images in these presentations of a relation on the domain of the structure. The study of relations on computable structures began with the work of Ash and Nerode [1], and has proved to be not only a useful way to study the differences between the various computable presentations of a structure, but also a fruitful independent area of research with ties to several other parts of computable model theory, as well as with other branches of logic and computer science.

In [1], Ash and Nerode were concerned with relations that maintain some degree of effectiveness in different computable presentations of a structure.

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

Ash and Nerode gave syntactic characterizations of the intrinsically c.e. and intrinsically computable relations under an extra decidability condition (which cannot be dropped in general), and there has been a large amount of research following this approach. For instance, in [12], Moses gave a syntactic characterization of the intrinsically computable relations on computable linear orderings.

3 Theorem (Moses). Let R be a computable relation on the domain of a computable linear ordering 𝔏. Then R is either definable by a quantifier-free formula with constants from 𝔏 (in which case it is intrinsically computable) or not intrinsically computable.

Another approach to the study of relations on computable structures is to examine their degree spectra, a concept which was first defined in Harizanov’s dissertation [6], although its study dates back at least to the work of Remmel [13]. 4 Definition. Let U be a relation on the domain of a computable structure A. The degree spectrum of U on A, DgSp_{A}(U), is the set of (Turing) degrees of the images of U in all computable presentations of A.

In the general case, there are no known restrictions on the sets of degrees that can be realized as degree spectra of relations on computable structures, other than the ones that follow from the fact that the set of images of a relation on the domain of a computable structure in different computable presentations of the structure is (by definition) Σ_{1}^{1}. Furthermore, there are many natural special cases that turn out to be no less restrictive than the general case. Hirschfeldt, Khoussainov, Shore, and Slinko [9] showed that the sets of degrees that can be realized as degree spectra of relations on computable structures do not change if we restrict ourselves to structures in any of 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.

On the other hand, the class of possible degree spectra of “natural” relations appears much more restricted. Thus it becomes quite interesting to look for natural families of structures that give rise to more restricted classes of possible degree spectra of relations than in the general case. Research in this direction not only clarifies the computabilitytheoretic structure of these classes of structures, but also provides insight into the nature of computation under constraints.

One particularly interesting “pathological” phenomenon that can happen in general but not in certain particular cases is that of computable relations whose degree spectra are finite but not singletons. Such relations have been known to exist since the work of Harizanov [7], but seem to require complicated computability-theoretic constructions.

In [8], Hirschfeldt proved the following theorem. 5 Theorem (Hirschfeldt). Let R 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(R) is not computable then DgSp_{A}(R) is infinite.

Combining this result with the proof of Theorem 3 yields the following theorem.

6 Theorem (Hirschfeldt). Let R be a computable relation on the domain of a computable linear ordering. Then R either is intrinsically computable or has infinite degree spectrum.

In this paper, we prove the analog of Theorems 3 and 6 in the case of Boolean algebras. Our main tools will be Theorem 5 and a modification of a result of Moses, which we now explain.

Before proceeding, we need some notation to talk about finite portions of a computable structure A of (possibly infinite) signature L.

7 Definition. Let A be a computable structure of signature L and let m ∈ ω. Let L_{m} be the language obtained by restricting L to its first m 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 [0, m]. Define A ↾ m to be the finite structure obtained from A by restricting the domain to |A| ∩ [0, m] and restricting the language to L_{m}.

In the proof of Theorem 3, Moses used the following earlier result from [11].

8 Theorem (Moses). Let A be a computable structure and let R be a k-ary computable relation on A. Suppose there is a computable binary function f such that for every m ∈ ω there is a tuple a⃗ ∈ R for which there are infinitely many s ∈ ω with embeddings φ : A ↾ s → A ↾ f(m, s) with φ the identity on A ↾ m and φ(a⃗) ∉ R. Then R is not intrinsically c.e..

The original statement of Theorem 8 assumed that A is a structure in a finite relational language, but the original proof works in general, using the notion of “substructure” given in Definition 7. Furthermore, the proof of Theorem 8 builds a Δ_{2}^{0} function g such that g(A) is a computable structure and g(R) is not computable, and hence Theorem 5 implies that a relation satisfying the hypotheses of Theorem 8 has infinite degree spectrum. It is easy to modify the proof of Theorem 8 to establish the following result. We include a proof sketch for completeness.

9 Theorem. Let R be a k-ary computable relation on a computable structure A. Suppose there is a computable binary function f such that for every m ∈ ω there is a tuple a⃗ ∈ |A|^{k} for which there are infinitely many s ∈ ω with embeddings φ : A ↾ s → A ↾ f(m, s) with φ the identity on A ↾ m and R(φ(a⃗)) ≠ R(a⃗). Then DgSp_{A}(R) is infinite.

Proof sketch. By Theorem 5, it is enough to build a Δ_{2}^{0} function g such that g^{−1}(A) is a computable structure and g^{−1}(R) is not computable. For ease of notation, we assume that R is unary and |A| = ω.

We want to satisfy the following requirement for each e ∈ ω:

Q_{e} : g^{−1}(R) ≠ Φ_{e}.

At stage 0 we define g_{0} to be the empty map. At stage s + 1 we begin with a finite map g_{s} and extend it to a map g_{s+1}.

Let n = max(rng(g_{s})). For each e ⩽ s, define m_{e} to be the maximum of e, {g_{s}(i) | i ⩽ e}, and the last stage at which a requirement Q_{i}, i < e, acted (defined below). Say that b ∈ dom(g_{s}) may be used to attack Q_{e} if Φ_{e}(b) ↓= R(g_{s}(b)) and there is an embedding φ : A ↾ n → A ↾ f(m_{e}, n) with φ the identity on A ↾ m_{e} and R(φ ∘ g_{s}(b)) ≠ R(g_{s}(b)).

Look for the least e ⩽ s such that Q_{e} is not currently satisfied (defined below) and there is an a ∈ dom(g_{s}) that may be used to attack Q_{e}. If no such number exists then define g_{s+1} so that it extends g_{s} and g_{s+1}(x) = y, where x and y are the least numbers not in dom(g_{s}) and rng(g_{s}), respectively. Otherwise, let φ be as above and define g_{s+1} so that it extends φ ∘ g_{s} and g_{s+1}(x) = y, where x and y are the least numbers not in dom(g_{s}) and rng(φ ∘ g_{s}), respectively. We say that Q_{e} is satisfied and every Q_{i}, i > e, is unsatisfied.

This completes the construction. It is straightforward to check that g = lim_{s} g_{s} is a well-defined bijection from ω to ω, that g^{−1}(A) is a computable structure, and that the hypotheses of the theorem imply that each Q_{e} is met. For further details, see the proof of Theorem 1 in [11].

The following sufficient condition for a structure to have infinite degree spectrum follows easily from Theorem 9, but will be more convenient for our application to Boolean algebras.

10 Corollary. Let R be a computable k-ary relation on the domain of a computable structure A. Suppose there exists a Δ_{2}^{0} function h such that for each m ∈ ω there is a pair of elements x⃗_{0}, x⃗_{1} ∈ (A ↾ h(m))^{k} satisfying the following conditions.

1. R(x⃗_{0}) ≠ R(x⃗_{1}).

2. For all s ⩾ h(m) there exist embeddings g_{i} : A ↾ s → A, i = 0, 1, such that

(a) g_{0}(x⃗_{0}) = g_{1}(x⃗_{1}) and

(b) g_{0}(j) = g_{1}(j) = j for all j ∈ A ↾ m.

Then DgSp_{A}(R) is infinite.

Proof. Given m, s ∈ ω, look for a t ∈ ω such that either h(m)[t] > s or there exist x⃗_{0}, x⃗_{1} ∈ (A ↾ h(m))^{k} and embeddings g_{i} : A ↾ s → A ↾ t satisfying 1, 2.a, and 2.b above. By the hypotheses, such a t will be found. Define f(m, s) = t.

Fix m ∈ ω. By the hypotheses and the fact that there are only finitely many pairs x⃗_{0}, x⃗_{1} ∈ (A ↾ h(m))^{k}, there exists such a pair for which there are infinitely many s ∈ ω and embeddings g_{i}^{s} : A ↾ s → A ↾ f(m, s) satisfying 1, 2.a, and 2.b. For each such s we have R(g_{i}^{s}(x⃗_{i})) ≠ R(x⃗_{i}) for some i = 0, 1. So for some i = 0, 1 it must be the case that R(g_{i}^{s}(x⃗_{i})) ≠ R(x⃗_{i}) for infinitely many s ∈ ω. Taking a⃗ = x⃗_{i} we see that the hypotheses of Theorem 9 are satisfied.

We are now ready to prove the analog of Theorems 3 and 6 in the case of Boolean algebras.

11 Theorem. Let R be a computable relation on the domain of a computable Boolean algebra 𝔅. Then R either is definable by a quantifier-free formula with constants from 𝔅 (in which case it is intrinsically computable) or has infinite degree spectrum.

Proof. We assume that R is not definable by a quantifier-free formula with constants from 𝔅 and show that it satisfies the hypotheses of Corollary 10.

Given m ∈ ω, let b_{0}, b_{1}, …, b_{k} ∈ 𝔅 be such that b_{i}∩b_{j} = 0_{𝔅} for i ≠ j, b_{0}∪b_{1}∪⋯∪b_{k} = 1_{𝔅}, and the subalgebra generated by b_{0}, b_{1}, …, b_{k} contains the elements of 𝔅 ↾ m. (Here we are using the notation of Definition 7.) Let 𝔅_{i} be the subalgebra of 𝔅 consisting of those elements that are less than or equal to b_{i} (in the Boolean algebra sense).

Let r+1 be the arity of R. For a tuple ⟨x_{0}, …, x_{r}⟩, we think of each x_{i} as an element of 𝔅_{0} × ⋯ × 𝔅_{k} and denote its jth coordinate by x_{i}^{j}. We say that two tuples x⃗ and y⃗ of elements of 𝔅_{j} are compatible if there is an isomorphism f between the subalgebra of 𝔅_{j} generated by x⃗ and the subalgebra of 𝔅_{j} generated by y⃗ such that f(x⃗) = y⃗ (in other words, x⃗ and y⃗ have the same atomic type).

For each F ⊆ [0, k] (representing a guess as to which 𝔅_{i} are finite), let P_{F} be the set of all pairs (⟨x_{0}, …, x_{r}⟩, ⟨y_{0}, …, y_{r}⟩) such that for each j ⩽ k, the tuples ⟨x_{0}^{j}, …, x_{r}^{j}⟩ and ⟨y_{0}^{j}, …, y_{r}^{j}⟩ are compatible and are actually equal if j ∈ F. Let S be the set of all pairs (x⃗, y⃗) such that, for some F ⊆ [0, k], (x⃗, y⃗) is the least pair in P_{F} with R(x⃗) ≠ R(y⃗) (in some fixed effective ordering of pairs of r + 1-tuples of elements of B). Define h(m) = max{x⃗ ∪ y⃗ | (x⃗, y⃗) ∈ S}.

Clearly, h is Δ_{2}^{0}, so all we need to show to conclude that R satisfies the hypotheses of Corollary 10 is that, for each m ∈ ω, there is a pair x⃗, y⃗ ∈ (B ↾ h(m))^{r+1} such that R(x⃗) ≠ R(y⃗) and for all s ⩾ h(m) there exist embeddings g_{j} : 𝔅 ↾ s → 𝔅, j = 0, 1, such that g_{0}(x⃗) = g_{1}(y⃗) and g_{0}(l) = g_{1}(l) = l for all l ∈ 𝔅 ↾ m.

Fix m ∈ ω and let P_{F}, S, and 𝔅_{i} be as above. Let F be the set of all i such that 𝔅_{i} is finite. We claim that P_{F} ∩ S ≠ ∅. Suppose otherwise. It is easy to see that P_{F} is an equivalence relation which splits 𝔅^{r+1} into finitely many equivalence classes, and that for each equivalence class there is a quantifier-free formula with parameters b_{0}, …, b_{k} and the elements of the finite 𝔅_{i} that is satisfied exactly by the elements of that class. The assumption that P_{F} ∩ S = ∅ implies that any two P_{F} -equivalent tuples are either both in R or both not in R. Thus we can define R by a quantifier-free formula with constants b_{0}, …, b_{k} and the elements of the finite 𝔅_{i}. This contradicts our hypothesis, and hence establishes our claim.

So there is a pair (⟨x_{0}, …, x_{k}⟩, ⟨y_{0}, …, y_{k}⟩) ∈ P_{F} ∩S. Let s ⩾ h(m) and let n be such that every element of 𝔅 ↾ s can be represented as an element of 𝔅_{0} ↾ n × ⋯ × 𝔅_{k} ↾ n.

Let i ∉ F, so that 𝔅_{i} is infinite. Recall that ⟨x_{0}^{i}, …, x_{r}^{i}⟩ and ⟨y_{0}^{i}, …, y_{r}^{i}⟩ are compatible. Furthermore, the class of all finite Boolean algebras has the amalgamation property, and any finite Boolean algebra can be embedded into any infinite Boolean algebra. So there exist embeddings f_{i}^{j} : 𝔅_{i} ↾ n → 𝔅_{i}, j = 0, 1, such that f_{i}^{0}(⟨x_{0}^{i}, …, x_{r}^{i}⟩) = f_{i}^{1}(⟨y_{0}^{i}, …, y_{r}^{i}⟩).

For i ∈ F, let f_{i}^{j} : 𝔅_{i} ↾ n → 𝔅_{i} ↾ n be the identity embedding. Now we can define our required embeddings g_{0} and g_{1} by letting g_{j}(a_{0} ∪ ⋯ ∪ a_{k}) = f_{0}^{j}(a_{0}) ∪ ⋯ ∪ f_{k}^{j}(a_{k}) for a_{i} ∈ 𝔅_{i} ↾ n.

It is interesting to consider how far results such as Theorems 6 and 11 may be extended by weakening the hypothesis that the relation is computable.

12 Question. Is there any intrinsically arithmetical relation on a Boolean algebra that is not intrinsically computable but has finite degree spectrum (of cardinality greater than one)? If so, then what if the relation is intrinsically Δ_{2}^{0} or intrinsically c.e.?

In the case of linear orderings, we do know a little more. As pointed out in [8], the existence of a maximal d.c.e. degree, proved by Cooper, Harrington, Lachlan, Lempp, and Soare [2], can be used to show that there exists an intrinsically d.c.e. invariant relation on the domain of a Δ_{2}^{0}-categorical structure with a two-element degree spectrum.

We can give a similar example in the case of linear orderings, but we need to go one jump higher. It will also be convenient to note that, as shown in [2], there is a d.c.e. degree that is maximal not only in the d.c.e. degrees, but also in the 3-c.e. (or even the ω-c.e.) degrees. Relativizing the proof in [2], we see that there exists a 0′-d.c.e. degree that is maximal among the 0′-3-c.e. degrees, that is, a degree d such that d is d.c.e. relative to 0′ and there are no 0′-3-c.e. degrees in (d, 0′′).

13 Proposition. There exists a relation U on the domain of a computable linear ordering such that U has a two-element degree spectrum.

Proof. Let d be a 0′-d.c.e. degree maximal among the 0′-3-c.e. degrees, and let D ∈ d be 0′-d.c.e.. Let ⟨· , ·⟩ be a standard pairing function on ω. Define the binary relation R on the standard presentation of the linear ordering ω as follows. R(⟨n, i⟩, ⟨n, i+1⟩) holds for all i < 2n ∈ ω. If n ∈ D then R(⟨n, 2n⟩, ⟨n, 0⟩) holds; otherwise, R(⟨n, 2n⟩, ⟨n, 2n + 1⟩) and R(⟨n, 2n + 1⟩, ⟨n, 0⟩) hold. So, thinking of R as defining a directed graph, there is a (2n + 1)-cycle for each n ∈ D, a (2n + 2)-cycle for each n ∉ D, and no other cycles.

Clearly, R is 0′-3-c.e. and deg(R) = d. Now let L be a computable presentation of ω. It is easy to check that there is a Δ_{2}^{0} isomorphism f from the standard presentation of ω to L, and that this implies that R^{L} = f(R) is 0′-3-c.e. and 0′′-computable. But D is computable in R^{L}, and thus deg(R^{L}) ∈ [d, 0′′]. From this we conclude that the degree spectrum of R is either {d} or {d, 0′′}.

Now let η be the order type of the rationals and let R′ be the binary relation on (2 + η) · ω that holds of x and y if and only if x and y are elements of consecutive adjacencies. It is easy to check that the degree spectrum of R′ consists of all 0′-c.e. degrees. Thus the relation on (2 + η) · ω + ω consisting of R′ on (2 + η) · ω and R on ω has degree spectrum

{c | c = a ∨ b, a ∈ DgSp_{ω}(R), b ∈ DgSp_{(2+η)·ω}(R′)} = {c | c = d ∨ a, a is 0′-c.e.} = {d, 0′′}.

In light of this example, we ask the following question.

14 Question. Is the degree spectrum of an intrinsically Δ_{2}^{0} relation on a linear ordering always either a singleton or infinite? If not, then what if the relation is intrinsically c.e.?

While on the subject of linear orderings, we mention the question of the possible degree spectrum of the adjacency relation on a linear ordering. Downey and Moses [3] showed that there is a computable linear ordering whose adjacency relation is intrinsically complete, that is, has degree spectrum {0′}. Surprisingly little else is known about this question.

15 Question. Is there a computable linear ordering whose adjacency relation is intrinsically incomplete? Can the degree spectrum of an adjacency relation have finite cardinality greater than 2? Can it consist of a single degree other than 0 and 0′?

We conclude with the following question, which seems to be a natural next step after Theorems 6 and 11.

16 Question. Is the degree spectrum of a computable relation on an Abelian group always either a singleton or infinite?

References

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

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

[3] R. G. Downey and M. F. Moses, Recursive linear orders with incomplete successivities, Trans. Amer. Math. Soc. 326 (1991) 653–668.

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

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

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

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

[8] D. R. Hirschfeldt, Degree spectra of relations on computable structures in the presence of Δ_{2}^{0} isomorphisms, J. Symbolic Logic 67 (2002) 697–720.

[9] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, and A. M. Slinko, Degree spectra and computable dimension in algebraic structures, Ann. Pure Appl. Logic 115 (2002) 71–113.

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

[11] M. Moses, Recursive linear orderings with recursive successivities, Ann. Pure Appl. Logic 27 (1984) 253–264.

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

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

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