3.1 Requirements and strategies

We enumerate a uniform sequence of c.e. sets $\langle C_{e}: e\in \mathbb {N}\rangle $ such that the following requirements are satisfied.

1. (1) $\mathcal {P}_{\langle e, i\rangle }$ : $C_{e}\neq \varphi _{i}$ .

2. (2) $\mathcal {R}_{\langle e, i, i+j\rangle }$ : If $[i,i+j+1]\subseteq W^{K}_{e}$ and $(\exists ^{\infty } s) [\Phi ^{C_{e}}_{j}(j)[s]\downarrow ]$ , then $\Phi ^{C_{e}}_{j}(j)\downarrow $ .

   If $[i, i+j+1]\nsubseteq W^{K}_{e}$ and $\varphi ^{2}_{i}$ is a computable predecessor approximation function, then $C_{e}\neq O_{i}=\{\lim _{s}\varphi ^{2}_{i}(2m, s): m\in \mathbb {N}\}$ .

Here, $\langle \varphi _{i}: i\in \mathbb {N}\rangle $ , $\langle \varphi ^{2}_{i}: i\in \mathbb {N}\rangle $ and $\langle \Phi _{j}: j\in \mathbb {N}\rangle $ are effective listing of partial computable functions, partial computable binary functions and oracle Turing functionals, respectively.

For each e, all $\mathcal {P}_{\langle e, i\rangle }$ -requirements with $i\in \mathbb {N}$ together ensure the noncomputability of $C_{e}$ . For $e\in \mathrm {Cof}^{K}$ , $W^{K}_{e}$ is cofinite; that is, there is a number i such that $[i, \infty )\subseteq W^{K}_{e}$ . In this case, for all j, $[i, i+j+1] \subseteq W^{K}_{e}$ , and the requirement $\mathcal {R}_{\langle e, i,j\rangle }$ ensures that the computation $\Phi ^{C_{e}}_{j}(j)$ converges if and only if there are infinitely many stages s such that $\Phi ^{C_{e}}_{j}(j)$ converges at stage s. This implies that $C^{\prime }_{e}=\{j\in \mathbb {N}: \Phi ^{C_{e}}_{j}(j)\downarrow \}$ is $\Delta ^{0}_{2}$ and thus $C^{\prime }_{e}\leq _{T}\emptyset '$ , i.e., $C_{e}$ is low. As low c.e. sets are order-computable, $C_{e}$ is order-computable. On the other hand, for $e\notin \mathrm {Cof}^{K}$ , $W^{K}_{e}$ is not cofinite. Then for all $i\in \mathbb {N}$ , there exists a number $j_{i}$ such that $[i, i+j_{i}+1] \nsubseteq W^{K}_{e}$ , and the requirement $\mathcal {R}_{\langle e, i, j_{i}\rangle }$ ensures that $C_{e}$ is not order-computed by $\varphi ^{2}_{i}$ . So $C_{e}$ is not order-computable.

The construction of c.e. sets $ \langle C_{e}: e\in \mathbb {N}\rangle $ proceeds on a priority tree T whose nodes are assigned $\mathcal {P}$ - and $\mathcal {R}$ -requirements. We view each node $\alpha $ as a strategy for satisfying the assigned requirement whose possible outcomes are immediate successors of $\alpha $ on T. A $\mathcal {P}$ -strategy has two possible outcomes $d, f$ with priority $d<_{L}f$ on the priority tree T. While an $\mathcal {R}$ -strategy has three possible outcomes $\infty , d, f$ with priority $\infty <_{L}d<_{L}f$ on T. We assign $\mathcal {P}$ -requirements to nodes of length even and assign $\mathcal {R}$ -requirements to nodes of length odd. So the priority tree T is simply a subtree of the full tree $S=\{\infty , d, f\}^{<\omega }$ of finite strings on $\{\infty , d, f\}$ , where S has the usual lexicographic order such that $\alpha ^{\smallfrown }\infty <_{L}\alpha ^{\smallfrown }d<_{L}\alpha ^{\smallfrown }f$ for any $\alpha \in S$ .

At each stage s of the construction, we will define a current approximation $\delta _{s}\in T$ of the true path $\mathrm {TP}=\liminf _{s}\delta _{s}$ of the construction. $\mathrm {TP}$ will be an infinite path on the priority tree T. For any node $\alpha \in T$ , when $\alpha \subseteq \delta _{s}$ , say that $\alpha $ is visited at stage s, and call s an $\alpha $ -stage.

For ease of description, we often write the $\mathcal {P}_{\langle e, i\rangle }$ -requirement assigned to a node $\alpha \in T$ as $\mathcal {P}_{\langle e(\alpha ), i(\alpha )\rangle }$ (or simply $\mathcal {P}_{\alpha }$ ) with $e(\alpha )=e$ and $i(\alpha )=i$ . Similarly, we write the $\mathcal {R}_{\langle e, i, j\rangle }$ -requirement assigned to a node $\beta \in T$ as $\mathcal {R}_{\langle e(\beta ), i(\beta ), j(\beta )\rangle }$ (or simply $\mathcal {R}_{\beta }$ ) with $e(\beta )=e$ , $i(\beta )=i$ and $j(\beta )=j$ . In the following, we first give a basic $\mathcal {P}$ - and $\mathcal {R}$ -strategy for satisfying a single $\mathcal {P}$ - and $\mathcal {R}$ -requirement, respectively, and then define the assignment of the requirements to the priority tree T.

A basic $\mathcal {P}_{\langle e, i\rangle }$ -strategy. Let $\alpha $ be a node of length even on the priority tree T assigned the $\mathcal {P}_{\langle e,i\rangle }$ -requirement. A basic $\alpha $ -strategy works to diagonalize against $C_{e}=\varphi _{i}$ at $\alpha $ -stages.

1. (1) At the first $\alpha $ -stage s, choose a new witness $w_{\alpha ,s}$ and a set of fresh trigger elements $ \{x^{k}_{\alpha ,s}: 1\leq k\leq q_{\alpha }=2^{3^{|\alpha |+1}}\}$ for higher priority $\mathcal {R}$ -strategies $\beta $ with $C_{e(\beta )}=C_{e(\alpha )}$ on the priority tree T to enumerate into $C_{e(\beta )}$ later such that

   $$ \begin{align*}N_{\alpha, s}<x^{1}_{\alpha,s}< x^{2}_{\alpha,s}<\ldots <x^{q_{\alpha}}_{\alpha,s}<w_{\alpha,s},\end{align*} $$

   where $N_{\alpha , s}$ is a new number larger than all used numbers before; particularly, $N_{\alpha ,s}$ is bigger than all restraints $r(\beta , s)$ appointed on $C_{e(\beta )}$ by $\mathcal {R}$ -strategies $\beta <\alpha $ (i.e., $\beta <_{L}\alpha $ or $\beta \subset \alpha $ ).

   The witness $w_{\alpha , s}$ and the triggers $x^{k}_{\alpha ,s} (1\leq k\leq q_{\alpha })$ keep unchanged at later stages unless the node $\alpha $ is initialized by higher priority strategies.

2. (2) Wait for an $\alpha $ -stage $t>s$ such that $\varphi _{i,t}(w_{\alpha ,s})\downarrow =0$ .

3. (3) Put $w_{\alpha ,s}$ into $C_{e,t}$ .

The possible outcomes of a basic $\alpha $ -strategy are the following:

1. f : wait at Step (2) forever; in this case, either $\varphi _{i}$ is not total or $\varphi _{i}(w_{\alpha ,s})\downarrow =1\neq C_{e}(w_{\alpha ,s})=0$ ;

2. d : arrive at Step (3); in this case, $\varphi _{i}(w_{\alpha ,s})\downarrow =0\neq C_{e}(w_{\alpha ,s})=1$ .

In both cases, the strategy ensures that $C_{e}\neq \varphi _{i}$ . The priority of the two outcomes on the priority tree is $d<_{L}f$ .

A basic $\mathcal {R}_{\langle e, i, j\rangle }$ -strategy. Let $\alpha $ be a node of length odd on the priority tree T assigned the $\mathcal {R}_{\langle e,i,j\rangle }$ -requirement. First, define the following notion of expansionary stages to approximate the condition $[i, i+j+1]\subseteq W^{K}_{e}$ . Since the condition $[i, i+j+1]\subseteq W^{K}_{e}$ is $\Sigma ^{0}_{2}$ , as in usual infinite injury constructions, we ensure that the $\Sigma ^{0}_{2}$ condition $[i, i+j+1]\subseteq W^{K}_{e}$ holds if and only if there are finitely many expansionary stages during the construction.

Supposed that $\alpha $ is visited infinitely often during the construction. The $\Sigma ^{0}_{2}$ condition $[i, i+j+1]\subseteq W^{K}_{e}$ is true if and only if there is an $\alpha $ -stage s such that every $\alpha $ -stage $t\geq s$ is a non $\alpha $ -expansionary stage. An $\alpha $ -strategy works to satisfy its requirement $\mathcal {R}_{\langle e, i,j\rangle }$ . At a non $\alpha $ -expansionary stage s, it prevents numbers from enumerating into $C_{e}$ to preserve convergent computations of the form $\Phi ^{C_{e}}_{j}(j)[s]\downarrow $ . While at an $\alpha $ -expansionary stage s, it devotes to diagonalize against $\varphi ^{2}_{i}$ to be a computable predecessor approximation function for $C_{e}$ by enumerating numbers into $C_{e}$ .

Second, to measure the approximation of the order-computable set $O_{i}$ computed by $\varphi ^{2}_{i}$ , define the following length function $l(i, s)$ of $O_{i}$ .

1. (1) If there is a number $x\in [1, s]$ such that the following conditions hold:

   • • $\varphi ^{2}_{i,s}(n, x)\downarrow <x$ for all $n<x$ , and $\varphi ^{2}_{i,s}(m, x)\uparrow $ for all $x\leq m\leq s$ ;

   • • $\varphi ^{2}_{i,s}(\cdot , x)$ is a permutation on $\{0,1,\ldots , x-1\}$ ;

   • • $\varphi ^{2}_{i,s}(n,t)\leq \varphi ^{2}_{i,s}(n,t+1)\leq \varphi ^{2}_{i,s}(n,t)+1$ for all $n<t<x$ ;

   let $l(i, s)$ be the largest such a number x, and define

   $$ \begin{align*}O_{i,s}=\{\varphi^{2}_{i,s}(2m, l(i,s)): 2m<l(i,s)\}.\end{align*} $$

2. (2) Otherwise, such a number x does not exist, let $l(i, s)=0$ and $O_{i,s}=\emptyset $ .

If $\varphi ^{2}_{i}$ does become a computable predecessor approximation function, then we have $\lim _{s}l(i,s)=\infty $ , and the corresponding order-computable set is

$$ \begin{align*}O_{i}=\lim_{s}O_{i,s}=\{\lim_{s}\varphi^{2}_{i}(2m,s): m\in\mathbb{N}\}.\end{align*} $$

In order to diagonalize against $\varphi ^{2}_{i}$ to be a computable predecessor approximation function for $C_{e}$ , an $\alpha $ -strategy aims to make sure that either $\lim _{s}l(i,s)<\infty $ , or $\lim _{s}\varphi ^{2}_{i}(y,s)=\infty $ for some even number y, or $\varphi ^{2}_{i}$ really becomes a computable predecessor approximation function with $\lim _{s}l(i,s)=\infty $ but $C_{e}(x)\neq O_{i}(x)$ for some x; that is, there is a large stage $s_{x}$ such that for all $t\geq s_{x}$ , $C_{e,t}(x)\neq O_{i,t}(x)$ . This analysis motivates us to formally define the following approximation of the length of agreement between $C_{e}$ and $O_{i}$ . The idea behind this definition was already used in [Reference Hirschfeldt, Miller and Podzorov13, Theorem 3.11] to build a Turing degree which contains no order-computable sets.

A basic $\alpha $ -strategy acts to satisfy its requirement $\mathcal {R}_{\langle e(\alpha ), i(\alpha ), j(\alpha )\rangle }$ with $e(\alpha )=e$ , $i(\alpha )=i$ and $j(\alpha )=j$ at $\alpha $ -stages as follows. There are two cases:

Case 1. At a non $\alpha $ -expansionary stage s, an $\alpha $ -strategy proceeds to preserve the computation $\Phi ^{C_{e}}_{j}(j)[s]$ . Let $\phi ^{C_{e}}_{j}(j)[s]$ denote the use of the computation $\Phi ^{C_{e}}_{j}(j)[s]$ if it converges.

1. (1) If $\Phi ^{C_{e}}_{j}(j)[s]$ converges, appoint a restraint $r(\alpha ,s)=\phi ^{C_{e}}_{j}(j)[s]$ on $C_{e}$ to preserve the computation $\Phi ^{C_{e}}_{j}(j)[s]$ .

2. (2) If $\Phi ^{C_{e}}_{j}(j)[s]$ diverges, set $r(\alpha ,s)=0$ .

Any lower priority $\beta $ -strategy on T can only enumerate numbers $>r(\alpha ,s)$ into $C_{e(\beta )}$ later.

Case 2. At $\alpha $ -expansionary stages, a basic $\alpha $ -strategy acts to diagonalize against $\varphi ^{2}_{i}$ to be a computable predecessor approximation function for $C_{e}$ .

1. (1) At the first $\alpha $ -expansionary stage $s_{0}$ , choose a large new witness $w_{\alpha ,s_{0}}$ and a set of fresh trigger elements $ \{x^{k}_{\alpha ,s_{0}}: 1\leq k\leq q_{\alpha }=2^{3^{|\alpha |+1}}\}$ for higher priority $\mathcal {R}$ -strategies $\beta $ with $e(\beta )=e(\alpha )$ and $\beta \leq \alpha $ (i.e., $\beta <_{L} \alpha $ or $\beta \subseteq \alpha $ ) to enumerate into $C_{e(\beta )}$ later such that

   $$ \begin{align*}N_{\alpha, s_{0}}<x^{1}_{\alpha,s_{0}}< x^{2}_{\alpha,s_{0}}<\ldots <x^{q_{\alpha}}_{\alpha,s_{0}}<w_{\alpha,s_{0}},\end{align*} $$

   where $N_{\alpha , s_{0}}$ is a new number larger than all used numbers before; particularly, $N_{\alpha ,s_{0}}$ is bigger than all restraints $r(\beta , s_{0})$ appointed on $C_{e(\beta )}$ by $\mathcal {R}$ -strategies $\beta $ with $\beta <\alpha $ .

   • • Enumerate $w_{\alpha ,s_{0}}$ into $C_{e(\alpha ),s_{0}}$ .

   The witness $w_{\alpha , s_{0}}$ and the triggers $x^{k}_{\alpha ,s_{0}} (1\leq k\leq q_{\alpha })$ keep unchanged at later stages unless the node $\alpha $ is initialized by higher priority strategies.

2. (2) Wait for an $\alpha $ -expansionary stage $t_{0}>s_{0}$ such that the length approximation of the order-computable set $l(i(\alpha ), t_{0})>w_{\alpha ,s_{0}}$ , and $\varphi ^{2}_{i(\alpha )}$ appears to be a computable predecessor approximation function for $C_{e(\alpha )}$ at stage $t_{0}$ .

3. (3) Let $y_{\alpha , t_{0}}$ be the unique even number such that $\varphi ^{2}_{i(\alpha )}(y_{\alpha , t_{0}}, l(i(\alpha ), t_{0}))=w_{\alpha ,s_{0}}\in C_{e(\alpha ),s_{0}}$ .

   • • Pick the largest trigger element $x^{k}_{\alpha ,s_{0}}<w_{\alpha , s_{0}}$ that has not been enumerated into $C_{e(\beta )}$ by $\beta $ -strategies with $\beta <\alpha $ .

   • • Enumerate $x^{k}_{\alpha ,s_{0}}$ into $C_{e(\alpha ),t_{0}}$ .

   • • Go to Step (4.n) with $n=1$ .

   The even number $y_{\alpha , t_{0}}$ remains the same at later stages as long as $\alpha $ is not initialized.

4. (4.n) Wait for an $\alpha $ -expansionary stage $t_{n}>t_{n-1}$ such that $\varphi ^{2}_{i(\alpha )}$ appears to be a computable predecessor approximation function for $C_{e(\alpha )}$ at stage $t_{n}$ .

5. (5.n) Let $u_{\alpha , t_{0}}=w_{\alpha , s_{0}}$ and $u_{\alpha , t_{n}}=\varphi ^{2}_{i(\alpha )}(y_{\alpha , t_{0}}, l(i(\alpha ), t_{n}))$ . Then we have

   $$ \begin{align*} w_{\alpha,s_{0}} \leq u_{\alpha, t_{n-1}}&=\varphi^{2}_{i(\alpha)}(y_{\alpha, t_{0}}, l(i(\alpha), t_{n-1}))\nonumber\\ &<\varphi^{2}_{i(\alpha)}(y_{\alpha, t_{0}}, l(i(\alpha), t_{n}))=u_{\alpha, t_{n}}\in O_{i(\alpha), t_{n}}= C_{e(\alpha), t_{n}}\nonumber \end{align*} $$
   because the enumeration of the trigger element $x^{k}_{\alpha , s_{0}}< w_{\alpha , s_{0}}$ in Step (3) for $n=1$ or $x^{k}_{\beta , t}\in (w_{\alpha ,s_{0}}, u_{\alpha , t_{n-1}})$ in Step (5. $(n-1)$ ) for $n\geq 2$ forces the number of predecessors of $y_{\alpha , t_{0}}$ computed by $\varphi ^{2}_{i(\alpha )}$ to move up.

   As $u_{\alpha , t_{n}}\in C_{e(\alpha ), t_{n}}$ and $u_{\alpha , t_{n}}> w_{\alpha , s_{0}}$ , there is a unique node $\beta>\alpha $ on the priority tree T such that

   $$ \begin{align*}u_{\alpha, t_{n}}=w_{\beta, t} \text{ or }u_{\alpha, t_{n}}=x^{k}_{\beta, t} \text{ for some }k,\end{align*} $$
   where $w_{\beta ,t}$ and $x^{k}_{\beta ,t}(1\leq k\leq q_{\beta }=2^{3^{|\beta |+1}})$ were first appointed on $\beta $ at some $\beta $ -stage $t\in (t_{0}, t_{n})$ .

   • • Pick the largest trigger number $x^{k}_{\beta ,t}<u_{\alpha ,t_{n}}\leq w_{\beta ,t}$ that has not been enumerated into $C_{e(\beta ')}$ for any $\beta '\leq \beta $ .

   • • Enumerate $x^{k}_{\beta ,t}$ into $C_{e(\alpha ),t_{n}}$ .

   • • Go to Step (4.( $n+1$ )).

   For each node $\beta \in T$ , since the number of nodes $\beta '\in T$ with $\beta '<_{L}\beta $ or $\beta ' \subseteq \beta $ is strictly less than $3^{|\beta |+1}$ , we appoint enough (i.e., $2^{3^{|\beta |+1}}$ many) trigger elements $x^{k}_{\beta ,t}$ on node $\beta $ for higher priority $\beta '$ -strategies working for $\mathcal {R}$ -requirements to enumerate into $C_{e(\beta ')}$ during the construction. That is, the trigger elements in Step (3) or Step (5.n) always exist if needed (see Lemma 1 below).

The possible outcomes of a basic $\alpha $ -strategy is listed as follows:

• f: finitely many $\alpha $ -expansionary stages;

• d: wait at Step (2) or Step (4.n) for some $n\geq 1$ forever at $\alpha $ -expansionary stages;

• ∞: go to Step (4. $(n+1)$ ) from Step (5.n) infinitely often at $\alpha $ -expansionary stages.

The priority of the outcomes on the priority tree T is $\infty <_{L} d<_{L}f$ .

If there are finitely many $\alpha $ -expansionary stages, $\alpha $ has the finite outcome f, and the computation $\Phi ^{C_{e(\alpha )}}_{j(\alpha )}(j(\alpha ))$ will be preserved after certain stage if it converges at infinitely many $\alpha $ -stages. If there are infinitely many $\alpha $ -expansionary stages, $\alpha $ has two possible outcomes $\infty <_{L}d$ .

1. (i) If $\alpha $ has the outcome d, then either $\lim _{s}l(i(\alpha ),s)<\infty $ or $C_{e(\alpha )}\neq O_{i(\alpha )}$ in which case $\alpha $ only enumerates finitely many triggers into $C_{e(\alpha )}$ .

2. (ii) If $\alpha $ has the outcome $\infty $ , then $\lim _{s}\varphi ^{2}_{i(\alpha )}(y_{\alpha , t_{0}}, s)=\lim _{n}u_{\alpha ,t_{n}}=\infty $ in which case $\alpha $ enumerates infinitely many triggers into $C_{e(\alpha )}$ .

In both cases, $\varphi ^{2}_{i(\alpha )}$ cannot be a computable predecessor approximation function for $C_{e(\alpha )}$ . In other words, $C_{e(\alpha )}$ is not order-computed via $\varphi ^{2}_{i(\alpha )}$ .

This ends the description of basic strategies.

Fix a bijection $\langle \cdot , \cdot \rangle : \mathbb {N}^{2}\rightarrow \mathbb {N}$ such that $\langle e, i\rangle <\langle e, i'\rangle $ for all $e,i,i'$ with $i<i'$ . For $e,i,j\in \mathbb {N}$ , let $\langle e, i, j\rangle =\langle \langle e,i\rangle ,j\rangle $ . Then we can fix a linear order $\prec $ on all $\mathcal {P}_{\langle e, i\rangle }$ - and $\mathcal {R}_{\langle e, i, j\rangle }$ -requirements ( $e,i,j\in \mathbb {N}$ ) of order type $\omega $ as follows.

1. (1) For all $e,i, e', i'$ , let $\mathcal {P}_{\langle e, i\rangle }\prec \mathcal {P}_{\langle e', i'\rangle }$ if and only if $\langle e, i\rangle < \langle e', i'\rangle $ , and let the priority of all $\mathcal {P}$ -requirements be listed as

   $$ \begin{align*}\mathcal{P}_{\langle e_{0},i_{0}\rangle} \prec \mathcal{P}_{\langle e_{1}, i_{1}\rangle}\prec\ldots\prec \mathcal{P}_{\langle e_{n}, i_{n}\rangle}\prec\ldots.\end{align*} $$

   Particularly, for any number e, we have

   $$ \begin{align*}\mathcal{P}_{\langle e,0\rangle} \prec \mathcal{P}_{\langle e, 1\rangle}\prec\ldots\prec \mathcal{P}_{\langle e, i\rangle}\prec\ldots.\end{align*} $$

2. (2) For all $e,i,j, e', i',j'$ , let $\mathcal {R}_{\langle e, i,j\rangle }\prec \mathcal {R}_{\langle e', i', j'\rangle }$ if and only if $\langle e, i,j\rangle < \langle e', i', j'\rangle $ , and let the priority of all $\mathcal {R}$ -requirements be listed as

   $$ \begin{align*}\mathcal{R}_{\langle e^{\prime}_{0},i^{\prime}_{0},j^{\prime}_{0}\rangle} \prec \mathcal{R}_{\langle e^{\prime}_{1}, i^{\prime}_{1}, j^{\prime}_{1}\rangle}\prec\ldots\prec \mathcal{R}_{\langle e^{\prime}_{n}, i^{\prime}_{n}, j^{\prime}_{n}\rangle}\prec\ldots.\end{align*} $$

   Particularly, for fixed numbers $e,i$ , we have

   $$ \begin{align*}\mathcal{R}_{\langle e,i,0\rangle} \prec \mathcal{R}_{\langle e, i, 1\rangle}\prec\ldots\prec \mathcal{R}_{\langle e, i, j\rangle}\prec\ldots.\end{align*} $$

3. (3) Define the priority of all $\mathcal {P}$ - and $\mathcal {R}$ - requirements as

   $$ \begin{align*}\mathcal{P}_{\langle e_{0},i_{0}\rangle}\prec \mathcal{R}_{\langle e^{\prime}_{0},i^{\prime}_{0},j^{\prime}_{0}\rangle} \prec \mathcal{P}_{\langle e_{1},i_{1}\rangle} \prec \mathcal{R}_{\langle e^{\prime}_{1}, i^{\prime}_{1}, j^{\prime}_{1}\rangle}\prec\ldots\prec \mathcal{P}_{\langle e_{n},i_{n}\rangle}\prec \mathcal{R}_{\langle e^{\prime}_{n}, i^{\prime}_{n}, j^{\prime}_{n}\rangle}\prec\ldots.\end{align*} $$

The tree of strategies. The priority tree T of the construction is a subtree of $S=\{\infty , d, f\}^{<\omega }$ such that any node $\alpha \in T$ of length even has two immediate extensions $\alpha ^{\smallfrown } d$ and $\alpha ^{\smallfrown }f$ on T and any node $\alpha \in T$ of length odd has three immediate extensions $\alpha ^{\smallfrown }\infty $ , $\alpha ^{\smallfrown } d$ and $\alpha ^{\smallfrown }f$ on T. Say that a node $\alpha \in T$ is a $\mathcal {P}_{\langle e, i\rangle }$ - or an $\mathcal {R}_{\langle e, i, j\rangle }$ -strategy if it is assigned the corresponding requirement. As before, we write the $\mathcal {P}_{\langle e, i\rangle }$ -requirement assigned to a node $\alpha $ of T with length even as $\mathcal {P}_{\langle e(\alpha ), i(\alpha )\rangle }$ (or simply $\mathcal {P}_{\alpha }$ ). Similarly, we write the $\mathcal {R}_{\langle e, i, j\rangle }$ -requirement assigned to a node $\beta $ of T with length odd as $\mathcal {R}_{\langle e(\beta ), i(\beta ), j(\beta )\rangle }$ (or simply $\mathcal {R}_{\beta }$ ).

According to the priority of $\mathcal {P}$ -, $\mathcal {R}$ -requirements above, assign the requirements to nodes of the priority tree T by induction on their length as follows.

1. (1) For the empty node $\lambda \in T$ , assign the highest priority $\mathcal {P}$ -requirement $\mathcal {P}_{\langle e_{0}, i_{0}\rangle }$ to node $\lambda $ .

2. (2) For nodes $d,f\in T$ , assign the highest priority $\mathcal {R}$ -requirement $\mathcal {R}_{\langle e^{\prime }_{0}, i^{\prime }_{0}, j^{\prime }_{0}\rangle }$ to $d, f$ .

3. (3) Assume that $\alpha ={\alpha ^{-}}^{\smallfrown }o\in T$ with length $|\alpha |\geq 1$ . There are two cases depending on the parity of $|\alpha |$ .

   • • If $|\alpha |$ is odd, then $\alpha ^{\smallfrown }\infty $ , $\alpha ^{\smallfrown }d$ and $\alpha ^{\smallfrown }f\in T$ . Suppose that the immediate predecessor $\alpha ^{-}$ of $\alpha $ is assigned the $\mathcal {P}_{\langle e_{n}, i_{n}\rangle }$ -requirement with $n\geq 0$ .

     • – For $o\in \{\infty , d, f\}$ , assign $\mathcal {P}_{\langle e_{n+1}, i_{n+1}\rangle }$ to node $\alpha ^{\smallfrown }o$ .

   • • If $|\alpha |$ is even, then $\alpha ^{\smallfrown }d$ and $\alpha ^{\smallfrown }f\in T$ . Suppose that the immediate predecessor $\alpha ^{-}$ of $\alpha $ is assigned the $\mathcal {R}_{\langle e^{\prime }_{n}, i^{\prime }_{n}, j^{\prime }_{n}\rangle }$ -requirement with $n\geq 0$ .

     • * For $o\in \{d,f\}$ , find the least $m>n$ such that $\langle e^{\prime }_{m}, i^{\prime }_{m}\rangle \neq \langle e(\beta ), i(\beta )\rangle $ for all nodes $\beta $ of length odd assigned the $\mathcal {R}_{\langle e(\beta ), i(\beta ), j(\beta )\rangle }$ -requirement with $\beta ^{\smallfrown }d\subseteq \alpha $ or $\beta ^{\smallfrown }\infty \subseteq \alpha $ , and assign $\mathcal {R}_{\langle e^{\prime }_{m}, i^{\prime }_{m}, j^{\prime }_{m}\rangle }$ to node $\alpha ^{\smallfrown }o$ .

   Note that a node $\beta ^{\smallfrown }o\in T$ with $|\beta |$ odd and $o\in \{d, \infty \}$ represents that the $\beta $ -strategy has an infinite outcome o. In this case, $[i(\beta ), i(\beta )+j(\beta )+1]\nsubseteq W^{K}_{e(\beta )}$ and the $\beta $ -strategy works to diagonalize against $\varphi ^{2}_{i(\beta )}$ to be a computable predecessor approximation function for $C_{e(\beta )}$ . So we do not need to assign $\mathcal {R}_{\langle e(\beta ), i(\beta ), \cdot \rangle }$ -requirements to nodes of T below $\beta ^{\smallfrown }o$ .

We now describe possible conflictions between multiple $\mathcal {R}$ -strategies on the priority tree T. Let $\alpha $ be an $\mathcal {R}_{\langle e, i, j\rangle }$ -strategy on T. Suppose that $[i, i+j+1]\nsubseteq W^{K}_{e}$ . For all $j'>j$ , as $[i, i+j+1]\subseteq [i, i+j'+1]$ , we have $ [i, i+j'+1]\nsubseteq W^{K}_{e}$ . So we do not need to assign $\mathcal {R}_{\langle e, i,j'\rangle }$ requirements with $j'>j$ to nodes below the infinite outcomes of $\alpha $ (i.e., below $\alpha ^{\smallfrown } d$ or $\alpha ^{\smallfrown }\infty $ ) on the priority tree. However, for $i'\neq i$ , $\mathcal {R}_{\langle e,i',\cdot \rangle }$ -requirements are still assigned to nodes below the infinite outcomes of $\alpha $ . Let $\alpha '\supset \alpha $ be an $\mathcal {R}_{\langle e, i', j'\rangle }$ -strategy on T.

1. (i) If $\alpha ^{\smallfrown }d\subset \alpha '$ , then there are no conflictions because $\alpha $ only enumerates finitely many triggers of nodes with lower priority into $C_{e}$ .

2. (ii) If $\alpha ^{\smallfrown } \infty \subset \alpha '$ , then $\alpha $ acts infinitely often to enumerate triggers of nodes $\beta \in T$ with $\beta> \alpha $ into $C_{e}$ to force $\lim _{s}\varphi ^{2}_{i}(y,s)=\infty $ for some even number y; this may injure a convergent computation $\Phi ^{C_{e}}_{j'}(j')[s]\downarrow $ , which $\alpha '$ needs to preserve, infinitely often. Since the triggers enumerated by $\alpha $ during the construction tend to infinity, to deal with this problem, we only preserve believable computations $\Phi ^{C_{e}}_{j'}(j')[s]\downarrow $ where $\alpha $ will not enumerate triggers $<\phi ^{C_{e}}_{j'}(j')[s]$ , the use of the computation, after stage s.

3.2 Construction and verification

We are ready to provide a formal construction of the c.e. sets $C_{e}(e\in \mathbb {N})$ by stages according to the tree of strategies.

Construction.

Stage 0. Let $\delta _{0}=\lambda $ , the empty node on T. Initialize all nodes on T. For all e, let $C_{e,0}=\emptyset $ . For all nodes $\alpha \in T$ with length $|\alpha |$ odd, set the $C_{e(\alpha )}$ -restraint $r(\alpha ,0)=0$ .

Stage $s\geq 1$ . Define the current true path $\delta _{s}\in T$ with length $|\delta _{s}|\leq s$ at substages m with $0\leq m\leq s-1$ , starting at substage 0. Let $\alpha _{0}=\lambda $ , the empty node on T, and assume that we have defined $\alpha _{m}=\delta _{s}(0)\ldots \delta _{s}(m-1)$ by the end of substage $m-1$ for $1\leq m\leq s$ .

Substage $m(0\leq m\leq s-1)$ . Define the current true outcome $\delta _{s}(m)$ of $\alpha _{m}$ and enumerate numbers into $C_{e(\alpha _{m}),s}$ according to the basic $\alpha _{m}$ -strategy with additional initializations to strategies with lower priority on the priority tree T.

• – If a node $\alpha \in T$ is initialized at stage s, then the witness $w_{\alpha ,s}$ and triggers $x^{k}_{\alpha ,s}(1\leq k\leq q_{\alpha }=2^{3^{|\alpha |+1}})$ are undefined.

• – If $m=s-1$ , let $\delta _{s}={\alpha _{m}}^{\smallfrown }\delta _{s}(m)={\alpha _{s-1}}^{\smallfrown }\delta _{s}(s-1)=\delta _{s}(0)\ldots \delta _{s}(s-1)$ . Initialize all nodes $\alpha \geq \delta _{s}$ , also initialize all nodes of length $\geq s+1$ . End current stage s and go to next stage.

Substage m proceeds as follows. There are two cases depending on the parity of m.

Case I. If m is even, then $\alpha _{m}$ is a $\mathcal {P}$ -strategy. Check whether there was a last $\alpha _{m}$ -stage $s^{-}$ such that $\alpha _{m}$ has not been initialized since then.

1. (1) If such a last $\alpha _{m}$ -stage $s^{-}$ did not exist, then s is the first $\alpha _{m}$ -stage after last initialization. Act as in the basic $\alpha _{m}$ -strategy.

   • • Choose a large new witness $w_{\alpha _{m},s}$ and a set of fresh trigger elements $ \{x^{k}_{\alpha _{m},s}: 1\leq k\leq q_{\alpha _{m}}=2^{3^{|\alpha _{m}|+1}}\}$ for $\beta $ -strategies with $|\beta |$ odd and $\beta \leq \alpha _{m}$ (i.e., $\beta <_{L} \alpha _{m}$ or $\beta \subseteq \alpha _{m}$ ) on the priority tree T to enumerate into $C_{e(\beta )}$ later such that

     $$ \begin{align*}N_{\alpha_{m}, s}<x^{1}_{\alpha_{m},s}< x^{2}_{\alpha_{m},s}<\ldots <x^{q_{\alpha_{m}}}_{\alpha_{m},s}<w_{\alpha_{m},s},\end{align*} $$

     where $N_{\alpha _{m}, s}$ is a new number larger than all used numbers before; particularly, $N_{\alpha _{m},s}$ is bigger than all restraints $r(\beta , s)$ appointed on $C_{e(\beta )}$ by higher priority $\beta $ -strategies.

   • • Go to Step (2); that is, wait for $\varphi _{i(\alpha _{m})}(w_{\alpha _{m},s})\downarrow =0$ .

   • • Let $\delta _{s}(m)=f$ . Define $\delta _{s}={\alpha _{m}}^{\smallfrown }\delta _{s}(m)={\alpha _{m}}^{\smallfrown }f$ . Initialize all nodes $\alpha \geq {\alpha _{m}}^{\smallfrown }f$ , also initialize all nodes of length $\geq s+1$ .

   • • End Stage s and go to next stage.

   The witness $w_{\alpha _{m}, s}$ and the triggers $x^{k}_{\alpha _{m},s} (1\leq k\leq q_{\alpha _{m}})$ keep unchanged at later stages unless the node $\alpha _{m}$ is initialized by higher priority strategies.

2. (2) If such a last $\alpha _{m}$ -stage $s^{-}$ did exist, then there was a largest $\alpha _{m}$ -stage $s_{0}\leq s^{-}<s$ such that the witness $w_{\alpha _{m}, s_{0}}$ and trigger elements $x^{k}_{\alpha _{m}, s_{0}}$ with $1\leq k\leq q_{\alpha _{m}}=2^{3^{|\alpha _{m}|+1}}$ were defined at stage $s_{0}$ and $\alpha _{m}$ has not been initialized since then. Define the current outcome $\delta _{s}(m)$ of the $\alpha _{m}$ -strategy started at stage $s_{0}$ according to the current state of the strategy.

   • • If the $\alpha _{m}$ -strategy waits at Step (2), let $\delta _{s}(m)=f$ .

     • * Initialize all nodes $\alpha>_{L}{\alpha _{m}}^{\smallfrown }f$ . Go to substage $m+1$ of current stage s if $m+1<s$ .

   • • If the $\alpha _{m}$ -strategy currently arrives at Step (2), act as in Step (3).

     • * Enumerate $w_{\alpha _{m},s_{0}}$ into $C_{e(\alpha _{m}),s}$ .

     • * Let $\delta _{s}(m)=d$ . Define $\delta _{s}={\alpha _{m}}^{\smallfrown }\delta _{s}(m)={\alpha _{m}}^{\smallfrown }d$ . Initialize all nodes $\alpha \geq {\alpha _{m}}^{\smallfrown }d$ and all nodes of length $\geq s+1$ .

     • * End Stage s and go to next stage.

   • • Otherwise, the $\alpha _{m}$ -strategy was already arrived at Step (2) at last $\alpha _{m}$ -stage $s^{-}$ , let $\delta _{s}(m)=d$ .

     • * Initialize all nodes $\alpha>_{L}{\alpha _{m}}^{\smallfrown }d$ . Go to substage $m+1$ of current stage s if $m+1<s$ .

Case II. If m is odd, then $\alpha _{m}$ is an $\mathcal {R}$ -strategy. Act as follows.

Case 1. If s is a non $\alpha _{m}$ -expansionary stage, let $\delta _{s}(m)=f$ . Act as in the basic $\alpha _{m}$ -strategy.

1. (1) If the computation $\Phi ^{C_{e(\alpha _{m})}}_{j(\alpha _{m})}(j(\alpha _{m}))[s]$ newly converges and it is a believable computation at stage s, let $\phi ^{C_{e(\alpha _{m})}}_{j(\alpha _{m})}(j(\alpha _{m}))[s]$ be the use of the computation.

   • • Appoint a new $C_{e(\alpha _{m})}$ -restraint $r(\alpha _{m},s)=\phi ^{C_{e(\alpha _{m})}}_{j(\alpha _{m})}(j(\alpha _{m}))[s]$ .

   • • Define $\delta _{s}={\alpha _{m}}^{\smallfrown }\delta _{s}(m)={\alpha _{m}}^{\smallfrown }f$ . Initialize all nodes $\alpha \geq \delta _{s}$ (i.e., $\alpha>_{L}\delta _{s}$ or $\alpha \supseteq \delta _{s}$ ). Also initialize all nodes of length $\geq s+1$ .

   • • End Stage s and go to next stage.

2. (2) Otherwise, there are two possible subcases:

   1. (i) if $\Phi ^{C_{e(\alpha _{m})}}_{j(\alpha _{m})}(j(\alpha _{m}))[s]$ diverges or it converges but not believable at current stage, let the $C_{e(\alpha _{m})}$ -restraint $r(\alpha _{m},s)=0$ .

   2. (ii) otherwise, it is a believable computation already convergent at last non $\alpha _{m}$ -expansionary stage $s^{-}$ , let the $C_{e(\alpha _{m})}$ -restraint $r(\alpha _{m},s)= r(\alpha _{m},s^{-})$ .

   In both subcases, initialize all nodes $\alpha>_{L}{\alpha _{m}}^{\smallfrown }f$ . Go to substage $m+1$ of current stage s if $m+1<s$ .

Case 2. If s is an $\alpha _{m}$ -expansionary stage, check whether there was a last $\alpha _{m}$ -expansionary stage $s^{-}$ such that $\alpha _{m}$ has not been initialized since then.

1. (1) If such a last $\alpha _{m}$ -expansionary stage $s^{-}$ did not exist, then s is the first $\alpha _{m}$ -expansionary stage after last initialization. Act as in the basic $\alpha _{m}$ -strategy.

   • • Choose a large new witness $w_{\alpha _{m},s}$ and a set of fresh trigger elements $ \{x^{k}_{\alpha _{m},s}: 1\leq k\leq q_{\alpha _{m}}=2^{3^{|\alpha _{m}|+1}}\}$ for higher priority $\beta $ -strategies of length odd with $\beta \leq \alpha _{m}$ (i.e., $\beta <_{L} \alpha _{m}$ or $\beta \subseteq \alpha _{m}$ ) on the priority tree T to enumerate into $C_{e(\beta )}$ later such that

     $$ \begin{align*}N_{\alpha_{m}, s}<x^{1}_{\alpha_{m},s}< x^{2}_{\alpha_{m},s}<\ldots <x^{q_{\alpha_{m}}}_{\alpha_{m},s}<w_{\alpha_{m},s},\end{align*} $$

     where $N_{\alpha _{m}, s}$ is a new number larger than all used numbers before; particularly, $N_{\alpha _{m},s}$ is bigger than all restraints $r(\beta , s)$ appointed on $C_{e(\beta )}$ by $\mathcal {R}$ -strategies $\beta $ with priority strictly higher than $\alpha _{m}$ .

   • • Enumerate the witness $w_{\alpha _{m},s}$ into $C_{e(\alpha _{m}),s}$ .

   • • Define $\delta _{s}={\alpha _{m}}^{\smallfrown }\delta _{s}(m)={\alpha _{m}}^{\smallfrown }d$ . Initialize all nodes $\alpha \geq {\alpha _{m}}^{\smallfrown }d$ and all nodes of length $\geq s+1$ .

   • • End Stage s and go to next stage.

   The witness $w_{\alpha _{m}, s}$ and the triggers $x^{k}_{\alpha _{m},s} (1\leq k\leq q_{\alpha _{m}})$ keep unchanged at later stages unless the node $\alpha _{m}$ is initialized by higher priority strategies.

2. (2) If such a last $\alpha _{m}$ -expansionary stage $s^{-}$ did exist, then there was a largest $\alpha _{m}$ -expansionary stage $s_{0}\leq s^{-}<s$ such that the witness $w_{\alpha _{m}, s_{0}}$ and trigger elements $x^{k}_{\alpha _{m}, s_{0}}$ with $1\leq k\leq q_{\alpha _{m}}=2^{3^{|\alpha _{m}|+1}}$ were defined at stage $s_{0}$ and $\alpha _{m}$ has not been initialized since then. Define the current outcome $\delta _{s}(m)$ of the $\alpha _{m}$ -strategy started at stage $s_{0}$ according to the current state of the strategy.

   • • If the $\alpha _{m}$ -strategy waits at Step (2) or at Step (4.n) for some $n\geq 1$ , let $\delta _{s}(m)=d$ .

     • * Initialize all nodes $\alpha>_{L}{\alpha _{m}}^{\smallfrown }\delta _{s}(m)={\alpha _{m}}^{\smallfrown }d$ . Go to substage $m+1$ of current stage s if $m+1<s$ .

   • • If the $\alpha _{m}$ -strategy currently arrives at Step (2), let $\delta _{s}(m)=d$ . Act as in Step (3).

     • * Let $t_{0}=s$ and $u_{\alpha _{m}, t_{0}}=w_{\alpha _{m}, s}=w_{\alpha _{m}, s_{0}}$ . Let $y_{\alpha _{m}, s}$ be the unique even number such that

       $$ \begin{align*}\varphi^{2}_{i(\alpha_{m})}(y_{\alpha_{m}, s}, l(i(\alpha_{m}), s))=w_{\alpha_{m},s}=w_{\alpha_{m},s_{0}}\in O_{i(\alpha_{m}),s}= C_{e(\alpha_{m}),s}.\end{align*} $$
       The even number $y_{\alpha _{m}, s}$ remains the same at later stages as long as $\alpha _{m}$ is not initialized.

     • * Pick the largest trigger element $x^{k}_{\alpha _{m},s}=x^{k}_{\alpha _{m},s_{0}}<w_{\alpha _{m}, s_{0}}$ that has not been enumerated into $C_{e(\beta )}$ by $\beta $ -strategies with $\beta <\alpha _{m}$ (i.e., $\beta <_{L}\alpha _{m}$ or $\beta \subset \alpha _{m}$ ).

     • * Enumerate $x^{k}_{\alpha _{m},s}$ into $C_{e(\alpha _{m}),s}$ . Go to Step (4.1).By Lemma 1 below, such a trigger $x^{k}_{\alpha _{m},s_{0}}$ always exists.

     • * Define $\delta _{s}={\alpha _{m}}^{\smallfrown }\delta _{s}(m)={\alpha _{m}}^{\smallfrown }d$ . Initialize all nodes $\alpha \geq {\alpha _{m}}^{\smallfrown }d$ and all nodes of length $\geq s+1$ .

     • * End Stage s and go to next stage.

   • • If the $\alpha _{m}$ -strategy arrives at Step (4.n) for some $n\geq 1$ , let $\delta _{s}(m)=\infty $ . Act as in Step (5.n).

     • * Let $t_{n}=s$ and $u_{\alpha _{m}, t_{n}}=\varphi ^{2}_{i(\alpha _{m})}(y_{\alpha _{m}, t_{0}}, l(i(\alpha _{m}), s))$ . Then we have

       $$ \begin{align*} w_{\alpha_{m},s_{0}} \leq u_{\alpha_{m}, t_{n-1}}&=\varphi^{2}_{i(\alpha_{m})}(y_{\alpha_{m}, t_{0}}, l(i(\alpha_{m}), t_{n-1}))\nonumber\\ &<\varphi^{2}_{i(\alpha_{m})}(y_{\alpha_{m}, t_{0}}, l(i(\alpha_{m}), t_{n}))=u_{\alpha_{m}, t_{n}}\in C_{e(\alpha_{m}), t_{n}}\nonumber \end{align*} $$
       because the enumeration of the trigger element $x^{k}_{\alpha _{m}, t_{0}}< w_{\alpha _{m}, s_{0}}$ in Step (3) for $n=1$ or $x^{k}_{\beta , t}\in (w_{\alpha _{m},s_{0}}, u_{\alpha _{m}, t_{n-1}})$ in Step (5. $(n-1)$ ) for $n\geq 2$ forces the number of predecessors of $y_{\alpha _{m}, t_{0}}$ computed by $\varphi ^{2}_{i(\alpha _{m})}$ to move up.

       As $u_{\alpha _{m}, t_{n}}\in C_{e(\alpha _{m}), t_{n}}$ and $u_{\alpha _{m}, t_{n}}> w_{\alpha _{m}, s_{0}}$ , there is a unique node $\beta>\alpha _{m}$ on the priority tree T with $e(\beta )=e(\alpha _{m})$ such that

       $$ \begin{align*}u_{\alpha_{m}, t_{n}}=w_{\beta,t} \text{ or }u_{\alpha_{m}, t_{n}}=x^{k}_{\beta,t} \text{ for some }k,\end{align*} $$
       where $w_{\beta ,t}$ and $x^{k}_{\beta ,t}(1\leq k\leq q_{\beta }=2^{3^{|\beta |+1}})$ were first appointed on $\beta $ at some $\beta $ -stage $t\in (s_{0}, t_{n})$ .

     • * Pick the largest trigger number $x^{k}_{\beta ,t}<u_{\alpha _{m},t_{n}}\leq w_{\beta ,t}$ that has not been enumerated into $C_{e(\beta ')}$ for any $\beta '\leq \beta $ .

     • * Enumerate $x^{k}_{\beta ,t}$ into $C_{e(\alpha _{m}),t_{n}}$ . Go to Step (4.( $n+1$ )).By Lemma 1 below, such a trigger $x^{k}_{\beta ,t}$ always exists.

     • * Initialize all nodes $\alpha>_{L}{\alpha _{m}}^{\smallfrown }\infty $ . Go to substage $m+1$ of current stage s if $m+1<s$ .

This ends the construction.

Lemma 1. For each node $\alpha \in T$ , let $q_{\alpha }=2^{3^{|\alpha |+1}}$ . Suppose that $s_{0}$ is a first $\alpha $ -stage after last initialization during the construction such that the witness $w_{\alpha , s_{0}}$ and the set of trigger elements $X_{\alpha ,s_{0}}=\{x^{k}_{\alpha , s_{0}}: 1\leq k\leq q_{\alpha }\}$ were first chosen at stage $s_{0}$ . Then there are enough trigger elements from $X_{\alpha , s_{0}}$ for higher priority $\beta $ -strategies to enumerate into $C_{e(\beta )}$ after stage $s_{0}$ . That is,

$$ \begin{align*}\{x^{k}_{\alpha, s_{0}}\in C_{e(\beta)}: \beta\in T, \beta\leq \alpha, 1\leq k\leq q_{\alpha}\} \subsetneq X_{\alpha, s_{0}}.\end{align*} $$

Proof. During the construction, only higher priority $\mathcal {R}$ -strategies $\beta \leq \alpha $ with $e(\beta )=e(\alpha )$ can enumerate triggers from $X_{\alpha , s_{0}}$ into $C_{e(\beta )}$ after stage $s_{0}$ . Furthermore, if $\beta \leq \alpha $ is initialized at some stage $s>s_{0}$ , then it will initiate a new strategy later; thus $\beta $ will not use triggers from $X_{\alpha , s_{0}}$ after stage s.

Let $\beta _{1}$ be the first $\mathcal {R}$ -strategy with $\beta _{1}\leq \alpha $ that acts as in Step (3) or Step (5.n) for some n to enumerate a trigger $x^{k}_{\alpha ,s_{0}}$ into $ C_{e(\beta _{1}),s_{1}}$ at some stage $s_{1}> s_{0}$ . Then there is a unique even number $y_{\beta _{1}, s_{1}}$ such that

$$ \begin{align*}\varphi^{2}_{i(\beta_{1})}(y_{\beta_{1}, s_{1}}, l(i(\beta_{1}), s_{1}))=w_{\alpha,s_{0}}\in O_{i(\beta_{1}),s_{1}}= C_{e(\beta_{1}),s_{1}},\end{align*} $$

so we have $e(\beta _{1})=e(\alpha )$ , and the $\beta _{1}$ -strategy enumerates the largest $x^{q_{\alpha }}_{\alpha ,s_{0}}$ into $ C_{e(\beta _{1}), s_{1}}=C_{e(\alpha ),s_{1}}$ . This enumeration forces the number of predecessors of $y_{\beta _{1}, s_{1}}$ approximated by $\varphi ^{2}_{i(\beta _{1})}$ to move up if the $\beta _{1}$ -strategy next arrives at Step (4.1) from Step (3) or at Step (4. $(n+1)$ ) from Step (5.n) at some stage $s>s_{1}$ . That is, at stage s, we have

$$ \begin{align*}w_{\alpha,s_{0}}=\varphi^{2}_{i(\beta_{1})}(y_{\beta_{1}, s_{1}}, l(i(\beta_{1}), s_{1}))<\varphi^{2}_{i(\beta_{1})}(y_{\beta_{1}, s_{1}}, l(i(\beta_{1}), s))\in C_{e(\alpha),s}.\end{align*} $$

Since we only enumerate witnesses and triggers of nodes of T into $C_{e(\alpha )}$ during the construction, $\varphi ^{2}_{i(\beta _{1})}(y_{\beta _{1}, s_{1}}, l(i(\beta _{1}), s))$ is a trigger or witness of some node $\beta \in T$ with priority strictly lower than $\alpha $ . The $\beta _{1}$ -strategy enumerates some trigger of $\beta $ into $C_{e(\beta _{1})}=C_{e(\alpha )}$ at stage s. From this analysis, we see that $\beta _{1}$ never enumerates triggers from the set $X_{\alpha , s_{0}}$ into $C_{e(\beta _{1})}$ after stage $s_{1}$ . So $\beta _{1}$ uses at most one trigger from $X_{\alpha , s_{0}}$ .

Let $\beta _{2}$ be the first $\mathcal {R}$ -strategy in $\{\beta \in T: \beta \leq \alpha \}\setminus \{\beta _{1}\}$ that acts as in Step (3) or Step (5.n) for some n to enumerate a trigger $x^{k}_{\alpha ,s_{0}}$ into $ C_{e(\beta _{2}),s_{2}}$ at some stage $s_{2}>s_{1}$ . Then there is a unique even number $y_{\beta _{2}, s_{2}}$ such that

$$ \begin{align*}\varphi^{2}_{i(\beta_{2})}(y_{\beta_{2}, s_{2}}, l(i(\beta_{2}), s_{2}))=w_{\alpha,s_{0}} \text{ or } x^{q_{\alpha}}_{\alpha,s_{0}} \in O_{i(\beta_{2}),s_{2}}= C_{e(\beta_{2}),s_{2}},\end{align*} $$

then $e(\beta _{2})=e(\alpha )$ and $k=q_{\alpha }-1$ .

1. (i) If $\varphi ^{2}_{i(\beta _{2})}(y_{\beta _{2}, s_{2}}, l(i(\beta _{2}), s_{2}))=w_{\alpha ,s_{0}}$ , as in the case of $\beta _{1}$ -strategy above, $\beta _{2}$ never enumerates triggers from $X_{\alpha ,s_{0}}$ into $C_{e(\beta _{2})}$ after stage $s_{2}$ .

2. (ii) If $\varphi ^{2}_{i(\beta _{2})}(y_{\beta _{2}, s_{2}}, l(i(\beta _{2}), s_{2}))=x^{q_{\alpha }}_{\alpha ,s_{0}}<w_{\alpha ,s_{0}}$ , the enumeration of $x^{q_{\alpha }-1}_{\alpha ,s_{0}}$ forces $\varphi ^{2}_{i(\beta _{2})}(y_{\beta _{2}, s_{2}}, l(i(\beta _{2}), s))>x^{q_{\alpha }}_{\alpha ,s_{0}}$ if the $\beta _{2}$ -strategy acts as in Step (5.m) for some m to enumerate triggers at some least stage $s>s_{2}$ .

   • • If $\varphi ^{2}_{i(\beta _{2})}(y_{\beta _{2}, s_{2}}, l(i(\beta _{2}), s))>w_{\alpha , s_{0}}$ , then $\beta _{2}$ acts to enumerate a trigger of node $\beta $ with $\beta>\alpha $ at stage s.

   • • If $\varphi ^{2}_{i(\beta _{2})}(y_{\beta _{2}, s_{2}}, l(i(\beta _{2}), s))=w_{\alpha , s_{0}}$ , then $\beta _{2}$ acts to enumerate the largest unused trigger $x^{k}_{\alpha , s_{0}}$ at stage s.

   Therefore, the $\beta _{2}$ -strategy requires at most two triggers from $X_{\alpha , s_{0}}$ into $C_{e(\beta _{2})}$ after stage $s_{0}$ .

Let $\beta _{3}$ be the first $\mathcal {R}$ -strategy in $\{\beta \in T: \beta \leq \alpha \}\setminus \{\beta _{1}, \beta _{2}\}$ that acts as in Step (3) or Step (5.n) for some n to enumerate a trigger $x^{k}_{\alpha ,s_{0}}$ into $ C_{e(\beta _{3}),s_{3}}$ at some stage $s_{3}>s_{2}$ . Then there is a unique even number $y_{\beta _{3}, s_{3}}$ such that

$$ \begin{align*}\varphi^{2}_{i(\beta_{3})}(y_{\beta_{3}, s_{3}}, l(i(\beta_{3}), s_{3}))=w_{\alpha,s_{0}} \text{ or } x^{k}_{\alpha,s_{0}} \in O_{i(\beta_{3}),s_{3}}= C_{e(\beta_{3}),s_{3}}=C_{e(\alpha), s_{3}},\end{align*} $$

and there are at most 1+2=3 triggers $x^{k}_{\alpha ,s_{0}}\in C_{e(\alpha ), s_{3}} $ . Now it requires at most 4 enumerations of new triggers from $X_{\alpha , s_{0}}$ into $C_{e(\beta _{3})}=C_{e(\alpha )}$ to force the number of predecessors of $y_{\beta _{3}, s_{3}}$ approximated by $\varphi ^{2}_{i(\beta _{3})}$ , namely, $\varphi ^{2}_{i(\beta _{3})}(y_{\beta _{3}, s_{3}}, \cdot )$ , to exceed $w_{\alpha , s_{0}}$ . The total number of triggers from $X_{\alpha , s_{0}}$ used by $\beta _{1}, \beta _{2}$ and $\beta _{3}$ is at most $1+2+2^{2}=2^{3}-1$ .

Generally, for $m\geq 2$ , suppose that $\beta _{m}$ is the first $\mathcal {R}$ -strategy in $\{\beta \in T: \beta \leq \alpha \}\setminus \{\beta _{1}, \ldots , \beta _{m-1}\}$ that acts as in Step (3) or Step (5.n) for some n to enumerate a trigger $x^{k}_{\alpha ,s_{0}}$ into $ C_{e(\beta _{m}),s_{m}}$ at some stage $s_{m}>s_{m-1}$ . Then there is a unique even number $y_{\beta _{m}, s_{m}}$ such that

$$ \begin{align*}\varphi^{2}_{i(\beta_{m})}(y_{\beta_{m}, s_{m}}, l(i(\beta_{m}), s_{m}))=w_{\alpha,s_{0}} \text{ or } x^{k}_{\alpha,s_{0}} \in O_{i(\beta_{m}),s_{m}}= C_{e(\beta_{m}),s_{m}}=C_{e(\alpha), s_{m}},\end{align*} $$

and there are at most $1+2+\ldots +2^{m-2}=2^{m-1}-1$ triggers $x^{k}_{\alpha ,s_{0}}\in C_{e(\alpha ), s_{m}} $ . Since the value of $\varphi ^{2}_{i(\beta _{m})}(y_{\beta _{m}, s_{m}}, l(i(\beta _{m}), s_{m}))$ has at most $2^{m-1}$ many possible choices, it requires at most $2^{m-1}$ many enumerations of new triggers from $X_{\alpha , s_{0}}$ into $C_{e(\beta _{m})}=C_{e(\alpha )}$ to force the number of predecessors of $y_{\beta _{m}, s_{m}}$ to exceed $w_{\alpha , s_{0}}$ . So the total number of triggers from $X_{\alpha , s_{0}}$ used by $\beta _{1},\ldots , \beta _{m}$ is at most $1+2+\ldots +2^{m-1}=2^{m}-1$ .

Since the number of nodes of length $\leq |\alpha |$ in the priority tree T is strictly less than

$$ \begin{align*}1+3+\ldots+3^{|\alpha|}=\frac{3^{|\alpha|+1}-1}{2}<3^{|\alpha|+1},\end{align*} $$

the number of higher priority nodes $\beta \in T$ with $\beta \leq \alpha $ is strictly less than $3^{|\alpha |+1}$ , and we have $m< 3^{|\alpha |+1}$ . This implies that the total number of triggers from $X_{\alpha , s_{0}}$ used by all higher priority $\mathcal {R}$ -strategies $\beta $ with $\beta \leq \alpha $ is strictly less than

$$ \begin{align*}1+2+\ldots +2^{3^{|\alpha|+1}-1}=2^{3^{|\alpha|+1}}-1<2^{3^{|\alpha|+1}}=q_{\alpha}.\end{align*} $$

Therefore, we appoint enough trigger elements $x^{k}_{\alpha ,s_{0}}$ on node $\alpha $ for higher priority $\beta $ -strategies to enumerate into $C_{e(\beta )}=C_{e(\alpha )}$ during the construction. That is, the trigger elements in Step (3) or Step (5.n) of a basic $\alpha $ -strategy initiated at stage $s_{0}$ always exist if needed. This completes the proof of the lemma.

Let $\mathrm {TP}=\liminf _{s}\delta _{s}$ be the leftmost path on T visited infinitely often during the construction, called the true path of the construction. That is, for any $n\geq 1$ , the node $\mathrm {TP}\upharpoonright _{n}=\mathrm {TP}(0)\ldots \mathrm {TP}(n-1)\in T$ is visited infinitely often, but any node $\alpha <_{L} \mathrm {TP}\upharpoonright _{n}$ is visited finitely often during the construction.

Proof. For fixed numbers $e, i$ , let $\alpha $ be the unique $\mathcal {P}_{\langle e, i\rangle }$ -strategy along the true path $\mathrm {TP}$ of the construction, then $\alpha $ is initialized finitely often, and there are infinitely many $\alpha $ -stages during the construction. Suppose that $\alpha $ has the highest priority after some least stage $s_{\alpha }$ . The $\alpha $ -strategy acts to diagonalize against $\varphi _{i}$ computing $C_{e}$ after stage $s_{\alpha }$ .

1. (i) If the strategy waits at Step (2) forever after certain stage, then there is a witness w such that either $\varphi _{i}(w)$ diverges or it converges with $\varphi _{i}(w)\downarrow =1\neq C_{e}(w)=0$ ; in this case, $\alpha $ has true outcome $ f$ .

2. (ii) If the strategy arrives at Step (2) and acts as in Step (3) at some stage $s>s_{\alpha }$ , then there is a witness w such that $\varphi _{i}(w)\downarrow =0\neq C_{e}(w)=1$ ; in this case, $\alpha $ has true outcome $ d$ .

The $\alpha $ -strategy succeeds to ensure that $C_{e}\neq \varphi _{i}$ after stage $s_{\alpha }$ . Then $C_{e}\neq \varphi _{i}$ for all i, and thus it is not computable.

Lemma 4. For all e, $e\in \mathrm {Cof}^{K}$ if and only if $C_{e}$ is order-computable.

Proof. Fix a number e. If $e\in \mathrm {Cof}^{K}$ , $W^{K}_{e}$ is cofinite. Then there exists a number i such that $[i, \infty )\subseteq W^{K}_{e}$ , that is, $[i, i+j+1] \subseteq W^{K}_{e}$ for all j. For any node $\alpha $ assigned an $\mathcal {R}_{\langle e, i,\cdot \rangle }$ -requirement on the priority tree, there are only finitely many $\alpha $ -expansionary stages. For each j, there is a unique node $\alpha _{\langle e, i,j\rangle }$ working for $\mathcal {R}_{\langle e, i,j\rangle }$ along the true path $\mathrm {TP}$ of the construction such that

$$ \begin{align*}{\alpha_{\langle e, i,0\rangle}}^{\smallfrown}f\subset{\alpha_{\langle e, i,1\rangle}}^{\smallfrown}f\subset\ldots \subset{\alpha_{\langle e, i,j\rangle}}^{\smallfrown}f \subset\ldots\subset \mathrm{TP}.\end{align*} $$

For each j, the $\alpha _{\langle e, i,j\rangle }$ -strategy is not initialized after certain stage $s_{j}$ . Then $s_{0}\leq s_{1}\leq \ldots \leq s_{j}\leq \ldots $ because of the priority of the strategies. $\alpha _{\langle e, i,j\rangle }$ acts at most once to appoint a new $C_{e}$ -restraint $\phi ^{C_{e}}_{j}(j)[s]$ to preserve the believable computation $\Phi ^{C_{e}}_{j}(j)[s]$ if it newly converges at some stage $s\in (s_{j}, s_{j+1}]$ . Since the computation $\Phi ^{C_{e}}_{j}(j)[s]\downarrow $ is believable, all higher priority $\mathcal {R}$ -strategies $\beta $ with $\beta ^{\smallfrown } \infty \subset \alpha _{\langle e, i,j\rangle }$ only enumerate triggers $x^{k}_{\beta ', s'}$ of nodes $\beta '>\alpha _{\langle e, i, j\rangle }$ at any stage $s'\geq s$ such that $x^{1}_{\beta ', s'}>\phi ^{C_{e}}_{j}(j)[s]$ , the use of the believable computation. Then the computation $\Phi ^{C_{e}}_{j}(j)[s]\downarrow $ is not injured by $\beta $ -strategy after stage s, and thus, it is preserved forever. Then $C^{\prime }_{e}$ is a $\Delta ^{0}_{2}$ set because for all j, $j\in C^{\prime }_{e}$ if and only $\Phi ^{C_{e}}_{j}(j)$ converges if and only if there are infinitely many stages s such that the computation $\Phi ^{C_{e}}_{j}(j)[s]\downarrow $ is believable. Therefore, $C_{e}$ is a low c.e. set, and thus, it is order-computable.

If $e\notin \mathrm {Cof}^{K}$ , $W^{K}_{e}$ is not cofinite. Now for all i, there is a least number $j_{i}$ such that $[i, i+j_{i}+1]\nsubseteq W^{K}_{e}$ . For all i, there are only finitely many nodes for $\mathcal {R}_{\langle e, i,\cdot \rangle }$ -requirements along the true path $\mathrm {TP}$ of the construction, one node $\alpha _{\langle e, i,j\rangle }$ for $\mathcal {R}_{\langle e, i,j\rangle }$ with $0\leq j\leq j_{i}$ such that each $\alpha _{\langle e, i,j\rangle }$ with $j<j_{i}$ has the finite outcome f and the longest node $\alpha _{\langle e, i,j_{i}\rangle }$ has an infinite outcome $o\in \{d,\infty \}$ . That is,

$$ \begin{align*}{\alpha_{\langle e, i,0\rangle}}^{\smallfrown}f\subset{\alpha_{\langle e, i,1\rangle}}^{\smallfrown}f\subset\ldots \subset{\alpha_{\langle e, i,j_{i}-1\rangle}}^{\smallfrown}f\subset {\alpha_{\langle e, i,j_{i}\rangle}}^{\smallfrown}o\subset \mathrm{TP}.\end{align*} $$

Let $\alpha =\alpha _{\langle e, i,j_{i}\rangle }$ be the $\mathcal {R}_{\langle e, i, j_{i}\rangle }$ -strategy along the true path $\mathrm {TP}$ of the construction, then $\alpha $ is initialized finitely often, and there are infinitely many $\alpha $ -expansionary stages. $\alpha $ has the highest priority after certain stage $s_{\alpha }$ . After stage $s_{\alpha }$ , the $\alpha $ -strategy acts to diagonalize against $\varphi ^{2}_{i}$ to be a computable predecessor approximation function for $C_{e}$ .

1. (i) If the strategy waits at Step (2) or Step (4.n) forever after certain stage, then either $\lim _{s}l(i,s)<\infty $ or $C_{e}\neq O_{i}$ , the order-computable set computed by $\varphi ^{2}_{i}$ ; in this case, $\alpha $ has true outcome d, and $\alpha ^{\smallfrown } d\subset \mathrm {TP}$ .

2. (ii) If the strategy first arrives at Step (2) and then arrives at Step (4. $(n+1)$ ) from Step (5.n) infinitely often, then there is an even number y such that $\lim _{s}\varphi ^{2}_{i}(y,s)=\infty $ ; in this case, $\alpha $ has true outcome $\infty $ , and $\alpha ^{\smallfrown }\infty \subset \mathrm {TP}$ .

The $\alpha $ -strategy succeeds in ensuring that $C_{e}$ is not order-computed by $\varphi ^{2}_{i}$ after stage $s_{\alpha }$ . Then $C_{e}$ is not order-computed by $\varphi ^{2}_{i}$ for all i, and thus it is not order-computable.

We have constructed a uniform sequence of c.e. sets $\langle C_{e}: e\in \mathbb {N}\rangle $ such that $e\in \mathrm {Cof}^{K}$ if and only if $ C_{e}$ is order-computable for all e. Since $\mathrm {Cof}^{K}$ is $\Sigma ^{0}_{4}$ -complete, so is the index set of c.e. order-computable sets. This completes the proof of Theorem 1.