Splitting theorems and low degrees

Abstract

We prove that if A is a non-low c.e. set, then there exists noncomputable sets $A_{1} ⊔ A_{2} = A$ splitting A with $A_{1}$ non-low.

Keywords

Splitting low computably enumerable set non-uniformity domination

1. Introduction

Some of the earliest theorems in computability theory are those concerning splittings of computably enumerable (c.e.) sets. We say that $A_{1} ⊔ A_{2} = A$ is a splitting of A if $A_{1}$ , $A_{2}$ are c.e., disjoint and $A_{1} \cup A_{2} = A$ . One of the earliest results is Friedberg’s splitting theorem [13] which asserts that each noncomputable c.e. set has a nontrivial split, meaning that neither $A_{1}$ nor $A_{2}$ are computable.

One of the reasons that splitting theorems have interest is their interactions with the c.e. degrees. If $A_{1} ⊔ A_{2} = A$ , then $deg (A_{1}) \lor deg (A_{2}) = deg (A)$ holds in the Turing (and in fact weak truth table) degrees. Thus Sacks famous splitting theorem [18] asserts that for each noncomputable c.e. set A and noncomputable $Δ_{2}^{0}$ set B there is a splitting $A_{1} ⊔ A_{2} = A$ with $B {⩽̸}_{T} A_{i}$ for $i \in {1, 2}$ . Thus there is no least c.e. degree and all c.e. degrees are join reducible.

For more on the extensive interactions of splittings of c.e. sets with the c.e. degrees and other topics in classical computability theory, we refer to the somewhat dated but extensive paper Downey–Stob [12].

The current paper is concerned with interactions of splitting theorems and the jump operator. As observed by Soare, the standard proof of Sacks’ splitting theorem automatically give low c.e. sets $A_{1}, A_{2}$ , meaning that $A_{i}^{'} \equiv_{T} \emptyset^{'}$ .

A natural question is to ask whether this is tight in some sense. Can c.e. sets always be nontrivially be split into non-low c.e. sets? Of course this question is only meaningful if A is non-low.

A strong counterexample would be provided by showing that each c.e. set A was mitotic meaning that it has a splitting $A_{1} ⊔ A_{2} = A$ where $A_{1} \equiv_{T} A_{2} \equiv_{T} A$ . Unfortunately Ladner [16] proved that not every c.e. set was mitotic, but also proved [17] that there were nonzero c.e. degrees containing only mitotic sets. For more on this see Downey and Slaman [11], and Griffiths [14].

Perhaps a weak example could be provided by only looking at jumps. However, Ingrassia and Lempp [15] proved that there are c.e. sets A such that there is no splitting $A_{1} ⊔ A_{2} = A$ with $A_{1}^{'} \equiv_{T} A_{2}^{'} \equiv_{T} A^{'}$ . Also Chih [5] has shown that there is a c.e. A set whose complement is not “semilow” (i.e. ${e ∣ W_{e} \cap \overline{A}} {⩽̸}_{T} \emptyset^{'}$ ), known as a speedable c.e. set, which cannot be split into a pair of c.e. speedable sets.

Towards the other direction, Ambos-Spies [1] proved that there is a complete c.e. set A such that if $A_{1} ⊔ A_{2} = A$ is a splitting, then at least one of $A_{1}$ or $A_{2}$ is low. Can we have that both sides of every nontrivial splitting of a complete set always low? That is, the only splits with both sides noncomputable are essentially Sacks’ splits? Downey and Stob [12] showed that the answer is no since if A is prompt (i.e. of promptly simple degree) then there is a splitting $A_{1} ⊔ A_{2} = A$ with $A_{2} ≢_{T} \emptyset$ and $A_{1} \equiv_{T} A$ .

Finally Downey and Shore [10] proved the following

Theorem 1.1 (Downey and Shore [10]).

There is a high c.e. set A (i.e. $A^{'} \equiv_{T} \emptyset^{″}$ ) such that if $A_{1} ⊔ A_{2} = A$ is a nontrivial splitting (i.e. neither $A_{1}$ nor $A_{2}$ are computable) of A then both $A_{1}$ and $A_{2}$ are low₂. (i.e. $A^{″} \equiv_{T} \emptyset^{″}$ )

In terms of the jump operator, we show that Theorem 1.1 settles the matter since we prove the following definitive result.

Theorem 1.2.
If A is any non-low c.e. set, then there exists a non-low c.e. set $A_{1}$ and a non-computable c.e. set $A_{2}$ with $A_{1} ⊔ A_{2} = A$ .

The question we answer with Theorem 1.2 has attracted several conjectures. Theorem 1.2 certainly conjectured to be true around 1990, but no proof appeared; and in recent years conjectured to be not true.

Our proof is somewhat subtle (and surprisingly difficult) in that we will essentially use that fact that we can begin with A non-prompt. To the authors’ knowledge, this is the first proof that nonuniformly splits into two cases, depending on whether A is prompt or tardy. Technically, we will use the tardy assumption to force certain “gaps” to remain open that we can argue that certain small numbers don’t enter sets capriciously. This is done by trying to build noncomputable sets $Q_{α}$ at nodes α on the true path, with the $Q_{α}$ below a minimal pair. This must fail on some witness since they are a minimal pair, and it is here that we meet the requirement. The technique should be useful elsewhere.

We will work up to the proof by first establishing the result with the assumption that A is high. Once this is done we modify the proof for the non-low case, which involves significant surgery on the tree from the high case for purely technical reasons. Certain fundamental ideas from the high case remain, and there are most easily understood without the additional nonuniformity present in the non-high case.

We remark that Downey and Ng [9] have shown that if we consider splitting with low replaced by superlow1
¹
That is, $A_{i}^{'} \equiv_{t t} \emptyset^{'}$ .

then the splitting result fails more spectacularly, even for degrees. Downey and Ng showed that there is a c.e. degree a such that if $a_{1} \cup a_{2} = a$ in the c.e. degrees, then one of $a_{1}$ or $a_{2}$ is not totally ω-c.a. Being totally ω-c.a. is a weakening of being superlow (and array computable) and means that if $f ⩽_{T} a_{i}$ then f has a computable approximation $f (n) = {lim}_{s} f (n, s)$ with a computable function h, such that $| {s ∣ f (n, s + 1) \neq f (n, s)} | ⩽ h (n)$ . Downey and Ng also showed that every high c.e. degree is the join of two totally ω-c.a. c.e. degrees. This extends a classical theorem of Bickford and Mills [4] who showed that $0^{'}$ is the join of two superlow c.e. degrees. However, in [9] it is shown that there are (super-)high c.e. degrees that are not the joins of two superlow degrees. Finally, Ambos-Spies, Downey and Monath have proven
Theorem 1.3 (Ambos-Spies, Downey, and Monath [2]).

Every c.e. set can be split into a pair of c.e. sets which are totally $ω^{3}$ -c.a.

Here a is totally $ω^{n}$ -c.a. means that every $f ⩽_{T} a$ has an $ω^{n}$ -approximation, given by effective Cantor Normal Form. (See Downey and Greenberg [6].) It is unknown if Theorem 1.3 can be improved to $ω^{2}$ , even for degrees.

We refer to Soare [19] or the computability section of Downey-Hirschfeldt [8] as a general reference to our notation and terminology. We tend to use the Lachlan convention that appending $[s]$ to a parameter, indicates its state at stage s. We denote the jump function $J^{A} (e) = {e ∣ Φ_{e}^{A} (e) ↓}$ . The use of the jump function will be denoted by $j (e)$ , and more generally, uses will be lower case letters of the functionals. Parameters don’t change from stage to stage unless indicated otherwise.

2. The evolution of the present paper

Ellen Chih established a sketch of a proof of the result proven in this paper, but no details have appeared, or are likely to, for various reasons.

Independently, and thinking Chih had claimed the opposite direction, the second author also worked on the problem. Both authors independently split the proof into the non-prompt and prompt case, which seems essential. In an e-mail to Downey, Leo Harrington described Chih’s proof which otherwise worked quite differently, and involved a lemma about lowness of independent interest. We give a proof of this Lemma in Section 5. Chih’s proof involved yet another level of nonuniformity, than the proof here. Our proof works through the Downey, Jockusch, Schupp non-lowness permitting machinery ([7]).

The point of all of this is that all errors in the present paper are due entirely to Downey. Given the long history of the problem, at least since 1990, it is important to get a proof in the literature.

3. The high case

We are given a c.e. set A of high degree and need to construct disjoint c.e. sets X and Y so that $X ⊔ Y = A$ and meet the requirements $\begin{array}{l} R_{e} : J^{X} \neq lim_{s} φ_{e} (\cdot, s), \\ P_{e} : \overline{Y} \neq W_{e} . \end{array}$

3.1. Using highness

We will begin by proving the result for the more familiar case that A is of high degree. This proof has most of the elements we need and we later modify the proof to the situation of A only assumed non-low, in Section 4.

Since A is high we are given an A-computable function $Γ^{A}$ such that for any computable function h, $\begin{matrix} (a . a . z) Γ^{A} (z) > h (z) . \end{matrix}$ Of course, we will have a $Δ_{2}^{0}$ approximation $Γ^{A} (z) [s]$ with use function $γ (z) [s]$ . This is sped up so that at every stage s, $Γ^{A} (p) ↓ [s]$ for $p < s$ .

For each requirement R or P we will build computable functions h and use them to force elements into A. Namely, if a function h is associated with a requirement and for its sake we wish to enumerate a element into A to put into one of X or Y, we will arrange things so that the relevant element needed is bigger than $γ (z) [s]$ , and we have not as yet defined $h (z)$ . (In fact it will be that this is the least such z with $h (z)$ undefined.) Note that $γ (z) [s]$ can only change if some element $a ⩽ γ (z) [s]$ enters $A - A_{s}$ . Now, we will define $h (z) > Γ^{A} (z) [s]$ .

The opponent only have two options. Either it gives up on z and admits that $Γ^{A} (z) < h (z)$ , or it can change its stage s value to make $Γ^{A} (z) > h (z)$ . In the latter case we are supplied with a permission.

If the requirement is infinitely active, then we can ensure that h is computable. Hence option 1 can only occur for finitely many z, as $Γ^{A}$ is dominant. Option 2, will therefore occur almost always and hence almost always we get permissions from A.

Remark 3.1.
We remark that with this methodology, as will also happen in the case that A is only non-low and not necessarily high, that although almost always A will permit, the opponent won’t let this happen promptly. Naturally, while we await a permission, some new strategy is begun with the assumption that this z does not permit. For a single requirement this is of no consequence, but as we later see, the lack or promptness is the essence of difficulties we have when we consider interactions of requirements.

3.2. The basic $R_{e}$ -module

Meeting $R_{e}$ works as follows. We will pick an index $i = i_{0}$ , potentially computable function h, and start argument 0 for h.

We will keep $J^{X} (i_{0}) ↑ [s]$ until a stage s is found where $φ_{e} (i_{0}, s) = 0$ .

At this stage, we will declare that $J^{X} (i_{0}) ↓ [s + 1]$ with use $j (i_{0}) [s + 1] > γ (p) [s + 1]$ . where p is the first argument for which we have not yet defined $h (p)$ .

For stages $t ⩾ s + 1$ , until we see $φ_{e} (i_{0}, s) = 1$ , we keep $j (i_{0}) [t] > γ (p) [t]$ . To do this, whenever some number $q ⩽ γ (p) [t]$ enters $A_{t + 1} - A_{t}$ we will put at least one such number into $X_{t + 1} - X_{t}$ . Notice for a fixed argument p of $Γ^{A}$ , this will only effect a finite number of numbers entering A, essentially bounded by $γ (p)$ .

Should we see a stage $u > s$ where $φ_{e} (i_{0}, u) = 1$ , then we will try to make $J^{X} (i_{0}) ↑ [u^{'}]$ for some $u^{'} > u$ .

The way we will implement this idea is to now define $h (p) > γ (p) [u]$ .

The strategy for $i_{0}$ now stalls until we see a stage $u^{'} > u$ (if any) where $A ↾ γ (p) [u^{'}]$ changes. If we see such a stage $u^{'}$ we would return to step (i). $i_{0}$ would now assert control of the strategy and we would not do further work until (ii) is again found for $i_{0}$ .

While the $i_{0}$ strategy is stalled in (v), we’d begin the $i_{1}$ -strategy for a newly chosen argument $i_{1}$ , and whilst $i_{0}$ is stalled we would run through the same steps for $i_{1}$ , which would assert control of the first unused argument for h. In general, the $i_{k}$ strategy is initialized each time an $i_{k - 1}$ strategy is no longer stalled. We always ensure that $j (i_{k}) [s] > j (i_{k - 1}) [s]$ .

There are several outcomes to the module above. The module could get stuck in (i) for some fixed $i_{k}$ . This is outcome w which satisfies the requirement since $J^{X} (i_{k}) ↑ \neq {lim}_{s} φ_{e} (i_{k}, s) = 1$ , the $Σ_{2}^{0}$ -outcome. Otherwise we see that the $R_{e}$ module is infinitely often active, and hence h is total. Because $Γ^{A}$ is dominant, only finitely many $i_{k}$ can be permanently stuck in (v), and hence there is a least k with the outcome $(k, \infty)$ , saying that $i_{k} [s]$ has come to a limit, and the whole cycle repeats infinitely often for this least $i_{k}$ . We would conclude that ${lim}_{s} φ_{e} (i_{k}, s)$ fails to exist. We would organize the outcomes as $(0, \infty) <_{L} (1, \infty) <_{L} \dots <_{L} w$ , an $ω + 1$ list on the tree.

Remark 3.2.
In the case of outcome w, the $R_{e}$ -module has finite effect on the construction. In the case of outcome $(k, \infty)$ , $i_{d}$ for $d < k$ never again active, from some stage $s^{'}$ onwards, but thereafter there will be infinitely many stages where $J^{X} (i_{k}) ↑ [s]$ . At such stages s, the $R_{e}$ -module does not care if a number enters A, in the sense that we would not be forced by (iii) or (v) to put such a number into X.

3.3. The basic $P_{f}$ -module

This is essentially Friedberg Strategy.

Pick some $d_{0}$ .

We see that $Y ↾ d_{0} = W_{f} ↾ d_{0} [s]$ . Declare $d_{0}$ as active. We would begin a strategy on $d_{1} > d_{0}$

We see some number $a < d_{p}$ for some active p enter A. In this case we put a into Y and win $P_{f}$ .

This strategy has two outcomes $s <_{L} w$ . (More thematically, we could use $1 + ω^{*} + 1$ , where the left 1 represents s and the order type $ω^{*}$ the number of times we play (ii). Using this, each time we play (ii) we can initialize on the priority tree to the right.) The second means that we get stuck waiting for (ii) on some $d_{k}$ , the first means we invoke (iii).

This module is finitary. The strategy wins because A is noncomputable, and hence some a must so enter.

3.4. The conflicts and their resolution

The first thing to note is that there are no conflicts between $R_{e}$ strategies. They want to put numbers into X. So we concentrate on $P_{f}$ vs $R_{e}$ . A $P_{f}$ above a $R_{e}$ is finitary and this simply works by initialization (by moving left on the tree).

So we will concentrate upon $P_{f}$ below an $R_{e}$ . As we said in Remark 3.1, the conflicts between the strategies above all revolve around the fact that it is the opponent who chooses when to enumerate elements into A to witness the domination of $Γ^{A}$ . Consider a version of $P_{f}$ guessing the outcome of $R_{e}$ is $(k, \infty)$ . It would like to see it’s witnessing element a enter A at a stage where $J^{X} (i_{k}) ↑ [s]$ . That is because at such a stage s, an element entering A would be free to enter Y to meet $P_{f}$ .

Certainly $P_{f}$ could begin it’s attack as per (ii) in $R_{e}$ ’s cycle at a stage where $J^{X} (i_{k}) ↑ [s]$ . But there is no a priori reason that such an element would enter while $R_{e}$ is not in (iii) or (v) for $R_{e}$ , when $J^{X} (i_{k}) ↓ [t]$ . If such an a entered $A_{t}$ when $R_{e}$ is in that part of its cycle, we’d be forced to put a into X, otherwise the strategy for $R_{e}$ would be invalidated. We would no longer have the ability to correct $J^{X} (i_{k})$ .

This conflict seems to be nearly fatal, and can be turned around to give a proof that there is no uniform method of constructing the split $X ⊔ Y = A$ .

The method of solving the problem we use is rather unusual. We know that there is no problem is A is prompt by Downey and Stob [12], as mentioned earlier.

We desire that no small number like $a ⩽ d_{p}$ enters A while $J^{X} (i_{k}) ↓$ . The plan is to try to impose restraint on A for stages while this is true. Of course, A is played by the opponent, so any restraint must be indirect. This restraint is imposed by utilizing the fact that since A is not prompt, it must be cappable. That is, if A is not prompt then there is a noncomputable c.e. set B such that ${deg}_{T} (A) \land {deg}_{T} (B) = 0$ , by Ambos-Spies, Jockusch, Shore and Soare [3].

The idea is the following. We will build a c.e. set $Q ⩽_{T} A, B$ and try to meet the requirements $\begin{matrix} M_{m} : Q \neq \overline{W_{m}} . \end{matrix}$

We will amalgamate these requirements with the outcomes of $R_{e}$ , $(k, \infty)$ met before. The outcomes will now read as of the form $(k, m, \infty)$ of $R_{e}$ . These are ordered by regarding $k, m$ as a pairing function, hence give a list, again of order type ω, below $R_{e}$ .

Now each of these subrequirements of $R_{e}$ will have associated with it a follower $i_{k, m} [s]$ (for the jump function $J^{X} (i_{k, m})$ ) serving the role of $i_{k}$ discussed above. The rules of the basic module apply in that if something to the left acts then this witness is initialized.

The driver is that we don’t want random small numbers entering A which should be usable for some $P_{f}$ requirements being forced into X because $J^{X} (n) ↓$ , and either we want to change the value of this ((v) of the basic module) or maintain the value ((iii) of the basic module). The plan is to use the fact that for some m we must fail to meet $M_{m}$ , since A and B form a minimal pair.

The $(k, m)$ -strategy for $R_{e}$ .

The $(k, m)$ strategy works by generating a stream of numbers ${q_{j}^{m} : j \in ω}$ with (dropping the superscript) $q_{0} < q_{1} < \dots$ . We will say that $q_{i}$ is realized when we see $q_{i} \in M_{m} [s]$ . $q_{i + 1}$ is defined as large and picked after $q_{i}$ becomes realized. $q_{i}$ is said to be B-permitted at stage s if it is realized and $B_{s} ↾ q_{i} \neq B_{s - 1} ↾ q_{i}$ .

We modify the basic module as follows. We do this while $(k, m)$ is not yet diagonalized.

We will keep $J^{X} (i_{k, m}) ↑ [s]$ until a stage s is found where $φ_{e} (i_{k, m}, s) = 0$ , and some $q_{i}$ (the largest such) has been permitted since the last stage we visited the node representing $R_{e}$ .

At this stage, we will declare that $J^{X} (i_{k, m}) ↓ [s + 1]$ with use $j (i_{k, m}) [s + 1] > γ (p) [s + 1]$ , where p is the first argument for which we have not yet defined $h (p)$ .

For stages $t ⩾ s + 1$ , until we see $φ_{e} (i_{k, m}, s) = 1$ , we keep $j (i_{k, m}) [t] > γ (p) [t]$ . To do this, whenever some number $n ⩽ γ (p) [t]$ enters $A_{t + 1} - A_{t}$ we will put at least one such number into $X_{t + 1} - X_{t}$ . Notice for argument p, this will only affect a finite number of numbers entering A.

Should we see a stage $u > s$ where $φ_{e} (i_{k, m}, u) = 1$ , then we will try to make $J^{X} (i_{k, m}) ↑ [u^{'}]$ for some $u^{'} > u$ .

The way we will implement this idea is to now define $h (p) > γ (p) [u]$ .

The following is new.

While this is happening, (i.e. since we began (iii)) should some number $⩽ γ (q_{i}) [s]$ enter $A_{t}$ , then we will put $q_{i}$ into $Q_{t}$ and declare that all subrequirements of $R_{e}$ of the form $(k^{'}, m)$ for some $k^{'}$ are diagonalized. That would finish the stage, and $i_{k, m}$ would be discarded.

The strategy for $i_{k, m}$ now stalls until we see a stage $u^{'} > u$ (if any) where $A ↾ γ (p) [u^{'}]$ changes. If we see such a stage $u^{'}$ we would return to step (i), with $J^{X} (i_{k, m}) ↑$ . We would declare that $q_{i}$ is no longer permitted.

As in the Basic Module,

While the $i_{k, m}$ strategy is stalled in (v), we’d begin the $i_{k^{'}, m^{'}}$ -strategy for the next not yet diagonalized $(k^{'}, m)$ with a newly chosen argument $i_{k^{'}, m^{'}}$ . In general, the $i_{k}$ strategy is initialized each time an $i_{k - 1}$ strategy is no longer stalled. We always ensure that $j (i_{k}) [s] > j (i_{k - 1}) [s]$ .

So why does this work? First note that if we get stuck in (i) or (iii) waiting for a flip in the value of $φ_{e} (i_{k, m}, s)$ then this is a global win for $R_{e}$ , and the outcome will be w. (Note, however, we could get stuck in (iv).)

Since there are infinitely many permitted $q_{i}$ (as B is noncomputable), Thus if the $φ_{e}$ behaves honestly, we will infinitely often play outcomes of the form $(k, m, \infty)$ . We first claim that there is a least such $(k, m)$ .

Suppose not. We can move to a stage $s_{0}$ where we are never again left of $(k, m, \infty)$ , and hence thereafter $i_{k, m} [s_{0}] = i_{k, m}$ is immortal. The stream of $q_{i}$ associated with $(k, m, \infty)$ is growing with time and hence there are infinitely many stages where $(k, m, \infty)$ asserts control of the $R_{e}$ -module. We cannot get stuck in (i) or (iii) by assumption, and hence the only way this can only act finitely often is either by being diagonalized (so that $Q \cap W_{m} \neq \emptyset$ ), or by being stuck in (v).

Lemma 3.3.
Assuming that we are dealing with an infinitely active version of $R_{e}$ on the true path, $Q ⩽_{T} B, A$ .
Proof.
For the same reason as the basic module, only finitely many $(k, m)$ modules can be stuck in (v), as $Γ^{A}$ is dominant. If we assume that the node representing $R_{e}$ is on the true path, then for any $q_{i}^{x}$ , once it is B-permitted, either that permission will be initialized because of a higher priority $(r, z) < (w, x)$ acting at the next $R_{e}$ -stage, or we will begin an attack for the outcome $(w, x, \infty)$ associated with that $q_{i}^{x}$ . Now either that attack is initialized, or for almost all $q_{i}^{x}$ ’s the attack reaches (v), or a diagonalization occurs using $q_{i}^{x}$ via a $γ (q_{i}^{x})$ -permission. Therefore $Q ⩽_{T} B, A$ . □

It follows that for some least $(k, m)$ , $(k, m, \infty)$ is on the true path and $W_{m} = \overline{Q}$ , no $q_{i}^{m}$ is ever enumerated into Q. Moreover, if we call this the true $(k, m)$ , then the following holds.
Lemma 3.4.
For the true $(k, m)$ , every $i_{k, m}$ cycle runs from (i) to (v). Suppose that a cycle is begun following a permission on $q_{i}$ at stage $s_{0}$ and reaches (v) at stage $s_{1}$ . Then no number enters A below $γ (q_{i}) [s]$ for any stage $s \in [s_{0}, s_{1}]$ .

So now we see how we can make no small numbers enter A whilst $R_{e}$ would put them into X. During a cycle, Lemma 3.4 says no small numbers enter A during a cycle. Between cycles, $Γ^{X} (i_{k, m}) ↑$ so outcome $(k, m, \infty)$ does not care about numbers entering A.

The $P_{f}$ strategy remains the same. It does not care about B, only the noncomputabilty of A. The point is that some $R_{e}$ strategy at left of a node τ representing $P_{f}$ could ask that a number entering A go into X for the sake of (iii). Since $Γ^{A}$ is total this can only happen finitely often and we can afford to initialize each time this request happens. Thus, in the case of A high, there is only finite injury from the left. In the later non-low case things are more complex.

The remainder of the argument is to put this on a tree in a standard way; and this is routine.
4. The case that A is only non-low

Being non-low resembles being “nonuniformly locally high”. This has been made precise in, for example, Downey, Jockusch and Schupp [7] where the methodology is used to show that non-low c.e. degrees contain c.e. sets of density 1 with no computable subset of density 1.

The idea is to try to build a proof that A is low, and we see that for some argument k this proof will fail. It will be here that we succeed.

In more detail, for the basic module first, we again split $R_{e}$ into infinitely many subrequirements $R_{e, k}$ . This time subrequirement k is attempting to give a limit lemma definition of $\emptyset^{'} (k)$ , ${lim}_{s} Θ (k, s)$ .

Initially, $Θ (k, t) = 0$ indicating that we believe that $Φ_{k}^{A} (k) ↑$ . At some stage s we see $Φ_{k}^{A} (k) [s] ↓$ . The question is, should we change $Θ (k, s) = 1$ ? What we will do in synchronise this belief with attempts to meet $R_{e}$ . We will have a current $i_{k} [s]$ devoted to this subrequirement, as in the Basic Module of Section 3.2.

What we will do is now is to invoke the basic module; a modification of the one from the previous section. Currently we are keeping $Θ (k, u) = 0$ , until we hit (v) below. If, during the execution of the below, before we reach (iii) we see $Φ_{k}^{A} (k) ↑ [u]$ then we abandon this attack. Note we are not yet initializing anything right of $(k, \infty)$ .

We will keep $J^{X} (i_{k}) ↑ [s]$ until a stage s is found where $φ_{e} (i_{k}, s) = 0$ .

At this stage, we will declare that $J^{X} (i_{k}) ↓ [s + 1]$ with use $j (i_{p}) [s + 1] > p$ . Here p is some number chosen with $p > ϕ_{k} (k) [s]$ (which denotes $ϕ_{k}^{A} (k) [s]$ ).

For stages $t ⩾ s + 1$ , until we see $φ_{e} (i_{k}, s) = 1$ , we will monitor the situation, and if some number $⩽ ϕ_{k} (k) [s]$ enters $A_{t}$ we declare $J^{X} (i_{k}) ↑ [t]$ by putting said number into X.

Should we see a stage $u > s$ where $φ_{e} (i_{k}, u) = 1$ , then we will try to make $J^{X} (i_{0}) ↑ [u^{'}]$ for some $u^{'} > u$ .

New: The new way we do this is that we will finally define $Θ (k, u^{'}) = 1$ (with big use, in particular $> ϕ_{k} (k) [u]$ ), for $u^{'} > u$ unless (v) below occurs.

The strategy for $i_{0}$ now stalls until we see a stage $u^{'} > u$ (if any) where $A ↾ ϕ_{k} (k) [u^{'}]$ changes. If we see such a stage $u^{'}$ we would return to step (i). $i_{0}$ would now assert control of the strategy and we would not do further work until (ii) is again found for $i_{0}$ . Also making $Θ (k, u^{″}) = 0$ , for $u^{″} ⩾ u^{'}$ unless otherwise specified.

While the $i_{0}$ strategy is stalled in (v), we’d begin the $i_{1}$ -strategy for a newly chosen argument $i_{1}$ , and whilst $i_{0}$ is stalled we would run through the same steps for $i_{1}$ . It is here that initialization occurs. In general, the $i_{k}$ strategy is initialized each time an $i_{k - 1}$ strategy is no longer stalled. We always ensure that $j (i_{k}) [s] > j (i_{k - 1}) [s]$ .

Now the argument that the new $R_{e}$ -module succeeds is similar. Suppose that for all k, the k-module fails, and the $Σ_{2}^{0}$ outcome is not on the true path. Then each k module can only reach (v) finitely often. We claim that A is low, and $Θ (k, \cdot)$ is correct. The only time we change the value of $Θ (k, s)$ is when we reach (v). This will be correct, unless a stage $u^{'}$ as above occurs, and then the value will be changed back to 0. The fact that each k-module only acts finitely often means that ${lim}_{s} Θ (k, s)$ exists for all s. The fact that w is not correct, means that each cycle of the basic module is either completed or the $Φ_{k}^{A} (k) ↓ [s]$ computation goes away before the cycle if completed. The fact that we only initialize to the right at step (v), means that no false initiation of k-modules can upset our actions.

Therefore, some k module must succeed. If the $Σ_{2}^{0}$ -outcome is not correct, then this means that there is some least k which reaches (v) infinitely often and hence ${lim}_{s} φ_{e} (i_{k}, s)$ has no limit, and cannot compute $J^{X} (i_{k})$ where $i_{k} = {lim}_{s} i_{k} [s]$ .

Finally adding the B-permitting is exactly as before with the changes according to the module above.

So here is how the construction looks at a node ρ devoted to $R_{e}$ . For undiagonalized $k, m$ , if we hit ρ, then we will either play the outcome w or be in some attack as described below.

If, during the execution of the below, before we reach (iii), we see $Φ_{k}^{A} (k) ↑ [u]$ then we abandon this attack at any stage u between the stage where the attack was begun and we hit ρ this time. Note we are not yet initializing anything right of $(k, m, \infty)$ . If this occurs, $q_{i}$ is no longer permitted.

We do not allow a $k, m$ strategy to initialize outcome to the right unless we hit (iv) where we define $Θ (k, s)$ . i.e. $q_{i}$ is no longer permitted.

A consequence of these two outcomes is that there may be many $k^{'}, m^{'}$ -strategies played in parallel, because of the capriciousness of the $Φ_{k^{'}}^{A} (k^{'})$ . This is of no consequence, because we do not play nodes extending $ρ \hat{} (k, m, \infty)$ until we play (v) in the module.

We will keep $J^{X} (i_{k, m}) ↑ [s]$ until a stage s is found where $φ_{e} (i_{k, m}, s) = 0$ , $Φ_{k}^{A} (k) ↓ [s]$ , $Θ (k, s) = 0$ , and some $q_{i}$ (the largest such) has been permitted since the last stage we visited ρ. (Note that the requirement $Θ (k, s) = 0$ means that at most one $k, m$ has defined $Θ (k, s) = 1$ at a stage.)

At this stage, we will declare that $J^{X} (i_{k, m}) ↓ [s + 1]$ with use $j (i_{k, m}) [s + 1] > p$ . Here p is some number chosen with $p > ϕ_{k} (k) [s]$ .

For any stages $t ⩾ s + 1$ , until this module is resolved, until we see $φ_{e} (i_{k, m}, s) = 1$ , we will monitor the situation, and if some number $⩽ ϕ_{k} (k) [s]$ enters $A_{t}$ we declare $J^{X} (i_{k}) ↑ [t]$ by putting said number into X.

Should we see a stage $u > s$ where $φ_{e} (i_{k, m}, u) = 1$ , then we will try to make $J^{X} (i_{k, m}) ↑ [u^{'}]$ for some $u^{'} > u$ (i.e. using Θ).

While this is happening, (i.e. since we began (iii)) should some number $q_{i}$ enter $A_{t}$ , then we will put $q_{i}$ into $Q_{t}$ and declare that all subrequirements of $R_{e}$ of the form $(k^{'}, m)$ for some $k^{'}$ are diagonalized. That would finish the stage, and $i_{k, m}$ would be discarded.

Else we will finally define $Θ (k, u^{'}) = 1$ , for $u^{'} > u$ unless (v) below occurs. It is at this stage that we would initialize $(k^{'}, m^{'})$ right of $(k, m)$ .

The strategy for $i_{k, m}$ now stalls until we see a stage $u^{'} > u$ (if any) where $A ↾ ϕ_{k} (k) [u^{'}]$ changes. If we see such a stage $u^{'}$ we would return to step (i), with $J^{X} (i_{k, m}) ↑$ , putting the number entering A into X. We would decare that $q_{i}$ is no longer permitted.

When (v) occurs it is now that we would allow the construction to play strategies at nodes ν with $ρ \hat{} (k, m, \infty) ⪯ ν$ .

While the $i_{k, m}$ strategy is stalled in (v), we’d begin the $i_{k^{'}, m^{'}}$ -strategy for the next not yet diagonalized $(k^{'}, m^{'})$ with a newly chosen argument $i_{k^{'}, m^{'}}$ . In general, the $i_{k}$ strategy is initialized each time an $i_{k - 1}$ strategy is no longer stalled. We always ensure that $j (i_{k}) [s] > j (i_{k - 1}) [s]$ .

Now, in the construction, as opposed to the basic module, it is (iii) that causes a problem. It could be that some $(k^{'}, m^{'}) < (k, m)$ is working with a fake $Φ_{k^{'}}^{A} (k^{'})$ and during its cycle it sees a number entering A from the right and this number is below $φ_{k^{'}}^{A} (k^{'}) [s]$ , forcing this number into X, to correct $J^{X} (i_{k^{'}, m^{'}})$ . This can only occur finitely in the high case as $γ (k^{'}) [s]$ has a limit. But in the non-high case, it is conceivable it might happen infinitely often. Because of this, the $P_{f}$ modules below need to know if this happens. Thus for each outcome of the form $ρ \hat{} (k, m, \infty)$ we will have a second layer of outcomes guessing this $Π_{2}^{0}$ behaviour. To wit, we would have finite sets $F_{n}$ coding the $(k^{'}, m^{'}) <_{L} (k, m)$ for which this fake behaviour, and it would be enough to order them numerically.

The plan would be that if a $P_{f}$ is guessing that $(k^{'}, m^{'}) \in F_{n}$ is acting in this way infinitely often, it would demand that its $d_{i} < q_{i^{'}}$ where $q_{i^{'}}$ is the permitted $q_{j}$ associated with $ϕ_{k^{'}} (k^{'}) [s]$ . This means that if some small a from this version is pulled by $ρ \hat{} (k^{'}, m^{'}, \infty)$ , then it will be so small that $q_{i^{'}}$ will succeed in diagonalizing $M_{m^{'}}$ . Hence, this set-up allows for infinitely many numbers to enter A left of the true path for $(k^{'}, m^{'})$ , but conclude that they are so large that they are of no consequence for $(k, m, \infty)$ .

Being $Π_{2}^{0}$ behaviour, we can play this each time this event fires as the outcome of $ρ \hat{} (k, m, \infty)$ by reaching (v).

Next suppose that τ is a $P_{f}$ -node. The strategy is similar, but takes the comments above into account.

First if τ is infinitely often accessible, then it will be allowed to cycle through its definitions of $d_{i}$ as desired. If it was infinitely often active, as A is noncomputable, this will produce infinitely many active a’s, and by construction, these are small. On the assumption that all the nodes $ρ \hat{} (k^{'}, m^{'}, \infty)$ above are on the true path, a cannot enter A at a stage where $J^{X} (i_{k^{'}, m^{'}}) ↓ [s]$ lest $m^{'}$ become diagonalized. Note that if this number a is forced into X, it can only be because of some strategy left of τ. In particular, it is some strategy of the form $ρ \hat{} (p, m, \infty)$ , with $Φ_{p}^{A} (p) ↓ [s]$ , and $a < φ_{p} (p) [s]$ . If we are dealing with the leftmost version of τ on the true path we would have $a < q_{i}^{p, m}$ , since if this happens infinitely often, then $q_{i}^{p, m} \to \infty$ and $φ_{p} (p) [s] \to \infty$ . But then we would put $q_{i}^{p, m}$ into $M_{m}$ , diagonalizing $M_{m}$ henceforth. Therefore, only finitely many such a can be pulled into X for version of $P_{f}$ at τ, assuming it is on the true path. Thus after some stage, they enter when $J^{X} (i_{k^{'}, m^{'}}) ↑$ and can successfully be put into Y and not X.

The result now follows.

5. Characterization of lowness

The proof sketch communicated to Downey by Harrington used a different strategy. This strategy involved a new characterization of lowness that is worth recording, and we do so here.

Lemma 5.1 (Chih-Harrington).

A computably enumerable set A is low iff there is a computable order (i.e. increasing computable function) such that for all e, $\begin{matrix} \exists^{\infty} s \forall t \in [s, f (s)] (Φ_{e}^{A} (e) [s] ↓) ⟹ Φ_{e}^{A} (e) ↓ . \end{matrix}$ (Indeed, this will also hold for all orders $f^{*}$ growing faster than f.)

Proof.

First suppose that the hypothesis holds. Define $Θ (e, s) = 1$ iff $Φ_{e} (e) ↓ [s]$ and $\forall t \in [s, f (s)] (Φ_{e}^{A} (e) [s] ↓$ . Define $Θ (e, s) = 0$ otherwise. Then by hypothesis and the Limit Lemma $J^{A} (e)$ is determined by ${lim}_{s} Θ (e, s)$ , and hence $J^{A} ⩽_{T} \emptyset^{'}$ .

Conversely, suppose that A is low. We define a computable function f. Since A is low we know that $X = {j ∣ (\exists n \in W_{j}) [D_{n} \subseteq \overline{A}} ⩽_{T} \emptyset^{'}$ . (See Soare [19], XI, Lemma 3.1.) Hence by the Limit Lemma, there is a computable function h, and an enumeration of the c.e. sets, such that, for each stage s $X_{s} = {j ⩽ s ∣ (\exists n \in W_{j}) [D_{n} \subseteq \overline{A}] [s] = ra (h (\cdot, s))$ . We build uniformly for each e a c.e. set $V_{e}$ whose index $W_{g (e)}$ is given by the Recursion Theorem. Initially, $V_{e} = \emptyset$ . Thus, initially, $h (g (e), s) = 0$ .

Stage s. We are ready to define $f (s)$ .

$e ⩽ s$ will either be active or inactive. If e is inactive, then $Φ_{e}^{A} (e) ↓ [t]$ for all $t \in [u, s]$ where u was the stage where it was declared inactive. If e was inactive at stage $s - 1$ but now $Φ^{A} (e) ↑ [s]$ we will declare that e is active.

Suppose we see a stage s where $Φ_{e}^{A} (e) [s] ↓$ , for some active e.

Then for all active $e^{'} ⩽ s$ , we do the following. While the active requirements $e^{'}$ are unconfirmed for all $s^{'} > s$ if we see $Φ_{e^{'}}^{A} (e^{'}) ↓ [s^{'}]$ (so that $s^{'} = s$ for e), we will put $φ_{e^{'}}^{A} (e^{'}) \cap \overline{A} [s^{'}]$ into $V_{e^{'}} [s^{'}]$ , and hence $W_{g (e^{'})} [t (s^{'})]$ at some stage $t (s^{'})$ given by the s-m-n Theorem, and we wait for a stage $u > s^{'}$ where either (i) $h (g (e^{'}), u) = 1$ or (ii) $Φ_{e^{'}}^{A} (e^{'}) ↑ [u]$ (Here we are using the hat convention, that if a computation changes on its use, it must diverge for at least one stage.) When we see this, we will declare that $e^{'}$ is confirmed. Once confirmed we do not allow a requirement active at stage s to become unconfirmed until stage $f (s)$ defined below, so that each $e ⩽ s$ will have at most one activity cycle before we define $f (s)$ .

We then define $f (s)$ to be the first stage where all arguments n, active at stage s are confirmed, or for which during the confirmation process for active $e^{'} ⩽ s$ , $Φ_{n}^{A} (n) ↑ [s^{'}]$ for all $s^{'}$ .

Then f is clearly computable, and works. For suppose $Φ_{e}^{A} (e) ↓ [t]$ for all $t \in [s, f (s)]$ . Then it must be that $h (g (e), u) = 1$ for some $u \in [s, f (s)]$ . Then the only way that $Φ_{e}^{A} (e) ↑ [v]$ for some $v > f (s)$ , is that $h (g (e), v) = 0$ by the conventions on X. By the Limit Lemma, this can happen only finitely often. The result follows. □

Footnotes

Acknowledgements

Downey thanks to the Marsden Fund of New Zealand. Many thanks to Leo Harrington for a long discussion about this result, and to Rutger Kuyper for many corrections of false claims.

References

Ambos-Spies, Antimitotic recursively enumerable sets, Z. Math. Logik Grundlagen Math.31 (1985), 461–467. doi:10.1002/malq.19850312903.

Ambos-Spies,

Downey and

Monath, Notes on sacks splitting theorem, in preparation.

Ambos-Spies,

Jockusch,

Shore and

Soare, An algebraic decomposition of recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. Soc.281 (1984), 109–128. doi:10.1090/S0002-9947-1984-0719661-8.

Bickford and

C.F.

Mills, Lowness properties of r.e. sets, unpublished.

Chih, Non-splitting of recursively enumerable sets, J. Symb. Logic80 (2015), 609–635. doi:10.1017/jsl.2014.83.

Downey and

Greenberg, A hierarchy of low computably enumerable degrees, unifying classes and natural definability, 172 pp., Submitted.

Downey,

Jockush and

P.E.

Schupp, Asymptotic density and computably enumerable sets, Journal of Mathematical Logic13 (2013), 43 pages. doi:10.1142/S0219061313500050.

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, 2010.

R.G.

Downey and

K.M.

Ng, Splitting into degrees with low computational strength, Annals of Pure and Applied Logic, accepted.

10.

R.G.

Downey and

Shore, Splitting theorems and the jump operator, Annals Pure and Applied Logic94 (1998), 45–52. doi:10.1016/S0168-0072(97)00066-3.

11.

R.G.

Downey and

T.A.

Slaman, Completely mitotic r.e. degrees, Ann. Pure Appl. Logic41 (1989), 119–152. doi:10.1016/0168-0072(89)90011-0.

12.

R.G.

Downey and

Stob, Splitting theorems in recursion theory, Ann. Pure Appl. Logic65 (1993), 1–106. doi:10.1016/0168-0072(93)90234-5.

13.

Friedberg, Three theorems on recursive enumeration, J. Symbolic Logic23 (1958), 308–316.

14.

Griffiths, Completely mitotic c.e. degrees and non-jump inversion, Annals of Pure and Applied Logic132 (2005), 181–207. doi:10.1016/j.apal.2004.06.008.

15.

Ingrassia and

Lempp, Jumps of nontrivial splittings of r.e. sets, Z math. Logic. Grundlagen Math.36 (1990), 285–292. doi:10.1002/malq.19900360403.

16.

Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic38 (1973), 199–211. doi:10.2307/2272056.

17.

Ladner, A completely mitotic nonrecursive recursively enumerable degree, Trans. Amer. Math. Soc.184 (1973), 479–507. doi:10.1090/S0002-9947-1973-0398805-7.

18.

G.E.

Sacks, On the degrees less than

0^{'}

, Ann. Math. (2)77 (1963), 211–231. doi:10.2307/1970214.

19.

R.I.

Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, New York, 1987.