Observation 2.2 If g is total, then $g\leq _Tf$ if and only if $g\leq _{\mathrm {subT}} f$ .

Observation 2.4 Any partial function $f\colon \subseteq \omega \to \omega $ is subTuring equivalent to a partial binary function $G_f\colon \subseteq \omega \to 2$ .

Proof Let $G_f$ be the graph of f in the following sense:

$$\begin{align*}G_f(n,m)= \begin{cases} 1 & \text{ if }{f(n)\downarrow}=m\\ 0 & \text{ if }{f(n)\downarrow}\not=m\\ \uparrow & \text{ if }f(n)\uparrow. \end{cases} \end{align*}$$

For $G_f\leq _{\mathrm {subT}} f$ , to compute $G_f(n,m)$ , just ask for the value of $f(n)$ , where $(n,m)\in \mathrm {dom}(G_f)$ implies $n\in \mathrm {dom}(f)$ . For $f\leq _{\mathrm {subT}} G_f$ , to compute $f(n)$ , ask for the values of $G_f(n,0),G_f(n,1),G_f(n,2),\dots $ , where $n\in \mathrm {dom}(f)$ implies $(n,m)\in \mathrm {dom}(G_f)$ for any m. If $n\in \mathrm {dom}(f),$ then the answer $G(n,k)=1$ will be returned at some point, so we can output k at that time.

Observation 2.5 $\leq _{\mathrm {subT}}$ is transitive.

Proof Assume that $f\leq _{\mathrm {subT}} g\leq _{\mathrm {subT}} h$ . Then, we get $f\subseteq \Phi [g]$ and $g\subseteq \Psi [h]$ . By monotonicity, we get $f\subseteq \Phi [g]\subseteq \Phi [\Psi [h]]$ . By composing the two sequential computations, we get $f\leq _{\mathrm {subT}} h$ .

Observation 2.6 The least subTuring degree consists of exactly those functions with a partial computable extension.

Observation 2.7 If the domain of $f\colon \subseteq \omega \to \omega $ is c.e. relative to a total function $g\colon \omega \to \omega $ , then $f\oplus g$ has a total subTuring degree.

Proof Let $D_s$ be the stage s approximation of the domain of f with respect to its g-computable enumeration. Define $\tilde {f}(n,s)=f(n)+1$ if $n\in D_s$ ; otherwise, $\tilde {f}(n,s)=0$ . Then, $\tilde {f}\oplus g$ is total. Obviously, $\tilde {f}\oplus g\leq _{\mathrm {subT}} f\oplus g$ . For $f\oplus g\leq _{\mathrm {subT}}\tilde {f}\oplus g$ , to compute $f(n)$ , search for s such that $\tilde {f}(n,s)>0$ .

Fact 1 [Reference Faber and van Oosten6, Corollary 2.13]

Every realizability subtopos of the effective topos is equivalent to one of the form $\mathsf {RT}(K_1[f])$ for some partial function f on the natural numbers.

Moreover, there is an inclusion of toposes $\mathsf {RT}(K_1[f])\hookrightarrow \mathsf {RT}(K_1[g])$ if and only if $g\leq _{\mathrm {subT}} f$ .

Proof The join is given by $f\oplus g$ . The meet $f\cap g$ is defined as follows:

$$\begin{align*}(f\cap g)(d,e,n)= \begin{cases} \Phi_d[f](n)&\text{ if }{\Phi_d[f](n)\downarrow}={\Phi_e[g](n)\downarrow}\\ \uparrow&\text{ otherwise}. \end{cases} \end{align*}$$

For $f\cap g\leq _{\mathrm {subT}} f$ , to compute $(f\cap g)(d,e,n)$ , simulate $\Phi _d[f](n)$ . If $(d,e,n)\in \mathrm {dom}(f\cap g),$ then $\Phi _d[f](n)\downarrow $ by definition, so any queries made during the computation are contained within the domain of f. The same applies to $f\cap g\leq _{\mathrm {subT}} g$ .

To show that $f\cap g$ is the greatest lower bound of f and g, assume $h\leq _{\mathrm {subT}} f,g$ . Then, there exist d and e such that $h\subseteq \Phi _d[f],\Phi _e[g]$ . This means that $n\in \mathrm {dom}(h)$ implies ${\Phi _d[f](n)\downarrow }={\Phi _e[g](n)\downarrow }=h(n)$ , so we have $(d,e,n)\in \mathrm {dom}(f\cap g)$ and $(f\cap g)(d,e,n)=h(n)$ . This shows $h\leq _{\mathrm {subT}} f\cap g$ .

Proof Assume that we are given a countable sequence $(g_n)_{n\in \omega }$ of partial functions of increasing subTuring degrees. Let us check that given any upper bound h of $(g_n)_{n\in \omega }$ , we can construct another upper bound f such that $h\not \leq _{\mathrm {subT}} f$ . For this purpose, we construct a strictly increasing sequence $(a_n)_{n\in \omega }$ and guarantee that $f(a_n,x)=g_n(x)$ . Also, let $f(b,x)$ be undefined if $b\not =a_n$ for any $n\in \omega $ . In this case, it is clear that $g_n\leq _{\mathrm {subT}} f$ for any $n\in \omega $ , so we want to guarantee $h\not \leq _{\mathrm {subT}} f$ by choosing $a_n$ appropriately.

We describe a strategy to ensure $h\not \leq _{\mathrm {subT}} f$ via e, i.e., $h\not \subseteq \Phi _e[f]$ . Assume that $(a_n)_{n\leq e}$ has already been constructed and that $f(b,x)$ is determined for any $b\leq a_e$ . At stage e, perform the following actions: Ask if the computation of $\Phi _e[f](n)$ for some input $n\in \mathrm {dom}(h)$ makes a query $(b,x)$ for some $b>a_e$ and $x\in \omega $ .

Case (1): If yes, declare $f(b,x)\uparrow $ . In other words, put $a_{e+1}=b+1$ and proceed to the next stage $e+1$ . In this case, the computation of $\Phi _e[f](n)$ for some $n\in \mathrm {dom}(h)$ makes a query to $(b,x)\not \in \mathrm {dom}(f)$ , which implies $\Phi _e[f](n)\uparrow $ . In particular, we have $h\not \subseteq \Phi _e[f]$ .

Case (2): If no, then do nothing and proceed to the next stage $e+1$ . In this case, only queries whose first coordinates are at most $a_e$ are asked to f during the computation of $\Phi _e[f](n)$ for any $n\in \mathrm {dom}(h)$ . By our definition of f, using $g_0\oplus \dots \oplus g_e$ , one can easily compute $f(b,x)$ for any $b\leq a_e$ and $x\in \omega $ . In other words, $f\upharpoonright (a_e+1)\times \omega \leq _{\mathrm {subT}} g_0\oplus \dots \oplus g_e\leq _{\mathrm {subT}} g_e$ . By assumption, we have $h\not \leq _{\mathrm {subT}} g_e$ , so $h\not \leq _{\mathrm {subT}} f\upharpoonright (a_e+1)\times \omega $ . However, the computation of $\Phi _e[f]$ is performed by accessing only to $f\upharpoonright (a_e+1)\times \omega $ , so computing h must have failed somewhere. Hence, we get $h\not \subseteq \Phi _e[f]$ .

Proof Assume that we are given a countable sequence $(g_n)_{n\in \omega }$ of partial functions of decreasing subTuring degrees. Let us check that given any lower bound h of $(g_n)_{n\in \omega }$ , we can construct another lower bound $f\not \leq _{\mathrm {subT}} h$ . Now, instead of $g_n$ , consider $g_n^\ast =g_0\cap \dots \cap g_n$ . For simplicity, we can assume that an input of $g_n^\ast $ is of the form $(e_0,\dots ,e_n,x)$ . That is, $g_n^\ast (e_0,\dots ,e_n,x)$ is the common value of $\Phi _{e_0}[g_0](x),\dots ,\Phi _{e_n}[g_n](x)$ if it is defined. In particular, we have $\mathrm {dom}(g_n^\ast )\subseteq \omega ^{n+2}$ , so we can assume that the domains of $g_n^\ast $ ’s are pairwise disjoint. We construct a strictly increasing sequence $(a_n)_{n\in \omega }$ such that $a_n\in \mathrm {dom}(g_n^\ast )$ and define $f(a_n)=g_n^\ast (a_n)$ . Also, let $f(b)$ be undefined if $b\not =a_n$ for any $n\in \omega $ .

First, let us check $f\leq _{\mathrm {subT}} g_n^\ast $ no matter how we choose $(a_n)_{n\in \omega }$ . For each $m\geq n$ , if $a_m$ is of the form $\langle e_0,\dots ,e_m,x\rangle $ and $f(a_m)\downarrow $ , then the value of $f(a_m)$ is the common value of $\Phi _{e_0}[g_0](x),\dots ,\Phi _{e_m}[g_m](x)$ , which is especially the common value of $\Phi _{e_0}[g_0](x),\dots ,\Phi _{e_n}[g_n](x)$ . Therefore, it follows that $f(a_m)=g_m^\ast (e_0,\dots ,e_m,x)=g_n^\ast (e_0,\dots ,e_n,x)$ . In this way, using $g_n^\ast $ , one can compute f except for finitely many values, so we obtain $f\leq _{\mathrm {subT}} g_n^\ast $ . Now, we want to guarantee $f\not \leq _{\mathrm {subT}} h$ by choosing $a_n$ appropriately.

We describe a strategy to ensure $f\not \leq _{\mathrm {subT}} h$ via e, i.e., $f\not \subseteq \Phi _e[h]$ . Assume that $(a_n)_{n<e}$ has already been constructed. At stage e, perform the following actions: Find $a_{e}\in \mathrm {dom}(g_e)$ such that $a_{e}>a_{e-1}$ and $\Phi _e[h](a_{e})\not =g_e^\ast (a_{e})$ . Since $g_e^\ast \not \leq _{\mathrm {subT}} h$ by assumption, such $a_{e}$ must exist. Then proceed to the next stage $e+1$ . Note that $a_{e}\in \mathrm {dom}(g_e)$ implies $a_{e}\in \mathrm {dom}(f)$ by definition. Therefore, our strategy ensures $\Phi _e[h](a_e)\not =f(a_e)$ , which implies $f\not \subseteq \Phi _e[h]$ .

Observation 3.6 $K_0$ is not monotone.

Proof Observe $\chi _{\mathrm {dom}(f)}\leq _{\mathrm {subT}} K_0(f)$ . This is because if $\Phi _{d(n)}$ is a computation that asks the query n and halts regardless of the solution, then being $n\in \mathrm {dom}(f)$ and $\Phi _{d(n)}^f(d(n))$ halting are equivalent, which is equivalent to $d(n)\in K_0(f)(d(n))$ .

If f is a total function, then $f\upharpoonright A\leq _{\mathrm {subT}} f$ for any A. Let us take A such that $\chi _A\not \leq _{\mathrm {subT}} K_0(f)$ . If $K_0$ is monotone, then we get $\chi _A\leq _{\mathrm {subT}} K_0(f\upharpoonright A)\leq _{\mathrm {subT}} K_0(f)$ , which is a contradiction.

Proof (1) One can easily find an index $i(n)$ such that $\Phi _{i(n)}[f](x)$ simulates $f(n)$ no matter what f and x are. Then, we have $f(n)=K(f)(i(n))$ ; hence, $f\leq _{\mathrm {subT}} K(f)$ via an index of $\lambda n.i(n)$ .

(2) Assume $f\leq _{\mathrm {subT}} g$ via d; that is, $f\subseteq \Phi _d[g]$ . If $e\in \mathrm {dom}(K(f))$ , $\Phi_e[f](e)$ makes queries only within the domain of f. Therefore, the replies to these queries by f and $\Phi _d[g]$ are identical. That is, $\Phi _e[f](e)$ and $\Phi _e[\Phi _d[g]](e)$ perform the same computation, especially whether they halt or not. One can effectively find an index $b(d,e)$ such that $\Phi _{b(d,e)}[g](x)$ simulates $\Phi _e[\Phi _d[g]](e)$ no matter what g and x are. Then, we get $K(f)(e)=K(g)(b(d,e))$ . Consequently, $f\leq _{\mathrm {subT}} g$ via d implies $K(f)\leq _{\mathrm {subT}} K(g)$ via an index of $\lambda e.b(d,e)$ .

(3) If f is total, then so is $K(f)$ . Thus, $K(f)=K_0(f)=f'$ .

Proof Assume $J(f)\leq _{\mathrm {subT}} f$ . Let $\mathcal {O}$ be Kleene’s system of ordinal notations [Reference Chong and Liang3], and let $a\in \mathcal {O}$ . We use $\emptyset ^{(a)}$ to denote the iterated Turing jump of $\emptyset $ along the notation a. If $a=2^b$ and $\emptyset ^{(b)}\leq _{\mathrm {subT}} f$ via $p_b$ , then by monotonicity and conservativity, we have $\emptyset ^{(a)}\equiv _{\mathrm {subT}}J(\emptyset ^{(b)})\leq _{\mathrm {subT}} J(f)\leq _{\mathrm {subT}} f$ via some index $p_a$ . By uniformity, $p_b\mapsto p_a$ is computable. If $a=3\cdot 5^e$ and $\emptyset ^{(\varphi _e(n))}\leq _{\mathrm {subT}} f$ via $p_{\varphi _e(n)}$ for any $n\in \omega $ , then whenever the sequence $(p_{\varphi _e(n)})_{n\in \omega }$ is computable, we have $\emptyset ^{(a)}=\bigoplus _{n\in \omega }\emptyset ^{(\varphi _e(n))}\leq _{\mathrm {subT}} f$ via some index $p_a$ , where $(p_{\varphi _e(n)})_{n\in \omega }\mapsto p_a$ is computable. Hence, by effective transfinite induction, we get $\emptyset ^{(a)}\leq _{\mathrm {subT}} f$ for any $a\in \mathcal {O}$ .

Proof Let $\theta _e^\Sigma $ and $\theta _e^\Pi $ be the eth $\Sigma ^1_1$ sentence and the eth $\Pi ^1_1$ sentence, respectively. Define $\psi $ as follows:

$$\begin{align*}\psi(a,b)= \begin{cases} 1&\text{ if both } \theta_a^\Sigma \text{ and } \theta_b^\Pi \text{ are true}\\ 0&\text{ if both } \theta_a^\Sigma \text{ and } \theta_b^\Pi \text{ are false}\\ \uparrow&\text{ otherwise.} \end{cases} \end{align*}$$

We claim $K(\psi )\leq _{\mathrm {subT}}\psi $ . To see this, we simulate the computation of $\Phi _e[\psi ](e)$ for given $e\in \mathrm {dom}(K(\psi ))$ . The history of the computation of $\Phi _e[\psi ](e)$ of length s is a sequence $(i_0,q_0,a_0,i_1,q_1,a_1,\dots ,i_s,q_s)$ such that, for any $k<s$ , $i_k=0,$ and ${\Phi _e(e,a_0,\dots ,a_k)\downarrow }=\langle i_{k+1},q_{k+1}\rangle $ , and if $q_k=\langle u,v\rangle ,$ then

(3.1) $$ \begin{align} \text{either } (\theta_u^\Sigma \text{ is true and } a_k=1) \text{ or } (\theta_v^\Pi \text{ is false and } a_k=0). \end{align} $$

This gives a $\Sigma ^1_1$ -description of being a history of some computation. If $e\in \mathrm {dom}(K(\psi ))$ , then we must have $q_k=\langle u,v\rangle \in \mathrm {dom}(\psi )$ , which means that the truth values of $\theta _u^\Sigma $ and $\theta _v^\Pi $ are the same. Thus, the condition (3.1) can be changed to the following:

(3.2) $$ \begin{align} \text{either } (\theta_v^\Pi \text{ is true and } a_k=1) \text{ or } (\theta_u^\Sigma \text{ is false and } a_k=0). \end{align} $$

This gives a $\Pi ^1_1$ -description of being a history of some computation. Now, $\Phi _e[\psi ](e)$ halts if and only if there exists a sequence which is the history of $\Phi _e[\psi ](e)$ of some length s such that $i_s=1$ . This is described just by adding existential quantifiers on natural numbers, so this also has $\Sigma ^1_1$ -description $\theta _{c(e)}^\Sigma $ and $\Pi ^1_1$ -description $\theta _{d(e)}^\Pi $ . Therefore, for $e\in \mathrm {dom}(K(\psi ))$ , whether $\Phi _e[\psi ](e)$ halts or not can be decided by looking at the value of $\psi (c(e),d(e))$ . This verifies the claim.

Question 1 Does there exist a uniformly inflationary, uniformly monotone, uniformly conservative, strict operator on the subTuring degrees?

Proof Assume that $g\leq _{\mathrm {subT}} (f\upharpoonright A)\oplus \beta $ via a partial computable function $\Phi $ . By monotonicity, we have $g\subseteq \Phi [(f\upharpoonright A)\oplus \beta ]\subseteq \Phi [f\oplus \beta ]$ , so there is no difference between the computation of $\Phi [(f\upharpoonright A)\oplus \beta ]$ and $\Phi [f\oplus \beta ]$ for input $n\in \mathrm {dom}(g)$ . Now, look at the queries $q_0,q_1,\dots $ made during the computation of $\Phi [f\oplus \beta ](n)$ , take out the even queries $2p_0,2p_1,\dots $ (i.e., the queries asking to f), and put $Q_n=\{p_0,p_1,\dots \}$ , which is the set of queries asking to f. If $\Phi [f\oplus \beta ](n)\downarrow $ , the set $Q_n$ is clearly $(f\oplus \beta )$ -c.e. uniformly in n. Furthermore, since $g\subseteq \Phi [(f\upharpoonright A)\oplus \beta ]$ , the queries to f that we make for input $n\in \mathrm {dom}(g)$ must be contained in $\mathrm {dom}(f\upharpoonright A)=A$ ; that is, if $n\in \mathrm {dom}(g)$ , then $Q_n\subseteq A$ . Consider $Q=\bigcup \{Q_n:n\in \mathrm {dom}(g)\}$ , which is an $(\alpha \oplus \beta \oplus f)$ -c.e. subset of A. By immunity, Q is finite. Since this is all the queries to f during the computation of g by $\Phi $ , we obtain $g\subseteq \Phi [(f\upharpoonright Q)\oplus \beta ]$ . However, since $f\upharpoonright Q$ is a finite function, it is computable, so we get $g\leq _{\mathrm {subT}}\beta $ as desired.

Proof Let $f\colon \subseteq \omega \to \omega $ be a non-computable function. By Lemma 4.2, if A is f-immune then every total function $g\leq _{\mathrm {subT}} f\upharpoonright A$ is computable. We also have $f\upharpoonright A\leq _{\mathrm {subT}} f$ . Therefore, it suffices to construct an f-immune set A such that $f\upharpoonright A$ is not computable.

At stage e, perform the following actions with auxiliary parameters $u_e$ and $r_e$ :

1. (1) Assume that $A\upharpoonright r_e$ has already been determined. Search for $n>r_e$ such that either $\varphi _e(n)\uparrow $ or $\varphi _e(n)\not =f(n)$ . Note that such an n always exists; otherwise, ${\varphi _e(n)\downarrow }=f(n)$ for any $n>r_e$ , which implies that f is computable, a contradiction. Choose such an n, declare $n\in A$ , and put $u_{e}=n+1$ .

2. (2) Search for $n>u_e$ such that $n\in W_e^f$ , where $W_e^f$ is the eth c.e. set relative to f. If $W_e^f$ is infinite, such an n exists. For such an n, declare $n\not \in A$ , and put $r_{e+1}=n+1$ . If there is no such n, put $r_{e+1}=u_e$ .

By the action (1), for any $e,$ we have $\varphi _e(n)\not =f(n)$ for some $n\in A$ , so $f\upharpoonright A$ is non-computable. By the action (2), the final obtained A is f-immune. Thus, by the argument above, $f\upharpoonright A$ is quasiminimal.

Proof Let $f,g\colon \subseteq \omega \to \omega $ be such that $g<_{\mathrm {subT}} f$ . Assume that the domain of g is $\alpha $ -c.e. As in the proof of Proposition 4.3, one can easily construct an $(\alpha \oplus f)$ -immune set A such that $f\upharpoonright A\not \leq _{\mathrm {subT}} g$ (by using the assumption $f\not \leq _{\mathrm { subT}} g$ ). Then, we have $f\not \leq _{\mathrm {subT}} (f\upharpoonright A)\oplus g$ ; otherwise, by Lemma 4.2, $f\leq _{\mathrm {subT}} (f\upharpoonright A)\oplus g$ implies $f\leq _{\mathrm {subT}} g$ , a contradiction. Consequently, we get $g<_{\mathrm {subT}}(f\upharpoonright A)\oplus g<_{\mathrm {subT}}f$ .

Proof The proof is almost the same as the proof of Proposition 4.3. Let $f,g\colon \subseteq \omega \to \omega $ be such that $g<_{\mathrm {subT}} f$ , and assume that the domain of g is $\alpha $ -c.e. We construct a family $\{A_x\}_{x\in 2^\omega }$ of continuum many subsets of $\omega $ such that each $A_x$ is $(\alpha \oplus A_y\oplus f)$ -immune for any $y\not =x$ . Moreover, we ensure that $f\upharpoonright A_x\not \leq _{\mathrm {subT}} g$ for any $x\in 2^\omega $ . Assuming that we could construct such a family, consider $h_x=(f\upharpoonright A_x)\oplus g$ for any $x\in 2^\omega $ . If $x\not =y$ , by Lemma 4.2, $h_y\leq _{\mathrm {subT}} h_x$ would imply $f\upharpoonright A_y\leq _{\mathrm {subT}} g$ , which is impossible by our assumption on $\{A_x\}_{x\in 2^\omega }$ . Hence, $\{h_x\}_{x\in 2^\omega }$ gives an antichain of continuum many subTuring degrees. Moreover, as in Theorem 4.1, one can also see that $g<_{\mathrm {subT}}h_x<_{\mathrm {subT}}f$ . Therefore, it suffices to construct such a family $\{A_x\}_{x\in 2^\omega }$ . What we actually construct is $\{A_\sigma \}_{\sigma \in 2^{<\omega }}$ , and then we define $A_x=\bigcup _{\sigma \prec x}A_\sigma $ .

At stage e, perform the following actions with auxiliary parameters $u_e$ and $r_e$ :

1. (1) Assume that $A_\sigma \upharpoonright r_e$ has already been determined for each $\sigma \in 2^e$ . Search for $n\in \mathrm {dom}(f)$ with $n>r_e$ such that either $\Phi _e[g](n)\uparrow $ or $\Phi _e[g](n)\not =f(n)$ . Note that such an n always exists; otherwise, ${\Phi _e[g](n)\downarrow }=f(n)$ for any $n\in \mathrm {dom}(f)$ with $n>r_e$ , which implies that $f\leq _{\mathrm {subT}} g$ , a contradiction. Choose such an n, declare $n\in A_\sigma $ for any $\sigma \in 2^e$ , and put $u_{e}=n+1$ .

2. (2) There are $2^{e+1}$ substages in the strategy to guarantee relative immunity. At substage $0$ , put $u^0_e=u_e$ . At substage $t<2^{e-1}$ , we focus on the t-th string $\sigma {}^\smallfrown i\in 2^{e+1}$ . Search for a finite string $\rho $ extending $A_\sigma \upharpoonright u_e^t$ and a number $n>u_e^t$ such that $n\in W_e^{\alpha \oplus \rho \oplus f}$ . If such $\rho $ and n exist, then declare that $A_{\sigma {}^\smallfrown i}$ extends $\rho $ , and protect $A_{\sigma {}^\smallfrown i}\upharpoonright |\rho |+1$ . Moreover, declare $n\not \in A_\tau $ for any string $\tau \not =\sigma {}^\smallfrown i$ of length $e+1$ . This means that we put $u_e^{t+1}=\max \{|\rho |,n\}+1$ . If there exist no such $\rho $ and n, put $A_{\sigma {}^\smallfrown i}=A_\sigma $ and $u_e^{t+1}=u_e$ . If $t=2^{e+1}-1,$ then put $r_e=u_e^{t+1}$ .

Finally, we define $A_x=\bigcup _{\sigma \prec x}A_\sigma $ for any $x\in 2^\omega $ . By the action (1), we get $f\upharpoonright A_\sigma \not \subseteq \Phi _e[g]$ for any $\sigma \in 2^e$ , so $f\upharpoonright A_x\not \subseteq \Phi _e[g]$ since $A_\sigma \subseteq A_x$ for any $x\succ \sigma $ ; hence, $f\upharpoonright A_x\not \leq _{\mathrm {subT}} g$ for any $x\in 2^\omega $ . By the action (2), since $A_x$ extends $A_{x\upharpoonright e+1}\upharpoonright u_e^{t}$ for a suitable t, if $W_e^{\alpha \oplus A_x\oplus f}$ is infinite, we always find $\rho $ and $n>u_e^t$ such that $n\in W_e^{\alpha \oplus \rho \oplus f}$ . If $x\upharpoonright e\not = y\upharpoonright e$ , then the action (2) ensures $n\not \in A_y$ , so we obtain $W_e^{\alpha \oplus A_x\oplus f}\not \subseteq A_y$ . If $x\not =y,$ then there is k such that $x\upharpoonright k\not =y\upharpoonright k$ , so given e, consider $d\geq k$ such that $W_d^{B}=W_e^{B}$ for any B (e.g., add meaningless lines to the program e to pad its size). By the above argument, we get $W_e^{\alpha \oplus A_x\oplus f}=W_d^{\alpha \oplus A_x\oplus f}\not \subseteq A_y$ . Consequently, $A_y$ is $(\alpha \oplus A_x\oplus f)$ -immune.

Proof It suffices to show that, for any partial function h, there exists a quasiminimal f such that $K(f)\leq _{\mathrm {subT}} h\oplus \emptyset '\leq _{\mathrm {subT}} f\oplus \emptyset '$ since $\emptyset '\leq _{\mathrm {subT}} K(\emptyset )\leq _{\mathrm {subT}} K(f)$ by monotonicity and conservativity. Let us construct a $\emptyset '$ -computable increasing sequence $(a_k)_{k\in \omega }$ of natural numbers. This is the coding location of h in f; that is, we define $f(a_k)=h(k)$ for each $k\in \omega $ and let f be undefined except on $\{a_k\}_{k\in \omega }$ .

Assume that $(a_k)_{k<e}$ has already been defined. For each partial function $\sigma $ defined only on $\{a_k\}_{k<e}$ , ask $\emptyset '$ if the computation of $\Phi _e[\sigma ](e)$ makes a query greater than $a_{e-1}$ . If so, let $q_\sigma $ be the first such query plus $1$ , or else let $q_\sigma =a_{e-1}+1$ . Similarly, ask $\emptyset '$ if there exists n such that the computation of $\Phi _e[\sigma ](n)$ makes a query greater than $a_{e-1}$ . If so, let $r_\sigma $ be the first such query plus $1$ , or else let $r_\sigma =a_{e-1}+1$ . Then, let $a_e$ be the maximum value of these $q_\sigma $ and $r_\sigma $ ’s.

This completes the construction. We claim that the computation of $\Phi _e[f](e)$ is determined by $\Phi _e[f\upharpoonright a_{e-1}+1](e)$ . Otherwise, this computation creates a query to f greater than $a_{e-1}$ . The computation is performed by $\Phi _e[f\upharpoonright a_{e-1}+1](e)$ until just before the first such query q is created. Note that the domain of $\sigma :=f\upharpoonright a_{e-1}+1$ is $\{a_k\}_{k<e}$ , so our construction ensures $a_{e-1}<q<q_\sigma \leq a_e$ , which implies $q\not \in \mathrm {dom}(f)$ . Therefore, $\Phi _e[f](e)$ does not halt.

Observe that $(a_k)_{k\in \omega }$ is $\emptyset '$ -computable. Thus, it is clear from the definition of f that $h\leq _{\mathrm {subT}} f\oplus \emptyset '$ and $f\leq _{\mathrm {subT}} h\oplus \emptyset '$ hold. Indeed, the graph of f is computable in $h\oplus \emptyset '$ . We show that $K(f)\leq _{\mathrm {subT}} h\oplus \emptyset '$ . To compute $K(f)(e)$ , first use $h\oplus \emptyset '$ to recover $(a_k)_{k< e}$ and the graph of $f\upharpoonright a_{e-1}+1$ . Ask $\emptyset '$ which of the following is true:

1. (1) $\Phi _e[f\upharpoonright a_{e-1}+1](e)$ makes a query $\leq a_{e-1}$ that is different from any of $\{a_k\}_{k<e}$ , or makes a query that is greater than $a_{e-1}$ .

2. (2) $\Phi _e[f\upharpoonright a_{e-1}+1](e)$ halts.

3. (3) Otherwise. That is, $\Phi _e[f\upharpoonright a_{e-1}+1](e)$ does not halt even though it only makes queries in $\{a_k\}_{k<e}$ .

Since $(a_k)_{k< e}$ and $f\upharpoonright a_{e-1}+1$ are finite, this decision can be performed with the unrelativized halting problem $\emptyset '$ . By the above construction, if (1) holds, $K(f)(e)\uparrow $ ; if (2) holds, $K(f)(e)=1$ ; and if (3) holds, $K(f)(e)=0$ . This shows $K(f)\leq _{\mathrm {subT}} h\oplus \emptyset '$ .

For quasiminimality, if $\Phi _e[f]$ is total, this computation can be simulated by $\Phi _e[f\upharpoonright a_{e-1}+1]$ . Otherwise, $\Phi _e[f\upharpoonright a_{e-1}+1](n)$ for some n makes a query q larger than $a_{e-1}$ , but by the same argument as in Claim above, for $\sigma :=f\upharpoonright a_{e-1}+1$ is $\{a_k\}_{k<e}$ , our construction ensures $a_{e-1}<q<r_\sigma \leq a_e$ , which implies $q\not \in \mathrm {dom}(f)$ . Thus, $\Phi _e[f]$ is computable since this computation uses only finite information on f.

Proof We construct Turing functionals $\Psi $ and $\Delta $ fulfilling the following requirement:

$$\begin{align*}R_e\colon (\forall f,g\in 2^\omega)\;\Psi^f\cap\Delta^g\subseteq\Phi_e^h\implies f\leq_{\mathrm{subT}} h \text{ or }g\leq_{\mathrm{subT}} h.\end{align*}$$

Here, $\Psi ^f\cap \Delta ^g$ is the intersection of $\Psi ^f$ and $\Delta ^g$ when identifying a function with its graph. That is, if (and only if) both $\Psi ^f(n)$ and $\Delta ^g(n)$ converge to the same value, $(\Psi ^f\cap \Delta ^g)(n)$ halts at the value. Obviously, $\Psi ^f\cap \Delta ^g\leq _{\mathrm {subT}} f\cap g$ , so it is sufficient to satisfy this requirement. Rewriting $R_e$ a little more concretely according to the actual strategy, we will ensure the following:

$$\begin{align*}R_e\colon (\forall f,g\in 2^\omega)\;[(\exists n)\;{\Psi^f(n)\downarrow}={\Delta^g(n)\downarrow}\not=\Phi_e^h(n)]\text{ or }f\leq_{\mathrm{subT}} h\text{ or }g\leq_{\mathrm{subT}} h.\end{align*}$$

Strategy: Let us describe the $R_e$ -strategy. The strategy must operate without knowing what f and g are and with all possibilities of $f,g\in 2^\omega $ in mind. This strategy consists of infinitely many substrategies. The $(s,t)$ -th substrategy proceeds as follows:

1. (1) For any f with $f(s)=i$ , put $\Psi ^f(e,s,t,i,j)=0$ . Similarly, for any g with $g(t)=j$ , put $\Delta ^g(e,s,t,i,j)=0$ .

2. (2) Wait for $\Phi _e^h(e,s,t,i,j)\downarrow =0$ for some $i,j<2$ .

   If no such $i,j$ exists, then proceed to the next stage $e+1$ . In this case, $\Psi ^f(e,s,t,f(s),g(t))=\Delta ^g(e,s,t,f(s),g(t))=0\not =\Phi _e^h(e,s,t,f(s),g(t))$ , so the requirement $R_e$ is satisfied.

   If such i and j exist, fix the first pair $i,j$ found.

3. (3) For any f with $f(s)=1-i$ , put $\Psi ^f(e,s,t,i,j)=1$ . Similarly, for any g with $g(t)=1-i$ , put $\Delta ^g(e,s,t,i,j)=1$ .

   Note that for any $f,g$ with $\langle f(s),g(t)\rangle =\langle 1-i,1-j\rangle ,$ then $\Psi ^f(e,s,t,i,j)=\Delta ^g(e,s,t,i,j)=1\not =0=\Phi _e^h(e,s,t,i,j)$ , so the requirement $R_e$ is satisfied.

4. (4) Wait for $\Phi ^h_e(e,s,t,1-i,j)\downarrow =0$ . While waiting, invoke the $\langle s+1,t\rangle $ -th substrategy.

   If we wait forever, for any $f,g$ with $\langle f(s),g(t)\rangle =\langle 1-i,j\rangle $ , then by (1), $\Psi ^f(e,s,t,1-i,j)=\Delta ^g(e,s,t,1-i,j)=0\not =\Phi _e^h(e,s,t,1-i,j)$ , so the requirement $R_e$ is satisfied. Thus, together with (3), we see that $R_e$ is satisfied for any value of $g(t)$ when $f(s)=1-i$ .

5. (5) Suppose that, after waiting for a while, $\Phi ^h_e(e,s,t,1-i,j)\downarrow =0$ occurs. While waiting, the $R_e$ -strategy is still running, so suppose that the substrategy currently in operation is $(s',t)$ (the $(s,t)$ -strategy will be abandoned when t increases, so we may assume that the second coordinate remains at t).

   Once we recognize that we reach (5), if $f(s)=i$ , then put $\Psi ^f(e,s,t,1-i,j)=1$ ; similarly, if $g(s)=1-j$ , then put $\Delta ^g(e,s,t,1-i,j)=1$ . Then stop the currently running substrategy and start a new substrategy $(s',t+1)$ .

   In this case, if $\langle f(s),g(s)\rangle =\langle i,1-j\rangle $ , then $\Psi ^f(e,s,t,1-i,j)=\Delta ^g(e,s,t,1-i,j)=1\not =0=\Phi _e^h(e,s,t,1-i,j)$ , so the requirement $R_e$ is satisfied. Together with (3), we see that $R_e$ is satisfied for any value of $f(s)$ when $g(t)=1-j$ . However, since the fulfillment of the requirement in (4) with $\langle f(s),g(s)\rangle =\langle 1-i,j\rangle $ has been withdrawn, $R_e$ is not satisfied when $g(t)=j$ .

Verification: Let us check that the requirement $R_e$ is satisfied by this construction.

Case 1: If we wait forever for (2) in either substrategy, the requirement $R_e$ is clearly satisfied.

Hereafter, we write i and j chosen in the state (2) of the $(s,t)$ -substrategy as $i_{s,t}$ and $j_{s,t}$ , respectively. Note that $(s,t)\mapsto i_{s,t},j_{s,t}$ is h-computable since the substrategy proceeds in an h-computable process.

Case 2: Consider the case where all substrategies pass through (3) but t converges to a finite value. In this case, for some $s_0$ , the substrategies after $(s_0,t)$ do not reach (5) but wait at (4) and continue to activate the next substrategy. As described in (4), the requirement $R_e$ is satisfied for any value of $g(t)$ when $f(s)=1-i_{s,t}$ . That is, the requirement $R_e$ is not yet satisfied only for $f(s)=i_{s,t}$ for any $s>s_0$ . However, in this case, as $s\mapsto i_{s,t}=f(s)$ is h-computable, one derives $f\leq _{\mathrm {subT}} h$ .

Case 3: Consider the case where t diverges to infinity. In this case, for each t, (5) occurs for $j=j_{s_t,t}$ defined by some substrategy $(s_t,t)$ . As described in (5), the requirement $R_e$ is satisfied for any value of $f(s_t)$ when $g(t)=1-j_{s_t,t}$ . That is, the requirement $R_e$ is not yet satisfied only for $g(t)=j_{s_t,t}$ for any t. Note that one can h-computably recognize what $j_{s_t,t}$ is by waiting for the occurrence of (5), so $t\mapsto j_{s_t,t}$ is h-computable. Thus, in this case, $g\leq _{\mathrm {subT}} h$ is derived and the requirement $R_e$ is satisfied.

Proof We construct partial functions $f\colon \subseteq \omega \times 2\times 2\to \omega $ and $g,h\colon \subseteq \omega \to 2$ such that $(f\oplus g)\cap (f\oplus h)\not \leq _{\mathrm {subT}} f\oplus (g\cap h)$ . It suffices to fulfill the following requirement:

$$\begin{align*}R_e\colon (f\oplus g)\cap (f\oplus h)\not\subseteq\Phi_e[f\oplus (g\cap h)].\end{align*}$$

Given e, we need to find $c,d,x$ such that ${((f\oplus g)\cap (f\oplus h))(c,d,x)\downarrow }\not =\Phi _e[f\oplus (g\cap h)](c,d,x)$ . Given n, consider the following Turing functionals $\Psi _n$ and $\Gamma _n$ :

$$ \begin{align*} \Psi_n[f\oplus g](x)=f(n,g(n),0)& &\Gamma_n[f\oplus h](x)=f(n,h(n),1). \end{align*} $$

If we write indices of $\Psi _n$ and $\Gamma _n$ as $c_n$ and $d_n$ , respectively, we actually guarantee the following requirement:

$$\begin{align*}R_e\colon\exists n,x\;[{\Psi_n[f\oplus g](x)\downarrow}={\Gamma_n[f\oplus h](x)\downarrow}\not=\Phi_e[f\oplus (g\cap h)](c_n,d_n,x)].\end{align*}$$

By the definition of the meet $\cap $ , it is easy to see that this modified requirement implies the first proposed requirement.

Strategy: At stage e, operate the strategy to satisfy the requirement $R_e$ . Inductively, assume that we have constructed finite functions $f_e,g_e,h_e$ and an auxiliary parameter $n_e$ . We also assume that, for any $t<n_e$ , $f_e(t,i,j)$ , $g_e(t)$ and $h_e(t)$ have already been determined, and for any $t\geq n_e$ , $f_e(t,i,j)$ , $g_e(t)$ and $h_e(t)$ are undefined. We refer to a triple of the form $\langle t,i,j\rangle $ as a level t input. Now, let c and d be indices of $\Psi :=\Psi _{n_e}$ and $\Gamma :=\Gamma _{n_e}$ , respectively.

Figure 1:

Overview of the $R_{e}$ -strategy.

This strategy consists of infinitely many rounds. See Figure 1 for the overview of the $R_{e}$ -strategy. First, regarding the computation of $\Phi _e[f\oplus (g\cap h)](c,d,x)$ , we have the following three possibilities:

1. (1a) $\Phi _e[f\oplus (g\cap h)](c,d,x)$ does not make a query, or makes a query only to f, which is of level $<n_e$ .

2. (1b) $\Phi _e[f\oplus (g\cap h)](c,d,x)$ makes a level $\geq n_e$ query to f.

3. (1c) $\Phi _e[f\oplus (g\cap h)](c,d,x)$ makes a query to $g\cap h$ .

Here, in the $(k+1)$ -th round, we ask about the subsequent queries after the query taken up in the $k^{th}$ round. As we will see later, no action is taken when advancing a round, always leaving room for the same action as in the first round. Therefore, follow the discussion as if we were in the first round.

Case (1a): Put $g_{e+1}(n_e)=h_{e+1}(n_e)=0$ , and set the level $n_e$ values of $f_{e+1}$ appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ , whose value is different from $\Phi _e[f_e\oplus (g_e\cap h_e)](c,d,x)$ . Put ${n_{e+1}=n_e+1}$ , and proceed to stage $e+1$ .

Verification: Since $\Phi _e[f_e\oplus (g_e\cap h_e)](c,d,x)$ only makes level $<n_e$ queries to f, the behavior of this computation coincides with $\Phi _e[f\oplus (g\cap h)](c,d,x)$ . By the action of the strategy, we have $\Psi [f\oplus g](x)=f(e,g(n_e),0)=f(e,h(n_e),1)=\Gamma [f\oplus h](x)\downarrow $ , whose value is different from $\Phi _e[f\oplus (g\cap h)](c,d,x)$ . Thus, the requirement $R_e$ is satisfied.

Case (1b): There is a query to f of the form $(m,i,j)$ for some $m\geq n_e$ . Declare $f_{e+1}(m,i,j)\uparrow $ . Put $g_{e+1}(n_e)=h_{e+1}(n_e)=1-i$ . Since $(m,i,j)\not =(n_e,g_{e+1}(n_e),0)$ and $(m,i,j)\not =(n_e,h_{e+1}(n_e),1)$ , one can set the level $n_e$ values of $f_{e+1}$ so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ . Put $n_{e+1}=m+1$ , and proceed to stage $e+1$ .

Verification: $\Phi _s[f\oplus (g\cap h)](d,e,x)$ makes a query $(m,i,j)\not \in \mathrm {dom}(f)$ , so the computation does not halt. We also have $\Psi [f\oplus g](x)=f(n_e,g(n_e),0)=f(n_e,h(n_e),1)=\Gamma [f\oplus h](x)\downarrow $ . Thus, the requirement $R_e$ is satisfied.

Case (1c): The computation makes a query $(a,b,y)$ to $g\cap h$ . By the definition of the meet $g\cap h$ , the oracle’s response to this query is the common value of $\Phi _a[g](y)$ and $\Phi _b[h](y)$ (if defined). Let us now go into the computation processes of $\Phi _a[g](y)$ and $\Phi _b[h](y)$ . We have the following possibilities:

1. (2a) Either $\Phi _a[g](y)$ or $\Phi _b[h](y)$ does not halt, but makes only small queries less than $n_e$ .

2. (2b) Either $\Phi _a[g](y)$ or $\Phi _b[h](y)$ halts after making only small queries less than $n_e$ .

3. (2c) Either $\Phi _a[g](y)$ or $\Phi _b[h](y)$ makes a query larger than $n_e$ .

4. (2d) None of the above; that is, both $\Phi _a[g](y)$ and $\Phi _b[h](y)$ make a query $n_e$ .

Case (2a): Put $g_{e+1}(n_e)=h_{e+1}(n_e)=0$ , and set the values appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ . Put $n_{e+1}=n_e+1$ , and proceed to stage $e+1$ .

Verification: Recall that we are in Case (1c), where $\Phi _e[f\oplus (g\cap h)](c,d,x)$ makes a query $(a,b,y)$ to $g\cap h$ , and we then enter Case (2a), where $\Phi _a[g_e](c)$ or $\Phi _b[h_e](c)$ is undefined, so $(g\cap h)(a,b,y)$ is also undefined. This means that $\Phi _e[f\oplus (g\cap h)](c,d,x)$ is accessing outside the domain of the oracle, so the computation does not halt. By our action, we have $\Psi [f\oplus g](x)=f(n_e,g(n_e),0)=f(n_e,h(n_e),1)=\Gamma [f\oplus h](x)\downarrow $ , so the requirement $R_e$ is satisfied.

Case (2b): In this case, the common value of $\Phi _a[g](c)$ and $\Phi _b[h](c)$ is determined by the current finite information $g_e$ or $h_e$ . Then, proceed to the next round $k+1$ ; that is, resume the computation of $\Phi _e[f\oplus (g\cap h)](c,d,x)$ , and check the conditional branch (1) again for the subsequent queries of the query $(a,b,y)$ taken up this time.

Case (2c): If $\Phi _a$ makes a query $m>n_e$ to g, then declare $g(m)\uparrow $ . Do the same for $\Phi _b$ and h. Put $g_{e+1}(n_e)=h_{e+1}(n_e)=0$ , and set the values appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ . Put $n_{e+1}=n_e+1$ , and proceed to stage $e+1$ .

Verification: Recall that we are in Case (1c), where $\Phi _e[f\oplus (g\cap h)](c,d,x)$ makes a query $(a,b,y)$ to $g\cap h$ , and we then enter Case (2c), where $\Phi _a$ makes a query $m>n_e$ to g. Then, our action ensures $m\not \in \mathrm {dom}(g)$ , so we have $\Phi _a[g](c)\uparrow $ . Do the same for the symmetric case. If $\Phi _a[g_e](c)$ or $\Phi _b[h_e](c)$ is undefined, then $(g\cap h)(a,b,y)$ is also undefined, which means that $\Phi _e[f\oplus (g\cap h)](c,d,x)$ is accessing outside the domain of the oracle, so the computation does not halt. By our action, we have $\Psi [f\oplus g](x)=f(n_e,g(n_e),0)=f(n_e,h(n_e),1)=\Gamma [f\oplus h](x)\downarrow $ , so the requirement $R_e$ is satisfied.

Case (2d): In this case, both $\Phi _a[g](y)$ and $\Phi _b[h](y)$ make only queries less than or equal to $n_e$ . Therefore, depending on the values of $g(n_e)$ and $h(n_e)$ , at most four different computations appear. Looking at these four computations, we have the following possibilities:

1. (3a) Either $\Phi _a[g](y)$ or $\Phi _b[h](y)$ may not halt, depending on the value of $g(n_e)$ or $h(n_e)$ .

2. (3b) Either $\Phi _a[g](y)$ or $\Phi _b[h](y)$ may make a query greater than $n_e$ , depending on the value of $g(n_e)$ or $h(n_e)$ .

3. (3c) $\Phi _a[g](y)$ or/and $\Phi _b[h](y)$ have the possibility of halting computations of different outputs, depending on the value of $g(n_e)$ or/and $h(n_e)$ .

4. (3d) Otherwise, that is, no matter what values $g(n_e)$ and $h(n_e)$ are set to, $\Phi _a[g](y)$ and $\Phi _b[h](y)$ both halts and return the same output, making only queries less than or equal to $n_e$ .

Case (3a): For instance, if setting $g_{e+1}(n_e)=i$ forces $\Phi _a[g_{e+1}](y)$ not to halt, then set $h_{e+1}(n_e)$ to any value. Do the same for the symmetric case. Set the values appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ . Put $n_{e+1}=n_e+1$ , and proceed to stage $e+1$ .

Case (3b): For instance, if setting $g_{e+1}(n_e)=i$ forces $\Phi _a[g_{e+1}](y)$ to make a query $m>n_e$ , then declare $g_{e+1}(m)\uparrow $ , and set $h_{e+1}(n_s)$ to any value. Do the same for the symmetric case. Set the values appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ . Put $n_{e+1}=n_e+1$ , and proceed to stage $e+1$ .

Case (3c): If setting $g_{e+1}(n_e)=i$ and $h_{e+1}(n_e)=j$ force the condition $\Phi _a[g](y)\not =\Phi _b[h](y)$ , then set the values appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ . Put $n_{e+1}=n_e+1$ , and proceed to stage $e+1$ .

Otherwise, put $g^i_{e+1}(n_e)=i$ for each $i<2$ , and assume $\Phi _a[g^0_{e+1}](y)\not =\Phi _a[g^1_{e+1}](y)$ . Then, put $h_{e+1}(n_e)=0$ . Assuming that (3a) does not hold, $\Phi _b[h_{e+1}](y)$ must halt, so $\Phi _b[h_{e+1}](y)\not =\Phi _a[g^i_{e+1}](y)$ for some $i<2$ . Then, put $g_{e+1}=g^i_{e+1}$ for such i. Do the same for the symmetric case. Set the values appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f(n_e,h_{e+1}(n_e),1)$ . Put $n_{e+1}=n_e+1$ , and proceed to stage $e+1$ .

Verification: The requirement $R_e$ is satisfied in Case (3a) for the same reason as (2a), and Case (3b) for the same reason as (2c). The same reasoning can be applied to Case (3c), since we ensure $\Phi _a[g_{e+1}](y)\not =\Phi _b[h_{e+1}](y)$ , which implies $(a,b,y)\not \in \mathrm {dom}(g\cap h)$ .

Case (3d): In this case, the common value of $\Phi _a[g](y)$ and $\Phi _b[h](y)$ is determined by the current finite information $g_e$ or $h_e$ (since the computations ask only for values of $g\upharpoonright n_e+1$ and $h\upharpoonright n_e+1$ by $\neg $ (2c), and the results of these computations do not depend on the values of $g(n_e)$ and $h(n_e)$ ). Then, proceed to the next round $k+1$ ; that is, resume the computation of $\Phi _e[f\oplus (g\cap h)](c,d,x)$ , and check the conditional branch (1) again for the subsequent queries of the query $(a,b,y)$ taken up this time.

Verification: The next round proceeds only if the strategy reaches (2b) or (3d). In this case, the response to the query $(a,b,y)$ made at (1c) can be computed only from the information of $g_e=g\upharpoonright n_e$ and $h_e=h\upharpoonright n_e$ . Moreover, the strategy does not take any action at (2b) or (3c), so nothing interferes with the next round of operation. Also, if the strategy arrives at a state other than (2b) or (3d) at some round, then the requirement $R_e$ is satisfied there.

Infinite rounds: If the strategy keeps arriving only at (2b) or (3d), it means that the round keeps going infinitely, and this also means, in particular that (1c) is passed through infinitely many times. Then, the computation of $\Phi _e[f\oplus (g\cap h)](c,d,x)$ continues to make queries to $g\cap h$ infinitely many times, so $\Phi _e[f\oplus (g\cap h)](c,d,x)$ does not halt. In this case, put $g_{e+1}(n_e)=h_{e+1}(n_e)=0$ , and set the values appropriately so that $f_{e+1}(n_e,g_{e+1}(n_e),0)\downarrow =f_{e+1}(n_e,h_{e+1}(n_e),1)$ . Put ${n_{e+1}=n_e+1}$ , and proceed to stage $e+1$ . Then, the requirement $R_e$ is satisfied for the same reason as (1a).

Proof We construct partial functions $f\colon \subseteq \omega \times 2\times 2\to \omega $ and $g,h\colon \subseteq \omega \to 2$ such that $(f\oplus g)\cap (f\oplus h)\not \leq _{\mathrm {subT}} f\oplus (g\cap h)$ . It suffices to fulfill the following requirement:

$$\begin{align*}R_e\colon (f\oplus g)\cap (f\oplus h)\not\subseteq\Phi_e[f\oplus (g\cap (f\oplus h))].\end{align*}$$

Given e, we need to find $c,d,x$ such that ${((f\oplus g)\cap (f\oplus h))(c,d,x)\downarrow }\not =\Phi _e[f\oplus (g\cap h)](c,d,x)$ . For the construction, the description becomes a little more complicated, but the idea of the proof is exactly the same as Theorem 4.9. For example, item (1c) is modified as follows:

1. (1c) $\Phi _e(f\oplus (g\cap (f\oplus h)))$ makes a query to $g\cap (f\oplus h)$ .

If this happens, assume that the computation makes a query $(a,b,y)$ to $g\cap (f\oplus h)$ . Then, go into the computation processes of $\Phi _a[g](y)$ and $\Phi _b[f\oplus h](y)$ . The discussion that follows is exactly the same as Theorem 4.9, but for example, item (2c) is modified as follows:

1. (2c) The computation of $\Phi _a[g](y)$ or $\Phi _b[f\oplus h](y)$ makes either a query to g or h which is larger than $n_e$ , or a query to f which is of level $\geq n_e$ .

Note that a query to f may be at level $n_e$ . In this case, the requirement is satisfied by exactly the same action as in Case (1b). If there is a query to g or h that is greater than $n_e$ , the situation is the same as Case (2c) in Theorem 4.9.

In Case (2d), both $\Phi _a[g](y)$ and $\Phi _b[f\oplus h](y)$ can only make queries to g and h which are less than or equal to $n_e$ and queries to f of level less than $n_e$ . Therefore, the situation is exactly the same as Case (2d) in Theorem 4.9, so the exact same argument applies.

Proof We claim that given any subTuring incomparable partial functions $g,h$ such that $g\cap h\not \equiv _{\mathrm {subT}} \emptyset $ , we can find sets A and B such that:

1. (1) $g\upharpoonright A\nleq _{\mathrm {subT}} h$ and $h\upharpoonright B\nleq _{\mathrm {subT}} g$ .

2. (2) $g \nleq _{\mathrm {subT}} (g\upharpoonright A)\oplus (h\upharpoonright B)$ and $ h \nleq _{\mathrm {subT}} (g\upharpoonright A)\oplus (h\upharpoonright B)$ .

3. (3) $g\cap h \nleq _{\mathrm {subT}} g\upharpoonright A$ and $g\cap h \nleq _{\mathrm {subT}} h\upharpoonright B$ .

If these conditions are satisfied, we can take ${f_0}= g\cap h $ , ${f_1}= g\upharpoonright A $ and ${f_2}= h\upharpoonright B $ and take ${ e_0}= { f_1}\oplus { f_2}$ , ${ e_1}= g $ and ${ e_2}= h $ . The condition (1) implies $f_1,f_2\not \leq _{\mathrm {subT}} f_0$ , and the condition (3) implies that $f_0\not \leq _{\mathrm {subT}} f_1,f_2$ and $f_1$ is incomparable with $f_2$ . Hence, $f_0,f_1,f_2$ are pairwise subTuring incomparable. The condition (2) implies $e_1,e_2\not \leq _{\mathrm {subT}} e_0$ , and the condition (1) implies that $e_0\not \leq _{\mathrm {subT}} e_1,e_2$ and $e_1$ is incomparable with $e_2$ . Hence, $e_0,e_1,e_2$ are pairwise subTuring incomparable.

Now, we have $f_1\cap f_2=(g\upharpoonright A)\cap (h\upharpoonright B)\leq _{\mathrm {subT}} g\cap h=f_0$ , so $f_0\oplus (f_1\cap f_2)\equiv _{\mathrm {subT}} f_0$ . Moreover, $f_0\leq _{\mathrm {subT}} f_0\oplus f_1=(g\cap h)\oplus (g\upharpoonright A)\leq _{\mathrm {subT}} g$ , and similarly $f_0\leq _{\mathrm {subT}} f_0\oplus f_2\leq _{\mathrm {subT}} h$ . Hence, $f_0\leq _{\mathrm {subT}}(f_0\oplus f_1)\cap (f_0\oplus f_2)\leq _{\mathrm {subT}} g\cap h=f_0$ . This shows $f_0\oplus (f_1\cap f_2)\equiv _{\mathrm {subT}} f_0\equiv _{\mathrm {subT}}(f_0 \oplus f_1)\cap (f_0\oplus f_2)$ .

Next, we have $e_0=(g\upharpoonright A)\oplus (h\upharpoonright B)\leq _{\mathrm {subT}} g\oplus h=e_1\oplus e_2$ , so $e_0\cap (e_1\oplus e_2)\equiv _{\mathrm {subT}} e_0$ . Moreover, $g\upharpoonright A\leq _{\mathrm {subT}}((g\upharpoonright A)\oplus (h\upharpoonright B))\cap g=e_0\cap e_1\leq _{\mathrm {subT}} e_0$ , and similarly, $h\upharpoonright B\leq _{\mathrm {subT}} e_0\cap e_2\leq _{\mathrm {subT}} e_0$ . Hence, $e_0=(g\upharpoonright A)\oplus (h\upharpoonright B)\leq _{\mathrm {subT}} (e_0\cap e_1)\oplus (e_0\cap e_2)\leq _{\mathrm {subT}} e_0$ . This shows ${e_0}\cap ({e_1}\oplus {e_2})\equiv _{\mathrm {subT}} e_0\equiv _{\mathrm {subT}} ({e_0}\cap {e_1})\oplus ({e_0}\cap {e_2})$ .

In order to show the claim, we need to construct $A\upharpoonright s$ and $B\upharpoonright s$ for each s; assume that these have been decided for s, and our next step is to satisfy a requirement of type (1), (2), or (3) above.

To satisfy (1), we pick $n>s$ such that $n\in \mathrm {dom}(g)$ and $g(n)\neq \Phi [h](n)$ , where $\Phi $ is the next Turing functional we are diagonalizing against. This n must exist lest $g\leq _{\mathrm {subT}} h$ . We then set $A\upharpoonright n+1=\left (A\upharpoonright s\right )\cup \{n\}$ , which will ensure that $g\upharpoonright A\not \subseteq \Phi [h]$ . We act similarly to make $h\upharpoonright B\not \subseteq \Phi [g]$ .

To satisfy (2), we check if there is some $x\in \mathrm {dom}(g)$ such that the computation $\Phi [\left (g\upharpoonright \left (A\upharpoonright s\right )\right )\oplus \left (h\upharpoonright \left (B\upharpoonright s\right )\right )](x)$ makes a query to the oracle $g(n)$ or $h(n)$ for some $n>s$ . If no, then $g\subseteq \Phi [{\left (g\upharpoonright A\right )\oplus \left (h\upharpoonright B\right )}]$ implies that $g\subseteq \varphi $ for some partial computable function simulating $\Phi $ with the given finite oracle, which is impossible. If the answer is yes, witnessed by some least $n>s$ , we take $A\upharpoonright n+1=\left (A\upharpoonright s\right )$ and $B\upharpoonright n+1=\left (B\upharpoonright s\right )$ , in particular setting $n\not \in A\cup B$ , and therefore ensuring $g\not \subseteq \Phi [{\left (g\upharpoonright A\right )\oplus \left (h\upharpoonright B\right )}]$ . We do similarly to make $h\not \subseteq \Phi [\left (g\upharpoonright A\right )\oplus \left (h\upharpoonright B\right )]$ .

To satisfy (3), we check if there is some $x\in \mathrm {dom}(g\cap h)$ such that the computation $\Phi [{g\upharpoonright (A\upharpoonright s)}](x)$ queries $g(n)$ for some $n>s$ . If not, then just like in (2) above, we have that $g\cap h\not \subseteq \Phi [{g\upharpoonright A}]$ , unless $g\cap h\equiv _{\mathrm {subT}}\emptyset $ . If yes, then we just keep $n\not \in A$ by taking $A\upharpoonright n+1=\left (A\upharpoonright s\right )$ which will ensure that $g\cap h\not \subseteq \Phi [{g\upharpoonright A}]$ . We proceed similarly to make $g\cap h\not \subseteq \Phi [{h\upharpoonright B}]$ . In fact, note that we can replace $g\cap h$ by any function which is $\not \equiv _{\mathrm { subT}} \emptyset $ .

Proof We construct a noncomputable partial function f such that for any $g,h\leq _{\mathrm {subT}} f$ if $f\leq _{\mathrm {subT}} g\oplus h$ then either $f\leq _{\mathrm {subT}} g$ or $f\leq _{\mathrm {subT}} h$ holds. It suffices to fulfill the following requirements:

$$ \begin{align*} P_e\colon&\ f\not\subseteq\varphi_e.\\ R_{e,d,j}\colon&\ \text{If } g\subseteq\Phi_e[f] \text{ and } h\subseteq\Phi_d[f] \text{ and } f\subseteq\Phi_j[g\oplus h]\\ &\text{ then } f\leq_{\mathrm{subT}} g \text{ or } f\leq_{\mathrm{subT}} h. \end{align*} $$

At the beginning of the stage s, assume that a computable infinite set $I_s\subseteq \omega $ has been constructed, and $f\upharpoonright \min I_s$ has been determined. That is, $f\upharpoonright \min I_s$ is guaranteed not to change after stage s. Each $n \not \in I_s$ with $n> \min I_s$ is removed from the domain of f.

$P_e$ -strategy: Assume $s=2e$ . For $n=\min I_s$ , one can choose the value of $f(n)$ so that $f(n)\downarrow \not =\varphi _e(n)$ . Put $I_{s+1}=\{x\in I_s:x>n\}$ . Then, the values of f up to n will be protected. The requirement $P_e$ is clearly satisfied.

$R_{e,k,j}$ -strategy: Assume $s=2\langle e,d,j\rangle +1$ . This strategy consists of infinitely many substrategies. The $t^{th}$ substrategy works with the t-th smallest element $n_t$ of $I_s$ . In particular, $n_0=\min I_s$ , and $f\upharpoonright n_0$ has already been determined. As long as we focus only on this one substrategy, it is somewhat similar to the strategy of Theorem 4.9. In particular, the $t^{th}$ substrategy itself also consists of infinitely many rounds. See Figure 2 for the overview of the $R_{e,d,j}$ -strategy.

Figure 2:

Overview of the $R_{e,d,j}$ -strategy.

First, regarding the computation of $\Phi _j[{g\oplus h}](n_t)$ , we have the following possibilities:

1. (1a) $\Phi _j[g\oplus h](n_t)$ is undefined without making a query.

2. (1b) $\Phi _j[g\oplus h](n_t)$ halts without making a query.

3. (1c) $\Phi _j[g\oplus h](n_t)$ makes a query for g or h.

Here, in the $k^{th}$ round (starting with $k=0$ ), we ask about the $k^{th}$ query during the computation of $\Phi _j[g\oplus h](n_t)$ . For instance, (1b) in the $k^{th}$ round means that this computation has already made k queries (since we have reached the $k^{th}$ round) and halts without making any further queries. That is, the computation halts after making exactly k queries.

Case (1a): In this case, by setting $f(n_t)\downarrow ,$ one can guarantee that $f(n_t)\not =\Phi _j[g\oplus h](n_t)$ . Here, if it is not the first round, set $f(n_t)\downarrow $ to be a value consistent with the current assumption on $f(n_t)$ (made by the previous rounds). Put $I_{s+1}=\{x\in I_s:x>n_t\}$ , and proceed to stage $s+1$ .

Case (1b): If we are in the first round, the computation halts without ever creating a query, so the value of $\Phi _j[g\oplus h](n_t)$ is constant regardless of what oracle $g\oplus h$ is. In this case, by setting $f(n_t)\downarrow $ to be an appropriate value, we can guarantee that $f(n_t)\not =\Phi _j[g\oplus h](n_t)$ . Put $I_{s+1}=\{x\in I_s:x>n_t\}$ and proceed to stage $s+1$ .

If the round has already progressed, there may already be a restriction on the value of $f(n_t)$ , which may prevent diagonalization, so the action in this case is discussed in detail below.

Case (1c): Since the argument is symmetric, assume that the computation has made a query to g. If the assumption $g\subseteq \Phi _e[f]$ is satisfied, then the solution of the query m to g should be obtained from the solution of $\Phi _e[f](m)$ . In this case, we have the following possibilities:

1. (2a) $\Phi _e[f](m)$ does not halt, but makes only small queries less than $n_0$ .

2. (2b) $\Phi _e[f](m)$ halts after making only small queries less than $n_0$ .

3. (2c) $\Phi _e[f](m)$ makes a query $n'\geq n_0$ with $n'\not =n_t$ .

4. (2d) None of the above; that is, $\Phi _e[f](m)$ makes a query $n_t$ .

Case (2a): In this case, $m\not \in \mathrm {dom}(g)$ is ensured, so $\Phi _j[{g\oplus h}](n_t)\uparrow $ . As in Case (1a), by setting $f(n_t)\downarrow ,$ one can guarantee that $f(n_t)\not =\Phi _j[g\oplus h](n_t)$ . Here, set $f(n_t)\downarrow $ to be a value consistent with the current assumption on $f(n_t)$ (made by the previous rounds). Put $I_{s+1}=\{x\in I_s:x>n_t\}$ and proceed to stage $s+1$ .

Case (2b): It means that the solution to the query m for g has already been determined from the current information in $f\upharpoonright n_0$ . In this case, proceed to round $k+1$ of the $t^{th}$ substrategy.

Case (2c): By setting $f(n')\uparrow ,$ one can force $g(m)\uparrow $ , which also forces $\Phi _j[{g\oplus h}](n_t)\uparrow $ . Since $n'\not =n_t$ , as in Case (1a), one can set $f(n_t)\downarrow $ to guarantee that $f(n_t)\not =\Phi _j[g\oplus h](n_t)$ . Here, set $f(n_t)\downarrow $ to be a value consistent with the current assumption on $f(n_t)$ (made by the previous rounds). Put $I_{s+1}=\{x\in I_s:x>n_t,n'\}$ and proceed to stage $s+1$ .

Case (2d): In this case, the computation may depend on the value of $f(n_t)\in \{0,1\}$ , so the case is divided again.

1. (3a) $\Phi _e[f](m)$ may make a query $n'\geq n_0$ with $n'\not =n_t$ , depending on the value of $f(n_t)$ .

2. (3b) $\Phi _e[f](m)$ may not halt, depending on the value of $f(n_t)$ .

3. (3c) Otherwise, that is, $\Phi _e[f](m)$ , for any value of $f(n_t)$ , halts after only making a query $n'<n_0$ or $n'=n_t$ .

Here, if the value of $f(n_t)$ has already been determined, we only look at that value.

Cases (3a) and (3b): Set $f(n_t)$ to the corresponding value. In this case, we perform the same action as in Cases (2c) and (2a), respectively, and then proceed to stage $s+1$ .

Case (3c): In this case, proceed to round $k+1$ of the $t^{th}$ substrategy. However, in this case, the computation of $\Phi _e[f](m)$ may depend on the value of $f(n_t)$ , so we perform the round $k+1$ when $f(n_t)=0$ and when $f(n_t)=1$ in parallel.

Next rounds: The next round proceeds only if the substrategy reaches (2b) or (3c). If the substrategy keeps arriving only at (2b) or (3c) for some value of $f(n_t)$ , it means that the round keeps going infinitely, and this also means, in particular that (1c) is passed through infinitely many times. In this case, the computation of $\Phi _j[g\oplus h](n_t)$ continues to make queries infinitely many times, so $\Phi _j[g\oplus h](n_t)$ does not halt. Thus, by setting $f(n_t)\downarrow ,$ one can guarantee that $f(n_t)\not =\Phi _j[g\oplus h](n_t)$ . Here, set $f(n_t)\downarrow $ to be a value consistent with the current assumption on $f(n_t)$ . Put $I_{s+1}=\{x\in I_s:x>n_t\}$ , and proceed to stage $s+1$ .

Note that if, for some value of $f(n_t)$ , the substrategy eventually reaches a state other than (1b), (2b), or (3c), then we proceed to the next stage, after satisfying the requirement. Also, as we saw above, if we only arrive at (2b) or (3c) for some value of $f(n_t)$ , we also satisfy the requirement and proceed to the next stage. The only remaining case is when we arrive at (1b) no matter how we choose the value of $f(n_t)$ . It is necessary to describe the action at (1b) after the round has progressed.

Case (1b): After the round has progressed, the computation may be asking for the value of $f(n_t)$ . At this time, there are two different possibilities in Case (1b).

1. (4a) The value of $\Phi _j[g\oplus h](n_t)$ does not depend on whether $f(n_t)=0$ or $f(n_t)=1$ .

2. (4b) The value of $\Phi _j[g\oplus h](n_t)$ depends on whether $f(n_t)=0$ or $f(n_t)=1$ .

Case (4a): In this case, one can choose the value of $f(n_t)$ so that $f(n_t)\not =\Phi _e[g\oplus h](n_t)$ . Put $I_{s+1}=\{x\in I_s:x>n_t\}$ , and proceed to stage $s+1$ .

Case (4b): In this case, start running the $(t+1)$ -th substrategy.

Let us analyze the situation when (4b) occurs. First, note that the behavior of each substrategy does not depend on the behavior of the other substrategies. In other words, since the behavior of the $t^{th}$ substrategy depends only on the values of $f\upharpoonright n_0$ and $f(n_t)$ , in fact, one can operate all substrategies in parallel. Furthermore, if (4b) occurs, then the computation $\Phi _j[g\oplus h](n_t)$ only makes queries $n\in \mathrm {dom}(f)$ with $n<n_0$ or $n=n_t$ . Now, for each $i<2$ , let $f_i$ be an extension of $f\upharpoonright n_0$ such that $f_i(n_t)=i$ . Dependently, the values of g and h also change, so that $\hat {g}_i=\Phi _e[f_i]$ and $\hat {h}_i=\Phi _d[f_i]$ .

Note that (4b) occurs because the solution of a query differs somewhere in the $\Phi _j$ -computations for $f(n_t)=0$ and for $f(n_t)=1$ . That is, for the queries $m_0,m_1,\dots $ during the computation of $\Phi _j[\hat {g}_0\oplus \hat {h}_0](n_t)$ and the queries $m_0',m_1',\dots $ during the computation of $\Phi _j[\hat {g}_1\oplus \hat {h}_1](n_t)$ , since we are running the same computation $\Phi _j$ , these queries must be the same until the very first difference on the solutions occurs. That is, there exists some $k(t)$ such that $m_i=m_i'$ for each $i\leq k(t)$ , but the solutions for $m_{k(t)}=m_{k(t)}'$ are different. For instance, if this is a query to g, then $\hat {g}_0(m_{k(t)})\not =\hat {g}_1(m_{k(t)}')$ . Let us now define $\tilde {m}_t:=m_{k(t)}$ . The point is that if $\hat {g}=\Phi _e[f]$ and $\hat {h}=\Phi _d[f]$ , then one can recover the value of $f(n_t)$ from the value of $\hat {g}(\tilde {m}_t)$ or $\hat {h}(\tilde {m}_t)$ . Moreover, even if $g\subseteq \hat {g}$ and $h\subseteq \hat {h}$ , if $\Phi _j[g\oplus h](n_t)\downarrow ,$ then the same computation is performed without accessing outside the domains of g and h, so one can recover the value of $f(n_t)$ from the value of ${g}(\tilde {m}_t)$ or $h(\tilde {m}_t)$ in the same way. This is the case, for example, when $n_t\in \mathrm {dom}(f)$ and $f\leq _{\mathrm {subT}} g\oplus h$ via j.

Infinite substages: Recall that, if a substrategy does not reach (4b) for some value of $f(n_t)$ , then we proceed to the next stage. Therefore, the process to proceed to the next stage is not yet described if all substrategies t reach (4b) for any value of $f(n_t)$ . Also, a new substrategy is activated only when it reaches (4b). Note that no action is taken at this point.

If each substrategy t reaches (4b), then we can use the information on the finite function $f\upharpoonright n_0$ to compute the sequences of queries $m_0,m_1,\dots $ and $m_0',m_1',\dots $ , and eventually find a query $\tilde {m}_t$ such that $\hat {g}_0(\tilde {m}_t)\not =\hat {g}_1(\tilde {m}_t)$ or $\hat {h}_0(\tilde {m}_t)\not =\hat {h}_1(\tilde {m}_t)$ . This procedure $t\mapsto \tilde {m}_t$ is computable using only $f\upharpoonright n_0$ . Furthermore, for $\hat {g}=\Phi _e[f]$ and $\hat {h}=\Phi _d[f]$ , the value of $f(n_t)$ is determined from $\hat {g}(\tilde {m}_t)$ or $\hat {h}(\tilde {m}_t)$ . Let $J_s\subseteq I_s$ be the set of locations $n_t$ such that $\tilde {m}_t$ is a query to the g-side and $\hat {g}_0(\tilde {m}_t)\not =\hat {g}_1(\tilde {m}_t)$ . If $J_s$ is infinite, put $I_{s+1}=J_s$ , otherwise, $I_{s+1}=I_s\setminus J_s$ . We then proceed to stage $s+1$ .

Verification: The requirement $P_e$ clearly ensures that f is not computable. Suppose now that $g,h\leq _{\mathrm {subT}} f$ and $f\leq _{\mathrm {subT}} g\oplus h$ . Then, $g\subseteq \Phi _e[f]$ , $h\subseteq \Phi _d[f]$ and $f\subseteq \Phi _j[g\oplus h]$ for some $e,d,j\in \omega $ . If some substrategy of the $R_{e,d,j}$ -strategy does not arrive at (4b), then $f\not \subseteq \Phi _j[g\oplus h]$ is guaranteed as discussed above, so all substrategies will always arrive at (4b). Let $s=2\langle e,d,j\rangle +1$ and consider $n_0=\min I_s$ . By the construction of f, for any $n\in \mathrm {dom}(f)$ , $n\geq n_0$ implies $n\in I_{s+1}$ . For any $n_t\in I_{s+1}$ , one can compute $\tilde {m}_t$ using information on the finite function $f\upharpoonright n_0$ . As noted above, if $n_t\in \mathrm {dom}(f)$ , then by our assumption that $f\leq _{\mathrm {subT}} g\oplus h$ via j, the value of $f(n_t)$ can be computed from $g(\tilde {m}_t)$ or $h(\tilde {m}_t)$ . If $n_t\in J_s$ , then the former, and if $n_t\not \in J_s$ , then the latter. Thus, we obtain $f\leq _{\mathrm {subT}} g$ if $I_{s+1}=J_s$ and $f\leq _{\mathrm {subT}} h$ if $I_{s+1}=I_s\setminus J_s$ .