On the jumps of the degrees below an r.e. degree^{∗}

David R. Belanger Richard A. Shore Department of Mathematics Cornell University Ithaca NY

Submitted 9 April 2015. This version 9 April 2015.

Abstract

A perhaps plausible conjecture about distinguishing among some r.e. degrees based on the jumps of degrees below them would prove the rigidity of the r.e. degrees. We show that the conjecture is false by exhibiting, for every c r.e. in and above 0′, distinct r.e. degrees a and b, each with jump c, such that the classes of the jumps of degrees below a and below b are the same.

1 Introduction

The general setting for this paper is the study of the relationships between a degree a and its jump a′ and, more generally, between a and the degrees REA(a), i.e. those recursively enumerable in and above a. The question that concerns us here is to what extent a degree, or more specifically, an r.e. degree a is determined by the jumps of, or degrees REA in, degrees x near a. In particular, we were motivated by a conjecture about these relationships that would have implied the rigidity of the r.e. degrees, R. The conjecture was inspired by the hope of combining two important results. One by Soare and Stob [1982] tells us that, under certain conditions, we can find degrees REA in a given a but not in another b. The second is the constellation of Jump Interpolation Theorems of Robinson [1971]. These theorems generally say that any simple statement about the ordering of r.e. degrees and and their jumps (e.g. extension-of-embeddings results) not shown false by an obvious property of the r.e. degrees and their jumps can be realized. We give specific versions of these results that we need for our analysis.

∗Both authors were partially supported by NSF Grant DMS-1161175.

Theorem 1.1 (Soare–Stob). If 0 < a ∈ R, then there is a degree c which is REA(a) but not r.e.

Theorem 1.2 (Robinson Jump Interpolation). If c, d, e ∈ R, e ≰ c < d, z ≥ c′ and is REA(d), then there is an f ∈ R with c < f < d, e ≰ f, and f′ = z.

Our thought was to combine and extend these ideas (and their standard relativizations) so as to characterize some r.e. degrees in terms of the jumps of degrees below them or equivalently (see Lemma 2.2) in terms of the degrees r.e. in them and above 0′. If we could do this for enough r.e. degrees, we knew that we could prove the rigidity of R. We begin with the definition of our primary object of study.

Definition 1.3. If a is a Turing degree, the class JB(a), jumps below a, consists of the jumps of degrees below a:

JB(a) = {x′ : x ≤ a}.

We will see in Lemma 2.2 that, by Theorem 1.2, if a ∈ R then in this definition we can consider just those x ≤ a which are also r.e. and that JB(a) = {z : 0′ ≤ z & z ∈ REA(a)}. (As usual, we use REA(a) to denote the class of degrees REA(a).)

As Soare and Stob [1982] point out, relativizing Theorem 1.1 to any incomplete high degree h (i.e. h′ = 0′′) and taking 0′ to play the role of a, one sees that, for any incomplete high degree h, there is a c REA(0′) which is not REA(h). Thus JB(0′) ≠JB(a) for any incomplete r.e. a and so 0′ is determined within R by JB(0′). (If a is not high, then it is trivial that JB(0′) ≠JB(a) as 0′′ ∉ JB(a) but, of course, 0′′ ∈ JB(0′).) Our goal was to extend this to other degrees. Our hope was that we could characterize enough r.e. degrees a in terms of JB(a) to provide an automorphism basis that would be fixed under all automorphisms of R and use this to prove its rigidity.

A slightly different relativized version of Theorem 1.1 is as follows:

Corollary 1.4 (Soare and Stob). For any r.e. a and b with a ≰ b, there is a c REA(a) which is not REA(b).

Proof. If b < a then this is the straightforward relativization of Theorem 1.1 as just used for h < 0′. Otherwise a itself is the desired c.

The theme of the Robinson Interpolation Theorems is that anything not ruled out by simple relations between degrees and their jumps should be realizable. Along these lines we hoped to prove that the witness c in Corollary 1.4 (which is to be REA in a but not in b) could be taken to lie between 0′ and a′ at least for many degrees. Clearly this is not possible if these degrees are low, i.e. a′ = b′ = 0′ but there are many other candidates. What constitutes “enough degrees” here is driven by the desire to get an automorphism basis for R whose elements a would be determined by the degrees REA(a) and above 0′, i.e. by JB(a). In particular, we state our original Conjecture for the class H_{2} = {x ∈ R|x′′ = 0′′′} of high_{2} r.e. degrees which is known to be an automorphism basis for R (see §4).

Conjecture 1.5. If a, b ∈ H_{2} and a ≰ b, then there is a c ≥ 0′ which is REA(a) but not REA(b). As usual this should also be true relativized to any x.

In §4 we show that this conjecture would imply the rigidity of R and so proving it would have answered many of the most important questions about R. Of course, if a and b have different jumps then, trivially, JB(a) ≠ JB(b) so the real questions only arise when a′ = b′. Known results can be used to show that we can at times distinguish between some a and b (with the same jump) by distinguishing between JB(a) and JB(b). The simplest examples follow easily from Theorems 1.1 and 1.2:

Proposition 1.6. If h ∈ R is high then there is an incomplete high r.e. g with JB(h) ≠ JB(g). In fact, we may find such a g which is incomparable with h.

Proof. As mentioned above, relativizing Theorem 1.1 to h and applying it to 0′ gives a c REA(0′) and not REA(h). Applying Theorem 1.2 (or just the jump theorem of Sacks [1963] gives us an r.e. k such that k′ = c. Of course, as k is not high, h ≰ k. Applying Theorem 1.2 again gives us an incomplete high r.e. g ≥ k with h ≰ g. It is now clear that c ∈ JB(g) but c ∉ JB(h) and so g ≰ h as well.

We can extend and then apply a result of Arslanov, Lempp and Shore [1996, Proposition 1.13] to get the same result for the high_{2} r.e. degrees.

Proposition 1.7 (Arslanov, Lempp and Shore). If c < h are r.e., c is low, i.e. c′ = 0′, and h is high, then there is an a < h which is REA(c) but not r.e.

Corollary 1.8. If x ∈ R is high_{2} then there is an r.e. degree g with x′ = g′ such that JB(x) ≠ JB(g). In fact, we may find such a g which is incomparable with x.

Proof. First note that the Proposition can be improved to allow c to be low_{2}, i.e. c′′ = 0′′: Given such a c and a high h > c apply Theorem 1.2 to get an r.e. d with d < c < h and d′ = c′. Now relativize the Proposition to d and note that c is low relative to d while h is still high relative to d as h′ = 0′′ = d′′. Thus we have an a which is REA(c) but not r.e. in d and so certainly not r.e.

Next, relativize this extension of the Proposition to our given x and apply it to 0′ (as c) and x′ (as h). (As x ∈ H_{2}, 0′ is low_{2} relative to x while x′ is obviously high relative to x.) This gives us an a with 0′< a < x′ such that a is REA(0′) but not r.e. in x. Now argue as for Proposition 1.6 using Theorem 1.2: First one gets an r.e., k ≱ x with k′ = a. Then one gets an r.e. g ≱ x with g ≥ k and g′ = x′ so that a ∈JB(g) but a ∉JB(x). (Of course, this also implies that g ≰ x.)

While these last results show that there are many degrees such that we can distinguish between them in terms of the JB operator, the main result of this paper is to exhibit (regrettably) a rather strong failure of any possible characterization of the r.e. degrees a in any particular jump class, i.e. those a with a′ = c for any c REA(0′) based simply on JB(a).

Theorem 1.9 (Main Theorem). If c is REA(0′), then

1. there is a pair a_{0}, a_{1} of r.e. degrees such that a′_{0} = a′_{1} = c, JB(a_{0}) = JB(a_{1}) and a_{0}|a_{1}; and

2. there is a pair b_{0}, b_{1} of r.e. degrees such that b′_{0} = b′_{1} = c, JB(b_{0}) = JB(b_{1}) and b_{0} < b_{1}.

Part 1 of the Main Theorem is proved in §2, by an argument extending the usual 0′′ tree proof of the Sacks jump theorem. Part 2 we do not prove in full; instead, in §3 we outline how to modify the proof from §2 to get degrees which are comparable instead of incomparable.

Before presenting the proofs, we mention a couple of the natural questions raised by these results and proofs and discuss some methodological issues.

Question 1.10. Are there any incomplete r.e. degrees a characterized by JB(a), i.e. such that JB(a) ≠ JB(b) for any r.e. b ≠ a? If so, are there enough to constitute an automorphism base for R and could one then prove its rigidity?

In the other direction, there are several possible strengthenings of the Main Theorem. We mention one that would provide a negative answer to the previous question.

Question 1.11. Is there, for every r.e. a, an r.e. b ≠ a such that JB(a) = JB(b)?

There are many possible variations on these questions some of which we discuss in §5 along with a couple of consequences of previous work which bear on them.

We also want to remark here on an unusual aspect of the construction for Theorem 1.9. While in several ways, it is quite similar to the usual proof of the Sacks jump theorem, satisfying the requirements to make JB(a_{0}) = JB(a_{1}) seems to require an unusual organization of the priority tree (certainly unusual for 0′′ constructions such as the Sacks jump theorem). What would seem to be individual requirements for this goal (the R_{e,i} below) are divided up into infinitely many subrequirements (the R_{e,i,n} below). These subrequirements are spread across the tree (rather than, for example, along the paths below a node assigned to R_{e,i} as is often the case). In combination with other requirements, the subrequirements (to the right of the true path) can interfere with each other with the possible outcome of subverting the final satisfaction of the basic requirement (even along the true path). Our solution is to change the priority of these subrequirements in a dynamic way that depends on the actions of nodes to their left. In particular, nodes on the priority tree are assigned different requirements at different stages of the construction. While this is common in 0′′′ constructions it is unusual in 0′′ ones (as ours is). Moreover, the nodes are assigned requirements in a way that does not depend solely on the outcomes along the path leading to the node (and possibly external approximation procedures as well). This seems unusual (if not unique) even for 0′′′ arguments.

The first example of which we are aware of changes in the priority of requirements in a somewhat similar way occurs in some cases of the minimal pair construction in αrecursion theory (Shore [1978]). Another relatively early result that has variable priority assignments is Theorem 2 of Jockusch and Soare [1991]. They construct a low linear order with a predicate for infinitely far apart not isomorphic to a recursive one. An unusual construction with a requirement analogous to our R_{e,i} (to make various sets have r.e. degree) occurs in the 0′′′ construction for Theorem 3.1 of Arslanov, Lempp and Shore [1996]. (We use this result below in Proposition 5.5.) The unusual procedure employed there is allowing nodes to act when they are to the left of the true path. A similar idea would probably work here as well but our construction while unusual in a different way seems simpler in this case.

We discuss some consequences of this unusual construction for a reverse mathematical analysis of our theorem in §5.

2 Proving part (1) of the theorem

Suppose c is REA(0′) and choose a representative C ∈ c. We may fix an r.e. set D such that, for all n, the n-th column D^{[n]} = {x : ⟨n, x⟩ ∈ D} is an initial segment of ω, finite if n ∈ C, and equal to ω if n ∉ C. We assume that no element s enters D before stage s. We will use D to build a pair A_{0}, A_{1} of sets such that a_{0} = deg(A_{0}) and a_{1} = deg(A_{1}) are as required by the theorem. Our argument closely follows the usual pattern of a 0′′ tree construction, with the peculiar feature that the assignment of requirements to nodes is allowed to vary from stage to stage.

Before we can specify our requirements, we need some more notation, and we need a way of characterizing JB(a) suitable for a priority construction. We use the following representation for relative enumerations:

Definition 2.1. If V is an r.e. set with enumeration (V_{s})_{s∈ω} and A is any set, then V^{A} is the set {n : (∃σ ⊆ A)⟨n, σ⟩ ∈ V }. For each s, we define V_{s}^{A} likewise, with V_{s} in place of V.

Note that the class of sets r.e. in A is equal to {W_{e}^{A}| e ∈ ω}.

Lemma 2.2. For every degree y and every r.e. degree a with representative A ∈ a, the following are equivalent:

1. y = x′ for some x ≤ a.

2. y = x′ for some r.e. x ≤ a.

3. y ≥ 0′ and y is REA(a).

4. y = deg(W_{e}^{A} ⊕ 0′) for some e.

Proof. The implications (2 ⇒ 1) and (3 ⇒ 4), and (4 ⇒ 3) are immediate. The implication (1 ⇒ 3) follows from the monotonicity of the jump operator and the fact that if X ≤_{T} A and Y is r.e. in X then Y is r.e. in A. The final implication (3 ⇒ 2) follows from Theorem 1.2.

The equivalence between 1 and 4 implies in particular that JB(a) = {deg(W_{e}^{A}⊕0′)|e ∈ ω}. It is this characterization that we use to frame our requirements.

2.1 Requirements

We begin by listing four basic goals for the construction.

• A_{0} ≰_{T} A_{1} and A_{1} ≰_{T} A_{0}

• C ≤_{T} A′_{0}, A′_{1}

• A′_{0}, A′_{1} ≤_{T} C

• For every e ∈ ω and i ∈ {0, 1}, there is an r.e. set V_{e,i} such that W_{e}^{A_{1−i}} ⊕ 0′ ≡_{T} V_{e,i}^{A_{i}} ⊕ 0′.

The first three goals are self-explanatory, while the fourth guarantees through Lemma 2.2 that JB(a_{0}) = JB(a_{1}). Hence a construction of any A_{i}, V_{e,i}, e ∈ ω, i ∈ {0, 1} meeting these goals will constitute a proof of the Main Theorem, part 1. We represent the first, second and fourth goals as requirements named with the letters N, P, and R, respectively. The third we do not capture directly as a requirement, although in the end it is satisfied by the R strategy as well (Proposition 2.10 below).

The N and P requirements are as in the usual proofs of the Friedberg-Muchnik and Sacks jump theorems, respectively. Namely, we ensure that A_{i} ≰_{T} A_{1−i} by using infinitely many diagonalization requirements:

N_{e,i} : A_{i} ≠ Φ_{e}^{A_{1−i}}, for all e ∈ ω, i ∈ {0, 1}.

We ensure that C ≤_{T} A′_{0}, A′_{1} by using infinitely many thickness requirements:

P_{e} : A_{0}^{[e]} =^{∗} D^{[e]} and A_{1}^{[e]} =^{∗} D^{[e]}. (Here X =^{∗} Y means that X, Y differ only by a finite set.)

We attack the fourth goal by breaking it up, for each e ∈ ω and each i ∈ {0, 1}, into infinitely many requirements R_{e,i,n}, with n ranging over ω. The idea is to construct a single r.e. set V_{e,i} so that W_{e}^{A_{1−i}} contains a number n if and only if V_{e,i}^{A_{i}} contains ⟨n, m⟩ for some m = m_{e,i,n} which can be computed by 0′ (so that W_{e}^{A_{1−i}} ≤_{T} V_{e,i}^{A_{i}} ⊕ 0′), while keeping the question of whether ⟨n, k⟩ is in V_{e,i}^{A_{i}} easy to answer (given m) for all k ≠ m (so that V_{e,i}^{A_{i}} ≤_{T} W_{e}^{A_{1−i}} ⊕ 0′). The formal requirements, and a lemma showing that they suffice to guarantee that W_{e}^{A_{1−i}} ⊕ 0′ ≡_{T} V_{e,i}^{A_{i}} ⊕ 0′, are as follows:

R_{e,i,n} : There is an r.e. set V_{e,i}, which does not depend on n, and a number m_{e,i,n} computable uniformly in n from 0′ such that n ∈ W_{e}^{A_{1−i}} ⇔ ⟨n, m_{e,i,n}⟩ ∈ V_{e,i}^{A_{i}}. Furthermore, k < m_{e,i,n} implies ⟨n, k⟩ ∈ V_{e,i}^{A_{i}}, and k > m_{e,i,n} implies ⟨n, k⟩ ∉ V_{e,i}^{A_{i}}.

Lemma 2.3. Fix e and i. If R_{e,i,n} is met for all n, then W_{e}^{A_{1−i}} ⊕ 0′ ≡_{T} V_{e,i}^{A_{i}} ⊕ 0′.

Proof. To compute whether n is in W_{e}^{A_{1−i}}, first use 0′ to find m_{e,i,n}, and then check whether ⟨n, m_{e,i,n}⟩ is in V_{e,i}^{A_{i}}. This shows that W_{e}^{A_{1−i}} ≤_{T} V_{e,i}^{A_{i}} ⊕ 0′. To compute whether ⟨n, k⟩ is in V_{e}^{A_{i}}, first use 0′ to find m_{e,i,n}, and compare it with k: if k < m_{e,i,n} then the answer is yes, if k > m_{e,i,n} then the answer is no, and if k = m_{e,i,n} then it is enough to check whether n is in W_{e}^{A_{1−i}}. Hence V_{e,i}^{A_{i}} ≤_{T} W_{e}^{A_{1−i}} ⊕ 0′.

2.2 Notation and bookkeeping.

The tree of nodes. We assign requirements to nodes on a tree as in a typical 0′′ priority argument, except that the assignment of requirements to nodes is allowed to change from stage to stage. The tree itself is {0, 1}^{<ω}, ordered lexicographically with 0 < _{lex}1 as usual. The P requirements have two possible outcomes, 0 and 1, representing an infinitary and a finitary action, respectively. The R and N requirements have only one outcome, 0.

The accessible path δ_{s}. At each stage s, we specify a node δ_{s} ∈ {0, 1}^{s}. (The precise construction of δ_{s} is presented in §2.3 below.) We say that δ_{s} and each of its initial segments α ⊆ δ_{s} are accessible at stage s. No other node is accessible at stage s.

Restraints r_{α,s} and r_{<α,s}. At each stage s, each node α ∈ {0, 1}^{<ω} places a restraint r_{α,s} limiting the possible actions of nodes that are lexicographically greater than α. For each α, the initial value is r_{α,0} = 0. If α is not accessible, then r_{α,s} = r_{α,s−1}. Otherwise, r_{α,s} is as specified in §2.3 below. For each α and s, we use r_{<α,s} to denote max{r_{β,s} : β <_{lex} α}. Notice that at every stage s cofinitely many r_{α,s} are equal to zero, and every r_{<α,s} is finite.

Assigning requirements to nodes. The R requirements are sensitive to injury because a single set V_{e,i} is shared across all nodes assigned an R_{e,i,n} requirement, and distinct R_{e,i,n} with the same e and i may each be adding elements to V_{e,i}. These elements cannot subsequently be removed, as V_{e,i} is r.e. Thus a version of an R_{e,i,n} requirement can act far to the right of the true path (which is defined as usual in §2.4) and we may later have to react to some injury from a node to its left (but still to the right of the true path) by making the only correction we can, i.e. changing the value of m_{e,i,n}. Allowing this to happen infinitely often will send m_{e,i,n} to infinity and ruin our coding procedure for computing W_{e}^{A_{1−i}}(n). One appropriate response is to increase the priority of the R_{e,i,n} requirements, relative to those that injured them, each time this happens; the countervailing constraint is the obvious one that we must eventually deal with all the requirements (on the true path) and so cannot increase the priority of all the R_{e,i,n} arbitrarily. The solution is to increase the priority of the R_{e,i,n} requirements in a controlled way that allows other requirements to act as well along the true path. We do this by assigning the requirements dynamically, i.e. by a scheme that depends on the stage s. We could define an assignment simultaneously with the full construction that depends directly on the nodes accessible at s and the actions taken (injuries sustained) at stages less than or equal to s. While that might produce a more intuitive definition (given that one already understood the construction), we instead give a simple (if uninformative) definition that is independent of the construction’s details and that uses a counting argument to allow the priority of an R_{e,i,n} requirement to increase while still leaving room for the other requirements on the true path. This makes both the assignment of requirements to nodes on the tree and the eventual verifications significantly simpler.

The precise assignment scheme is as follows. First, fix some recursive list of all the R requirements and a second recursive list of all the P and N requirements. At stage s, we assign a requirement to each node α ∈ {0, 1}^{<ω} by recursion on its initial segments. Let u be the number of proper initial segments of α assigned an R requirement at stage s, and let v be the number of nodes β ≤_{lex} α which have been accessible at any stage t ≤ s. If u < v/2, then assign to α the (u + 1)-th R requirement; otherwise, assign to α the next unused (i.e. the (|α| − u + 1)-th) requirement from the P, N list. Conventions for V^{A}, use, and ⟨· , ·⟩. The use of a convergent computation Φ_{e}^{A}(x) or Φ_{e,s}^{A}(x) is the least u ≤ s such that Φ_{e,u}^{A↾u}(x) ↓. If V^{A} is as in Definition 2.1, we identify V^{A} with its characteristic function as usual; if V^{A}(n) = 1, the use of V^{A}(n) is the shortest σ ⊆ A such that ⟨n, σ⟩ ∈ V. We do not define a use for V^{A}(n) = 0. We follow the convention that Φ_{e,s}(x) ↓ only if x < s, and a V_{s} in an r.e. approximation (V_{s})_{s} may contain n only if n < s. The pairing function ⟨x, y⟩ is recursive and increasing in each coordinate. Each binary string σ is naturally identified with a natural number through its binary expansion; this number grows monotonically with the length-lexicographic ordering. The pairing function is left-associative, so we may write ⟨n, m, σ⟩ for ⟨⟨n, m⟩, σ⟩.

α-believable computations. Fix any α ∈ {0, 1}^{<ω}, and suppose Φ_{e,s}^{A_{1−i,s}}(x) ↓ with use u. We say this computation is an α-believable computation at stage s if for every P_{j} which is assigned to an initial segment β ⊆ α at stage s with outcome α(|β|) = 0, we have

{k ∈ A_{1−i,s}^{[j]} : r_{<α,s} ≤ ⟨j, k⟩ ≤ u − 1} = {k : r_{<α,s} ≤ ⟨j, k⟩ ≤ u − 1}

where [x, y] denotes a closed interval in ω.

Now fix α ∈ {0, 1}^{<ω} and suppose n ∈ W_{e,s}^{A_{1−i,s}} by ⟨n, σ⟩ ∈ W_{e,s} with σ ⊆ A_{1−i,s}. We call this enumeration an α-believable computation at stage s if, for all j as above,

{k ∈ A_{1−i,s}^{[j]} : r_{<α,s} ≤ ⟨j, k⟩ ≤ |σ| − 1} = {k : r_{<α,s} ≤ ⟨j, k⟩ ≤ |σ| − 1}

2.3 The basic strategies and outcomes; defining δ_{s}.

Suppose k < s is fixed, α = δ_{s} ↾ k, and α is assigned the requirement Q at stage s. Our strategy for α determines any changes made by α to A_{0}, A_{1}, V_{e,0}, V_{e,1}, or m_{e,i,n} at stage s, the restraint r_{α,s}, and the outcome δ_{s}(k), and with it, if k < s − 1, the next accessible node α δ_{s}(k). We say that a node α acts at stage s if and only if its strategy changes one of A_{0}, A_{1}, V_{e,0}, V_{e,1}, m_{e,i,n}, or r_{α,s} ≠ r_{α,s−1} at stage s. If the construction does not explicitly change one of these sets or variables at stage s, then it takes the same value as at stage s − 1. Here are the strategies: If Q = P_{e}: If this is the first time α has been accessible or if no new element has entered D_{s}^{[e]} since last time α was accessible, do nothing; the outcome is the finitary outcome 1. Otherwise, add to A_{0}^{[e]} and A_{1}^{[e]} all k such that r_{<α,s} ≤ ⟨e, k⟩ and k ≤ s. In this case, the outcome is 0. [The intention is, as usual, that A_{i}^{[e]} will be finite if D^{[e]} is finite, and cofinite if D^{[e]} is ω. We add whole intervals at once to make it easier to determine when, and in what way, this action injures lower-priority requirements.] If Q = N_{e,i}: Check whether there is an x in the interval r_{<α,s} < x < s such that

i. x ≠ ⟨j, k⟩ for all j < |α| and all k; and

ii. Φ_{e,s}^{A_{1−i,s}}(x) ↓= y by an α-believable computation, where either y = 0, or y ≠ A_{i,s}(x).

If there is no such x, do nothing. Otherwise, take the least x which minimizes the use of the convergent computation Φ_{e,s}^{A_{1−i,s}}(x), and consider the value of y from condition (ii). If y = 0 and x is not in A_{i,s}, add x to A_{i}; otherwise, do not change A_{i}. In either case, set the restraint r_{α,s} to equal the use of the computation Φ_{e,s}^{A_{1−i,s}}(x). [The minimization is to guarantee that after the requirement has been “permanently” satisfied, it will not act again. Condition (i) helps ensure that the N strategy doesn’t interfere too often with a P_{j} requirement.]

If Q = R_{e,i,n}: Let m = m_{e,i,n,s−1}, or m = 0 if s = 0. Check whether n ∈ W_{e,s}^{A_{1−i,s}} by an α-believable computation.

Case 1: n is not in W_{e,s}^{A_{1−i,s}} by an α-believable computation. Check whether ⟨n, m⟩ ∈ V_{e,i,s}^{A_{i,s}}. If not, let m_{e,i,n,s} = m. Otherwise, let m_{e,i,n,s} = m + 1 and add all {⟨n, m, σ⟩ : σ ∈ 2^{<ω}} to V_{e,i}. [This is to meet the part of the requirement involving k < m_{e,i,n}.]

Case 2: n is in W_{e,s}^{A_{1−i,s}} by an α-believable computation. In this case, we leave m_{e,i,n,s} = m. Check whether ⟨n, m⟩ is already in V_{e,i,s}^{A_{i,s}}. If so, let r_{α,s} be either the use of V_{e,i,s}^{A_{i,s}}(⟨n, m⟩) or the use of W_{e,s}^{A_{1−i,s}}(n), whichever is larger. If, on the other hand, ⟨n, m⟩ ∉ V_{e,i,s}^{A_{i,s}}, let σ be the shortest initial segment of A_{i,s} satisfying:

i. r_{<α,s} < |σ|;

ii. |σ| is greater than the use of W_{e,s}^{A_{1−i,s}}; and iii. for each proper initial segment β ⊊ α assigned a requirement P_{j} with outcome

α(|β|) = 1, there exists an x of the form x = ⟨j, k⟩ for some k such that r_{β,s} < x < |σ| and σ(x) = 0.

Add ⟨n, m, σ⟩ to V_{e,i}, and set r_{α,s} to equal |σ|. [The intuition behind condition (iii) is that the existence of such an x with σ(x) = 0 protects against the possibility that α’s belief about the outcome of β – that D^{[j]} is finite – might be wrong. If it is wrong, the computation based on σ will automatically be injured by the action of β or some other node assigned P_{j}, and ⟨n, m⟩ will be removed automatically from V_{e,i,s}^{A_{i,s}}.]

2.4 Verification.

Define the true path tr ∈ {0, 1}^{ω} as the leftmost path which is visited infinitely often. That is, for all n, the initial segment tr ↾ n is the ≤_{lex}-least node of length n that is accessible infinitely often. We call tr(n) the true outcome of tr↾n. A node α is on the true path if α is an initial segment of tr. If a node α is assigned a particular requirement Q at all but finitely many stages, we say that α is eventually assigned Q and write ev(α) = Q. If there is no such Q, we leave ev(α) undefined. We begin with two straightforward lemmas. The first of these is, in fact, independent of the construction in §2.3.

Lemma 2.4. If α is a node and α ≤_{lex} tr, then ev(α) is defined.

Proof. By induction on the length of α. Choose a stage s_{0} large enough that for each s ≥ s_{0} we have α ≤_{lex} δ_{s}, and each strict initial segment of α is assigned the same requirement at stage s as at stage s_{0}. The assignment scheme in §2.2 gives the same requirement to α at each stage s ≥ s_{0}.

The second lemma relies on the construction in §2.3 only in that an R requirement always has 0 as its outcome.

Lemma 2.5. The function n ↦ ev(tr↾n) is a bijection between ω and the set {P_{e}, N_{e,i}, R_{e,i,n} : e, n ∈ ω, i < 2} of all requirements.

Proof. For each n, let u_{n} be the number of ℓ < n for which ev(tr ↾ ℓ) is an R requirement, and let v_{n} be the total number of nodes β ≤_{lex} tr ↾ n that are ever accessible (which is finite by the definition of tr). From the assignment scheme in §2.2 we know that ev(tr↾n) is an R requirement if u_{n} < v_{n}/2, and a P or N requirement if u_{n} ≥ v_{n}/2.

It suffices to check that ev(tr ↾n) is an R requirement infinitely often, and a P or N requirement infinitely often. A few observations: (i) if ev(tr↾n) is a P or N requirement, then u_{n+1} = u_{n} and v_{n+1} > v_{n}; and (ii) if ev(tr↾n) is an R requirement, then u_{n+1} = 1+u_{n} and v_{n+1} = 1 + v_{n} (since the outcome must be 0, and β <_{lex} α 0 implies either β <_{lex} α or β = α). If cofinitely many ev(tr ↾ n) were P or N requirements, then by definition u_{n} ≥ v_{n}/2 cofinitely often, eventually contradicting (i); while if cofinitely many ev(tr↾n) were R requirements, then by definition u_{n} < v_{n}/2 for cofinitely many n, eventually contradicting (ii). This completes the proof.

Now we check that each requirement is met. We do this in two steps: first, in Propositions 2.6, we argue that nodes along the true path act infinitely often if and only if they are eventually assigned a P requirement with the infinitary 0 as their true outcome; and then in Proposition 2.8 we argue that these nodes’ actions satisfy their respective requirements. For P and N requirements, the verification similar to the usual proof of the Sacks jump inversion; the method for R is new but straightforward. The remainder of this section makes full use of the construction in §2.3.

Proposition 2.6. If α ≤_{lex} tr, then α acts infinitely often if and only if α ⊆ tr, ev(α) is a P requirement, and its true outcome tr(|α|) is 0.

Proof. Since {α : α ≤_{lex} tr} is well-ordered by ≤_{lex}, we may work by induction on ≤_{lex}. Fix α. If α is strictly to the left of the true path, then the result is immediate, so assume that α = tr↾n for some n. Fix s_{0} such that α is accessible at stage s_{0}, and large enough that every β <_{lex} α meets the inductive hypothesis before stage s_{0} and α <_{lex} δ_{s} for all s ≥ s_{0}. In particular, the restraint r_{<α,s} is constant at stages s ≥ s_{0}, and α is assigned the same requirement Q = ev(α) at all stages s ≥ s_{0}. Consider the possible values of Q.

Case 1: Q = P_{e}. By the definition of an action for a P requirement, α acts infinitely often if and only if it has the infinitary outcome 0 infinitely often, which happens if and only if its true outcome is 0.

Case 2: Q = N_{e,i}. If α does not act after stage s_{0}, there is nothing to prove; so let s ≥ s_{0} be least such that α acts, using the restraint r_{α,s} to preserve an α-believable computation Φ_{e,s}^{A_{1−i,s}}(x) ↓= y with y ≠ A_{i,s}(x). Because the computation is α-believable, and because, by choice of s_{0}, the only higher-priority nodes acting after stage s are initial segments β ⊆ α assigned a P_{j} requirement with true outcome 0, the computation Φ_{e,t}^{A_{1−i,t}}(x) = y continues to be α-believable as long as r_{α,t} does not decrease. Furthermore, since the N -action of α stipulates as point (i) x is not of the form ⟨j, k⟩ for any such P_{j}, the disagreement y ≠ A_{i,s}(x) is also preserved. Although α may act again after stage s to preserve some other computation with lesser use or lesser x, this happens at most finitely often, as x and the use are chosen to be minimal. Therefore α acts at most finitely many times.

Case 3: Q = R_{e,i,n}. We claim that m_{e,i,n,s} is constant for s > s_{0}. Suppose for a contradiction that s > s_{0} + 1 is the least stage at which some node assigned R_{e,i,n} acts by setting m_{e,i,n,s} = m_{e,i,n,s−1} + 1. This action is in response to ⟨n, m_{e,i,n,s−1}⟩ being in V_{e,i,s}^{A_{i,s}} but n not being in W_{e,s}^{A_{1−i,s}}. Let β be the node that had placed the element in V_{e,i} in response to a β-believable computation, and let γ be the node that had injured this computation by placing an element into A_{1−i} below the use. Then γ ≤_{lex} β, i.e. γ has higher priority, and γ acted after stage s_{0}, since otherwise α would already have dealt with this disagreement, or set up a restraint to prevent it, at stage s_{0}. Furthermore, γ does not extend α, or again α would have set up a restraint to prevent its action. Hence by choice of s_{0}, γ and β are strictly to the right of α. Since all initial segments of β which are not initial segments of α are assigned an R requirement (this is clear from the assignment scheme), and γ does not have an R (as it changes A_{1−i}), γ is strictly to the left of β, that is, they have a common initial segment δ with γ(|δ|) = 0 and β(|δ|) = 1. But then at the stage at which γ was accessible, δ was assigned a P requirement which acted by adding elements to A_{i} below the use of β’s coding, and so (by condition (iii) in the R-action of β) γ itself removed ⟨n, m_{e,i,n,s−1}⟩ from V_{e,i}^{A_{i}} before γ had a chance to act. This is the desired contradiction.

We are ready to begin checking that requirements are satisfied. We begin with the P requirements, as they will be useful in checking the others.

Lemma 2.7. Every P requirement is satisfied.

Proof. Fix a requirement P_{e}, and let α ⊆ tr be such that ev(α) = P_{e}. Let s_{0} be as in the proof of Proposition 2.6 and let r = r_{<α,s_{0}}. If D^{[e]} = ω then there are infinitely many stages s at which new elements enter D_{s}^{[e]}, and so there are infinitely many stages at which α acts by adding elements to A_{0}^{[e]} and A_{1}^{[e]}. In the limit, A_{0}^{[e]} and A_{1}^{[e]} contain all k ≥ r, and so A_{0}^{[e]} =^{∗} D^{[e]} =^{∗} A_{1}^{[e]}, as required.

If, on the other hand, D^{[e]} is finite, it is easy to see that after some stage s no node assigned P_{e} ever again adds elements to A_{i}^{[e]}. We claim in addition that there is a stage s after which no node assigned an N requirement adds elements to A_{i}^{[e]}. By condition (i) of the N strategy, we need only consider nodes β of length ≤ e. If β is strictly left of the true path, it eventually stops acting by definition of the true path; if β is strictly to the right of the true path, then eventually it is assigned an R requirement instead of an N requirement; and if β is on the true path, then by the previous Proposition, β either stops acting or is assigned a P requirement.

Proposition 2.8. Every requirement is satisfied.

Proof. We have already dealt with the P requirements in the previous Lemma. Fix a requirement Q of the form N_{e,i} or R_{e,i,n}, and let α ⊆ tr such that ev(α) = Q. Let s_{0} be as in the proof of Proposition 2.6, and let r = r_{<α,s_{0}}. Assume by induction that the requirements assigned to each proper initial segment of α are eventually satisfied. Of course, our methods depend on whether Q is an N or an R requirement.

Case 1: Q = N_{e,i}. Suppose for a contradiction that Φ_{e}^{A_{1−i}} = A_{i}. Choose a j such that D^{[j]} is finite, j is larger than the restraint r, and no β ≤_{lex} α is ever assigned P_{j}. (Such a j exists because C is nonrecursive, and hence not cofinite.) Let α^{∗} ⊆ tr be such that ev(α^{∗}) = P_{j}, and notice that α ⊊ α^{∗}. As A_{i}^{[j]} is finite by Lemma 2.7, there is an x = ⟨j, k⟩ such that k ∉ A_{i}^{[j]}, so that Φ_{e}^{A_{1−i}}(x) = 0 = A_{i}(x). Since by Lemma 2.7 every P requirement assigned to an initial segment of α^{∗} is satisfied, there is an s ≥ s_{0} with α ⊆ δ_{s} such that Φ_{e,t}^{A_{1−i,t}}(x) = 0 is α-believable for all t ≥ s. But then α acts at or before this stage s and preserves a disagreement – a contradiction.

Case 2: Q = R_{e,i,n}. We saw in the proof of Proposition 2.6 that m = m_{e,i,n,s} is constant when s > s_{0}. If n ∈ W_{e}^{A_{1−i}}, then, again appealing to the Lemma, n ∈ W_{e,s}^{A_{1−i,s}} by an α-believable computation for large enough s, and so α eventually sets a restraint (and possibly adds to V_{e,i}) to preserve a computation ⟨n, m⟩ ∈ V_{e,i}^{A_{i}} as desired. If n ∉ W_{e}^{A_{1−i}}, suppose for a contradiction that ⟨n, m⟩ ∈ V_{e,i}^{A_{i}}. Then there is an s > s_{0} such that ⟨n, m⟩ ∈ V_{e,i}^{A_{i}} and n ∉ W_{e}^{A_{1−i}}. Since α ≤_{lex} δ_{s} by choice of s_{0}, there is a β ⊆ δ_{s} assigned the requirement R_{e,i,n} at stage s [this is immediate from the assignment scheme and the fact that δ_{s} > |α|]. But then β should act at stage s by incrementing m, a contradiction.

It remains only to verify that A′_{0}, A′_{1} ≤_{T} C. We use the following:

Lemma 2.9. The true path tr is recursive in C.

Proof. Using an oracle for C, we construct tr by recursion by building finite initial segments α_{0} ⊆ α_{1} ⊆ ⋯ ⊆ tr. Begin with α_{0} = ∅, the empty string. For the recursive step, suppose we have defined α_{n} = tr ↾n. Use 0′ (which is recursive in C) to find out exactly how many s there are such that δ_{s} ≤_{lex} α_{n}, and hence to compute ev(α_{n}). If ev(α_{n}) is an N or R requirement, then the true outcome is 0, so we let α_{n+1} = α_{n} 0. On the other hand, if ev(α_{n}) is P_{e}, then by Proposition 2.8 the true outcome tr(n) is 0 if D^{[e]} is infinite, and 1 otherwise. In other words, tr(n) is 0 if e ∉ C, and 1 otherwise. Use the C oracle to define α_{n+1} = α 0 or α_{n+1} = α 1, as appropriate.

Proposition 2.10. A′_{0}, A′_{1} ≤_{T} C.

Proof. We show that C can compute {e : e ∈ W_{e}^{A_{i}}} for either value of i. Using the method of Lemma 2.9, use C to find, uniformly in e, a node α on the true path such that ev(α) = R_{e,i,e}. As in the proof of Proposition 2.8, if e ∈ W_{e}^{A_{1−i}}, then eventually this computation is α-believable, so α acts (and succeeds) in preserving a coding ⟨e, m⟩ ∈ V_{e,i,s}^{A_{i,s}}; on the other hand, if α acts at a stage after s_{0} (defined as in the proof of Proposition 2.6) to preserve a such coding, then it also preserves e ∈ W_{e}^{A_{1−i}}. An oracle C can decide, using a query to 0′, whether α acts in this way, and hence whether e ∈ W_{e}^{A_{1−i}}.

This completes the proof of Theorem 1.9.

3 Proving part (2) of the Theorem

Here we give a quick summary of the alterations needed to convert the proof of Theorem 1.9 part (1) into a proof of part (2). Fix a c, C, and D as in the beginning of Section 3. Build two sets A_{0}, A_{1} meeting the following requirements, for all e, i, n:

P_{e} : A_{0}^{[e]} =^{∗} D^{[e]}.

N_{e} : A_{1} ≠ Φ_{e}^{A_{0}}.

R_{e,n} : There is an r.e. set V_{e}, which does not depend on n, and a number m_{e,n} computable uniformly in n from 0′ such that n ∈ W_{e}^{A_{0}⊕A_{1}} ⇔ ⟨n, m_{e,n}⟩ ∈ V_{e}^{A_{0}}. Furthermore, k < m_{e,n} implies ⟨n, k⟩ ∈ V_{e}^{A_{0}⊕A_{1}}, and k > m_{e,n} implies ⟨n, k⟩ ∉ V_{e}^{A_{0}⊕A_{1}}.

Then the required degrees are b_{0} = deg(A_{0}), and b_{1} = deg(A_{0} ⊕ A_{1}). The differences to keep in mind when adapting the construction are:

• P_{e} alters A_{0} but never A_{1}.

• N_{e} alters A_{1} but never A_{0}.

• R_{e,n} uses A_{0} ⊕ A_{1} as an oracle instead of A_{0} or A_{1}.

• The notion of α-believable computations W_{e}^{A_{0}⊕A_{1}}(n) is adapted to allow for the fact that P requirements add elements to columns of A_{0} but not to A_{1}.

From here the the proof proceeds by a sequence of lemmas analogous to that in Subsection 2.4.

4 From the Conjecture to Rigidity

In this section we give a proof based on Conjecture 1.5 of the rigidity of R. If the Conjecture held then by Lemma 2.2 we would know that, for a, b ∈ H_{2}, a = b ⇔JB(a) =JB(b): If a ≠ b, then one would be not below the other and the Conjecture would supply a c in one of JB(a) or JB(b) but not the other.

Now fix any automorphism Φ of R. By Nies, Shore and Slaman [1998], H_{2} is definable in R and so if a ∈ H_{2} then Φ(a) ∈ H_{2}. Now H_{2} is an automorphism basis for R. (Indeed, by Lerman [1977] every jump class is one but for H_{2} it follows easily from Theorem 1.2: If Φ(x) = y ≠ x then by Theorem 1.2 there is a z ∈ H_{2} such that z is above one of x and y but not the other for the desired contradiction.) So to establish rigidity (based on our Conjecture) it would suffice to prove that JB(a) =JB(Φ(a)) for any a ∈ H_{2}. Assuming the Conjecture, we in fact show that JB is invariant under Φ, i.e. JB(x) =JB(Φ(x)) for any x ∈ R.

We begin with the double jump version of JB: DJB(c) ={x′′ : x ≤ c}. By using Lemma 2.2 both as stated and relativized, we see that for r.e. c, DJB(c) ={x′′ : x ≤ c & x is r.e.}.

Claim 4.1. If x, y ∈ H_{2} and DJB(x) =DJB(y), then x′= y′. Moreover, if y = Φ(x) and x ∈ H_{2} then then x′= y′.

Proof. Suppose we have x and y as in the hypotheses of the Claim but x′≠ y′. Without loss of generality we may assume that x′≰ y′. As x′, y′ are high (and so high_{2}) relative to 0′, we can apply the Conjecture relativized to 0′ to the degrees x′≰ y′. This gives us a z REA(0′′) which is REA(x′) but not REA(y′). Next apply Theorem 1.2 relative to x with 0′ playing the role of c to get f REA(x), f > 0′ and f′ = z. Finally, apply Theorem 1.2 with 0, x and f playing the roles of c, d and z, respectively, to get an r.e. g < x with g′ = f. Thus g′′ = z and so z ∈DJB(x). On the other hand, since z is not REA(y′), z ∉DJB(y) for the desired contradiction.

For the second part of the Claim, we note that by Nies, Shore and Slaman [1998], not only is y ∈ H_{2} definable in R but each of the double jump classes (i.e. the sets {c ∈ R|c′′ = d} for any d REA(0′)) are definable in R. Thus DJB(c) is invariant under Φ and so DJB(x) =DJB(y) and we are done by the first part of the Claim.

We next wish to prove that the jump is invariant, i.e. for any x, y with Φ(x) = y, x′ = y′. We consider another operator on R: JA(x) = {c′|c ≥ x & c ∈ H_{2}}.

Claim 4.2. For any x, y ∈ R, if JA(x) = JA(y), then x′= y′. Moreover, for any x ∈ R and y = Φ(x), x′= y′.

Proof. If the first assertion fails, assume, without loss of generality, that y′ ≰ x′. By Theorem 1.2 relative to 0′ with x′, 0′′, y′, and 0′′′ playing the roles of c, d, e and z, respectively, we get an f > x′ with f′ = 0′′′ which is REA(0′) but not above y′. By Theorem 1.2 again we have an r.e. c > x with c′ = f and so c ∈ H_{2}. Thus c′ = f ∈ JA(x). On the other hand, for every v ∈JA(y), v ≥ y′ but f is not above y′ for the desired contradiction.

For the second part of the Claim, note that by the previous Claim, JA(x) is invariant under Φ: If z ∈ JA(x) then z = c′ for some c ∈ H_{2} with c ≥ x. By the previous Claim, c′ = Φ(c)′ (and so, in particular Φ(c) ∈ H_{2}). As Φ(c) ≥ Φ(x), z = c′ = Φ(c)′ ∈ JA(Φ(x)). Similarly, if z ∈ JA(Φ(x)) then z = c′ for some c ∈ H_{2} with c ≥ Φ(x). There is then a y with Φ(y) = c and so y ≥ x and y ∈ H_{2}. Again, by the previous Claim, y′ = Φ(y)′ = c′ = z and so z ∈ JA(x) as desired.

We can now complete our proof of the rigidity of R from the conjecture by noting that by this last Claim and the definition of JB, JB is invariant under Φ: If c ≤ x then Φ(c) ≤ Φ(x) and by the last Claim c′ = Φ(c)′. Thus JB(x) ⊆ JB(Φ(x)). Similarly, if d ≤ Φ(x) then d = Φ(c) for some c ≤ x and so c′ = d′ and JB(Φ(x)) ⊆ JB(x) giving rigidity as in the second paragraph of this section.

5 Questions and Observations

In this section, we pose a number of questions that naturally extend Proposition 1.6, Corollary 1.8 and Theorem 1.9 and make some observations which impede or even restrict such possibilities.

The first set of questions deal with the issue of when r.e. degrees a and b in the same jump class, given say by c ∈ REA(0′), have JB(a) ≠ JB(b) by extending Corollary 1.8.

Question 5.1. When (for c ∈ REA(0′) and c′′ ≠ 0′′′ ) do we have r.e. a ≠ b with jump c such that JB(a) ≠ JB(b)? Of course, we must here at least have c > 0′.

The noninversion theorem of Shore [1988] gives some examples of degrees distinguished by the JB operator along these lines beyond those given by Corollary 1.8. Indeed, it supplies two upward cones in R such that JB(a) ≠ JB(b) for any incomplete a and b in each cone and a cone of jump classes all realized by degrees in each of these two cones.

Proposition 5.2. There are incomparable r.e. c and d such that for 0′ > a ≥ c and 0′ > b ≥ d, JB(a) ≠ JB(b). Moreover, there is a w ∈ REA(0′) with w < 0′′ such that for any z ≥ w with z ∈ REA(0′), there are a ≥ c and b ≥ d with a′ = z = b′.

Proof. By Shore [1988, Theorem 1.1], there are a_{0}, a_{1} ∈ REA(0′) such that a_{0} ∨ a_{1} < 0′ and if u < 0′ then not both a_{0} and a_{1} are REA(u). Now take r.e. c and d such that c′ = a_{0} and d′ = a_{1}. Consider now any incomplete a ≥ c and b ≥ d. It is clear that a_{0} ∈ JB(a) and a_{1} ∈ JB(b). On the other hand, if a_{1} ∈ JB(a) then a would be complete and so a_{1} ∉ JB(a). Similarly a_{0} ∉ JB(b) as required. Of course, c and d are incomparable as otherwise the larger of the two would be an incomplete u in which both a_{0} and a_{1} would be r.e.

Finally, by Theorem 1.2, we may take a_{0}∨a_{1} as the w required in the Proposition.

All the examples of pairs of incomplete r.e. degrees a and b with JB(a) ≠ JB(b) that we have seen provide, as far as we have specifically determined, only incomparable a and b. As we know of no others, we ask for comparable such pairs.

Question 5.3. When (for c ∈ REA(0′)) do we have r.e. a < b < 0′ with a′ = b′ = c such that JB(a) ≠ JB(b)?

Of course, we must here also at least have c > 0′ but Proposition 1.6 and Corollary 1.8 do not supply an answer even for c = 0′′ or c′= 0′′′. We can ask for even more along the lines of distinguishing r.e. degrees.

Question 5.4. Is there, for every nonlow r.e. a, an r.e. b ≠ a with a′ = b′ and JB(a) ≠ JB(b)? For which such a can we, in addition, choose b so that we have a < b, b < a or a|b?

Using a result of Arslanov, Lempp and Shore [1996], we can show that the strongest possible version of such a statement does not hold.

Proposition 5.5. There is a nonlow r.e. c such that every incomplete r.e. b ≥ c with c′ = b′ has JB(c) = JB(b).

Proof. Arslanov, Lempp and Shore [1996, Theorem 3.1] states that there is an incomplete nonrecursive r.e. A such that every set REA(A) and recursive in 0′ is of r.e. degree. By the uniformity inherent in the proof of this result, we can apply the pseudojump inversion theorem of Jockusch and Shore [1983] to get an r.e. C such that some set A∈ 0′ has this property relative to C. That is, C <_{T} A < C′ and every set REA(A) and recursive in C′ is of degree r.e. in C. Thus if the degree x ∈ REA(0′) (which, of course, is the same as REA(a)) and x ≤ c′ then some X ∈ x is REA(A) and so x ∈ REA(c). Thus, in particular, if b ≥ c and b′ = c′ then then JB(c) = JB(b).

We note that, as Arslanov, Lempp and Shore point out, the A they construct cannot be either low_{2} or high. This translates into fact that the c produced in the above Proposition is neither high_{2} nor low_{2}. We do not know any more about the possibilities for such c but there are several tempting possibilities. For example, could such a c also be least in its jump class with this maximal value of JB(c), i.e. could it be that for x ≱ c, JB(x) ≠JB(c)? If so, this would in a different way characterize c in terms of the JB operator. If not then, perhaps it might be minimal, i.e. for x < c, JB(x) ⊊JB(c) and so one would have characterized at least an antichain of degrees as the ones with this value of JB.

Moving in the other direction, i.e. towards stronger versions of Theorem 1.9 and Question 1.11, we can ask the following:

Question 5.6. Is there, for every nonrecursive, incomplete r.e. a an r.e. b with JB(a) =JB(b) for which we can also guarantee that b > a, b < a or b|a?

Note that as we pointed out after Definition 1.3, Theorem 1.1 shows that even to get a b < a with JB(a) =JB(b) we must assume that a is incomplete. It is hard to see how the assumption of the incompleteness of a can be used in the construction of a b < a.

We conclude with some methodological remarks about the construction that highlights a reverse mathematical issue. First, we note that despite the unusual type of argument about the assignment of requirements along the true path, the construction is still, by the usual criterion, a 0′′ one: In particular, our proof shows that 0′′ can compute the true path. Once one knows the fact that each requirement is eventually assigned to a fixed node along the true path, 0′′ can compute where and when this happens and so the precise way in which each requirement is satisfied.

Now, it is generally the case that 0′′ constructions can be carried out in IΣ_{2}. The anomaly here is that the proof that each requirement is eventually assigned to a fixed node along the true path (Lemma 2.5) and so of the fact that 0′′ can calculate all the outcomes of the construction seems to require IΣ_{3}. The point here is that in order to prove Lemma 2.5, we use an instance of the principle that any finite iterate f_{m} = \underbrace{f ∘ ⋯ ∘ f}_{m times} of a total Π_{2}-definable function f is itself a total function. (In our case, f(n) is the number of elements which are ever accessible, and which are ≤_{lex} tr↾n, where tr denotes the true path. This f comes from the scheme for assigning requirements to nodes, which can be found in §2.) This principle is known as Π_{2} recursion. It is denoted by TΠ_{2} in Hajek and Pudlak [1993] in the setting of first order arithmetic and PREC_{3} in Hirschfeldt and Shore [2007] in the setting of second order arithmetic. In each setting, it is shown equivalent to IΣ_{3}. Thus our proof, unlike previous examples, uses IΣ_{3} and so more induction than one would expect.

The solution to this problem is to use Shore blocking to assign blocks of requirements along the paths of the construction (and so along the true path). Thus, for example, instead of assigning at stage s a single requirement of some type (R_{e,i,n}, P_{e} or N_{e,i}) at a node α as in our construction, one assigns the block of the next requirements of the same type of size s (i.e. ones not yet on the path of the form R_{k,j,l} for k, j, l < s, P_{j} for j < s or N_{j,i} for j < s, respectively). We do not know of another 0′′ construction that requires blocking along the paths of the priority tree to carry out the argument that the requirements are satisfied in IΣ_{2}.

References

M. Arslanov, S. Lempp, and R. A. Shore. Interpolating d-r.e. and REA degrees between r.e. degrees. Ann. Pure Appl. Logic, 78(1-3):29–56, 1996.

P. Hájek and P. Pudlák. Metamathematics of first-order arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1993.

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

C. G. Jockusch, Jr. and R. A. Shore. Pseudojump operators. I. The r.e. case. Trans. Amer. Math. Soc., 275(2):599–609, 1983.

C. G. Jockusch, Jr. and R. I. Soare. Degrees of orderings not isomorphic to recursive linear orderings. Ann. Pure Appl. Logic, 52(1-2):39–64, 1991.

M. Lerman. Automorphism bases for the semilattice of recursively enumerable degrees. Notices of the Am. Math. Soc., 24:A–251, 1977. Abstract no. 77T-E10.

A. Nies, R. A. Shore, and T. A. Slaman. Interpretability and definability in the recursively enumerable degrees. Proc. London Math. Soc. (3), 77(2):241–291, 1998.

R. W. Robinson. Jump restricted interpolation in the recursively enumerable degrees. Ann. of Math. (2), 93:586–596, 1971.

G. E. Sacks. Recursive enumerability and the jump operator. Trans. Amer. Math. Soc., 108:223–239, 1963.

R. A. Shore. Some more minimal pairs of α-recursively enumerable degrees. Z. Math. Logik Grundlag. Math., 24(5):409–418, 1978.

R. A. Shore. A noninversion theorem for the jump operator. Ann. Pure Appl. Logic, 40 (3):277–303, 1988.

R. I. Soare and M. Stob. Relative recursive enumerability. In Proceedings of the Herbrand symposium (Marseilles, 1981), volume 107 of Stud. Logic Found. Math., pages 299–324. North-Holland, Amsterdam, 1982.