Observation 2.1. If X is an initial segment of $\mathbb {N}$ , then we have $\widehat {\Sigma ^1_1\mbox {-}\mathsf {C}_X}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf { AC}_{\mathbb {N}\to X}$ .

Proof We prove the following Weihrauch inequality, in their order from left to right: $\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}^{\mathbb {N}}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}\leq _{\mathsf {W}}\mathsf { C}_{\mathbb {N}^{\mathbb {N}}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf { DC}_{\mathbb {N}^{\mathbb {N}}}$ .

$\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}^{\mathbb {N}}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ : The set of all solutions to an instance of $\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}^{\mathbb {N}}}$ is obviously $\Sigma ^1_1$ relative to the given parameter, and one can easily find its $\Sigma ^1_1$ -index.

$\Sigma ^1_1\mbox {-}\mathsf {C}_{\mathbb {N}^{\mathbb {N}}} \leq _{\mathsf {W}} \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ : Let $P\subseteq \mathbb {N}^{\mathbb {N}}$ be a $\Sigma ^1_1$ set. From its index, one can compute the index of a closed set $Q\subseteq \mathbb {N}^{\mathbb {N}}\times \mathbb {N}^{\mathbb {N}}$ such that the first projection of Q is P. Thus, given an element of Q, one can find an element of P by applying the first projection, and $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}\geq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf { C}_{\mathbb {N}^{\mathbb {N}}}$ .

$\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}}$ : Given a code q of a closed subset $C_q$ of $\mathbb {N}^{\mathbb {N}}$ , compute a code of a pruned $\Sigma ^1_1$ tree T such that $C_q=[T]$ (which is given by $\sigma \in T$ iff $C_q$ contains an extension of $\sigma $ ). Then, let $\varphi _T(\sigma ,\tau )$ be the formula expressing that $\tau $ is an immediate successor of $\sigma $ in T. Moreover, $\langle p,q,\varepsilon \rangle $ where $S_q=\mathbb {N}^{<\mathbb {N}}$ and $S_p=\{\langle \sigma ,\tau \rangle :\varphi _T(\sigma ,\tau )\}$ satisfies the premise of $\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}}$ since T is pruned. Let f be a solution to this instance of $\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}}$ . Since T is pruned, f must be a path through T.

$\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {DC}_{\mathbb {N}^{\mathbb {N}}}$ : This is obvious as $\mathbb {N}$ can be computably embedded in $\mathbb {N}^{\mathbb {N}}$ .

Observation 2.3. $\Sigma ^1_1\mbox {-}\mathsf {DC}_2\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {WKL}$ .

Fact 2.4 (Kihara et al. [Reference Kihara, Marcone and Pauly14])

$\widehat {\Sigma ^1_1\mbox {-}\mathsf {C}_2}\equiv _{\mathsf {W}}\Pi ^1_1\mbox {-}\mathsf {Sep}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {WKL}$ .

Proof By Observation 2.1, we have $\widehat {\Sigma ^1_1\mbox {-}\mathsf {C}_2}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}_{\mathbb {N}\to 2}$ . By Fact 2.4, $\Sigma ^1_1\mbox {-}\mathsf {AC}_{\mathbb {N}\to 2}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {WKL}$ . By Observation 2.3, we have $\Sigma ^1_1\mbox {-}\mathsf {WKL}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {DC}_2$ .

It remains to show that these are equivalent to the $\Sigma ^1_1$ compact choice principle. First note that the reduction $\Sigma ^1_1\mbox {-}\mathsf {WKL}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}$ is obvious, as if $T\subseteq {2^{\mathbb {N}}}$ is $\Sigma ^1_1$ , then $[T]$ is compact and $\Sigma ^1_1$ . For the converse, we claim that if a set $A\subseteq {\mathbb {N}^{\mathbb {N}}}$ is $\Sigma ^1_1$ and compact then it is arithmetically isomorphic to a closed set $B\subseteq {2^{\mathbb {N}}}$ .

So suppose that A is $\Sigma ^1_1$ and compact. First, it is clearly closed, so let $T_A\subseteq {\mathbb {N}^{<\mathbb {N}}}$ be a $\Sigma ^1_1$ tree such that $A=[T_A]$ and $T_A$ has no dead-end; that is, $T_A$ is defined as $\sigma \in T_A$ iff $\exists X\succ \sigma $ with $X\in A$ . By compactness and the fact that the tree is pruned, for every $\sigma \in {\mathbb {N}^{<\mathbb {N}}}$ , there exist finitely many $i\in \mathbb {N}$ such that $\sigma \mbox {}^\smallfrown i\in T_A$ . We define $T_B$ by $\forall \sigma \in {2^{<\mathbb {N}}}$ , $\sigma \in T_B$ if and only if $\exists \tau \in T_A$ such that $\sigma \prec 0^{\tau (0)}10^{\tau (1)}\cdots 0^{\tau (|\tau |-1)}1$ . Then, the transformation $T_B\mapsto T_A$ is computable, while $T_A\mapsto T_B$ is $T_A'$ -computable; hence $B=[T_B]$ is arithmetically isomorphic to A.

In particular, B is $\Sigma ^1_1$ , and moreover, from the above explicit definition of $T_B$ , one can effectively compute a $\Sigma ^1_1$ -code of B from a given $\Sigma ^1_1$ -code of A. It is easy to compute an element of A from a given element of B. This argument shows that $\Sigma ^1_1\mbox {-}\mathsf {WKL}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}$ .⊣

Proof We start by proving $\Sigma ^1_1\mbox {-}\mathsf {K}_\sigma \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf { KC}_{\mathbb {N}^{\mathbb {N}}}\star \Sigma ^1_1\mbox {-}\mathsf {C}_{\mathbb {N}}$ . Given a sequence $(S_n)$ of compact $\Sigma ^1_1$ sets, first use $\Sigma ^1_1\mbox {-}\mathsf {C}_{\mathbb {N}}$ to get n with $S_n\not =\emptyset $ (as the set $\{n\in \mathbb {N}:\exists x\in S_n\}$ is $\Sigma ^1_1$ ), and then $\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}$ to choose an element of $S_n$ .

For the converse direction, let $((S_n)_{n\in \mathbb {N}},P)$ be an instance of $\Sigma ^1_1\mbox {-}\mathsf { KC}_{\mathbb {N}^{\mathbb {N}}}\star \Sigma ^1_1\mbox {-}\mathsf {C}_{\mathbb {N}}$ , that is, for any $n \ S_n$ is a $\Sigma ^1_1$ set which is non-empty and compact whenever $n\in P$ . Let $\hat S_n$ be the $\Sigma ^1_1$ set defined by $x\in \hat S_n$ if and only if $n\in P$ and $x\in S_n$ . The collection $(\hat S_n)_{n\in \mathbb {N}}$ is an instance of $\Sigma ^1_1\mbox {-}\mathsf {K}_\sigma \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ , and any solution for it is a solution for the initial instance $(S_n)_{n\in \mathbb {N}},P$ .⊣

Proof By Corollary 2.11, it suffices to prove $\mathsf {ATR}_{2'}\leq _{\mathsf {W}}^a\widehat {\Sigma ^1_1\mbox {-}\mathsf {UC}^{\mathsf {tot}}_2}$ . Fix x a code for a linear order. Given $n\in \mathbb {N}$ , let $JH_{n}$ be the set of jump hierarchies for $\prec _x\! \upharpoonright _{n}$ (where $\prec _x\! \upharpoonright _{n}$ is the restriction of $\prec _x$ up to $\{y:y\prec _x n\}$ ). Note that $\{(n,H):H\in JH_n\}$ is arithmetical (since the definition of a jump hierarchy is described by an arithmetical condition as mentioned above). For $a,k\in \mathbb {N}$ , if $a\prec _x n$ then we consider the set $S^n_{a,k}$ of all possible values of $H_a(k)$ , the k-th value of the a-th level of H, for some jump hierarchy $H\in JH_n$ , i.e., $S^n_{a,k}=\{H_a(k):H\in JH_n\}$ . If $a\not \prec _x n$ then put $S^n_{a,k}=\{0\}$ . Clearly, $S^n_{a,k}$ is $\Sigma ^1_1$ uniformly in $n,a,k$ , and therefore there is a computable function f such that $S^n_{a,k}$ is the $f(n,a,k)$ -th $\Sigma ^1_1$ set. Note that if $\prec _x\! \upharpoonright _{n}$ is well-founded, then the product $S^n:=\prod _{\langle a,k\rangle }S^n_{a,k}$ essentiallyFootnote ¹ consists of the unique jump hierarchy for $\prec _x\! \upharpoonright _{n}$ . In particular, $S^n_{a,k}$ is a singleton for any $a\prec _xn$ and $k\in \mathbb {N}$ whenever $\prec _x\! \upharpoonright _{n}$ is well-founded.

Given $p_{n,a,k}\in \Sigma ^1_1\mbox {-}\mathsf {UC}^{\mathsf {tot}}_{2}(f(n,a,k))$ (that is, $p_{n,a,k}\in S^n_{a,k}$ whenever $S^n_{a,k}$ is a singleton), define $H_n=\bigoplus _{\{\langle a,k\rangle : a\prec _x n\}}p_{n,a,k}$ . Note that if n is contained in the well-founded part of $\prec _x$ , then $H_n$ must be the jump hierarchy for $\prec _x\! \upharpoonright _{n}$ . By using arithmetical power (being a jump hierarchy is a $\Pi ^0_2$ statement), first ask if $H_n$ is a jump hierarchy for $\prec _{x}\! \upharpoonright _{n}$ for every n. If yes, $\bigoplus _nH_n$ is a jump hierarchy along the whole ordering $\prec _x$ . In particular, the whole ordering includes the well-founded part of $\prec _x$ , and therefore is large.

If no, we claim that there is no $\prec _{x}$ -least n such that $H_n$ is not a jump hierarchy for $\prec _{x}\! \upharpoonright _{n}$ . Indeed, suppose there exists one, then obviously n is not contained in the well-founded part of $\prec _x$ . Hence, $\prec _x\! \upharpoonright _{n}$ is a large initial segment of $\prec _x$ . Moreover, by minimality of n, every $H_j$ for $j\prec _x n$ is a jump hierarchy, so by definition of a jump hierarchy, $\bigoplus \{H_j':j\prec _x n\}$ is the jump hierarchy for $\prec _x\! \upharpoonright _{n}$ . But then, none of the $S^n_{a,k}$ are empty, and $H_n$ must be a jump hierarchy for $\prec _x\! \upharpoonright _{n}$ , a contradiction proving the claim.

Let $j_0$ be the $<_{\mathbb {N}}$ -least number such that $H_{j_0}$ is not a jump hierarchy for $\prec _x\! \upharpoonright _{j_0}$ , and $j_{n+1}\prec _{x}j_n$ be the $<_{\mathbb {N}}$ -least number such that $H_{j_{n+1}}$ is not a jump hierarchy for $\prec _x\! \upharpoonright _{j_{n+1}}$ . Finding such a sequence is $\Delta ^0_3$ , so one can arithmetically find such an infinite sequence $(j_n)_{n\in \mathbb {N}}$ , which is clearly decreasing with respect to $\prec _x$ .⊣

Proof First, consider a computable instance S of $\Sigma ^1_1\mbox {-}\mathsf {C}^{\mathsf {aof}}_{\mathbb {N}}$ . Let $\prec _n$ be a linear order on an initial segment $L_n$ of $\mathbb {N}$ such that $n\in S$ iff $\prec _n$ is ill-founded. Let $H_n$ be a solution to the instance $\prec _n$ of $\mathsf {ATR}_{2'}$ . Ask the arithmetic question whether there exists n such that $H_n$ is an infinite decreasing sequence w.r.t. $\prec _n$ . If so, one can computably find such an n, which belongs to S. Otherwise, each $H_n$ is (essentially) a jump hierarchy along a large initial segment $J_n$ of $L_n$ . In an arithmetical way, one can obtain $J_n$ . Then ask if $L_n\setminus J_n$ is nonempty, and has no $\prec _n$ -minimal element. If the answer to this arithmetical question is yes, we have $n\in S$ .

Thus, we are left with the case where for any n either $L_n=J_n$ holds or $L_n\setminus J_n$ has a $\prec _n$ -minimal element. In this case, if $n\in S$ then $J_n$ is ill-founded. This is because if $J_n$ is well-founded, then $J_n$ is exactly the well-founded part of $L_n$ since $J_n$ is large, and thus $L_n\setminus J_n$ is nonempty and has no $\prec _n$ -minimal element. Moreover, since $J_n$ admits a jump hierarchy while it is ill-founded, $J_n$ is a pseudo-well-order; hence $H_n$ computes all hyperarithmetical reals (see [Reference Enderton and Putnam6]). Conversely, if $n\not \in S$ then $H_n$ is a jump hierarchy along the well-order $J_n=L_n$ , which is hyperarithmetic.

Now, ask if the following $(H_n)_{n\in \mathbb {N}}$ -arithmetical condition holds:

(1) $$ \begin{align} (\exists i)(\forall j)\;H_i\not<_TH_j. \end{align} $$

By our assumption that $S\not =\emptyset $ , there is $k\in S$ , so that $H_k$ computes all hyperarithmetic reals. Therefore, if (1) is true with witness i, the hierarchy $H_i$ cannot be hyperarithmetic; hence $i\in S$ . Then one can arithmetically find such an i. If (1) is false, for any i there is j such that $H_i<_TH_j$ . In this case, start from $i:=k\in S$ , and obtain an infinite sequence $j_0,j_1,j_2,\dots $ such that $H_k<_TH_{j_0}<_TH_{j_1}<_T\dotsb $ . Since $H_k$ computes all hyperarithmetical sets, $H_{j_n}$ is not hyperarithmetical for any n, i.e., $j_n\in S$ . This implies that S is an infinite set. However, by our assumption, if S is infinite, then $S=\mathbb {N}$ . Hence, any i is solution to S.

Finally, one can uniformly relativize this argument to any instance of $\Sigma ^1_1\mbox {-}\mathsf {C}^{\mathsf {aof}}_{\mathbb {N}}$ .⊣

Proof of Theorem 2.12 By Lemma 2.13, $\widehat {\mathsf {ATR}_{2'}}\leq _{\mathsf {W}}^a\widehat {\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}}$ . By Corollary 2.11, $\widehat {\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}}\equiv _{\mathsf { W}}\widehat {\widehat {\Sigma ^1_1\mbox {-}\mathsf {UC}^{\mathsf {tot}}_{\mathsf {2}}}}\equiv _{\mathsf {W}}{\widehat {\Sigma ^1_1\mbox {-}\mathsf {UC}^{\mathsf { tot}}_{\mathsf {2}}}}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}$ . By Proposition 2.10 and Definition 2.8, ${\widehat {\Sigma ^1_1\mbox {-}\mathsf {UC}^{\mathsf {tot}}_{\mathsf {2}}}}\equiv _{\mathsf { W}}\widehat {\Sigma ^1_1\mbox {-}\mathsf {C}^{\mathsf {aou}}_{X}}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aou}}_{\mathbb {N}\to \mathbb {N}}$ .

Clearly, $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aou}}_{\mathbb {N}\to \mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ , as witnessed by the identity reductions. By Definition 2.8 and Lemma 2.14, $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf { aof}}_{\mathbb {N}\to \mathbb {N}}\equiv _{\mathsf {W}}\widehat {\Sigma ^1_1\mbox {-}\mathsf {C}^{\mathsf {aof}}_{\mathbb {N}}}\leq _{\mathsf { W}}^a\widehat {\widehat {\mathsf {ATR}_{2'}}}\equiv _{\mathsf {W}}{\widehat {\mathsf {ATR}_{2'}}}$ .⊣

Proof Let S be a computable instance of $\Sigma ^1_1\mbox {-}\mathsf {C}^{\mathsf {aof}}_{\mathbb {N}}$ . Let $T_n$ be a computable tree such that $n\in S$ iff $T_n$ is ill-founded. Define

$$ \begin{align*} T=00\sqcup_nT_n=\{\langle\rangle,\langle 0\rangle,\langle 00\rangle\}\cup\{\langle 00n\rangle\sigma:\sigma\in T_n\}. \end{align*} $$

Let $i\mbox {}^\smallfrown H$ be a solution to the instance T (ordered by reverse inclusion) of $\mathsf {ATR}_{2}^{\mathsf {po}}$ . If $i=1$ , i.e., if H is an infinite decreasing sequence w.r.t. T, then this provides an infinite path p through T. Then, choose n such that $00n\prec p$ , which implies $T_n$ is ill-founded, and thus $n\in S$ . Otherwise, $i=0$ , and thus H is a jump hierarchy for T. We define $H^\ast _n=H_{\langle 00n\rangle }$ . Note that if $n\not \in S$ then $H^\ast _n$ is hyperarithmetic, and if $n\in S$ then $H^\ast _n$ computes all hyperarithmetical reals. By the definition of a jump hierarchy, we have $(H^\ast _n)''\leq _TH$ . Thus, the following is an H-computable question:

(2) $$ \begin{align} (\exists i)(\forall j)\;H^\ast_i\not<_TH^\ast_j. \end{align} $$

As in the proof of Lemma 2.14, one can show that if (2) is witnessed by i then $i\in S$ , and if (2) is false then any i is a solution to S. As before, one can uniformly relativize this argument to any instance S.⊣

Question 2.16. $\mathsf {ATR}_{2}\equiv ^a_{\mathsf {W}}\mathsf {ATR}_{2'}\equiv ^a_{\mathsf {W}}\mathsf {ATR}_{2}^{\mathsf {po}}$ ?

Proof First, it is clear that we have $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {fin}}_{\mathbb {N}\to \mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf { DC}^{\mathsf {fin}}_{\mathbb {N}}$ . Up to the coding of the instance, we also have $\Sigma ^1_1\mbox {-}\mathsf {DC}^{\mathsf {fin}}_{\mathbb {N}}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}$ . By Proposition 2.5, $\Sigma ^1_1\mbox {-}\mathsf {KC}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}_{\mathbb {N}\to 2}\equiv _{\mathsf { W}}\Sigma ^1_1\mbox {-}\mathsf {WKL}$ . But clearly, $\Sigma ^1_1\mbox {-}\mathsf {AC}_{\mathbb {N}\to 2}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {fin}}_{\mathbb {N}\to \mathbb {N}}$ .⊣

Proof To construct a greatest element in $\Sigma ^1_1\mbox {-}\mathsf {DC}^{\mathsf {fin}}_{\mathbb {N}}$ , by Proposition 2.5, we only need to enumerate all nonempty compact $\Sigma ^1_1$ subsets of $2^{\mathbb {N}}$ . Let $S_e$ be the e-th $\Sigma ^1_1$ subtree of $2^{<\mathbb {N}}$ . Then, consider a $\Delta ^1_1$ co-enumeration $(S_{e,\alpha })_{\alpha <\omega _1^{\text {CK}}}$ of $S_e$ (induced from a $\Pi ^1_1$ -norm, as explained in Section 1.2). If $[S_e]$ is empty, by compactness, $S_e$ is finite.

If $S_e$ is finite, we claim that there is $\alpha <\omega _1^{\text {CK}}$ such that $S_{e,\alpha }$ is finite, and the least such $\alpha $ is a successor ordinal. To see this, first note that for each $\sigma \in 2^{<\mathbb {N}}\setminus S_e$ , there is $\alpha (\sigma )<\omega _1^{\text {CK}}$ such that $\sigma \not \in S_{e,\alpha (\sigma )}$ . Now, $2^{<\mathbb {N}}\setminus S_e$ is cofinite, and in particular, computable, so by Spector bounding (Theorem 1.4), we have $\alpha =\sup \{\alpha (\sigma ):\sigma \in 2^{<\mathbb {N}}\setminus S_e\}<\omega _1^{\text {CK}}$ . For the second assertion of our claim, by minimality of $\alpha $ , we have $[S_{e,\beta }]\not =\emptyset $ for any $\beta <\alpha $ , and moreover, if $\alpha $ is a limit ordinal, then $[S_{e,\alpha }]=\bigcap [S_{e,\alpha [n]}]$ . However, by compactness, this intersection is nonempty, which contradicts our choice of $\alpha $ .

Now we construct a uniform $\Delta ^1_1$ approximation of a sequence $(T_e)_{e\in \mathbb {N}}$ of nonempty $\Sigma ^1_1$ sets such that if $[S_e]\not =\emptyset $ then $T_e=[S_e]$ . Define $T_{e,0}=2^{\mathbb {N}}$ , and for any $\alpha>0$ , $T_{e,\alpha }=[S_{e,\alpha }]$ if $[S_{e,\alpha }]\not =\emptyset $ (which is a $\Pi ^0_1(S_{e,\alpha })$ property by compactness, so in particular $\Delta ^1_1$ ). If $\alpha>0$ is the first stage such that $[S_{e,\alpha }]=\emptyset $ , then, by the above claim, $\alpha $ is a successor ordinal, say $\alpha =\beta +1$ . In this case, define $T_{e,\gamma }=T_{e,\beta }$ for any $\gamma \geq \alpha $ , and end the construction. By minimality of $\alpha $ , we have $T_{e,\beta }\not =\emptyset $ since $\beta <\alpha $ . Then consider $T_e=\bigcap _{\alpha }T_{e,\alpha }$ , and it is not hard to check that the sequence $(T_e)_{e\in \mathbb {N}}$ has the desired property. It is easy to check that this argument is uniformly relativizable to any oracle.

As a maximal instance of $\Sigma ^1_1\mbox {-}\mathsf {DC}^{\mathsf {fin}}_{\mathbb {N}}$ , it suffices to take the one consisting of the product of all $T_e$ . Note that by Theorem 3.3 this also shows the maximality result for $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {fin}}_{\mathbb {N}\to \mathbb {N}}$ .⊣

Proof Let $(\psi _e)$ be a list of higher Turing reductions. Let $K_0=K$ . For each e, let $Q_{e,n}=\{x\in \mathbb {N}^{\mathbb {N}}:\psi _e^x(n)\uparrow \}$ . Then $Q_{e,n}$ is a $\Sigma ^1_1$ closed set. If $K_e\cap Q_{e,n}$ is nonempty for some n, define $K_{e+1}=K_e\cap Q_{e,n}$ for such n; otherwise define $K_{e+1}=K_e$ . Note that if $K_e\cap Q_{e,n}$ is nonempty for some n, then $\psi _e^x$ is not total for any $x\in K_{e+1}$ . If $K_e \cap Q_{e,n}$ is empty for all n, then $\psi _e$ is total on the $\Sigma ^1_1$ compact set $K_e$ , one can find a $\Delta ^1_1$ function majorizing $\psi _e^x$ for all $x\in K_e$ (cf. the proof of [Reference Kihara, Marcone and Pauly14, Lemma 4.7]). Define $K_\infty =\bigcap _nK_n$ , which is nonempty since $K_n$ is compact. Then, for any $p\in K_\infty $ , every $f\leq _{hT}p$ is majorized by a $\Delta ^1_1$ function.⊣

Proof Let $(\varphi _e)$ be an effective enumeration of all partial $\Pi ^1_1$ functions $\varphi _e\colon \!\!\!\subseteq \mathbb {N}\to 2$ . As in the argument in Proposition 2.6 or Proposition 2.9, one can see that the set $S_e$ of all two-valued totalizations of the partial $\Pi ^1_1$ function $\varphi _e$ is nonempty and $\Sigma ^1_1$ . Then the product $K=\prod _eS_e$ is also a nonempty $\Sigma ^1_1$ subset of $2^{\mathbb {N}}$ . It is clear that every $p\in K$ computes any two-valued total $\Delta ^1_1$ function, so (non-uniformly) computes any total $\Delta ^1_1$ function on $\mathbb {N}$ . Let $BB$ be a total $p'$ -computable function which dominates all p-computable functions. In particular, $BB\leq _Tp'$ dominates all $\Delta ^1_1$ functions.⊣

Proof It is clear that $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}\geq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aou}}_{\mathbb {N}\to \mathbb {N}}$ , by the identity function. It remains to prove $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf { aof}}_{\mathbb {N}\to \mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aou}}_{\mathbb {N}\to \mathbb {N}}$ . Let $A=\prod _n A_n\in \Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ . We define uniformly in A the set $B=\prod _{\langle m,n\rangle } B^m_n$ such that $A\leq _MB$ and $B\in \Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aou}}_{\mathbb {N}\to \mathbb {N}}$ . We will ensure that there exists a single computable function $\Phi $ such that for any m and $X\in \prod _nB^m_n$ we have $\Phi ^X\in A_m$ .

We first describe the co-enumeration of $B^m_n$ . Let $(A_{m,\alpha })_{\alpha <\omega _1^{\text {CK}}}$ be an approximation of $A_m\subseteq \mathbb {N}$ (induced from a $\Pi ^1_1$ -norm, as explained in Section 1.2). First, wait for the first stage where $A_m$ is finite (if this never happens then $B_n^m=\mathbb {N}$ ). Here note that if $A_m$ is finite then its finiteness is witnessed at some stage before $\omega _{1}^{\text {CK}}$ by Spector bounding (Theorem 1.4) as seen in the proof of Theorem 3.4. If it happens, wait for exactly n additional elements to be removed from $A_m$ . If this happens, let $B^m_n=\{c\}$ where c is the code for the finite set $A_m$ at this stage $\alpha _n$ . More formally, we suppose that in the co-enumeration of $A_m$ at most one element is removed at each stage, and we let $\alpha _0$ be the least stage such that $A_{m,\alpha _0}$ is finite, and $\alpha _{n+1}$ be the least stage such that $A_{m,\alpha _{n+1}}\subsetneq A_{m,\alpha _n}$ if it exists. Then, let $D_e$ be the finite set coded by e, and set $B^m_n=\{c\}$ with $D_c=A_{m,\alpha _n}$ .

Now, we describe the function $\Phi $ . Given X, find the first i such that we do not have the following: $D_{X(i)}\supsetneq D_{X(i+1)}\not =\emptyset $ . Note that $X(0)$ codes a finite set, so the length of the chain $D_{X(0)}\supsetneq D_{X(1)}\supsetneq \cdots $ has to be finite. Therefore, there exists such an i. Then, output any element $\Phi ^X$ from $D_{X(i)}$ . If $X\in \prod _nB_n^m$ , whenever we reach stage $\alpha _n$ , we have $D_{X(n)}=A_{m,\alpha _n}$ , and thus $i\geq n$ . Assume that $\alpha _k$ is the last stage such that some element is removed from $A_m$ . Then, $k\leq i$ and $D_{X(k)}=A_{m,\alpha _k}=A_m\supseteq D_{X(i)}$ . This implies that if $X\in \prod _nB_n^m$ , then the chosen element $\Phi ^X$ is contained in $A_m$ , as required.⊣

Proof First, it is clear that $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {fosc}}_{\mathbb {N}\to \mathbb {N}}\geq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf { aof}}_{\mathbb {N}\to \mathbb {N}}$ as witnessed by the identity function. It remains to prove $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {fosc}}_{\mathbb {N}\to \mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf { AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ . Let $A=\prod _nA_n$ with a bound $\psi $ given. We will construct a uniformly $\Sigma ^1_1$ sequence $(B^n_m)_{m\leq \psi (n)}$ of subsets of $\mathbb {N}$ . We use $B^{n}_{0},B^{n}_{1},\dots ,B^{n}_{\psi (n)-1}$ to code information which element is removed from $A_n$ whenever $A_n$ is cofinite, and use $B^{n}_{\psi (n)}$ to code full information of $A_n$ whenever $A_n$ is finite. If $a_0$ is the first element removed from $A_n$ , then put $B^n_0=\{a_0\}$ , and if $a_1$ is the second element removed from $A_n$ , then put $B^n_1=\{a_1\}$ , and so on. If $A_n$ becomes a finite set, then $B_{\psi (n)}^n$ just copies $A_n$ , otherwise $B_{\psi (n)}^n=\mathbb {N}$ . One can easily ensure that for any $n\in \mathbb {N}$ and $m<\psi (n)$ , if $A_n$ is finite, then $B^n_m$ is a singleton disjoint from $A_n$ ; otherwise $B^n_m=\mathbb {N}$ . Moreover, we can also see that either $B^n_{\psi (n)}$ is nonempty and finite or $B^n_{\psi (n)}=\mathbb {N}$ .

Now, assume that $X\in \prod _{n,m}B^n_m$ is given. If $X(n,\psi (n))\not \in \{X(n,i):i<\psi (n)\}$ , then put $Y(n)=X(n,\psi (n))$ . Otherwise, choose $Y(n)\not \in \{X(n,i):i<\psi (n)\}$ . Clearly, the construction of Y from X is uniformly computable.

If $A_n$ becomes a finite set, the first case happens, and $Y(n)=X(n,\psi (n))\in B^n_{\psi (n)}=A_n$ . If $A_n$ remains cofinite, it is easy to see that $\mathbb {N}\setminus A_n\subseteq \{X(n,i):i<\psi (n)\}$ , and therefore $Y(n)\in A_n$ . Consequently, $Y\in A$ .⊣

Proof It is clear that $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {DC}^{\mathsf {aof}}_{\mathbb {N}}$ . The argument for $\Sigma ^1_1\mbox {-}\mathsf {DC}^{\mathsf {aof}}_{\mathbb {N}}\leq _{\mathsf {W}}\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ is similar to the finite case (Theorem 3.4). If T is a $\Sigma ^1_1$ tree, for every $\sigma $ define $T_\sigma $ by the following $\Sigma ^1_1$ procedure: First, put $T_\sigma =\mathbb {N}$ , and then wait for $\text {succ}_T(\sigma ):=\{n:\sigma \mbox {}^\smallfrown n\in T\}$ to be finite but nonempty. As in the proof of Theorem 3.4, if $\text {succ}_T(\sigma )$ is finite, its finiteness is witnessed at some stage $<\omega _1^{\text {CK}}$ by Spector bounding (Theorem 1.4). For the first such stage $\alpha $ (which is not necessarily a successor ordinal), if $\text {succ}_T(\sigma )$ becomes empty, we just keep $T_\sigma =\mathbb {N}$ , and end the construction. If $\text {succ}_T(\sigma )$ turns out to be finite but nonempty, at every stage after $\alpha $ define $T_\sigma $ to be $\text {succ}_T(\sigma )$ except if this one becomes empty. Note that if $\text {succ}_T(\sigma )$ becomes a finite set at some stage $\alpha _0$ , but an empty set at a later stage $\alpha _1$ , then the least such stage $\alpha _1$ must be a successor ordinal, and therefore we can keep $T_\sigma $ being nonempty (see also the proof of Theorem 3.4). Clearly, $T_\sigma $ is either finite or $\mathbb {N}$ . If T is an instance of $\Sigma ^1_1\mbox {-}\mathsf {DC}^{\mathsf {aof}}_{\mathbb {N}}$ , then $T_\sigma =\text {succ}_T(\sigma )$ and therefore $\prod _{\sigma \in \mathbb {N}^{<\mathbb {N}}} T_\sigma \geq _M[T]$ .⊣

Proof The argument is again similar to Theorem 3.4, even though we have no compactness assumption.

By Theorem 3.10 that $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}\equiv _W\Sigma ^1_1\mbox {-}\mathsf {DC}^{\mathsf {aof}}_{\mathbb {N}}$ , it suffices to prove the result for one of the functions, let us say $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ . Let $A_e=\prod _n S^e_n$ be the e-th $\Sigma ^1_1$ homogeneous set. We set $\tilde {A_e}=\prod _n\tilde {S^e_n}$ to be defined by the following $\Sigma ^1_1$ procedure: First, set $\tilde {S^e_n}=\mathbb {N}$ , and then wait for some $S^e_n$ to become finite and nonempty. If this happens, define $\tilde {S^e_n}=S^e_n$ until it removes its last element. At this point, leave $\tilde {S^e_n}$ nonempty, which is possible since it can happen only at a successor stage (this is because $S^e_n$ has already become a finite set at some previous stage). Then, one can see that $\tilde {A_e}$ is in $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ , and if $A_e$ is also an instance of $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ then $\tilde {A_e}=A_e$ .

Then $(\tilde {A_e})_{e\in \mathbb {N}}$ is an enumeration of all nonempty elements of $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ . Define the maximum to simply be $\prod _e\prod _n\tilde {S^e_n}$ .⊣

Proof We will find $C=\prod _nC_n\in \Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ such that $C\not \leq _MA$ . Then, $B=A\times C$ will witness the theorem.

Now, let us describe the co-enumeration of $C_n$ . First, wait for $x\mapsto \Phi _n^x(n)$ to be total on A, where $\Phi _n$ is the n-th partial computable function: More precisely, as $\Phi ^x_n(n)\downarrow $ is $\Sigma ^0_1$ , the formula $\forall x(x\in A\rightarrow \Phi ^x_n(n))$ is $\Pi ^1_1$ . Hence, if it holds, it is witnessed at some stage before $\omega _1^{\text {CK}}$ (via a $\Pi ^1_1$ norm assigned to this formula). Next, since A is compact and $\Phi $ is continuous, $\Phi $ takes only finitely many values on A; that is, $\Phi _n^A(n):=\{\Phi ^x_n(n):x\in A\}$ is finite. Clearly, $\Phi _n^A(n)$ is $\Sigma ^1_1$ , and therefore, again, as in the proof of Theorem 3.4, the finiteness of $\Phi _n^A(n)$ is witnessed at some stage $\alpha $ before $\omega _1^{\text {CK}}$ . At this point, remove everything from $C_n$ except $\max \Phi _{n,\alpha }^A(n)+1$ , where $\Phi _{n,\alpha }^A(n)$ is the stage $\alpha $ approximation of $\Phi _n^A(n)$ .

We have that $C_n$ is either $\mathbb {N}$ if the co-enumeration is stuck waiting for $x\mapsto \Phi _n^x(n)$ to be total on A, or a singleton otherwise. Also, it is clear that for any n, $\Phi _n$ cannot be a witness that $C\leq _MA$ , so $C\not \leq _MA$ .⊣

Proof By Theorem 3.12 and Theorem 3.4.⊣

Proof Let $(\varphi _e)_{e\in \mathbb {N}}$ be an effective enumeration of all partial $\Pi ^1_1$ functions on $\mathbb {N}$ . Define $A_{\langle e,k\rangle }\subseteq \mathbb {N}$ for $k, e\in \mathbb {N}$ as follows. Begin with $A_{\langle e,k\rangle }=\mathbb {N}$ . Wait until we see $\varphi _e(k)\downarrow $ . If it happens, set $A_{\langle e,k\rangle }=\{\varphi _e(k)\}$ . Define $A=\prod _nA_n$ . Then define $\Psi ^p(k)=\sum _{e\leq k}p(\langle e,k\rangle )$ , which is clearly computable in p. It is easy to see that $\Psi ^p$ dominates all $\Delta ^1_1$ function whenever $p\in A$ .⊣

Proof Recall that a computable instance of $\Sigma ^1_1\mbox {-}\mathsf {K}_\sigma \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ is a countable union of compact $\Sigma ^1_1$ sets. Thus, by Lemma 3.5, there is a solution p to any given computable instance of $\Sigma ^1_1\mbox {-}\mathsf { K}_\sigma \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ such that any function which is higher Turing reducible to p is majorized by a $\Delta ^1_1$ function. However, by Proposition 3.14, there is a computable instance of $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aou}}_{\mathbb {N}\to \mathbb {N}}$ whose solution consists of $\Delta ^1_1$ dominants.⊣

Proof Clearly, $\Sigma ^1_1\mbox {-}\mathsf {AC}^{{}}_{\mathbb {N}\to \mathbb {N}}$ (and therefore $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {aof}}_{\mathbb {N}\to \mathbb {N}}$ ) is Weihrauch reducible to the parallelization of $\Sigma ^1_1\mbox {-}\mathsf {K}_\sigma \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ . Therefore, by Corollary 3.15, $\Sigma ^1_1\mbox {-}\mathsf {K}_\sigma \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ is not parallelizable. By definition, any $\Sigma ^1_1\mbox {-}\mathsf {AC}^{\mathsf {\triangledown }}_{\mathbb {N}\to \mathbb {N}}$ is parallelizable, and so is $\Sigma ^1_1\mbox {-}\mathsf {K}\mathsf { C}_{\mathbb {N}^{\mathbb {N}}}$ by Proposition 2.5.⊣

Proof We use the existence of a maximum all-or-finite degree of Theorem 3.11 to actually only prove

$$ \begin{align*}\forall B\in\Sigma^1_1\mbox{-}\mathsf{AC}^{\mathsf{aof}}_{\mathbb{N}\to\mathbb{N}},\exists A\in\Sigma^1_1\mbox{-}\mathsf{AC}^{\mathsf{cof}}_{\mathbb{N}\to\mathbb{N}}: A\not\leq_M B.\end{align*} $$

Fix a $B=\prod _{n\in \mathbb {N}}B_n$ , with $B_n\subseteq \mathbb {N}$ being either $\mathbb {N}$ or finite. We will construct $A=\prod _{e\in \mathbb {N}}A_e$ , and use $A_e$ to diagonalize against $\Phi _e$ being a witness for the reduction, by ensuring that either $\Phi _e$ is not total on B, or $\exists k\in \mathbb {N}, \sigma \in \prod _{n<k}B_n$ with $\Phi _e^\sigma (e)\downarrow \not \in A_e$ . Here is a description of the construction of $A_e$ , along with sequences of string $(\sigma _n)$ and $(\tau _n)$ :

1. 1. First, $A_e=\mathbb {N}$ . Wait for a stage where $B\subseteq \text {dom}(\Phi _e)$ , that is $\Phi _e$ is total on the current approximation of B. Define $\sigma _0=\epsilon =\tau _0$ , and move to step (2).

2. 2. Let n be the maximum such that $\tau _n$ is defined. Find $\sigma _{n+1}\succ \tau _n$ in the current approximation of B such that $\Phi _e^{\sigma _{n+1}}(e)\downarrow $ . Take $\sigma _{n+1}$ to be the leftmost such, and remove $\Phi _e^{\sigma _{n+1}}(e)$ from $A_e$ . Move to step (3).

3. 3. Wait for some stage where $\Phi _e^B(e):=\{\Phi _e^X(e):X\in B\}\subseteq A_e$ . If it happens, wait again for the current approximation of B to be “all or finite,” which will happen. Take $\tau _{n+1}$ to be the greatest prefix of $\sigma _{n+1}$ still in B, and return to step (2).

As in the proof of Theorem 3.12, the property $B\subseteq \text {dom}(\Phi _e)$ is $\Pi ^1_1$ , so it is witnessed at some stage $<\omega _1^{\text {CK}}$ . Let us prove that $A_e$ is cofinite. If the co-enumeration of $A_e$ stays at step (1), then $A_e=\mathbb {N}$ is cofinite. Otherwise, let us prove that there can only be finitely many $\tau _n$ defined.

Suppose all $\tau _n$ are defined. Then, the pointwise limit of the $\tau _n$ must be defined: Let $\ell $ be an integer such that $(\tau _n(\ell '))_{n\in \mathbb {N}}$ stabilizes for big enough n, for all $\ell '<\ell $ . Start from a stage $n_0$ where they have stabilized. For $n>n_0$ , if $\tau _{n+1}(\ell )$ changes, that is $\tau _{n+1}(\ell )\neq \tau _n(\ell )$ , it must be that $\tau _n(\ell )$ has been removed from $B_\ell $ . But then, $B_\ell $ will become finite before the co-enumeration continues, and $\tau _n(\ell )$ can only take values in $B_\ell $ and never twice the same. Therefore, $(\tau _n(\ell ))_n$ becomes constant at some point. Now, let $X\in \mathbb {N}^{\mathbb {N}}$ be the limit of $(\tau _n)$ . As $X(\ell )\in B_\ell $ for every $\ell $ , we have $X\in B$ . Since $B\subseteq \text {dom}(\Phi _e)$ is already witnessed at some previous stage, and this is a positive property, we must have $X\in \text { dom}(\Phi _e)$ . Thus, there is $\sigma \prec X$ such that $\Phi _e^\sigma (e)\downarrow $ . Let s be such that $\sigma \preceq \tau _t$ for any $t\geq s$ . However, our algorithm can reach step (2) at most once after s: This is because, as $\sigma \preceq \tau _s\preceq \sigma _{s+1}$ , we must have $\Phi _e^{\sigma _{s+1}}(e)=\Phi _e^\sigma (e)$ , which is removed from $A_e$ at step (2). This ensures that $\Phi _e^X(e)=\Phi _e^\sigma (e)\not \in A_e$ , so $\Phi _e^B(e)\subseteq A_e$ is never witnessed, and thus $\tau _{s+1}$ is undefined.

Hence, there is an $n_0$ such that $\tau _n$ is defined only for $n<n_0$ , and thus $\sigma _n$ can be defined only for $n\leq n_0$ , therefore by construction at most $n_0+1$ elements are removed from $A_e$ , and thus $A_e$ is cofinite.

It remains to prove that $A\not \leq _M B$ . Suppose $\Phi _e$ is a witness for the Medvedev reduction. $\Phi _e$ must be total on B, so we get past step (1) in the definition of $A_e$ . Then, as only finitely many $\tau _n$ are defined, the co-enumeration has to be stuck at some step, waiting for something to happen. It cannot be stuck in step (2), as $\Phi _e$ is total on B, and any finite sequence $\tau \in \prod _{n<|\sigma |} B_n$ can be extended in an element of B by homogeneity. This means that the co-enumeration is stuck at step (3), waiting for $\Phi _e^B(e)\subseteq A_e$ , to never happen. This leaves us with $\Phi _e^B(e)\not \subseteq A_e$ , so there is $X\in B$ such that $\Phi _e^X(e)\not \in A_e$ , and so $\Phi _e^X\not \in A$ .⊣

Proof Assume that $A\leq _MB$ via some partial computable function $\Phi $ , and A and B are of the forms $\prod _nA_n$ and $\prod _nB_n$ , respectively. We describe the $\Delta ^1_1$ procedure to define $C\in A$ :

Given n, in parallel, wait for n to be enumerated in one of those two $\Pi ^1_1$ sets:

1. 1. If n is enumerated in $\{n:\exists k\in \mathbb {N}, \forall f\in {\mathbb {N}^{\mathbb {N}}}, \exists \sigma \geq f,\ \Phi ^\sigma (n)=k\}$ , define $C(n)$ to be one of these k.

2. 2. If n is enumerated in $\{n:\forall f\in {\mathbb {N}^{\mathbb {N}}}, \forall k, \exists k'>k, \exists \sigma \geq f$ such that $\Phi ^\sigma (n)=k'\}$ then define $C(n)=0$ .

Here, $\sigma \geq f$ denotes the pointwise domination order, that is, $\sigma (n)\geq f(n)$ for all $n<|\sigma |$ . As the items (1) and (2) are both $\Pi ^1_1$ , it is easy to check that C is $\Delta ^1_1$ .