Splitting and jump inversion in the Turing degrees

Abstract

It is shown that for any computably enumerable degree $a \neq 0$ , and any Turing degree $s$ , if $s ⩾ 0^{'}$ , and c.e. in $a$ , then there exists a c.e. degree x with the following properties: $x < a$ , $a$ is splittable over $x$ , and $x^{'} = s$ .

Keywords

Turing degrees jump inversion splitting computably enumerable degree

1. Introduction

The Sacks’ splitting theorem [5] and the Jump theorem [6] are fundamental and have wide applications in computability theory. The difficulty of splitting the computably enumerable (c.e.) Turing degrees is due to a very strong non-extension of the non-splitting feature (see for instance, Cooper and Li [1]). Intuitively speaking, the splitting construction is incompatible with infinite injury argument. However the Sacks Jump theorem is nevertheless an infinite injury proposition. A deeper understanding of the structural theory of the Turing degrees calls for further examination of some subtle relationships between the basis notions and the fundamental results of the theory. In the present paper, we investigate the relationship between the Sacks Jump theorem and the splitting theorem. We show that

Theorem 1.1.
Let $a \neq 0$ be a c.e. degree, $c \neq 0$ and $s$ be Turing degrees. If $s ⩾ 0^{'}$ and c.e. in $a$ , then there exists a c.e. degree $x$ with the following properties,
$x < a$ ,

$x^{'} = s$ , and

$a$ is splittable above $x$ .

Using Robinson interpolation theorem [3,4], the degree $x$ can be chosen with cone-avoiding $c ≰ x$ for any c.e. degree $c \neq 0$ .

The theorem unifies the Sacks splitting theorem and the Sacks jump theorem simultaneously. The theorem allows refined analysis of the structure of the c.e. Turing degrees, while its proof offers refined techniques of constructions in the classical computability.

The proof of the theorem is an infinite priority tree argument with interesting new features. The new ideas in the proof are:

There is a decreasing sequence of permitting markers of a γ-marker for the Turing functional Γ we build, and

There is a finite injury from nodes to the right of the true path, due to the impossibility of initialization of γ-markers.

Property A was first introduced by Cooper and Li [2]. It is true that one of the crucial new ideas in the resolving of the Lachlan’s major sub-degree problem in Cooper and Li [2] is the introduction of a system of dynamical permitting markers governed by a new minmax principle. Here, we used only a bit of the idea of dynamical permitting markers. We remark that the method of dynamical permitting markers could be a general approach to new theory of computability, if any.

Property B is unusual in priority tree arguments.

The terminology and the notations are standard and generally can be found in Soare [7].
2. The requirements and strategies

In this section, we describe the requirements of the theorem and the strategies for each type of the requirements.

The requirements. Let A be a c.e. set of degree $a$ , and $S = W^{A}$ for some c.e. set W. We construct c.e. sets X, $X_{0}$ , $X_{1}$ , and B, and Turing functionals Γ, and Ω to satisfy the following conditions and requirements,

(1) For all e, y, $Γ (X; e, y) ↓$

(2) For all e, ${lim}_{y} Γ (X; e, y) ↓$

$T$ : $X ⩽ A$ , $X_{0} \cap X_{1} = \emptyset$ , and $X_{0} \cup X_{1} = A$

$N_{2 e}$ : $A \neq Φ_{e} (X_{0}, X)$

$N_{2 e + 1}$ : $A \neq Φ_{e} (X_{1}, X)$

$R_{e}$ : $W^{A} (e) = {lim}_{s} Γ (X; e, y)$

$S_{e}$ : $X^{'} (e) = Ω (B, W^{A}; e)$

where $e \in ω$ , $X^{'} = {e ∣ Φ_{e} (X; e) ↓}$ , ${Φ_{e} ∣ e \in ω}$ is an effective enumeration of all Turing functionals Φ.

It is clear that meeting the requirements is sufficient to prove the theorem.

The $T$ -strategy. To satisfy $X ⩽_{T} A$ , we build a Turing reduction from X to A by the permitting method. We ensure that at any stage $s + 1$ , an element x can be enumerated into X only if there is a natural number $a ⩽ x$ such that $a \in A_{s + 1} ∖ A_{s}$ . From this, we can argue that X is computable in A.

To satisfy $A ⩽_{T} X_{0} \oplus X_{1}$ , we split A into $X_{0}$ and $X_{1}$ such that

If $x \in A$ , then $X_{0} (x) \neq X_{1} (x)$ ,

If $x \notin A$ , then $X_{0} (x) = X_{1} (x) = 0$ .

The key to the $T$ -strategy is to describe the rules for the use function γ of the Turing reduction Γ, see below.

An $N$ -strategy. An $N$ -strategy is the usual Sacks preservation method. Suppose that we want to satisfy the following $N$ -requirement, $N : A \neq Φ (X_{0}, X)$ . We will build a computable partial function f such that if $A = Φ (X_{0}, X)$ , then f is total, and $f = A$ .

f will be built as follows.

Let x be the least y such that $f (y) ↑$ .

If $Φ (X_{0}, X; x) ↓ = A (x)$ , then define $f (x) = A (x)$ , and define the $X_{0}$ -, and X-restraints by $r^{X_{0}} = r^{X} = ϕ (x)$ , respectively.

The $X_{0}$ -, and X-restraints in step 2 above will ensure that for any x, if $f (x)$ is defined, then $f (x) = Φ (X_{0}, X; x)$ , so that if $A (x) = Φ (X_{0}, X; x)$ , then $f (x) = A (x)$ . Therefore if f is built infinitely many times, then f is total, and $f = A$ , so that A is computable. A contradiction.

Suppose that $A ≰_{T} \emptyset$ . Then there is no $N$ -strategy acts infinitely many times. So we use 1 to denote the unique outcome of an $N$ -strategy, which indicates that the strategy acts only finitely many times.

An $R$ -strategy. An $R$ -requirement $R_{e}$ for a fixed e will be arranged to a strategy on every infinite branch of a strategy tree. Therefore, there are many strategies together working for defining the functional Γ at pairs $(e, y)$ for the fixed e and for all y. Consequently, all the $R_{e}$ -strategies will compete to define $Γ (X; e, y)$ for all y such that for each y, $Γ (X; e, y)$ is defined eventually and ${lim}_{s} Γ (X; e, y) ↓ = W^{A} (e)$ .

Suppose that α is an $R_{e}$ -strategy. α will build $λ y Γ (X; e, y)$ as follows.

If $e \in W^{A}$ , then let x be the least y such that $Γ (X; e, y) ↑$ , define $Γ (X; e, x) ↓ = 1$ with $γ (e, x)$ fresh (i.e., the least number greater than any number used so far), locate $γ (e, x)$ at $α \hat{} ⟨ 1 ⟩$ , and define the permitting marker $m (z)$ for $z = γ (e, x)$ to be the least u such that $e \in W^{A ↾ (u + 1)}$ .

The $R$ -strategy α defines $Γ (X; e, y)$ for larger and larger y. Whenever we define a value, we specify the use function and specify a location of the use function. The rectification of Γ can only be done by enumerating the corresponding use function into X. On the other hand, we are allow to enumerate an element x into X only if there is a number $a < x$ that enters A at the same stage. The permitting marker $m (z)$ specifies the controlling condition of the enumeration of the value z into X.

If $γ (e, x) = y$ is located at $α \hat{} ⟨ 1 ⟩$ , and A changes below the permitting marker $m (y)$ for $y = γ (e, x)$ , then enumerate $γ (e, x)$ into X.

This means that whenever there is a change below some permitting marker $m (z)$ for some use function γ value z, the use function value z is enumerated into X. Once the use function $z = γ (e, y)$ is enumerated, $Γ (X; e, y)$ becomes undefined immediately and automatically.

Let $s^{-}$ be the greatest stage $v < s$ at which $α \hat{} ⟨ 0 ⟩$ was visited.

If there is a v such that $s^{-} < v ⩽ s$ at which $e \notin W^{A}$ , then let x be the least y such that $Γ (X; e, y)$ undefined, define $Γ (X; e, x) = 0$ with $γ (e, x)$ fresh, and locate it at $α \hat{} ⟨ 0 ⟩$ .

Before analysing the possible outcomes of the $R$ -strategy, we introduce some rules of $W^{A}$ . We ensure that the enumeration of $W^{A}$ will have the following properties:

$e \in W^{A}$ if and only if there is a $σ \subset A$ such that $⟨ e, σ ⟩ \in W$ .

A will be enumerated at odd stages.

At each odd stage s, there is exactly one element which is enumerated into A.

By (i)–(iii), we have that $e \notin W^{A}$ if and only if there are infinitely many s such that $e \notin W^{A} [s]$ .

We define the possible outcomes of an $R_{e}$ -strategy by $0 <_{T} 1$ , where 0 means that $e \notin W^{A}$ , and 1 means that $e \in W^{A}$ .

Suppose that $e \in W^{A}$ , we use $w (e)$ to denote the least u such that $e \in W^{A ↾ (u + 1)}$ . We call $w (e)$ the use of $e \in W^{A}$ .

The permitting marker. Let $γ (e, y) = x$ be a γ-marker and ξ be a node.

If $ξ = α \hat{} ⟨ 1 ⟩$ for some $R_{e}$ -strategy α for some e, then we define the permitting marker of ξ by $p (ξ)$ to be the use $w (e)$ .

If $x = γ (e, y)$ is located at ξ, then we define the permitting marker $m (x) = max {p (β) ∣ β ⩽ ξ}$ .

The enumeration of X. Let $x = γ (e, y) [v]$ for some e, y, and v. Then x is enumerated into X at stage $s + 1$ if and only if both (i) and (ii) below hold,

$x > R (x) = max {r^{X} (β) ∣ β ⩽ loc (x)}$ , where $loc (x)$ is the location of x, and

There is a natural number $a ⩽ m (x)$ such that $a \in A_{s + 1} ∖ A_{s}$ .

An $S$ -strategy. Given an $S$ -requirement, $S_{e}$ , say, we may introduce several $S_{e}$ -strategies. All $S_{e}$ -strategies will compete to define $Ω (B, W^{A}; e)$ . Suppose that β is an $S_{e}$ -strategy. Then β will proceed as follows.

Let $s^{-}$ be the greatest stage at which some $(b, β, e, 1)$ was enumerated into Ω, if any, and there is a stage v such that $s^{-} < v ⩽ s$ such that $Φ_{e} (X; e) ↑$ . Then if there is an axiom $(b, β, e, 1) \in Ω$ such that $b \notin B$ , then enumerate all these b into B; and if there is no axiom $(b, β, e, 0) \in Ω$ for any $b \notin B$ , then let b be a fresh number, and enumerate $(b, β, e, 0)$ into Ω.

Otherwise, then if there is an axiom $(b, β, e, 0) \in Ω$ , then enumerate b into B; if there is no $b \notin B$ such that $(b, β, e, 1) \in Ω$ , then let b be fresh, and enumerate $(b, β, e, 1)$ into Ω; and define the X-restraint by $r^{X} (β) = ϕ_{e} (e)$ .

The X-restraint $r^{X} (β)$ can be injured only finitely many times by the γ-markers that are located at nodes $< β$ .

The unique outcome of β is 1.

3. Interactions of strategies

The injury of an $N$ -, or an $S$ -strategy from an $R$ -strategy. Suppose that β is an $N$ -, or an $S$ -strategy. β will impose an X-restraint $r^{X} (β)$ . However β can be injured by $R$ -strategies $α ⩽ β$ only finitely many times. We consider two cases. If $α \hat{} ⟨ 1 ⟩ \subseteq β$ , then α injures β only finitely many times. If $α \hat{} ⟨ 0 ⟩ \subseteq β$ , then at the stages at which β is visited, there is no γ-marker x such that x is located at a node to the right of $α \hat{} ⟨ 0 ⟩$ which can be enumerated into X. The idea is that at the stage at which A changed below the $W^{A}$ -use of α, every $γ (e, y) = x > w^{A} (α)$ , if $x > max {r^{X} (ξ) ∣ ξ < α}$ has been enumerated into X. In this case, we say that the $R$ -strategy α receives attention.

This idea is crucial for the consistency of Γ. We look at the following situation. Suppose that $α_{1} <_{L} α_{2}$ are two $R_{e}$ -strategies. If $α_{1}$ is on the true path, we must make sure that there are only finitely many $γ (e, y)$ markers which are located at $α_{2} \hat{} ⟨ i ⟩$ for any $i ⩽ 1$ permanently. This ensures that for almost every y, $Γ (X; e, y)$ will be defined by the $R_{e}$ -strategy on the true path and are located at the true path.

Updating the location of a γ-marker. Since any enumeration of a γ-marker into X must respect some X-restraints. An $N$ - or an $S$ -strategy may update the location of γ-markers as follows.

If an $N$ -, or an $S$ -strategy β increases its X-restraint, then for any $x = γ (e, y)$ , if $loc (x) \supset β$ , then re-locate it at β, by defining $loc (x) = β \hat{} ⟨ 1 ⟩$ .

This is a simple system of dynamical permitting markers, which is crucial for the construction of Γ. (The full methodology of dynamical permitting markers was proposed by Cooper and Li [2].)

To better understand the interactions among the strategies, we consider the following typical cases.

Case 1. $(R_{0}, R_{1})$ .

Now we want to satisfy two $R$ -requirements $R_{0}$ and $R_{1}$ simultaneously. We use $α_{0}$ and $α_{1}$ to denote an $R_{0}$ - and an $R_{1}$ -strategy, respectively. According to the $R$ -strategy, $α_{0}$ will try to define $Γ (X; 0, y)$ for all y, and $α_{1}$ tries to define $Γ (X; 1, y)$ for all y. There are two subcases.

Subcase 1a. $α_{0} \hat{} ⟨ 1 ⟩ \subseteq α_{1}$ .

In this case, whenever $α_{1}$ acts at a stage s, $α_{0}$ is visited, and at the same stage, we observed that $0 \in W^{A} [s]$ with an use $w^{A} (0) [s]$ . Therefore, when $α_{1}$ defines $Γ (X; 1, y)$ at stage s, we define the use $x = γ (1, y) [s]$ to be fresh, and in this case, the permitting marker of x must be $⩾ w^{A} (0) [s]$ .

Our construction ensures that if there is a stage $v > s$ at which A changes below $w^{A} (0) [s]$ , then we know that $α_{0} \hat{} ⟨ 0 ⟩$ will be visited at some stage $u > v$ , once $α_{0}$ is visited. This means that the definition of $Γ (X; 1, y) [s]$ was found to be wrong at stage v, therefore, the $γ (1, y) [s]$ defined by $α_{1}$ at stage s is enumerated into X at stage v, which invalidates the actions done by $α_{1}$ at stage s.

Subcase 1b. $α_{0} \hat{} ⟨ 0 ⟩ \subseteq α_{1}$ .

By the arguments in Subcase 1a, whenever $α_{1}$ is visited at stage s, we know that the wrong definitions of $Γ (X; 1, y)$ done by some strategies α with $α_{0} \hat{} ⟨ 1 ⟩ \subseteq α$ have already been invalidated before stage s. Therefore the current strategy $α_{1}$ is responsible for defining its own functional $Γ (X; 1, y)$ . Of course, $α_{1}$ respects the values $Γ (X; 1, y)$ defined by the $R_{1}$ -strategies to the left of $α_{1}$ , if any.

The arguments above ensure that if α is the correct $R_{e}$ -strategy, i.e., the one on the true path, then for almost all y, $Γ (X; e, y)$ are eventually defined by α.

Case 2. $(R, N)$ .

Suppose that α and β are an $R$ - and an $N$ -strategy, respectively. Note that α is responsible for defining and rectifying its $Γ (X; e, y)$ for some e and y. β may restrain $X_{i}$ - and X-restraints. We consider two subcases.

Subcase 2a. $α \hat{} ⟨ 1 ⟩ \subseteq β$ .

In this subcase, β believes that $e \in W^{A}$ with a bounded use $w^{A} (e)$ , where e is the index of α. Therefore, there are finitely many markers of the form $x = γ (e, y)$ that can be enumerated into X, meaning that α injures β only finitely many times. β works for its own requirement after A is fixed below $w^{A} (e)$ , a bounded number. $N$ is satisfied.

Subcase 2b. $α \hat{} ⟨ 0 ⟩ \subseteq β$ .

The key to β is that at the stage s at which β is visited, all the γ-markers defined by the strategies $α^{'}$ with $α \hat{} ⟨ 1 ⟩ \subseteq α^{'}$ have already been proven wrong and invalidated. This property holds by the argument in Case 1 above.

Therefore, almost all the γ-markers defined by the $R$ -strategies to the right of β cannot injure β. In addition, α will not cause the enumeration of γ-markers in X. This ensures that the X-restraint imposed by β can be injured only finitely many times by the collection of the γ-markers located at the strategies $α^{'}$ not to the left of β.

Case 3. $(R, S)$ .

This is the same as that in Case 2.

The splitting strategies enumerate $X_{0}$ and $X_{1}$ as that in the Sacks splitting.

The arguments will help to understand the construction and proofs of the theorem.

A reader may notice that the argument in Case 1 is actually the key. Because it shows that the wrong γ-markers have already been cancelled before a true strategy works. This property guarantees that the injuries come from the right of the true path are finite.

4. The construction

First we introduce some notations which will be useful in the description of the construction and the verification.

Definition 4.1.

Define the priority ranking of the requirements by $\begin{matrix} N_{0} < R_{0} < S_{0} < N_{1} < R_{1} < S_{1} < \dots . \end{matrix}$

Define the possible outcomes of an $R$ -strategy by $0 <_{L} 1$ .

Define the unique outcome of an $N$ -, or an $S$ -strategy to be 1.

Definition 4.2.
We arrange the requirements on nodes of a tree, the priority tree T, by the priority ranking of the requirements, such that at each level there is only one requirement to be arranged, while each node has immediate successors to be the possible outcomes of the corresponding strategy.
Definition 4.3.

We assume that A is enumerated at odd stages, and that at each odd stage, there is a unique element which is enumerated into A.

The tree construction will be implemented at even stages.

Let α be an $R_{e}$ -strategy for some e. We use $w (α)$ to denote the current use $w^{A} (e)$ , if $e \in W^{A}$ .
Definition 4.4.
Let α be an $R$ -strategy, s be an odd stage, and a be the element which is enumerated into A at stage s. We say that α requires attention at stage s, if $w (α) ↓ > a$ holds at the beginning of stage s.

During the course of the construction, a strategy may be initialized. We interpret the action of initialization as follows.

If an $N$ -strategy β is initialized, then $f_{β}$ is set to be totally undefined, and all restraints of β are cancelled.

If an $S$ -strategy β is initialized, then for any axiom $(b, β, e, i) \in Ω$ , if $b \notin B$ , then b is enumerated into B.

Now we are ready to describe the construction.
Definition 4.5.
The construction will proceed stage by stage as follows.
Stage $s = 0$ .
Set $X_{0} = X_{1} = X = \emptyset$ , and initialize all strategies.
Stage $s = 2 n + 1$ .
Let a be the number enumerated into A at stage s. There are two phases.
Phase I ( $R$ -Strategies receiving attention).

Suppose that $α_{1} \subset α_{2} \subset \dots \subset α_{m}$ are all <-minimal $R$ -strategies which require attention at stage s. Let $δ_{s} = α_{m}$ . In decreasing order, for all $j = m, \dots, 1$ , execute the following:

Let $r_{j} = max {r^{X} (β) ∣ β < α_{j}}$ .

For any γ-marker $γ (e, y) = x$ , let $ξ = loc (x)$ , if:

$ξ \supseteq α_{j} \hat{} ⟨ 1 ⟩$ or ξ is to the right of $δ_{s}$ ,

$a < m (x)$ , and

$x > r_{j}$ ,

then enumerate x into X.

[Remark. (1) This action ensures that for any $y^{'} ⩾ y$ , $Γ (X; e, y^{'})$ becomes undefined automatically. Because for $y^{'} > y$ , the current $Γ (X; e, y^{'})$ must be defined after the current $Γ (X; e, y)$ . (2) If a γ-marker $γ (e, y) = x$ with $loc (x) \supseteq α_{j} \hat{} ⟨ 0 ⟩$ , the current definition $Γ (X; e, y)$ is still correct, so there is no need to rectify the computation, although a permission occurred. This is also important, because, otherwise, we may define $Γ (X; e, y)$ for a fixed y infinitely many times, which is wrong.]

For any $N$ - or $S$ -strategy β, if $α_{j} \hat{} ⟨ 0 ⟩ <_{L} β$ , then β is initialized.

Phase II (Splitting of A).

Let β be the <-least $N$ -strategy ξ such that $r^{X_{i}} (ξ) ⩾ a$ , where $i = j$ ( $mod 2$ ), and j is the index of ξ.

If β is defined, then let $i = j + 1$ ( $mod 2$ ) for the index j of β, and enumerate a into $X_{i}$ .

Otherwise, then enumerate a into $X_{0}$ .

Stage $s = 2 n + 2$ .
We allow some strategies to act at substages $t < s$ . At each substage t, we let some strategy act, and then either close the current stage or specify some lower priority strategy to act at the next substage. Initially we allow the root node λ to act at substage $t = 0$ .
Substage $t$ .
Let ξ be the strategy which is eligible to act at substage t. If $t = s$ , then all nodes $ξ^{'}$ to the right of ξ is initialized, and close the current stage. If $t < s$ , then there are 3 cases.

Case 1. $ξ = β$ is an $N_{j}$ -strategy for some j. Suppose without loss of generality that $j = 2 e$ for some e. We build $f_{β}$ as follows.

Let x be the least y such that $f_{β} (y) ↑$ .

If $Φ_{e} (X_{0}, X; x) ↓ = A (x)$ , then

define $f_{β} (x) = Φ_{e} (X_{0}, X; x)$ , define the $X_{0}$ , and X-restraints by $r^{X_{0}} (β) = max {old r^{X_{0}} (β), ϕ_{e} (x)}$ , and define $r^{X} (β) = max {old r^{X} (β), ϕ_{e} (x)}$ ,

for any γ-marker $y = γ (e^{'}, z^{'})$ , if y is located at some node $ξ^{'} \supset β$ , then relocate it at $β \hat{} ⟨ 1 ⟩$ , that is, redefine $loc (y) = β$ ,

initialize all nodes $ξ^{'}$ with $ξ < ξ^{'}$ , and go to stage $s + 1$ .

Otherwise, then let $β \hat{} ⟨ 1 ⟩$ be eligible to act at substage $t + 1$ of stage s.

[Remark. In this case, β acts, therefore all the γ markers defined by the strategies ξ with $β < ξ$ are probably injured. The relocation of the γ-markers redefines the permitting markers of the γ-markers to be smaller numbers. This allows us to rectify the Γ-computations in case needed.]

Case 2. $ξ = α$ is an $R_{e}$ -strategy for some e. We run the following

Program α

Let $s^{-}$ be the greatest stage $v < s$ at which $α \hat{} ⟨ 0 ⟩$ was visited.

If there is a stage v such that $s^{-} < v ⩽ s$ and $e \notin W^{A} [v]$ , then:

let x be the least y such that $Γ (X; e, y)$ is not defined,

define $Γ (X; e, x) ↓ = 0$ with $γ (e, x)$ fresh,

locate the $γ (e, x)$ at $α \hat{} ⟨ 0 ⟩$ , and

let $α \hat{} ⟨ 0 ⟩$ be eligible to act at the next substage.

Otherwise, then:

let x be the least y such that $Γ (X; e, y)$ is not defined,

define $Γ (X; e, x) ↓ = 1$ with $γ (e, x)$ fresh,

locate $γ (e, x)$ at $α \hat{} ⟨ 1 ⟩$ ,

define $p (α) = w (e)$ to be the permitting marker of x, and

let $α \hat{} ⟨ 1 ⟩$ be eligible to act next.

Note that for any $x = γ (e, y)$ , if x is located at ξ, then the permitting marker of x is defined as $\begin{matrix} (1) & m (x) = max {p (α) ∣ α < ξ} . \end{matrix}$

This means that if A changes below $m (x)$ , x is qualified to be enumerated into X.

Case 3. $ξ = β$ is an $S_{e}$ -strategy for some e. Then implement the following

Program β

If there is an axiom $(b, β, e, 0) \in Ω$ such that $b \notin B$ and $Φ_{e} (X; e) ↓$ , then for any axiom $(b, β, e, 0) \in Ω$ , if $b \notin B$ , then enumerate b into B, let b be a fresh number, enumerate $(b, β, e, 1)$ into Ω, define the X-restraint by $r^{X} (β) = ϕ_{e} (X; e)$ , every γ-marker $x = γ (e^{'}, y)$ located at nodes at some $ξ > β$ is re-located at $β \hat{} ⟨ 1 ⟩$ , initialize all nodes $ξ^{'}$ with $β < ξ^{'}$ , and go to stage $s + 1$ .

If there is no axiom $(b, β, e, 0) \in Ω$ , and $Φ_{e} (X; e) ↑$ , then for any axiom $(b, β, e, 1) \in Ω$ , if $b \notin B$ , then enumerate b into B; let b be fresh, and enumerate $(b, β, e, 0)$ into Ω; for any γ-marker $γ (e^{'}, y) = x$ , if x is located at a node below β, then re-locate it at $β \hat{} ⟨ 1 ⟩$ ; initialize all nodes $ξ^{'}$ with $β < ξ^{'}$ , and go to stage $s + 1$ .

Otherwise, then let $β \hat{} ⟨ 1 ⟩$ be eligible to act at the next substage.

This completes the description of the construction.
5. The verification

The verification of the construction consists of the following propositions.

Proposition 5.1.
$X ⩽_{T} A$ .
Proof.
A number x can be enumerated into X, only if x is defined to be $γ (e, y)$ at some stage v for some e, y, and v.

For any $s ⩾ v$ , if $x \notin X [s]$ , then the permitting marker $m (x)$ is the maximum of $w (α)$ over all $R$ -strategies $α \subset loc (x)$ .

Let $C (x) [s]$ be the set of all $R$ -strategies $\subset loc (x)$ during stage s. By the construction, we have that $\begin{matrix} (2) & C (x) [v] \supseteq C (x) [v + 1] \supseteq C (x) [s] . \end{matrix}$ We prove that for any $s > v$ , $\begin{matrix} (3) & m (x) [s] = max {w (α) [v] ∣ α \in C (x) [s]} . \end{matrix}$ Towards a contradiction, assume that s is the least stage $> v$ at which A changes below $m (x) [v]$ . Let α be the longest $R$ -strategy which requires attention at stage s. By the choice of s, $loc (x) \supset α$ . Therefore there is no $N$ -, or $S$ -strategy $β \subset α$ which has increased its X-restraint (otherwise, the location of x at stage s is above α). Therefore, the maximum X-restraints by strategies $\subset α$ at stage s is no more than that observed at stage v. Since x is chosen to be fresh at stage v, x is not restrained from entering X at stage s. (2) follows.

By combining (1) and (2), the permitting marker $m (x)$ is decreasing (precisely non-increasing) before it is enumerated into X.

On the other hand, at the stage s at which x is enumerated into X, there is an $a ⩽ m (x)$ which enters A.

The direct permitting method ensures that X is computable in A. Proposition 5.1 follows. □
Proposition 5.2.
$X_{0} \cap X_{1} = \emptyset$ , and $X_{0} \cup X_{1} = A$ .
Proof.
By the construction. □
Definition 5.1.

Let $δ_{s}$ be the longest strategy which is visited at an even stage s.

Define the true path $TP$ of the construction by $\begin{matrix} (4) & TP = \underset{s = 2 n}{lim inf} δ_{s} . \end{matrix}$

We examine the existence of the true path $TP$ .
Proposition 5.3.
Let $A ≰_{T} \emptyset$ . For any $α \in TP$ , there is an outcome o such that:
$α \hat{} ⟨ o ⟩$ is initialized only finitely many times.

$α \hat{} ⟨ o ⟩ \in TP$ is visited infinitely many times.

Proof.
This is straightforward from the construction. □
Proposition 5.4 (The true path properties proposition).

Let $A ≰_{T} \emptyset$ . Given $ξ \in TP$ :

If $ξ = β$ is an $N_{j}$ -strategy for some j, then

if $f_{β}$ is built infinitely many times, then $f_{β}$ is total, and $f_{β} =^{*} A$ .

If $ξ = α$ is an $R_{e}$ -strategy for some e, then:

For all y, $Γ (X; e, y)$ is defined eventually and permanently.

${lim}_{y} Γ (X; e, y) ↓ = W^{A} (e)$ .

If $ξ = δ$ is an $S_{e}$ -strategy for some e, then:

If there is an axiom $(b, β, e, i) \in Ω$ for some $b \notin B$ and some i, then there is no axiom $(b^{'}, β, e, 1 - i) \in Ω$ for any $b^{'} \notin B$ .

There is a fixed quadruple $(b, β, e, i)$ such that it is kept in Ω permanently for some $b \notin B$ and some i.

$X^{'} (e) = i$ if and only if there is an axiom $(b, β, e, i) \in Ω$ for some $b \notin B$ .

Proof.

Suppose by induction that the proposition holds for all $ξ^{'} \subset ξ$ . Let $s_{0}$ be minimal such that for any $s > s_{0}$ .

If $ξ^{'} \subset ξ$ is an $N$ - or an $S$ -strategy, then $ξ^{'}$ does not act at stage s.

ξ will not be initialized at stage s.

If $α \subset α \hat{} ⟨ 1 ⟩ \subseteq ξ$ is an $R_{e}$ -strategy for some e, then $e \in W^{A} [s]$ .

We prove the proposition for ξ by considering the following cases.

Case 1. $ξ = β$ is an $N_{j}$ -strategy for some j.

Suppose without loss of generality that $j = 2 e$ for some e. By induction we can choose a minimal stage $s_{1} > s_{0}$ with the following properties:

For each $i ⩽ 1$ , the maximum $X_{i}$ -restraints which are imposed by strategies $ξ^{'} < β$ has reached to its limit by stage $s_{1}$ , we use r to denote the limit of this maximum restraints.

A will never change below r after stage $s_{1}$ .

The maximum of the X-restraints imposed by strategies $< β$ has reached to its limit by stage $s_{1}$ . We use $r^{X}$ to denote this limit.

Suppose that $α_{1} \subset α_{2} \subset \dots \subset α_{m}$ are all $R$ -strategies α with $α \hat{} ⟨ 0 ⟩ \subset β$ .

Let $s > s_{1}$ be a stage at which β is visited. We prove that

(∗) For any j, any γ-marker $x = γ (e^{'}, y^{'})$ , if $loc (x) [s] \supseteq α_{j} \hat{} ⟨ 1 ⟩$ , and $x > r^{X}$ , then x is in X during stage s (before β is visited at stage s).

Suppose that a γ-marker $x = γ (e^{'}, y^{'})$ was created and located at a node $\supseteq α_{j} \hat{} ⟨ 1 ⟩$ at a stage $v < s$ ( $s_{1} < v$ ). Then $α_{j} \hat{} ⟨ 1 ⟩$ was visited at stage v, so that the permitting marker of the γ-marker x is greater than the use of $w (α_{j}) [v]$ . Since β is visited at stage s. There is a stage $s^{'}$ such that $v < s^{'} < s$ at which A changes below $w (α_{j}) [v]$ . Let $s^{″}$ be the least such $s^{'}$ . Then x has been enumerated into X at stage $s^{″}$ . This argument applies to all j. (∗) is established.

Let $s_{2} > s_{1}$ be minimal after which there is no γ-marker located at any node $\supseteq α_{j} \hat{} ⟨ 1 ⟩$ for any j, which can be enumerated into X.

By (∗) and by the choice of $s_{2}$ , the X-restraint of β after stage $s_{2}$ , will not be injured by any strategy $ξ^{'}$ with $β ⊈ ξ^{'}$ .

Given an x, if $f_{β} (x)$ is created at a stage $s > s_{2}$ , then the X-restraint $r^{X} (β) [s]$ ensures that $Φ_{e} (X_{0}, X; x) [s] ↓$ will be X-correct at any stage $s^{'} ⩾ s$ . On the other hand, by the choice of $s_{1}$ , $s_{2}$ , the $X_{0}$ -restraint $r^{X_{0}} (β) [s]$ will never be injured by the splitting of A at odd stages $s^{'} > s$ . Therefore, $f_{β} (x) = Φ_{e} (X_{0}, X; x) [s]$ will be preserved forever.

So if $f_{β}$ is built infinitely many times, then $f_{β}$ is total, and $f_{β} =^{*} A$ .

By the assumption that $A ≰_{T} \emptyset$ , $f_{β}$ is built only finitely many times, and then the length function $l (A, Φ_{e} (X_{0}, X)) [s]$ will be bounded during the course of the construction.

$N_{2 e}$ is satisfied. (i) follows.

Case 2. $ξ = α$ is an $R_{e}$ -strategy for some e.

Suppose that α is an $R_{e}$ -strategy on the true path $TP$ . First we prove that

( $* *$ ) There are only finitely many y such that $Γ (X; e, y)$ is defined permanently by $R_{e}$ -strategies $α^{'} \neq α$ .

Since α is on the true path, there are only finitely many stages at which some $R_{e}$ -strategies $α^{'} <_{T} α$ which are visited. We consider only an $R_{e}$ -strategy $α^{'}$ to the right of α. By the construction of the tree, there is an $R$ -strategy $α_{0}$ such that $α_{0} \hat{} ⟨ 0 ⟩ \subseteq α$ , and $α_{0} \hat{} ⟨ 1 ⟩ \subseteq α^{'}$ . By induction, we can choose $r_{0}$ to be the limit of maximum of all X-restraints imposed by nodes $< α_{0}$ .

By the construction at odd stages, every γ-marker defined by $α^{'}$ , which is greater than $r_{0}$ will be eventually enumerated into X before α is visited next time.

Therefore there are only finitely many γ-markers defined by strategies to the right of α which will be kept out of X permanently.

( $* *$ ) is established.

By ( $* *$ ), for almost every y, $Γ (X; e, y)$ will be eventually defined by α.

By observing α, we have that

for every y, $Γ (X; e, y)$ is eventually defined, and

${lim}_{y} Γ (X; e, y) ↓ = W^{A} (e)$ .

Case 3. $ξ = δ$ is an $S_{e}$ -strategy for some e.

By the proof in Case 1, the X-restraint $r^{X} (δ)$ will ensure that there are only finitely many axioms of the form $(b, δ, e, i)$ which are enumerated into Ω.

By observing δ, it is easy to see that

If there is an axiom $(b, δ, e, i) \in Ω$ with $b \notin B$ , then there is no axiom $(b^{'}, δ, e, 1 - i) \in Ω$ for any $b^{'} \notin B$ .

$X^{'} (e) = i$ if and only if there is an axiom $(b, δ, e, i) \in Ω$ such that $b \notin B$ .

(iii) holds.

This completes the inductive proof of the proposition. □

Proposition 5.5.

$TP ⩽_{T} W^{A}$ .

Proof.

The only non-trivial case is that for an $R_{e}$ -strategy $α \in TP$ . By definition of the tree, $α \hat{} ⟨ W^{A} (e) ⟩ \in TP$ . The proposition follows. □

Proposition 5.6.

If $A ≰_{T} \emptyset$ , then all $N$ - and $R$ -requirements are satisfied.

Proof.

This follows from Proposition 5.4. □

Proposition 5.7.

All $S_{e}$ are satisfied unless A is computable.

Proof.

Given e, by Proposition 5.4, $X^{'} (e) = i$ if and only if there is an axiom $(b, δ, e, i) \in Ω$ such that $b \notin B$ , and $δ \in TP$ .

Therefore, $X^{'} ⩽_{T} B \oplus TP ⩽_{T} B \oplus W^{A} ⩽_{T} S$ . All $S$ -requirements are satisfied.

The proposition follows. □

This completes the proof of the theorem.

Footnotes

Acknowledgements

The first author is partially supported by the EPSRC grant No. GR/S28730/01. The second author is partially supported by NSFC grant No. 60325206. The first two authors are partially supported by the Royal Society Joint Project between China and UK. All three authors are partially supported by NSFC Grand International Joint Project, New Directions in Theory and Application of Models of Computation, grant No. 60310213 (China). The proofs in this paper were given in 2005, when the first author was visiting Beijing.

References

S.B.

Cooper and

Li, Splitting and nonsplitting, II: A

{low}_{2}

c.e. degree above which

0^{'}

is not splittable, The Journal of S. Logic67(4) (2002), 1391–1430. doi:10.2178/jsl/1190150292.

S.B.

Cooper and

Li, On Lachlan’s major sub-degree problem, Arch. Math. Log.47(4) (2008), 341–434. doi:10.1007/s00153-008-0083-5.

R.W.

Robinson, Interpolation and embedding in the recursively enumerable degrees, Annals of Mathematics93(2) (1971), 285–314. doi:10.2307/1970776.

R.W.

Robinson, Jump restricted interpolation in the recursively enumerable degrees, Annals of Mathematics93(2) (1971), 586–596. doi:10.2307/1970889.

G.E.

Sacks, On the degrees less than

0^{'}

, Annals of Mathematics77(2) (1963), 211–231. doi:10.2307/1970214.

G.E.

Sacks, Recursive enumerability and the jump operator, Tran. Amer. Math. Soc.108 (1963), 223–239. doi:10.1090/S0002-9947-1963-0155747-3.

R.I.

Soare, Recursively Enumerable Sets and Degrees, Springer, 1987.