COMPUTABLY ENUMERABLE PARTIAL ORDERS

PETER A. CHOLAK, DAMIR D. DZHAFAROV, NOAH SCHWEBER, AND RICHARD A. SHORE

Abstract. We study the degree spectra and reverse-mathematical applications of computably enumerable and co-computably enumerable partial orders. We formulate versions of the chain/antichain principle and ascending/descending sequence principle for such orders, and show that the latter is strictly stronger than the latter. We then show that every ∅′-computable structure (or even just of c.e. degree) has the same degree spectrum as some computably enumerable (co-c.e.) partial order, and hence that there is a c.e. (co-c.e.) partial order with spectrum equal to the set of nonzero degrees.

1. Introduction

A major theme of applied computability theory is the study of the algorithmic properties of countable structures and their presentations, and of the logical content of theorems concerning them. Partial orders, in particular, have been investigated extensively, most recently by Downey, Hirschfeldt, Lempp, and Solomon [3]; Hirschfeldt and Shore [6]; Jockusch, Kjos-Hanssen, Lempp, Lerman, and Solomon [7]; and Greenberg, Montalbán, and Slaman [4].

There are several approaches taken in such analyses. Most commonly, we restrict attention to computable orders and study the effectivity (or lack thereof) of particular combinatorial constructions or objects of interest. In computable model theory we might consider noncomputable orders, and inquire instead about which ones admit computable (isomorphic) copies, or more generally, in which Turing degrees copies can be found and how complicated the witnessing isomorphisms are. Finally, in reverse mathematics we formalize theorems

The authors are grateful to Julia Knight for helpful comments. This research was partly conducted while Dzhafarov and Shore were visiting the Institute for Mathematical Sciences at the National University of Singapore in 2011, with funding from the John Templeton Foundation. Cholak was partially supported by NSF grant DMS-0800198, Dzhafarov by an NSF Postdoctoral Fellowship, and Shore by NSF grant DMS-0852811.

pertaining to partial orders, and calibrate the strengths of these theorems according to which set-existence axioms are necessary to prove them. There is a fruitful interplay between these approaches, particularly the first and last, with results and insights from one often leading to results in the others. For a detailed account of this relationship, see for example [6, Section 1]. We refer the reader to Soare [12] for background in computability theory; to Ash and Knight [1] for computable model theory; and to Simpson [10] for reverse mathematics.

In this article, we look at several questions pertaining to computably enumerable (c.e.) and co-computably enumerable (co-c.e.) partial orders. Such orders, in which the relationship between a given pair of elements is not decidable but rather may only be revealed over time, arise naturally in different contexts in computability theory. For example, the inclusion order on a uniformly computable family of sets (possibly with repetition) is co-c.e., and in fact, in terms of computational complexity the two are interchangeable, as we show (Proposition 3.1). Previous work on c.e. partial orders was done by Case [2], who studied their extensibility to total orders, and Roy [9], who studied which c.e. binary relations have computable copies.

Our interest was motivated by generalizations of the chain/antichain principle (CAC) and the ascending/descending sequence principle (ADS); see Section 3 for definitions. In the context of reverse mathematics, where the orders one considers may be regarded as being computable, it is easy to see that CAC implies ADS over RCA_{0}, but it is unknown whether the reverse implication holds. We show that when the principles are formulated for (formalizations of) c.e. and co-c.e. partial orders, the answer to the analogous question is no (Proposition 3.2 and Corollary 3.4).

We then look at the degree spectra of c.e. and co-c.e. partial orders on ω, the degree spectrum of an order being the class of degrees containing a copy of it. We show (Theorem 2.1) that even though there are c.e. partial orders with no co-c.e. copy, and co-c.e. ones with no c.e. copy, the degree spectra of the two classes of orders coincide (Corollary 4.4). Our main result is that the degree spectra of these partial orders are in fact universal for ∅′-computable structures: for every such structure (or indeed for any structure of c.e. degree) there is a c.e. (or co-c.e.) partial order with the same degree spectrum, and of the same degree if the structure has c.e. degree (Theorem 4.3). As a corollary, we obtain a new example of the Slaman-Wehner theorem ([11], [13]) that there is a structure with a copy in every nonzero degree. Specifically, it follows that such a structure can be found among the c.e. and co-c.e. partial orders in any nonzero c.e. degree (Corollary 4.6).

2. Preliminaries

In this paper, we are interested in countably infinite structures and (unless otherwise noted) assume that their domains are ω. We also identify orders with the binary relations defining them. Our terminology and notation will for the most part be standard. Given a partial order ≤_{P} on ω and A, B ⊆ ω, we say A ≤_{P} B when (∀a ∈ A)(∀b ∈ B)[a ≤_{P} b], and similarly for A <_{P} B and A ≰_{P} B. When A or B is finite, we often replace it by its members, as in A ≤_{P} b or a ≤_{P} b_{0}, b_{1}.

In referring to or building a c.e. partial order ≤_{P} on ω, we usually assume we begin with a computable partial order. We then enumerate additional pairs ⟨a, b⟩ into the order relation and speak of (computably) adding elements to (the graph of) ≤_{P}, or of setting a ≤_{P} b for some a, b ∈ ω. In the co-c.e. case, we again begin with some computable partial order, and then remove pairs, or set a ≰_{P} b. In both cases, of course, we must take care to build a transitive relation.

In this section we prove that c.e. and co-c.e. partial orders cannot be used interchangeably. The following theorem extends Theorem 2.5 of Roy [9] that there is a c.e. antisymmetric binary relation with no computable copy.

Theorem 2.1. There exists a co-c.e. partial order on ω which is not isomorphic to any c.e. such order, and conversely.

Proof. We partition ω computably into the following sets:

• {a, b, c, f, l};

• A = {a_{i,k} : i ∈ ω, k < i + 1};

• B = {b_{i} : i ∈ ω};

• C = {c_{i,k} : i ∈ ω, k < i}.

We shall use the elements of the first of these sets to identify the elements of the others, and the relations that hold between them, in a given copy of (ω, ≤_{P}). For each i ∈ ω, the a_{i,k} for k < i + 1 will code the number i as a sequence of length i + 1. The elements f and l will identify the first and last element of this sequence, and the c_{i,k} for k < i will identify pairs of consecutive elements.

Let U be a fixed Σ_{2}^{0}-complete subset of ω, and let R be a computable predicate so that U = {i : (∃x)(∀y)R(i, x, y)}. We use B to represent whether or not U(i) holds, with b_{x} ≤_{P} a_{i,0}, …, a_{i,i} if and only if we believe that (∀y)R(i, x, y) holds. Whenever we find some y such that R(i, x, y) does not hold, we thus set b_{x} ≰_{P} a_{i,0}, …, a_{i,i}, so that in the end we have that U(i) holds if and only if there is an n ∈ B with n ≤_{P} a_{i,0}, …, a_{i,i}, namely n = b_{x} for the least x such that (∀y)[R(i, x, y)].

Formally, we build ≤_{P} as follows. The initial setup is to remove elements from ω^{2} so that no relations hold except for those needed for reflexivity and the following:

• A <_{P} a;

• B <_{P} b;
• C <_{P} c;
• B <_{P} A;

and for all i ∈ ω, • a_{i,0} <_{P} f and a_{i,i} ≤_{P} l;

• a_{i,k} <_{P} c_{i,k} and a_{i,k+1} <_{P} c_{i,k} for all k < i.

We now proceed by stages, at each of which we remove at most finitely many elements from the graph of ≤_{P}. Associate to each i ∈ ω a natural number called its witness, initially declared to be 0. At stage s, consider each i ≤ s in turn, and suppose the witness of i is x. If R(i, x, y) holds for all y ≤ s, do nothing. Otherwise, set b_{x} ≰_{T} a_{i,0}, …, a_{i,i}, and redefine the witness of i to be x + 1.

The resulting order is clearly co-c.e. We also have that A is the set of elements below a and not below b, B is the set of elements below b, and C the set of elements below c. Hence, the images of these sets in any copy of (ω, ≤_{P}) are computable in that copy, and if the order in that copy is c.e. then so are B and C.

Seeking a contradiction, suppose there exists a c.e. copy (ω, ≤_{Q}) of (ω, ≤_{P}). Identify f, l, A, B, and C with their images in this copy. Given i, we search for elements a_{0}, …, a_{i} ∈ A such that

• f ≤_{Q} a_{0} and l ≤_{Q} a_{i};

• for each j < i + 1, there is an element of C below both a_{i,k} and

a_{i,k+1}. This search is computable since ≤_{Q} and C are c.e. Furthermore, the search must succeed since the images of a_{i,0}, …, a_{i,i} would do, and these are also the only possibilities. By construction, we thus have that i ∈ U if and only if there is an n ∈ B with n ≤_{Q} a_{0}, …, a_{i}. But this now yields a Σ_{1}^{0} definition of U since B is c.e., contradicting the choice of U as a Σ_{2}^{0}-complete set.

A similar argument yields a c.e. partial order with no co-c.e. copy. □

While we are here particularly interested in partial orders, there are other natural binary relations one could consider. For example, partial orders can be viewed as directed graphs and we could obtain the preceding theorem for graphs by virtually the same argument. These classes of relations (and others) were studied in [5] alongside partial orders, and the same results were obtained for each. Similarly, we can recast all the results of Section 4 about spectra of c.e. and co-c.e. structures for any of these relational structures (see the comments at the end of Section 4).

3. Generalizations of ADS and CAC

In this section, we investigate the reverse mathematical strength of several mild generalizations of the principles CAC and ADS, defined below. Recall that a chain, respectively, antichain, for a partial order ≤_{P} on an arbitrary set S ⊆ ℕ is a subset of S any two members of which are ≤_{P} -comparable, respectively, ≤_{P} -incomparable. An ascending sequence, respectively descending sequence, for ≤_{P}, is a subset of S on which ≤_{P} agrees with the natural order ≤_{N}, respectively, the reverse natural order ≥_{N}.

Chain/antichain principle (CAC). Every partial order on ℕ has either an infinite chain or an infinite antichain.

Ascending/descending sequence principle (ADS). Every linear order on ℕ has either an infinite ascending sequence or an infinite descending sequence.

The computability-theoretic and reverse mathematical content of CAC and ADS was studied by Hirschfeldt and Shore [6], who established, among other results, that both principles are strictly weaker than Ramsey’s theorem for pairs (RT_{2}^{2}) and incomparable with WKL_{0}. While CAC implies ADS over RCA_{0}, it is unknown whether ADS implies CAC ([6], Question 6.1). We show that the answer to the above question is no when we consider more general types of orders.

To begin, we can easily formalize the notions of c.e. and co-c.e. partial orders in RCA_{0}: we let a c.e. partial order be any function whose values, viewed as pairs, satisfy reflexivity, antisymmetry, and transitivity; similarly for co-c.e. orders. This allows us to formulate CAC and ADS for c.e. and co-c.e. partial orders on ℕ. (Instances of these principles are thus no longer analogous to computable partial and linear orders, but rather to c.e. or co-c.e. ones.)

A different but related class of orders is that of inclusion orders on families of sets. For computable families, inclusion is co-c.e. But since a family of sets can in general contain repetitions, we do not necessarily obtain a co-c.e. partial order isomorphic to the inclusion order on a given computable family ⟨A_{i} : i ∈ ω⟩ simply by setting i ≤ j if A_{i} ⊆ A_{j}. However, we do obviously obtain a preorder (a reflexive, transitive relation). The converse is also true:

Proposition 3.1. Every co-c.e. preorder on ω is isomorphic to the inclusion order on a computable family of sets.

Proof. Fix a co-c.e. preorder (ω, ≤_{P}), along with a computable enumeration of its complement. Write i ≰_{P,s} j and i ≤_{P,s} j depending on whether the pair ⟨i, j⟩ has or has not been enumerated by stage s, and assume our enumeration has been speeded up, if necessary, to ensure that the relation ≤_{P,s} is transitive on ω ↾ s + 1. We define ⟨A_{i} : i ∈ ℕ⟩ by stages, defining the A_{i} for i ≤ s on a common initial segment of ω at stage s. The isomorphism will be given by i ↦ A_{i}.

At stage s, add to A_{s} all elements of A_{i} for all i ≤ s with i ≤_{P,s} s. Then, consider any i, j ≤ s with i ≰_{P,s} j, and let n be the least number at which no set has yet been defined. For each k ≤ s, add n to A_{k} if i ≤_{P,s} k, and to the complement of A_{k} otherwise.

The family ⟨A_{i} : i ∈ ℕ⟩ is computable. It is also clear that if i ≰_{P} j then A_{i} ⊈ A_{j}, as some number will be put into A_{i} − A_{j} at a sufficiently large stage. Now suppose i ≤_{P} j, so that i ≤_{P,s} j for all s. By our assumption about ≤_{P,s}, for any stage s ≥ max{i, j} and any k ≤ s, we will necessarily have k ≤_{P,s} j whenever k ≤_{P,s} i. Thus, any number put into A_{i} at such a stage will also belong to A_{j}. Since numbers can only be put into A_{i} at a stage s ≥ i, it thus follows that if j < i then A_{i} ⊆ A_{j}. On the other hand, if i < j, then all elements of A_{i} are put into A_{j} at stage s = j, so we reach the same conclusion. □

We can formalize c.e. and co-c.e. preorders on ℕ in RCA_{0} just as we did partial orders, and then consider formulations of CAC and ADS for them as well. We can also look at versions for actual preorders, that is, those given as relations rather than graphs of functions. While we could formulate versions of CAC and ADS directly for families of sets under inclusion, this would be unnecessary by the preceding proposition. (Note that the proof of that proposition can be carried out in RCA_{0}.)

Each of the generalized principles can easily be seen to imply the corresponding original one. In the case of ADS, and in the case of CAC for preorders on ℕ, we also obtain reversals:

Proposition 3.2. Over RCA_{0}, the following are equivalent: (1) ADS;

(2) ADS for c.e. partial orders on ℕ;

(3) ADS for co-c.e. partial orders on ℕ;

(4) ADS for c.e. preorders on ℕ;

(5) ADS for co-c.e. preorders on ℕ;

(6) ADS for preorders on ℕ.

In addition, CAC for preorders on ℕ is equivalent to CAC.

Proof. That (1) is implied by each of the other statements is clear. To see that (1) implies (2), note that a c.e. linear order on ℕ must, for all distinct pairs i, j ∈ ℕ, have precisely one of ⟨i, j⟩ or ⟨j, i⟩ in its range. Thus, its range exists by Δ_{1}^{0} comprehension and is therefore a linear order that we may apply ADS to. An ascending or descending sequence for this order is such a sequence for the original c.e. order. The same argument shows that (1) implies (3).

Each of (4) and (5) implies (6), so it remains only to show that (1) implies (4) and (5). We prove the former, the proof of the latter being similar. So let a c.e. linear preorder be given. Formally, this is a function, but we denote it by ≤_{P} and write i ≤_{P} j to mean that ⟨i, j⟩ is in the range. We write i ∼_{P} j if i ≤_{P} j and j ≤_{P} i. There are two cases to consider.

First, suppose there exist i_{0}, …, i_{n−1} ∈ ω such that i_{j} ≁_{P} i_{k} for all distinct j, k < n, and for every i there is a j < n such that i ∼_{P} i_{j}. Then for each j < n, the set I_{j} = {i ∈ ℕ : i ∼_{P} j} exists by Δ_{1}^{0} comprehension. By the infinitary pigeonhole principle (RT^{1}), which follows from ADS ([6, Proposition 4.5]), we may fix a j < n such that I_{j} is infinite. Then this is an ascending (and also descending) sequence for ≤_{P}.

Now suppose no such i_{0}, …, i_{n−1} as above exist. Then for every finite set F there exists an i > max F such that i ≁_{P} j for all j ∈ F, and, in fact, there is a function g, total by assumption, that assigns to each F the least such i. We now define by primitive recursion a function f : ℕ → ℕ such that f(i) = g(f ↾ i) for all i ∈ ℕ. Let R be the range of f, which exists because f is strictly increasing and is thus also infinite. For all i, j ∈ R we have i <_{P} j or j <_{P} i. If we write the elements of R as r_{0} < r_{1} < ⋯, we can define a linear order <_{Q} on ℕ by i <_{Q} j if and only if r_{i} <_{P} r_{j}, which exists by Δ_{1}^{0} comprehension. If S is any infinite ascending or descending sequence for (ℕ, ≤_{Q}) as given by ADS, then {r_{i} : i ∈ S} is such a sequence for (ℕ, ≤_{P}).

A similar argument establishes the equivalence of CAC for preorders on ℕ with CAC. □

In contrast to the preceding theorem it follows by Theorem 2.1 that there are c.e. and co-c.e. partial orders with no computable copies. This also follows from the next theorem, as computable instances of CAC always have solutions that do not compute ∅′ (see Diagram 1 in [6]).

Theorem 3.3.

(1) There exists a co-c.e. partial order on ω with no infinite antichains and with all chains computing ∅′.

(2) There exists a c.e. partial order on ω with no infinite chains and with all infinite antichains computing ∅′.

Proof. To prove (1), fix a computable enumeration ⟨∅′_{s} : s ∈ ω⟩ of ∅′, and let t_{i} be the least s such that ∅′_{s} ↾ i = ∅′ ↾ i. We build a co-c.e. partial order ≤_{P} by stages. To begin, we make ≤_{P} agree with the natural order on ω.

At stage 0, we do nothing. At stage s > 0, we consider consecutive substages i ≤ s. At substage i, if no number enters ∅′ ↾ i at stage s, we do nothing and go either to substage i + 1 or to stage s + 1, depending on whether i < s or i = s. Otherwise, for all j, k with i ≤ j < k ≤ s, we make j ≰_{P} k and go to stage s + 1.

It is easily seen that ≤_{P} is a co-c.e., reflexive, antisymmetric relation, while its transitivity follows from the fact that i ≤_{P} j implies i ≤ j, and that if i ≰_{P} k for some k > i then necessarily i ≰_{P} j for all j with i < j ≤ k. So ≤_{P} is a partial order, and we note that it admits no infinite antichain since for every i, i ≤_{P} j for all j ≥ t_{i}.

Suppose now that C = {c_{0} < c_{1} < ⋯ } is an infinite chain for ≤_{P}, so that c_{0} <_{P} c_{1} <_{P} · · ·. In particular, since i ≤ c_{i}, we must have c_{i+1} ≥ t_{i} for all i by construction. Thus for every i we have ∅′↾i = ∅′_{c_{i+1}}↾i, whence it follows that ∅′ ≤_{T} C, as desired.

The argument for (2) is analogous. □

Formalizing the previous argument immediately yields the following (note that (4) and (5) are included since all partial orders are preorders):

Corollary 3.4. Over RCA_{0}, the following are equivalent:

(1) ACA_{0};

(2) CAC for c.e. partial orders on ℕ;

(3) CAC for co-c.e. partial orders on ℕ;

(4) CAC for c.e. preorders on ℕ;

(5) CAC for co-c.e. preorders on ℕ.

Together with Proposition 3.2, this provides a separation between the c.e. and co-c.e. forms of CAC on the one hand, and the c.e. and co-c.e. forms of ADS on the other.

4. Degree spectra

The degree spectrum of a countable structure S is the set of Turing degrees of copies of S. The study of degree spectra, and in particular, of which classes of degrees can be realized as spectra, has been the subject of many investigations in computable model theory. A partial survey of previous results appears in Section 1 of [5].

Every structure S we consider below will be assumed to be in a computable language, with computable signature. We also assume that S is automorphically nontrivial (meaning there is no finite F ⊆ |S| such that each permutation of |S| fixing F is an automorphism), as trivial structures are structurally uninteresting. By Knight’s theorem ([8], Theorem 4.1), the degree spectrum of any S we consider is therefore closed upwards, and thus also equal to the set of degrees of sets that compute a copy of S.

In this section, we show that the degree spectra of c.e. and co-c.e. partial orders are universal for ∅′-computable structures. In contrast with Theorem 2.1, this also shows that the classes of degree spectra of c.e. and co-c.e. partial orders are the same.

We begin with a reduction of arbitrary structures to graphs (symmetric, irreflexive binary relations). As with orders, we identify graphs on ω with their relations.

Lemma 4.1. For every structure S with domain ω there exists a graph R on ω such that R ≡_{T} S and R and S have the same degree spectrum.

Proof. This proof of this result is folklore, and has appeared in various forms in the published and unpublished literature. A complete proof can be found in [5, Appendix A]. □

Lemma 4.2. For every ∅′-computable graph R on ω there exists a c.e. (and a co-c.e.) partial order ≤_{P} on ω with the same degree spectrum. Furthermore, if R has c.e. degree then deg(≤_{P}) = deg(R).

Proof. We begin by providing a uniform effective transformation taking any graph R to a partial order ≤_{P} with a uniformly effective inverse transformation taking any copy of this partial order to a copy of R. Thus R and ≤_{P} have the same degree spectrum. We partition ω computably into the following sets:

• {a, g, r_{0}, r_{1}};

• A = {a_{i} : i ∈ ω}
• G = {g_{i,j,k} : i < j, k ∈ ω}.

Intuitively, the a_{i} represent the elements of the domain of a given copy of R and the g_{i,j,k} represent guesses at whether or not R holds of the pair (a_{i}, a_{j}) in that copy. We code these guesses using r_{0} and r_{1}, with r_{0} representing that R does not hold, and r_{1} that it does. (The guessing will be tied to a computable approximation of R when deg(R) is c.e.)

10 P. A. CHOLAK, D. D. DZHAFAROV, N. SCHWEBER, AND R. A. SHORE

The numbers a and g help us recognize the pieces of the above partition in a given copy of ≤_{P}.

We can describe the isomorphism type of the desired partial order by saying that A is the set of elements below a and not below g, and G is the set of elements below a and g. For each i < j and all k, g_{i,j,k} is below a_{i}, a_{j}, and g. Additionally, all but one g_{i,j,k} are below both r_{0} and r_{1}, and exactly one is below just one of r_{0} and r_{1}. The latter g_{i,j,k} is below r_{0} if R(i, j) does not hold, and below r_{1} otherwise. It is easy to see that we can build an order of this type computably in R, and that, conversely, any order of this type computes a copy of R (and indeed, that the transformation in either direction preserves degree). The point here is that, given a copy of this partial order, we start with the elements corresponding to a, g, r_{0} and r_{1} and then compute a copy of R with domain A by, for each a_{0}, a_{1} ∈ A, searching for a g ∈ G with g ≤ a_{0}, a_{1} such that g ≰ r_{0} or g ≰ r_{1}. Exactly one of these must happen and we let there be an edge between a_{0} and a_{1} if and only if it is the first.

When R is ∅′-computable, we make ≤_{P} c.e. as follows. By Knight’s theorem, as discussed above, we may assume that R has c.e. degree, since if not we can replace it by a copy of degree 0′. Initially, we let ≤_{P} be the transitive closure of the following conditions:

• A <_{P} a;
• G <_{P} g;
• g_{i,j,k} ≤_{P} a_{i}, a_{j} for all i < j and k.

By the modulus lemma there is a computable function f(i, j, s) with lim_{s} f(i, j, s) = 0 if R(i, j) does not hold and lim_{s} f(i, j, s) = 1 if it does, and with modulus of convergence m of the same degree as R. At stage s > 0, for every i < j ≤ s, we let k be the largest number less than or equal to s such that f(i, j, k) ≠ f(i, j, k − 1), or 0 if there is no such number. We make g_{i,j,k} ≤_{P} r_{f(i,j,k)} and g_{i,j,l} ≤_{P} r_{0}, r_{1} for all l ≤ s not equal to k.

It is easy to see from the limit properties of f(i, j, s) that ≤_{P} is c.e. and that it has the isomorphism type described above. Thus, in particular, its degree spectrum is the same as that of R. Furthermore, for each i < j it is precisely g_{i,j,m(i,j)} which is below just one of r_{0} and r_{1} (indeed, it is below just r_{f(i,j,m(i,j))} = r_{lim_{s} f(i,j,s)}, as desired). Thus, ≤_{P} is of the same degree as m, and so of the same degree as R.

To obtain instead a co-c.e. partial order, we modify the construction of ≤_{P} by initially setting g_{i,j,k} ≤_{P} r_{0} and g_{i,j,k} ≤_{P} r_{1} for all i < j, k ∈ ω, and then removing one of these relations when our guess about R(i, j) changes (including by default at k = 0) and both of them when it does not. In the end, there will be exactly one k such that g_{i,j,k} is below r_{0} or r_{1}. It will be below just one of them and R(i, j) will hold just in case it is below r_{1}. This completes the proof. □

Theorem 4.3. For every ∅′-computable structure S on ω there exists a c.e. (and a co-c.e.) partial order on ω with the same degree spectrum as S. Furthermore, there exists such a partial order in every c.e. degree containing a copy of S .

Proof. By Lemma 4.1, for every ∅′-computable copy of S on ω there is a graph R on ω of the same degree and with the same degree spectrum. By Lemma 4.2, there exists a c.e. (and a co-c.e.) partial order with the same degree spectrum as R, and if the degree of a given copy of S, and hence of the corresponding one of R, is c.e., we may choose the order to be of that degree as well. □

As an immediately corollary, we have:

Corollary 4.4. Let S be a structure with domain ω. The following are equivalent:

(1) S has a copy of c.e. degree;

(2) S has a ∅′-computable copy;

(3) there is a c.e. (and a co-c.e.) partial order on ω with the same degree spectrum as S.

By Theorem 4.3, we obtain a wide array of classes of degrees realized as degree spectra of c.e. (or co-c.e.) partial orders, including, for example, the class of degrees ≥ 0′. A particularly interesting class is that of the degrees strictly above 0. Recall the following well-known result:

Theorem 4.5 (Slaman [11], Wehner [13]). There exists a countable structure whose degree spectrum consists precisely of the nonzero degrees.

Since any two copies of the same structure have the same degree spectrum, it follows that an S as above can be found in any nonzero degree. The following consequence of Theorem 4.3 is a considerably more effective version.

Corollary 4.6. Every nonzero c.e. degree contains a c.e. (and a coc.e.) partial order on ω whose degree spectrum consists precisely of the nonzero degrees.

Proof. Fix a nonzero c.e. degree, and any structure in that degree satisfying Theorem 4.5. Then apply Theorem 4.3. □

As partial orders are directed graphs, all the results of this section hold for directed graphs as well. As for graphs, one could prove a general coding result taking c.e. or co-c.e. partial orders to c.e. or coc.e. graphs as in [5, Appendix A]. There is a simpler route in our case, however. The crucial item here is Lemma 4.2. Note first that the comparability graph R̃ of a partial order ≤_{P}, defined for x, y in the domain of ≤_{P} by R̃(x, y) ⟺ x <_{P} y ∨ y <_{P} x, is always computable from ≤_{P} and is c.e. (co-c.e.) if ≤_{P} is. Next, given a graph R as in Lemma 4.2 and the corresponding partial order ≤_{P} computing R constructed there, it is clear that the associated comparability graph R̃ has enough information to compute R, and hence also ≤_{P}. It is then a c.e. (co-c.e.) graph of the same degree, and with the same degree spectrum, as ≤_{P}. Thus all the results of this section also hold for graphs in place of partial orderings.

References

[1] C. J. Ash and J. Knight. Computable structures and the hyperarithmetical hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 2000.

[2] John Case. Sortability and extensibility of the graphs of recursively enumerable partial and total orders. Z. Math. Logik Grundlagen Math., 22(1):1–18, 1976.

[3] Rodney G. Downey, Denis R. Hirschfeldt, Steffen Lempp, and Reed Solomon. Computability-theoretic and proof-theoretic aspects of partial and linear orderings. Israel J. Math., 138:271–289, 2003.

[4] Noam Greenberg, Antonio Montalbán, and Theodore A. Slaman. Relative to any non-hyperarithmetic set. 2011. Submitted.

[5] Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore, and Arkadii M. Slinko. Degree spectra and computable dimensions in algebraic structures. Ann. Pure Appl. Logic, 115(1-3):71–113, 2002.

[6] Denis R. Hirschfeldt and Richard A. Shore. Combinatorial principles weaker than Ramsey’s theorem for pairs. J. Symbolic Logic, 72(1):171–206, 2007.

[7] Carl G. Jockusch, Jr., Bart Kastermans, Steffen Lempp, Manuel Lerman, and Reed Solomon. Stability and posets. J. Symbolic Logic, 74(2):693–711, 2009.

[8] Julia F. Knight. Degrees coded in jumps of orderings. J. Symbolic Logic, 51(4):1034–1042, 1986.

[9] Dev K. Roy. Recursive versus recursively enumerable binary relations. Studia Logica, 52(4):587–593, 1993.

[10] Stephen G. Simpson. Subsystems of second order arithmetic. Perspectives in Logic. Cambridge University Press, Cambridge, second edition, 2009.

[11] Theodore A. Slaman. Relative to any nonrecursive set. Proc. Amer. Math. Soc., 126(7):2117–2122, 1998.

[12] Robert I. Soare. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets.

[13] Stephan Wehner. Enumerations, countable structures and Turing degrees. Proc. Amer. Math. Soc., 126(7):2131–2139, 1998.

Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556 U.S.A.

E-mail address: cholak@nd.edu

Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556 U.S.A.

E-mail address: ddzhafar@nd.edu

Department of Mathematics, University of California, Berkeley, California 94720 U.S.A.,

E-mail address: schweber@math.berkeley.edu

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

E-mail address: shore@math.cornell.edu