Splitting Theorems and the Jump Operator

R. G. Downey^{∗} Department of Mathematics Victoria University of Wellington P. O. Box 600 Wellington New Zealand

Richard A. Shore^{§} Department of Mathematics White Hall Cornell University Ithaca NY 14853 USA

Abstract We investigate the relationship of (jumps of) the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low_{2}.

∗Research partially supported by the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell University Contract DAAL03-91-C-0027, the IGC of Victoria University and the Marsden Fund for Basic Science under grant VIC-509.

§Research partially supported by NSF Grant DMS-9503503 and the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell University Contract DAAL03-91-C-0027.

1 Introduction

All sets and degrees will be computably enumerable unless otherwise stated. We say that A_{1} and A_{2} split A, written A = A_{1} ⊔ A_{2}, if A_{1} ∪ A_{2} = A and A_{1} ∩ A_{2} = ∅. Such a splitting is called proper if both A_{1} and A_{2} are noncomputable. Ever since Friedberg [6] proved that any noncomputable set has a proper splitting, splitting theorems have been intimately related to the development of classical computability theory. We refer the reader to Downey and Stob [5] for a survey.

The present paper is concerned with a question of Remmel who asked if a high set could always be properly split into two sets one of which is high. This question is related to earlier work of Ladner [8] on mitotic sets (see also Downey-Slaman [4]), and later work of Lerman and Remmel [9] and Ambos-Spies and Fejer [2] on the universal splitting property. Recall that a set A is called mitotic if it has a splitting A_{1} ⊔ A_{2} = A with A_{1} ≡_{T} A_{2} ≡_{T} A, and A has the universal splitting property if for all C ≤_{T} A, there is a splitting A_{1} ⊔A_{2} = A with A_{1} ≡_{T} C. Ladner proved that not all computably enumerable sets are mitotic, and, indeed, 0′ contains a nonmitotic set.

Ambos-Spies [1] proved that mitoticity could fail quite dramatically by constructing a complete A such that for any splitting A_{1} ⊔ A_{2} = A, one of A_{1} or A_{2} is low. On the other hand, Ambos-Spies’s construction could not be used to solve Remmel’s question since his set A, being complete, is of promptly simple degree while Downey and Stob [5] proved that if A has promptly simple degree then there is a splitting A_{1} ⊔ A_{2} = A such that A_{1} ≡_{T} A. Ingrassia and Lempp [7] provided a counterexample to a stronger version of Remmel’s question by constructing a computably enumerable set A such that for all nontrivial splittings A_{1} ⊔ A_{2} = A, A′_{1}, A′_{2} <_{T} A′.

The goal of the present paper is to prove the following theorem.

Theorem 1.1 There is a high computably enumerable set A such that if A_{1} ⊔ A_{2} = A is a proper splitting of A, then both A_{1} and A_{2} are low_{2}.

Corollary 1.2 There is a high computably enumerable set A such that for all n ≥ 1, if A_{1} ⊔ A_{2} is a proper splitting of A then A_{i}^{(n)} <_{T} A^{(n)} for i = 1, 2.

We remark that Cooper, Lachlan and Slaman have claimed (personal communication) that for all nonlow computably enumerable sets A, there is a proper splitting A_{1} ⊔ A_{2} = A with A_{1} nonlow. Given this result, ours is the strongest possible negative answer to Remmel’s question. Moreover, our result together with that of Cooper et. al. completely answers all possible versions of Remmel’s question in terms of the jump classes.

Our notation is standard and follows Soare [11]. As usual all computations etc. are bounded by the stage number and uses are monotone in both the argument and stage number. A number in brackets at the end of an expression such as Φ_{i}^{W_{e}}(y) [s] indicates that all computations and approximations to sets are to be understood as defined at stage s.

2 The Requirements and Construction

2.1 The Requirements and Intuition

We build a set A and a reduction Γ in stages to satisfy the following requirements:

R_{e} : lim_{s} Γ^{A}(e, s) = T ot(e).

N_{e} : W_{e} ⊔ V_{e} = A → (W_{e} low_{2}. ∨ .V_{e} ≡ ∅).

Here of course, T ot denotes the Π_{2}^{0}-complete index set {e : φ_{e} total}. We decompose the negative requirements N_{e} into further subrequirements of the form

N_{e,i} : W_{e} ⊔ V_{e} = A → (V_{e} ≡_{T} ∅. ∨ .[ℓ(τ, s) → ∞ → Φ_{i}^{W_{e}} is total]).

Here ℓ(τ, s) denotes the length of convergence

max{x : ∀y ≤ x(W_{e,s} ⊔ V_{e,s} = A_{s} ↾ y ∧ Φ_{i}^{W_{e}}(y) ↓ [s])}

measured at the node τ on the true path devoted to N_{e,i}. Note that this will make W_{e} low_{2} if V_{e} is noncomputable since, as usual for an infinite injury argument, the true path, T P, is recursive in 0′′ and hence we can answer the question “Is Φ_{i}^{W_{e}} total?” recursively in 0′′.

The priority tree will have 3 types of nodes :

• β nodes for the sake of R_{e} with outcomes ∞ <_{L} f.

• τ nodes for the sake of N_{e,i} with outcomes ∞ <_{L} f.

• α nodes living below τ ∞ also devoted to N_{e,i} via subrequirements N_{e,i,j}. Such an α will be trying to preserve a computation of the form Φ_{i}^{W_{e}}(j) or to demonstrate that V_{e} ≡_{T} ∅. These nodes have outcomes s <_{L} g. The unique τ node associated with α will be denoted by τ(α).

The action of a β node is as usual. We must build a Δ_{2}^{A} approximation to T ot via Γ. We may as well assume that φ_{e}(x) ↑ [0] for all x. At stage 0, we will define γ^{A}(e, x)[0] = ⟨e, x, 0⟩. As with the standard thickness lemma, the basic idea is that when we see φ_{e}(y) ↓ for all y ≤ x, we will enumerate some g ≤ γ(e, x) into A[s] allowing us to redefine Γ^{A}(e, x) = 1. This will be the only reason we will change the value of Γ^{A}(e, x)[s]. (But not the only reason we might change γ(e, x)[s].) If we succeed for almost all x then

φ_{e} is total iff lim_{x} Γ^{A}(e, x) = 1.

Thus A will be high as ∅′′ will be Δ_{2}^{A}. In the construction to follow, γ(e, x)[s] can also be changed for the sake of the N_{f,j,k} of lower priority (which are defined precisely below). However, this action will be controlled by τ(α)), and we will certainly ensure that lim_{s} γ(e, x)[s] exists.

Below the infinite outcome of a τ node there will be a tree of α nodes each devoted to some k, that is some subrequirement N_{e,i,k} of N_{e,i}. These nodes will be devoted to requirements of the form

V_{e} ≡_{T} ∅ ∨ Φ_{i}^{W_{e}}(k) ↓ .

The infinite outcome for an α node is the g outcome which corresponds to a global win for τ(α) in the sense that it will witness the fact that V_{e(α)} is computable. Naturally, below the infinite outcome of an α node we will have no nodes devoted to N_{e}.

Associated with α will be a marker m(α, s) which represents an attempt to compute an initial segment of V_{e} based on the assumption that (α is on T P and) we fail to force convergence of Φ_{i}^{W_{e}}(k). There are two types of actions associated with α corresponding to the two types of positive requirements it must deal with.

A typical situation is the following. We have a node τ devoted to N_{e,i}. Naturally, it is able to guess at the behavior of higher priority R_{f} nodes, and will only use correspondingly τ-correct computations. However, if ℓ(τ, s) → ∞ we need to ensure either that W_{e} is low_{2} or that V_{e} is computable. Thus we will need to deal with various β-nodes between τ ∞ and α as well as β nodes below α. So suppose that we have

τ ∞ ⊂ β_{1} ∞ ⊂ β_{2} f ⊂ β_{3} ∞ ⊂ α.

The way that α deals with these β-nodes between it and τ is the following. We reach τ (i. e. s is a τ stage) and it is expansionary with ℓ(τ, s) > k. We also assume that ℓ(τ, s) > m(α, s) + 1 via τ-correct computations. What α would now like to do is to preserve its computation from W_{e},

Φ_{i}^{W_{e}}(k) ↓ [s].

But it cannot really stop the β_{i} from putting their numbers (which may well be below the use φ_{i}(k)[s]) into A. What α tries to do is to lift the relevant β_{i}- uses above φ_{i}(k)[s], or to increase m(α, s) thereby increasing the likelihood that V_{e} is computable.

Initially, m(α, 0) = k. Now as above we reach τ and each of the β_{i} with τ ∞ ⊆ β_{i} ∞ ⊆ α (in our case i = 1, 3) indicate that they desire to change Γ^{A}(e(β_{i}), x(β_{i}))[s] for some least x(β_{i}). (This is the main idea.) What α does is

• lift m(α, s + 1) = m(α, s) + 1, • request that a single number z ≤ γ(e(β_{i}), x(β_{i}))[s] enter A[s], and

• lift γ(e(β_{i}), x′) above s for all x′ greater than x(β_{i}). (Here we assume that all the Γ^{A}(e(β_{i}), x′′) for x′′ < x(β_{i}) have been dealt with and are either permanently restrained or set to 1.)

Now, since the entry of z allows us to correct Γ^{A}(e(β_{i}), x(β_{i})) = 1[s]. β_{1} and β_{3} are happy. Notice that since we lifted all the γ(e(β_{i}), x′) above s for all x′ greater than x(β_{i}), after stage s, the only numbers β_{1} and β_{3} will wish to put in will be numbers bigger than s = m(α, s). The relevance of this comes at the next τ ∞ stage s′. The single number z has entered A below φ_{i}(m(α, s))[s] between stages s and s′. Since W_{e} and V_{e} are disjoint, z has either entered W_{e} or V_{e} but not both. If z entered V_{e} then α can now successfully restrain the Φ_{i}^{W_{e}}(k) ↓ [s′] computation since it is identical to the Φ_{i}^{W_{e}}(k) ↓ [s] computation. Now α can put finite restraint on the β′ of lower priority, and the β of higher priority now only want to put numbers above m(α, s) into A. (The β above τ were taken care of by the fact that we were dealing with τ-correct computations and ℓ(τ, s) > k; β between τ ∞ and α have had their γ(e(β_{i}), x′) lifted above s.) Then the next time we hit α we simply play outcome s defining a restraint r(α, s) = φ_{i}(k)[s].

On the other hand, it is possible that z went into W_{e}. In this case, when we reach α we play outcome g. Now we note that the only numbers that can be put into A by nodes β above α are bigger than m(α, s + 1). The only numbers below m(α, s + 1) which enter A after stage s must therefore come from nodes ν below α and can, like z above, only enter at stages at which we lift m(α, t) and hence as the single small number that enters between successive α stages. Assuming that g is the correct outcome, this single small number must enter W_{e} each time. If we assume that m(α, s) → ∞ then we can compute V_{e} ↾ p by simply waiting for a τ ∞ stage with ℓ(τ, s) > m(α, s) and m(α, s) > p.

The final point we need to notice is that it does not really matter what number z ≤ γ(e(β_{i}), x(β_{i}))[s] is used. We could equally well use some number requested by some β′ below α g. In this way we also get to meet the R_{f} of priority lower than α in case α g ⊂ T P.

We now turn to the formal construction.

2.2 The Priority Tree

Define the priority tree as follows. If ν is on the priority tree and |ν| = 3e, ν is devoted to R_{e}. Put ν ∞ and ν f on the priority tree. ν is a β-node and e(ν) = e.

Otherwise, we use two lists L_{1} and L_{2} to assign requirements to nodes. As usual the lists L_{1}(λ) = L_{2}(λ) = ω. We use the convention that we do not change lists as we pass to the outcomes of a node unless specifically so instructed.

If |ν| ≡ 1 mod 3 assign N_{e,i} to ν where ⟨e, i⟩ is the least member of L_{1}(ν). Put ν ∞ and ν f on the priority tree. Let L_{1}(ν ∞) = L_{1}(ν f) = L_{1}(ν) − {⟨e, i⟩}. Let L_{2}(ν f) = L_{2} − {⟨e, i, k⟩ : k ∈ ω}. ν is a τ node, e(ν) = e and i(ν) = i.

Finally, if |ν| ≡ 2 mod 3, find the least ⟨e, i, k⟩ in L_{2}(ν) such that ⟨e, i⟩ ∉ L_{1}(ν). Assign N_{e,i,k} to α. Put ν s and ν g on the priority tree. Let L_{2}(ν s) = L_{2}(ν) − {⟨e, i, k⟩}. Let L_{2}(ν g) = L_{2}(ν) − {⟨e, i′, k′⟩ : i′, k′ ∈ ω}. Let L_{1}(ν g) = L_{1}(ν) − {⟨e, i′⟩ : i′ ∈ ω}. ν is an α-node, e(ν) = e, i(ν) = i and k(ν) = k.

2.3 The Construction

Step 1.

At each stage of the construction, we put at most one number into A. We determine this number by approximating T P by T P_{s} as follows. We begin at λ and say that s is a λ-stage. Suppose that s is a ν-stage. And suppose that t is the maximum of 0 and the last ν-stage. There are 3 cases.

Case 1. ν is a β-node.

If | max{q : φ_{e(ν)}(q′) ↓ [s] for all q′ ≤ q}| > | max{q : φ_{e(ν)}(q′) ↓ [t] for all q′ ≤ q ∧ t a ν stage}|, declare that s is a ν ∞ stage and that ν desires the largest number less than or equal to all γ_{ν}(e(ν), x), if any, with γ_{ν}(e(ν), x) > max{r(δ, s) : δ < ν}, and φ_{e(ν)}(x′) ↓ for all x′ ≤ x, but Γ^{A}(e(ν), x) = 0 to enter A.

Otherwise say that s is a ν f stage.

Case 2. ν is a τ-node.

Let e = e(ν). Determine the ν-correct length of convergence. ℓ(ν, s) = max{x : ∀y ≤ x(W_{e,s} ⊔V_{e,s} = A_{s} ↾ y ∧Φ_{i}^{W_{e}}(y) ↓ [s])} where the computations are ν-correct. That is, for all β ∞ ⊆ ν, with |β| ≡ 0 mod 3, and any x, if (i) γ(e(β), x) < u(Φ_{i}^{W_{e}}(y)) (ii) γ(e(β), x) > max{r(δ, s) : δ < β}, (iii) φ_{e(β)}(x′) ↓ for all x′ ≤ x, then Γ^{A}(e(β), x) = 1.

If the stage is ν-expansionary we say that s is a ν ∞-stage. We require that the k^{th} expansionary stage have ν-correct length of agreement exceeding

• max{m(α, s) + 1 : α ⊇ ν ∞, such that e(α) = e, i(α) = i and α is devoted to N_{e,i,k′} for some k′ ≤ k}.

If s is not ν-expansionary, we say that s is a ν f stage. Let r(τ f, s) be the last τ ∞-stage (or 0 if there is no such stage).

Case 3. ν is an α-node.

Let e = e(α), i = i(α), k = k(α), and τ = τ(α). If ℓ(τ, s) ≤ m(ν, s), set T P_{s} = ν. Otherwise, see if for all β ∞ ⊆ ν, with |β| ≡ 0 mod 3, and any x, if

(i) γ(e(β), x) < u(Φ_{i}^{W_{e}}(k′)) for k′ ≤ k, (ii) γ(e(β), x) > max{r(δ, s) : δ < β}, (iii) φ_{e(β)}(x′) ↓ for all x′ ≤ x, then Γ^{A}(e(β), x) = 1, If so, let r(ν, s) = u(Φ_{i}^{W_{e}}(k)). Declare s to be a ν s-stage. If not then declare s to be a ν g-stage, and reset m(ν, s+1) = m(ν, s)+1.

Step 2.

Having determined T P_{s}, we initialize all α-nodes σ to the right of T P_{s}. This entails returning m(σ, s + 1) to m(σ, 0), and setting r(σ, s + 1) = 0. Step 3.

Finally, put into A the smallest number z, if any, that any β node σ (such that s is a σ-stage) desires to put into A. For β ⊂ T P_{s}, reset γ(e(β), x)[s+1] for all e(β), x with γ(e(β), x)[s] > z, and some Γ(e(β), x′)[s] with x′ ≤ x causes β to desire a number to enter A at stage s. For such e(β), x, set Γ^{A}(e(β), x) = 1[s + 1] if {φ_{e(β)}(x′) ↓: for all x′ ≤ x}. Step 4.

For each τ-node μ with μ ∞ ⊆ T P_{s}, set r(μ f, s + 1) = s + 1. For each α-node μ with μ g ⊆ T P_{s}, set r(μ g, s + 1) = s + 1. End of Construction.

3 The Verification

We verify the following by simultaneous induction on ν ⊂ T P:

(i) lim_{{s:s is a ν-stage}} r(ν′, s) < ∞ exists for all ν′ ≤ ν.

(ii) If ν is a β-node, then lim_{x} Γ^{A}(e, x) = T ot(e). Moreover, ν ∞ ⊆ T P iff T ot(e) = 1.

(iii) If ν is a τ-node, then ν ∞ ⊂ T P iff there are infinitely many τcorrect τ-expansionary stages and hence ν ∞ ⊆ T P iff W_{e} ⊔ V_{e} = A and Φ_{i(ν)}^{W_{e(ν)}} is total.

(iv) If ν is an α node then ν g ⊂ T P implies that V_{e(ν)} is computable. If ν s ⊂ T P then Φ_{i(ν)}^{W_{e(ν)}}(k(ν)) ↓

We assume (i)-(iv) for all σ ⊂ ν. Let s_{0} be a stage at which the hypotheses apply to all such σ and we are never again to the left of ν. There are 3 cases to consider.

Case 1. ν is a β-node. Then there is no restraint associated with ν and hence (i) holds and (iii) and (iv) are irrelevant. Let e = e(ν). To see that (ii) holds suppose first that T ot(e) = 0. Then, after some stage, ν will stop desiring to put numbers into A in accordance with the first case of the construction. Hence ν f ⊂ T P. Next, suppose that T ot(e) = 1. In this case, infinitely often when we reach ν there will have been a change in T ot(e)[s] since the last ν-stage t (i. e. | max{q : φ_{e(ν)}(q′) ↓ [s] for all q′ ≤ q}| > | max{q : φ_{e(ν)}(q′) ↓ [t] for all q′ ≤ q ∧t a ν stage}|). According to case 1 of the construction, all such stages will be ν ∞ stages. Furthermore, since the higher priority restraints come to a limit, for sufficiently large x, if s is a ν ∞ stage and ν desires a number below γ_{ν}(e(ν), x), for some e(ν), x to enter A since γ_{ν}(e(ν), x) > max{r(δ) : δ < ν}, and φ_{e(ν)}(x′) ↓ for all x′ ≤ x, but Γ^{A}(e(ν), x) = 0, then this desire cannot be restrained by any σ. Therefore at step 3 of the construction, either γ_{ν}(e(ν), x) itself, or some z < γ_{ν}(e(ν), x) will be enumerated into A. Finally, to see that the γ(e(ν), x)[s] come to a limit, note that we only gratuitously change γ(e(ν), x)[s] in step 3 of the construction when ν desires to correct Γ_{e(ν)} on some x′ ≤ x. But each time such a change is desired and made for some x′, we will set Γ^{A}(e(ν), x′) = 1 during that stage. Of course, this can happen only finitely often.

Case 2. ν is a τ node. Straightforward.

Case 3. ν is a α-node. Let e = e(ν), i = i(ν), and k = k(ν). By the construction of the priority tree, we can suppose that for all ν-nodes ν′ ⊂ T P, devoted to N_{e,i,k′} for k′ < k, ν′ s ⊂ ν. It follows that after some stage s_{1} > s_{0} each time we have a τ(ν) ∞-stage, we must have the τ-correct length of agreement above m(ν, s). We argue as in the intuitive discussion. First, suppose that at some stage s_{2} after s_{1}, ν imposes restraint. Now we see that s_{2} must be an ν-stage at which, for all β ∞ ⊆ ν with |β| ≡ 0 mod 3 and for any x, if (i) γ(e(β), x) < u(Φ^{W_{e}}(k′)) for k′ ≤ k, (ii) γ(e(β), x) > max{r(δ, s) : δ < β}, (iii) φ_{e(β)}(x′) ↓ for all x′ ≤ x, then Γ^{A}(e(β), x) = 1. It follows that no number of higher priority can injure the Φ_{i}^{W_{e}}(k)[s_{2}]-computation. By ν’s restraint and the step 3 initialization, no δ of lower priority can injure the Φ^{W_{e}}(k)[s_{2}]-computation. Therefore Φ_{i}^{W_{e}}(k)[s_{2}] ↓= Φ_{i}^{W_{e}}(k)[s_{2}] m(ν, s_{2}) = m(ν), and r(ν, s_{2}) = r(ν).

Thus we can suppose that there is no stage s_{2} after s_{1} where restraint is imposed by ν. In this case, we claim that V_{e} is computable. We reason by induction on stages after s_{1}. Suppose that no number below m(ν, s) will ever again enter V_{e}. And that s is some τ ∞ stage after s_{2}. Now the computation up to ℓ(τ, s) is τ-correct and we know that the length of agreement exceeds m(ν, s)+1 τ-correctly. We will not reset m(ν, s′) until a stage s′ ≥ s at which we visit ν. Suppose that s′ is such a stage. At stage s′ we will increment m(ν, s′ + 1) to be m(ν, s) + 1. At stage s′, at most one number will enter A and, by construction, every β with β ∞ ⊆ ν desires to put a number into A.

The action of putting z into A in case 3 will clearly lift all the γ(e(β), x) for β ∞ ⊆ ν which are not permanently restrained and have γ(e(β), x) < m(ν, s′) above m(ν, s′)+1. Therefore no β with β ∞ ⊆ ν can ever later desire to put a number below m(ν, s′ +1) into V_{e}. Furthermore no δ ≥_{L} ν can put a number below m(ν, s′ + 1) by ν restraint. Finally, at most one number below m(ν, s′ + 1) can enter A from nodes below ν g, and since no later stage is a ν s stage, this small number must enter W_{e} and not V_{e}. Therefore, V_{e} is now fixed on m(ν, s′) + 1 and hence by induction, V_{e} is computable. □

References

[1] K. Ambos-Spies, Antimitotic recursively enumerable sets, Z. Math. Logik Grundlagen Math. 31 (1985), 461-467.

[2] K. Ambos-Spies and P. A. Fejer, Degree theoretical splitting properties of recursively enumerable sets, J. Symbolic Logic 53 (1988), 1110-1137.

[3] R. G. Downey, Localization of a theorem of Ambos-Spies and the strong antisplitting property, Archiv math. Logik Grundlag. 26 (1987), 127-136.

[4] R. G. Downey and T. A. Slaman, Completely mitotic r.e. degrees, Ann. Pure Appl. Logic 41 (1989), 119-152.

[5] R. G. Downey and M. Stob, Splitting theorems in recursion theory, Ann. Pure Appl. Logic 65 (1993), 1-106.

[6] R. Friedberg, Three theorems on recursive enumeration, J. Symbolic Logic, 23 (1958), 308-316.

[7] M. Ingrassia and S. Lempp, Jumps of nontrivial splittings of r.e. sets, Z math. Logic. Grundlagen Math., 36 (1990), 285-292.

[8] R. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic, 38 (1973), 199-211.

[9] M. Lerman and J. B. Remmel, The universal splitting property, II, J. Symbolic Logic 49 (1984), 137-150.

[10] P. Odifreddi, Classical Recursion Theory, North-Holland, Amsterdam, 1990.

[11] R. I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, New York, 1987.