Proof. The proofs are straightforward from the definitions above.

Proof. Let T be a binary tree such that $\left [{T}\right ]$ is perfect. We show that no $f \in \left [{\rho _{\mathbb {N}^{\mathbb {N}}}(T)}\right ]$ is isolated, i.e., $(\forall n)(\exists g \in \left [{\rho _{\mathbb {N}^{\mathbb {N}}}(T)}\right ])(f[n] \sqsubset g \land f \neq g)$ . Fix n: by Theorem 2.8(6) we get that $\rho _{2^{\mathbb {N}}}(f) \in \left [{T}\right ]$ and, in particular, $\sigma := \rho _{2^{\mathbb {N}}}(f[n]) \in T$ . Since $\left [{T}\right ]$ is perfect, by Theorem 2.2, there exists $h \in \left [{T}\right ]$ with infinitely many ones such that $\sigma \sqsubset h$ and $\rho _{2^{\mathbb {N}}}(f) \neq h$ . By Theorem 2.8(5) $\rho _{\mathbb {N}^{\mathbb {N}}}(h) \in \left [{\rho _{\mathbb {N}^{\mathbb {N}}}(T)}\right ]$ and letting $g:= \rho _{\mathbb {N}^{\mathbb {N}}}(h)$ , we reach the conclusion.

In case T is a perfect tree, it suffices to show that $\rho _{\mathbb {N}^{\mathbb {N}}}(T)$ is pruned. Suppose there exists $\sigma \in \rho _{\mathbb {N}^{\mathbb {N}}}(T)$ with no extensions in $\rho _{\mathbb {N}^{\mathbb {N}}}(T)$ . Then $\tau := \rho _{2^{\mathbb {N}}}(\sigma )$ belongs to T and the only path in T extending $\tau $ is of the form $\tau 0^{\mathbb {N}}$ , contradicting the perfectness of T.

Proof. To show that $\mathcal {IF}$ is $\Sigma _1^1$ -complete see [Reference Kechris14, Theorem 27.1]: the theorem states the boldface case, but its proof works also in the lightface one. If $T\in \mathbf {Tr}_2$ , notice that, by König’s lemma, $T \in \mathcal {IF}_2$ iff $(\forall n)(\exists \tau \in 2^{n})(\tau \in T)$ ; hence $\mathcal {IF}_2$ is $\Pi _1^0$ and completeness is straightforward. It follows immediately that $\mathcal {WF}$ is $\Pi _1^1$ -complete and $\mathcal {WF}_2$ is $\Sigma _1^0$ -complete.

To prove that $\mathcal {T}^{>\aleph _0}$ is $\Sigma _1^1$ -complete notice that, by the Cantor–Bendixson theorem for trees, $T \in \mathcal {T}^{>\aleph _0} $ iff $(\exists S \subseteq T)(S \text { is nonempty and perfect})$ : the latter is a $\Sigma _1^1$ formula and it remains to show that $\mathcal {T}^{>\aleph _0}$ is complete for $\Sigma _1^1$ sets. This is immediate as $T \in \mathcal {IF} \iff \mathsf {Expl}(T) \in \mathcal {T}^{>\aleph _0}$ . The proof for $\mathcal {T}^{>\aleph _0}_2$ is similar and it follows immediately that $\mathcal {T}^{\leq \aleph _0}$ and $\mathcal {T}^{\leq \aleph _0}_2$ are $\Pi _1^1$ -complete.

To prove that $\mathcal {UB}$ is $\Pi _1^1$ -complete notice that, by the effective perfect set theorem (see [Reference Moschovakis20, Theorem 4F.1]), $T \in \mathcal {UB}$ iff

$$\begin{align*}(\exists p \in \mathsf{HYP}(\mathbb{N}^{\mathbb{N}}))(p \in \left[{T}\right]) \land (\forall \tau,\tau')(\tau ~|~ \tau' \implies T_\tau \in \mathcal{WF} \lor T_{\tau'} \in \mathcal{WF}),\end{align*}$$

where $\mathsf {HYP}(\mathbb {N}^{\mathbb {N}})$ is the set of hyperarithmetical elements in $\mathbb {N}^{\mathbb {N}}$ . Notice that the formula is $\Pi _1^1$ : indeed, the second conjunct is clearly $\Pi _1^1$ and by Kleene’s quantification theorem (see [Reference Moschovakis20, Theorem 4D.3]), the first conjunct is $\Pi _1^1$ as well. It remains to show that $\mathcal {UB}$ is complete for $\Pi _1^1$ sets. To do so, it suffices to notice that $T \in \mathcal {WF}$ iff $S \in \mathcal {UB}$ , where $S:= \{0^n:n \in \mathbb {N}\} \sqcup T$ (indeed, $\left [{S}\right ]=\{0^{\mathbb {N}}\} \cup \{1p:p \in \left [{T}\right ]\}$ ). If $T \in \mathbf {Tr}_2$ , notice that $T \in \mathcal {UB}_2$ iff

$$\begin{align*}T \in \mathcal{IF}_2 \land (\forall \tau,\tau')(\tau ~|~ \tau' \implies T_\tau \in \mathcal{WF}_2 \lor T_{\tau'} \in \mathcal{WF}_2).\end{align*}$$

The formula is clearly $\Pi _2^0$ and proving completeness is straightforward.

Proof. The reduction $ {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \le _{\mathrm {W}} {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ is trivial; by the effective version of the Novikov–Kondo–Addison uniformization theorem [Reference Moschovakis20, Theorem 4E.4], we obtain ${\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \le _{\mathrm {W}} {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ . Hence, $\widehat {{\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} } \equiv _{\mathrm {W}} \widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} }$ .

By [Reference Kihara, Marcone and Pauly15, Theorem 3.11] $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {W}}\widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{2}} }$ (in [Reference Kihara, Marcone and Pauly15] $\widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{2}} }$ is denoted by $\boldsymbol {\Delta }_1^1\text {-}\mathsf {CA}$ ). Since $\widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{2}} }\le _{\mathrm {W}}\widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} }$ is trivial, we obtain $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {W}} \widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} }$ . To complete the proof of the equivalence between the first three problems, it suffices to show that $ {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \le _{\mathrm {W}} \widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{2}} }$ and then notice that $\widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{2}} }$ is parallelizable. We can think of an input for $ {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ as a sequence $(T^i)_{i \in \mathbb {N}} \in \mathbf {Tr}^{\mathbb {N}}$ such that exactly one $T^i$ belongs to $\mathcal {WF}$ . For every i, we compute the pair of trees $(S^i,R^i)$ where $S^i:=\underset {j\leq i}{*}T^j$ and $R^i:=\underset {j> i}{*}T^j$ : notice that exactly one of $S^i$ and $R^i \in \mathcal {WF}$ . We can view the sequence $(S^i,R^i)_{i \in \mathbb {N}}$ as an instance of $\widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{2}} }$ . Finally, let $n:=\min \big \{m: \widehat { {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{2}} }((S^i,R^i)_{i \in \mathbb {N}}))(m)=0 \big \}$ . Clearly $T^n \in \mathcal {WF}$ .

The last two (strict) reductions are [Reference Kihara, Marcone and Pauly15, Theorem 4.3] and [Reference Anglès d’Auriac and Kihara1, Theorem 3.34].

Proof. Let ${{f}} :\subseteq {\mathbb {N}^{\mathbb {N}}} \rightrightarrows {\mathbb {N}}$ be a partial multi-valued function and assume that $f\le _{\mathrm {W}} h$ via $\Phi ,\Psi $ . For every $p\in \operatorname {dom}(f)$ and let $\Phi (p)$ be a name for $x\in \operatorname {dom}(h)$ . Consider the set

$$\begin{align*}A(x):=U(x) \cap \{\sigma \in \mathbb{N}^{<\mathbb{N}}: \Psi(p[\left|{\sigma}\right|],\sigma)(0)\downarrow \}. \end{align*}$$

Observe that $A(x) \neq \emptyset $ : indeed, by hypothesis, there is $q\in \delta _Y^{-1}(h(x))$ such that $(\forall n \in \mathbb {N} )(\exists \sigma \in U(x))(q[n] \sqsubseteq \sigma )$ . Since $\Phi ,\Psi $ witness a Weihrauch reduction, there is n such that $\Psi (p[n],q[n])(0)\downarrow $ . Let $\sigma \in U$ such that $q[n]\sqsubseteq \sigma $ . By continuity, $\Psi (p[\left |{\sigma }\right |],\sigma )(0)\downarrow $ and therefore $\sigma \in A(x)$ .

Notice that $A(x) \in \Lambda ^p$ where $\Lambda $ is:

• • $\Gamma $ if $\Gamma $ contains all $\Sigma _1^0$ sets;

• • $\Sigma _2^0$ if $\Gamma =\Pi _1^0$ ;

• • and $\Sigma _1^0$ if $\Gamma =\Delta _1^0$ .

It is easy to observe that ${\boldsymbol {\Sigma }_{n+1}^0}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} {\boldsymbol {\Pi }_n^0}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ for every n, and hence, in any case, ${\boldsymbol {\Gamma }}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} {\boldsymbol {\Lambda }}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ . Applying ${\boldsymbol {\Lambda }}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ to $A(x)$ produces a string $\sigma $ such that $\Psi (p[\left |{\sigma }\right |],\sigma )(0)\in f(p)$ as $\sigma \in U(x) \subseteq \mathbf {Prefixes}(x)$ .

Proof. The equivalence ${}^1{\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}}\equiv _{\mathrm {W}} {\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ is proved in [Reference Le Goh, Pauly and Valenti18, Proposition 2.4]; essentially the same proof shows that ${}^1{\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}}\equiv _{\mathrm {W}} {\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ .

If $A\subseteq \mathbb {N}$ is a singleton then $n \in A$ iff $(\forall m\neq n)(m \notin A)$ . This implies that A is $\Sigma _1^1$ iff A is $\Pi _1^1$ iff A is $\Delta _1^1$ and this shows that $ {\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} {\boldsymbol {\Delta }_1^1}\text {-}\mathsf {UC}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ . These equivalences, together with Theorems 2.14 and 2.16 allow us to derive all the stated equivalent characterizations of ${}^1{\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}}$ .

By Theorem 2.16, $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}} <_{\mathrm {W}} \widehat {{\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} }$ : since $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ is parallelizable, this implies ${\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \not \le _{\mathrm {W}} \mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ and hence ${}^1{\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}} <_{\mathrm {W}} {}^1{\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}}$ .

Proof. The equivalences in (i) are from [Reference Soldà and Valenti25, Theorem 7.2]. It follows from [Reference Soldà and Valenti25, Theorem 5.10(5)] that $\widehat { \mathsf {LPO} ^{(n)^{u*}}} \equiv _{\mathrm {W}} \widehat { \mathsf {LPO} ^{(n)}} \equiv _{\mathrm {W}} \mathsf {lim}^{(n)}$ ; since $\mathsf {lim}^{(n)} <_{\mathrm {sW}} \mathsf {lim}^{(n+1)}$ this implies the non-reductions in (i) and (ii).

The equivalence in (iii) is from Theorem 2.18, while the strictness follows from (i).

Proof. The reduction $\mathsf {PTT}_{1}{\restriction }\mathbf {Tr}_2\le _{\mathrm {sW}} \mathsf {PTT}_{1}$ is trivial.

We now prove that $\mathsf {PST}_{2^{\mathbb {N}}} \le _{\mathrm {sW}} \mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}$ . Let $T \in \mathbf {Tr}_2$ and let the forward functional be the identity. Let P be a name for $\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}([T])$ : even if $P\in \mathbf {Tr}$ , notice that $\left [{P}\right ]$ is perfect and $\left [{P}\right ]\subseteq 2^{\mathbb {N}}$ . Let $\Psi (P)=\{\sigma \in P: \sigma \in 2^{<\mathbb {N}}\}$ and notice that $\Psi (P)$ is a name for an element $\mathsf {PST}_{2^{\mathbb {N}}}(\left [{T}\right ])$ .

For the other direction, the reduction $\mathsf {PTT}_{1}\le _{\mathrm {sW}}\mathsf {PTT}_{1}{\restriction }\mathbf {Tr}_2 $ is witnessed by the maps $\rho _{2^{\mathbb {N}}}$ (forward) and $\rho _{\mathbb {N}^{\mathbb {N}}}$ (backward) from Theorem 2.5. Let $T\in \mathcal {T}^{>\aleph _0}$ and let $P \in \mathsf {PTT}_{1}\restriction \mathbf {Tr}_2(\rho _{2^{\mathbb {N}}}(T))$ . By Theorem 2.9, $\rho _{\mathbb {N}^{\mathbb {N}}}(P)$ is a perfect tree. To show that $\rho _{\mathbb {N}^{\mathbb {N}}}(P) \subseteq T$ , it suffices to prove that $\left [{\rho _{\mathbb {N}^{\mathbb {N}}}(P)}\right ]\subseteq \left [{T}\right ]$ . Let $f \in \left [{\rho _{\mathbb {N}^{\mathbb {N}}}(P)}\right ]$ : by Theorem 2.8(6) we have that $\rho _{2^{\mathbb {N}}}(f) \in \left [{P}\right ]\subseteq \left [{\rho _{2^{\mathbb {N}}}(T)}\right ]$ and by Theorem 2.8(4) we conclude that $f \in \left [{T}\right ]$ .

The proof that $\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {sW}} \mathsf {PST}_{2^{\mathbb {N}}}$ is similar.

Proof. Since $\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {sW}} \mathsf {PST}_{2^{\mathbb {N}}}$ (Theorem 3.3), we prove the lemma with $\mathsf {PST}_{2^{\mathbb {N}}}$ in place of $\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}$ .

To show $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {sW}}\mathsf {PST}_{2^{\mathbb {N}}}$ , fix $T \in \mathcal {UB}$ an let $p_0$ be the unique element of $\left [{T}\right ]$ . Let $S:= \rho _{2^{\mathbb {N}}}(\mathsf {Expl}(T))$ and notice that, by definition of $\mathsf {Expl}(\cdot )$ and by Theorem 2.8(4), all paths in $ \left [{S}\right ]$ are either eventually zero or are of the form $\rho _{2^{\mathbb {N}}}(p_0*q)$ for some $q \in 2^{\mathbb {N}}$ .

Fix a name P for an element of $\mathsf {PST}_{2^{\mathbb {N}}}(\left [{S}\right ])$ . We claim that all the paths in $\left [{P}\right ]$ are of the form $\rho _{2^{\mathbb {N}}}(p_0*q)$ for some $q \in 2^{\mathbb {N}}$ . To prove this, we need to rule out that some eventually zero path belongs to $\left [{P}\right ]$ . Let $r \in 2^{\mathbb {N}}$ be of the form $\sigma 0^{\mathbb {N}}$ , where $\sigma =\langle \rangle $ or $\sigma (\left |{\sigma }\right |-1)=1$ . Notice that $\rho _{2^{\mathbb {N}}}(\rho _{\mathbb {N}^{\mathbb {N}}}(\sigma ))=\sigma $ . Let

$$\begin{align*}k:= \begin{cases} p_0( {\left|{\rho_{\mathbb{N}^{\mathbb{N}}}(\sigma)}\right|}/2) & \text{if } \left|{\rho_{\mathbb{N}^{\mathbb{N}}}(\sigma)}\right| \text{ is even},\\ 1 & \text{otherwise,} \end{cases}\end{align*}$$

and set $m= \left |{\sigma }\right |+ k +1$ . It suffices to prove that

$$ \begin{align*}(\forall q \in 2^{\mathbb{N}})(r[m]\not\sqsubset \rho_{2^{\mathbb{N}}}(p_0*q)),\end{align*} $$

so that all paths in $\left [{S}\right ]$ which extend $r[m]$ are eventually zero and $S_{r[m]} \in \mathcal {T}^{\leq \aleph _0}$ , which implies $r \notin \left [{P}\right ]$ . Fix $q \in 2^{\mathbb {N}}$ :

• • if $\sigma \not \sqsubset \rho _{2^{\mathbb {N}}}(p_0*q)$ then $r[m]\not \sqsubset \rho _{2^{\mathbb {N}}}(p_0*q)$ ;

• • if $\sigma \sqsubset \rho _{2^{\mathbb {N}}}(p_0*q)$ then either $\sigma 0^k 1$ or $\sigma 0^{k-1} 1$ (in case $\left |{\rho _{\mathbb {N}^{\mathbb {N}}}(\sigma )}\right |$ is odd and $q((\left |{\rho _{\mathbb {N}^{\mathbb {N}}}(\sigma )}\right | -1)/2) =0$ ) is a prefix of $\rho _{2^{\mathbb {N}}}(p_0*q)$ which is incomparable with $r[m] = \sigma 0^{k+1}$ ; hence $r[m] \not \sqsubset \rho _{2^{\mathbb {N}}}(p_0*q)$ also in this case.

We show how to computably retrieve $p_0$ from ${P}$ . To find $p_0(0)$ we search for n such that

$$ \begin{align*}(\forall \tau \in 2^{n+1})( P_\tau \in \mathcal{IF}_2 \implies \tau = 0^{n}1 ).\end{align*} $$

Indeed, the previous claim implies that the unique n satisfying this condition is $p_0(0)$ . Since $\mathcal {IF}_2$ is a $\Pi _1^0$ set (Theorem 2.11(i)), the above condition is $\Sigma _1^0$ and at some finite stage we find $p_0(0)$ .

Suppose now that we computed the first i coordinates of $p_0$ , i.e., $p_0[i]$ . We generalize the previous strategy to compute $p_0(i)$ . Let

$$ \begin{align*}A_i:= \{0^{p_0(0)} 1 \xi_0 0^{p_0(1)} 1 \xi_1 \dots \xi_{i-2} 0^{p_0(i-1)} 1 \xi_{i-1} \in P: (\forall j<i) (\xi_j \in \{1,01\})\} \end{align*} $$

(recall that $\rho _{2^{\mathbb {N}}}(0)=1$ and $\rho _{2^{\mathbb {N}}}(1)=01$ ). Informally, the $\xi _j$ ’s come from the interleaving of sequences in T with sequences in $2^{<\mathbb {N}}$ . Notice that $A_i$ is finite and nonempty; moreover, there exists $\sigma \in A_i$ which is the prefix of some path in $\left [{P}\right ]$ . We search for n satisfying the $\Sigma _1^0$ property

$$ \begin{align*}(\forall \sigma \in A_i)(\forall \tau \in 2^{n+1})( P_{\sigma\tau} \in \mathcal{IF}_2 \implies \tau = 0^{n}1 ).\end{align*} $$

As before the claim implies that the unique n satisfying this condition is $p_0(i)$ . The main difference with the case $i=0$ is that it may be the case that different sequences in $A_i$ are prefixes of paths in $\left [{P}\right ]$ that come from the interleaving of $p_0$ with different elements of $2^{\mathbb {N}}$ . However, any such $\sigma $ provides the correct $n = p_0(i)$ . This ends the proof of the reduction.

To show that $\mathsf {PST}_{2^{\mathbb {N}}}\not <_{\mathrm {W}}\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ , recall from Section 2.2 that $\mathsf {lim}*\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {W}} \mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ , so it suffices to show that $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {W}} \mathsf {lim}*\mathsf {PST}_{2^{\mathbb {N}}}$ . From [Reference Kihara, Marcone and Pauly15, Proposition 6.3] and Theorem 3.3, it follows that $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {W}} \mathsf {PTT}_{1}\equiv _{\mathrm {W}} \mathsf {PTT}_{1}\restriction \mathbf {Tr}_2$ and hence it is enough to show that $\mathsf {PTT}_{1}\restriction \mathbf {Tr}_2\le _{\mathrm {W}} \mathsf {lim}*\mathsf {PST}_{2^{\mathbb {N}}}$ . From [Reference Nobrega and Pauly21, Lemma 4.46], we know that $\mathsf {lim}$ is equivalent to the function that prunes elements in $\mathbf {Tr}_2$ . So let $T\in \mathcal {T}^{>\aleph _0}_2$ be the input of $\mathsf {PTT}_{1}\restriction \mathbf {Tr}_2$ and let P be a name for an element of $\mathsf {PST}_{2^{\mathbb {N}}}(\left [{T}\right ])$ : pruning P with $\mathsf {lim}$ is enough to obtain a perfect subtree of T.

Proof. The fact that ${\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \le _{\mathrm {W}}{}^1{\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}}$ follows from the fact that ${}^1{\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}}\equiv _{\mathrm {W}}{\boldsymbol {\Pi }^1_1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ by Theorem 2.18 and $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}<_{\mathrm {sW}}\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}$ by Theorem 3.4.

For the opposite direction, with the goal of using Theorem 2.17, let ${{U}} :\subseteq {\mathbf {Tr}}\rightarrow {\boldsymbol {\Pi }_1^1(\mathbb {N}^{<\mathbb {N}})}$ be defined by

$$\begin{align*}U(T) :=\{s \in \mathbb{N}^{<\mathbb{N}}: s \text{ is a prefix of a tree } \land (\forall \tau)(s(\tau)=0\implies T_\tau \in \mathcal{T}^{\leq\aleph_0})\} \end{align*}$$

for any $T \in \mathcal {T}^{>\aleph _0}$ ; $U(T)$ is $\boldsymbol {\Pi }_1^1$ as $\mathcal {T}^{\leq \aleph _0}$ is $\Pi _1^1$ (see Theorem 2.11(ii)).

The elements of $U(T)$ are the prefixes of the names for the perfect kernel of T, and hence belong to $\mathbf {Prefixes}(T)$ . Moreover if q is any name for the perfect kernel of T then $q[n] \in U(T)$ for all n. Hence Theorem 2.17 applies and we obtain ${}^1{\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}} \le _{\mathrm {W}} {\boldsymbol {\Pi }^1_1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ .

Proof. The first strict reduction and the first equivalence were proven in Theorems 3.4 and 3.3, respectively. The last reduction follows from the fact $\mathsf {PTT}_{1}\equiv _{\mathrm {W}} \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ [Reference Kihara, Marcone and Pauly15, Proposition 6.3] and a solution for $\mathsf {PTT}_{1}$ is also a solution for $\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}$ . Strictness follows by Theorem 3.5 as, by Theorem 2.18, ${\boldsymbol {\Pi }^1_1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} <_{\mathrm {W}}{}^1{\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}}$ .

Proof. The fact that $\mathsf {List}_{2^{\mathbb {N}},< \omega } ~|_{\mathrm {W}~} \mathsf {wList}_{2^{\mathbb {N}}, \leq \omega }$ is [Reference Kihara, Marcone and Pauly15, Corollary 6.15].

To prove that $\mathsf {wList}_{2^{\mathbb {N}}, \leq \omega } \le _{\mathrm {W}}\mathsf {wList}_{2^{\mathbb {N}}}$ , let $A \in \mathcal {A}({2^{\mathbb {N}}})$ be countable and nonempty and let $(b_i,p_i)_{i \in \mathbb {N}} \in \mathsf {wList}_{2^{\mathbb {N}}}(A)$ . Then, $\{p_i:b_i=1\}$ can be easily rearranged, and possibly duplicated, to produce an element of $\mathsf {wList}_{2^{\mathbb {N}}, \leq \omega }(A)$ .

For the opposite direction, let $A \in \mathcal {A}({2^{\mathbb {N}}})$ be countable and possibly empty. Define $A':=\{0^{\mathbb {N}}\} \cup \{1 x: x \in A\}$ : $A'$ is still countable but nonempty, i.e., a suitable input for $\mathsf {wList}_{2^{\mathbb {N}}, \leq \omega }$ . Let $(p_i)_{i \in \mathbb {N}}\in \mathsf {wList}_{2^{\mathbb {N}}, \leq \omega }(A')$ : then $(p_i(0),p_i^-)_{i \in \mathbb {N}} \in \mathsf {wList}_{2^{\mathbb {N}}}(A)$ .

The reductions $\mathsf {wList}_{2^{\mathbb {N}}} \le _{\mathrm {W}} \mathsf {List}_{2^{\mathbb {N}}}$ and $\mathsf {List}_{2^{\mathbb {N}},<\omega }\le _{\mathrm {W}} \mathsf {List}_{2^{\mathbb {N}}}$ are immediate. Strictness follows from incomparability of $\mathsf {wList}_{2^{\mathbb {N}}}$ and $\mathsf {List}_{2^{\mathbb {N}}, < \omega }$ .

By Theorem 3.8 and [Reference Kihara, Marcone and Pauly15, Theorem 6.4] we obtain that $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}} \equiv _{\mathrm {W}} \mathsf {wList}_{\mathbb {N}^{\mathbb {N}}} \equiv _{\mathrm {W}} \mathsf {List}_{\mathbb {N}^{\mathbb {N}}}$ .

The reduction $\mathsf {List}_{2^{\mathbb {N}}}\le _{\mathrm {W}} \mathsf {List}_{\mathbb {N}^{\mathbb {N}}}$ is obvious. To prove that $\mathsf {List}_{\mathbb {N}^{\mathbb {N}}}\not \le _{\mathrm {W}} \mathsf {List}_{2^{\mathbb {N}}}$ we recall that by Theorem 2.19(i) and (iii) ${\boldsymbol {\Pi }_3^0}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} <_{\mathrm {W}} {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} {}^1{\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}}$ . It thus suffices to show that ${}^1{\mathsf {List}_{2^{\mathbb {N}}}}\le _{\mathrm {W}}{\boldsymbol {\Pi }_3^0}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ and to this end we use Theorem 2.17. Consider the formula

$$\begin{align*}(\exists \sigma_0,\dots,\sigma_{n-1})(\forall i \neq j< n)(\sigma_i ~|~ \sigma_j \land T_{\sigma_i} \in \mathcal{IF}_2), \end{align*}$$

that we denote by $\varphi (n,T)$ . Since $\mathcal {IF}_2$ is $\Pi _1^0$ (see Theorem 2.11(i)) $\varphi $ is $\Sigma _2^0$ . Notice that in this case $\mathbf {Prefixes}(T)$ is the set of all $n\rho $ such that, if we read $\rho $ as the dove-tailing of the strings $(b_i\sigma _i)_{i< m}$ for some $m \in \mathbb {N}$ , then

• • $(\forall i < m)(b_i=1 \implies T_{\sigma _i} \in \mathcal {IF}_2)$ ;

• • $(n=0 \land (\forall k)(\varphi (k,T))) \lor (n>0 \land \varphi (n-1,T) \land \lnot \varphi (n,T))$ .

Since $\mathbf {Prefixes}(T)$ is $\Pi _3^{0,T}$ we can apply Theorem 2.17 to $U:=T \mapsto \mathbf {Prefixes}(T)$ , thereby concluding the proof.

Proof. To prove the claim it suffices to show that $\widehat {\mathsf {wList}_{2^{\mathbb {N}}}}\le _{\mathrm {W}} \mathsf {wList}_{2^{\mathbb {N}}}$ . Given $(T^n)_{n \in \mathbb {N}}$ , an input for $\widehat {\mathsf {wList}_{2^{\mathbb {N}}}}$ , i.e., a sequence of binary trees with countable body, compute and notice that $T \in \mathbf {Tr}_2$ (see Theorem 2.3). Given $(b_i,p_i) \in \mathsf {wList}_{2^{\mathbb {N}}}(T)$ , it is straightforward to check that $\{(b_i,p_i): b_i=1 \land 0^n1\sqsubset p_i\} \in \mathsf {wList}_{2^{\mathbb {N}}}(T^n)$ .

Proof. We first show that ${}^1{\mathsf {wList}_{2^{\mathbb {N}}}}\le _{\mathrm {W}} \mathsf {C}^{\mathsf {\vphantom {g}}}_{{\mathbb {N}}} $ , and to do so, we use Theorem 2.17.

Let $T\in \mathcal {T}^{\leq \aleph _0}_2$ and notice that $\mathbf {Prefixes}(T)$ is the set of all $\rho \in 2^{<\mathbb {N}}$ such that if we read $\rho $ as the dove-tailing of the strings $(b_i\sigma _i)_{i< m}$ for some $m \in \mathbb {N}$ then $(\forall i < m)(b_i=1 \implies T_{\sigma _i} \in \mathcal {IF}_2)$ . Since $\mathcal {IF}_2$ is a $\Pi _1^{0}$ set (Theorem 2.11(i)), $\mathbf {Prefixes}(T)$ is $\Pi _1^{0,T}$ . Thus, we can apply Theorem 2.17 to $U:=T \mapsto \mathbf {Prefixes}(T)$ , thereby concluding the proof of the left-to-right direction.

We now show that $\mathsf {C}^{\mathsf {\vphantom {g}}}_{{\mathbb {N}}} \le _{\mathrm {W}} \mathsf {wList}_{2^{\mathbb {N}}}$ . Let $A \in \mathcal {A}({\mathbb {N}})$ be nonempty, and let $A^c[s]$ denote the enumeration of the complement of A up to stage s. We compute the tree

$$ \begin{align*}T:= \{\langle \rangle\} \cup \{0^n10^{s}: n \notin A^c[s]\}.\end{align*} $$

Notice that for every n, $n \in A$ iff $0^n10^{\mathbb {N}} \in \left [{T}\right ]$ . Given $(b_i,p_i)_{i \in \mathbb {N}} \in \mathsf {wList}_{2^{\mathbb {N}}}(\left [{T}\right ])$ , we computably search for some i such that $b_i=1$ and $0^n1\sqsubset p_i$ for some $n \in \mathbb {N}$ (such an i exists because A is nonempty). By construction, $n \in \mathsf {C}^{\mathsf {\vphantom {g}}}_{{\mathbb {N}}} (A)$ .

Proof. The fact that $\mathsf {WF}\not \le _{\mathrm {W}} \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ was already noticed in [Reference Kihara, Marcone and Pauly15, page 1033].

To show that $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {W}} \widehat {\mathsf {WF}}$ it suffices to notice that $\mathsf {PTT}_{1}\equiv _{\mathrm {W}} \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ [Reference Kihara, Marcone and Pauly15, Proposition 6.3] and $\mathsf {PK}$ clearly computes $\mathsf {PTT}_{1}$ . The strictness of the reduction is immediate by the first part of this proposition and the fact that $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ is parallelizable.

Proof. Towards a contradiction, suppose that $\mathsf {lim}*\widehat {\mathsf {WF}} \le _{\mathrm {W}} \widehat {\mathsf {WF}}$ . By the definition of compositional product (see Section 2.2) and the facts that $\mathsf {lim} \equiv _{\mathrm {sW}} \mathsf {J}$ and $\mathsf {J} \circ \widehat {\mathsf {WF}}$ is defined, let $\Phi $ and $\Psi $ witness $\mathsf {J}\circ \widehat {\mathsf {WF}} \le _{\mathrm {W}} \widehat {\mathsf {WF}}$ .

Let $(T^i)_{i \in \mathbb {N}}$ be a computable list of all computable elements $\mathbf {Tr}$ and notice that $\widehat {\mathsf {WF}}((T^i)_{i \in \mathbb {N}}) \equiv _T \mathsf {HJ}(\emptyset )$ . Then, $\Phi ((T^i)_{i \in \mathbb {N}})$ is a computable list of trees and $\widehat {\mathsf {WF}}(\Phi ((T^i)_{i \in \mathbb {N}}))$ is Turing reducible to $\mathsf {HJ}(\emptyset ) \equiv _T \mathsf {HJ}({\Phi ((T^i)_{i \in \mathbb {N}})})$ . Therefore, $\Psi \big ((T^i)_{i \in \mathbb {N}}, \widehat {\mathsf {WF}}(\Phi ((T^i)_{i \in \mathbb {N}}))\big ) \leq _T \mathsf {HJ}(\emptyset )$ as well. On the other hand, $(\mathsf {J}\circ \widehat {\mathsf {WF}}) ((T^i)_{i \in \mathbb {N}})$ computes the Turing jump of $\mathsf {HJ}(\emptyset )$ , which is not Turing reducible $\mathsf {HJ}(\emptyset )$ .

Proof. We follow the pattern of the proof of Theorem 3.3.

$\mathsf {PK}{\restriction }\mathbf {Tr}_2\le _{\mathrm {sW}}\mathsf {PK}$ is trivial and $\mathsf {PK}_{2^{\mathbb {N}}} \le _{\mathrm {sW}} \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ is witnessed by the same functionals of the proof of $\mathsf {PST}_{2^{\mathbb {N}}}\le _{\mathrm {sW}}\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}$ in Theorem 3.3. Given $T \in \mathbf {Tr}_2$ , and a name P for $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}(\left [{T}\right ])$ we get $\left [{\Psi (P)}\right ]=\left [{P}\right ]$ . Hence, $\Psi (P)$ is a name for $\mathsf {PK}_{2^{\mathbb {N}}}(\left [{T}\right ])$ .

For the opposite directions, we only deal with $\mathsf {PK} \le _{\mathrm {sW}} \mathsf {PK}{\restriction }\mathbf {Tr}_2$ , as the proof of $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {sW}} \mathsf {PK}_{2^{\mathbb {N}}}$ follows the same pattern. Again, the reduction is witnessed by the same functionals of the analogous proof in Theorem 3.3. Fix $T\in \mathbf {Tr}$ and let $P:= \mathsf {PK}(\rho _{2^{\mathbb {N}}}(\left [{T}\right ]))$ . As before, set $\Psi (P):=\rho _{\mathbb {N}^{\mathbb {N}}}(P)$ . To prove the reduction, it suffices to show that $\left |{\left [{T}\right ]\setminus \left [{\rho _{\mathbb {N}^{\mathbb {N}}}(P)}\right ]}\right |\leq \aleph _0$ . We claim that $\left [{T}\right ]\setminus \left [{\rho _{\mathbb {N}^{\mathbb {N}}}(P)}\right ]\subseteq \{\rho _{\mathbb {N}^{\mathbb {N}}}(q): q \in \left [{\rho _{2^{\mathbb {N}}}(T)}\right ]\setminus \left [{P}\right ]\land (\exists ^\infty i)(q(i)=1)\}$ , which completes the proof as the set on the right-hand side is countable. If $p \in \left [{T}\right ]\setminus \left [{\rho _{\mathbb {N}^{\mathbb {N}}}(P)}\right ]$ , then by Theorem 2.8(4) and (6) we have that $\rho _{2^{\mathbb {N}}}(p) \in \left [{\rho _{2^{\mathbb {N}}}(T)}\right ] \setminus \left [{P}\right ]$ . Moreover, $q:=\rho _{2^{\mathbb {N}}}(p)$ has infinitely many ones and, by Theorem 2.8(2), $p=\rho _{\mathbb {N}^{\mathbb {N}}}(q)$ .

Proof. To prove the statement, by Theorem 4.5, it is enough to show that $\widehat {\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}\le _{\mathrm {sW}}\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ . Given $(T^i)_{i \in \mathbb {N}}$ an input for $\widehat {\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}$ , let P be a name for $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}(\left [{\bigsqcup _{{i \in \mathbb {N}}}{T^i}}\right ])$ . By the definitions of perfect kernel and disjoint union of trees we have that for every i, $\{\sigma : i^\smallfrown \sigma \in P\}$ is a name for $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}(\left [{T^i}\right ])$ .

Proof. All six functions are parallelizable (this is either obvious or follows from Theorems 4.6 and 4.2) and hence it is enough to show that $\operatorname {id}$ strongly Weihrauch reduces to each of them. As $\widehat {\mathsf {WF}_{\mathbb {S}}} \le _{\mathrm {sW}} \widehat {\mathsf {WF}} \equiv _{\mathrm {sW}} \mathsf {PK} \equiv _{\mathrm {sW}} \mathsf {PK}{\restriction }\mathbf {Tr}_2$ (Theorems 4.5 and 4.2) and $\mathsf {PK}_{2^{\mathbb {N}}} \equiv _{\mathrm {sW}} \mathsf {PK}_{\mathbb {N}^`\mathbb {N}}$ (Theorem 4.5), it suffices to show that $\operatorname {id} \le _{\mathrm {sW}} \widehat {\mathsf {WF}_{\mathbb {S}}}$ and $\operatorname {id} \le _{\mathrm {sW}} \mathsf {PK}_{2^{\mathbb {N}}}$ .

For the first reduction let p be an input for $\operatorname {id}$ . For any $i,j \in \mathbb {N}$ let

$$\begin{align*}T^{\langle i,j \rangle}:=\begin{cases} \emptyset & \text{if } p(i)=j,\\ 2^{<\mathbb{N}} & \text{if } p(i)\neq j. \end{cases} \end{align*}$$

Let $\widehat {\mathsf {WF}_{\mathbb {S}}}((T^{\langle i,j \rangle })_{i,j \in \mathbb {N}})=(a_{\langle i,j \rangle })_{i,j \in \mathbb {N}}$ . To compute $p(i)$ we search for the unique j such that $a_{\langle i,j \rangle }=1_{\mathbb {S}}$ (recall that the set of names for $1_{\mathbb {S}}$ is $\boldsymbol {\Sigma }_1^0$ ).

For the second reduction, recall that by Theorem 3.4, $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {sW}}\mathsf {PST}_{2^{\mathbb {N}}}$ , clearly $\mathsf {PST}_{2^{\mathbb {N}}}\le _{\mathrm {sW}}\mathsf {PK}_{2^{\mathbb {N}}}$ and $\operatorname {id} \le _{\mathrm {sW}}\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ .

Proof. Recall that by Theorem 4.5, $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {W}} \mathsf {PK}_{2^{\mathbb {N}}}$ so that it suffices to show that $\mathsf {PK}_{2^{\mathbb {N}}} \equiv _{\mathrm {W}} \widehat {\mathsf {WF}_{\mathbb {S}}}$ .

Let $T\in \mathbf {Tr}_2$ be a name for an input of $\mathsf {PK}_{2^{\mathbb {N}}}$ . Notice that $\{\sigma : T_\sigma \in \mathcal {T}^{\leq \aleph _0}_2\}$ is $\Pi _1^{1,T}$ (see Theorem 2.11(ii)) and hence, using Theorem 2.11(i), we can compute from T a sequence $(S(\sigma ))_{\sigma \in 2^{<\mathbb {N}}} \in \mathbf {Tr}^{\mathbb {N}}$ such that $S(\sigma ) \in \mathcal {WF}$ iff $T_\sigma \in \mathcal {T}^{\leq \aleph _0}_2$ . Let $A:=\{p \in 2^{\mathbb {N}}: (\forall n)(\mathsf {WF}_{\mathbb {S}}(S(p[n]))=0_{\mathbb {S}})\}$ : since the set of names for $0_{\mathbb {S}}$ is $\boldsymbol {\Pi }_1^0$ , $A \in \mathcal {A}({2^{\mathbb {N}}})$ and we can compute $U \in \mathbf {Tr}_2$ with $\left [{U}\right ]=A$ . Notice that for any $\tau \in U$ , $\tau $ is a prefix of a path through $\left [{U}\right ]$ iff $T_\tau \in \mathcal {T}^{>\aleph _0}$ . Therefore, U is a name for $\mathsf {PK}_{2^{\mathbb {N}}}(\left [{T}\right ])$ .

To show that $\widehat {\mathsf {WF}_{\mathbb {S}}} \le _{\mathrm {W}} \mathsf {PK}_{2^{\mathbb {N}}}$ , as $\mathsf {PK}_{2^{\mathbb {N}}}$ is parallelizable it suffices to prove that $\mathsf {WF}_{\mathbb {S}} \le _{\mathrm {W}} \mathsf {PK}_{2^{\mathbb {N}}}$ . Let $T \in \mathbf {Tr}$ be an input for $\mathsf {WF}_{\mathbb {S}}$ and notice that $T \in \mathcal {WF}$ iff $\mathsf {Expl}(T) \in \mathcal {WF}$ iff $\rho _{2^{\mathbb {N}}}(\mathsf {Expl}(T)) \in \mathcal {T}^{\leq \aleph _0}$ . Hence, if S is a name for $ \mathsf {PK}_{2^{\mathbb {N}}}(\left [{\rho _{2^{\mathbb {N}}}(\mathsf {Expl}(T))}\right ])$ , $T \in \mathcal {WF}$ iff $S \in \mathcal {WF}_2$ . Since $\mathcal {WF}_2$ is a $\Sigma _1^0$ set (see Theorem 2.11(i)), given S we can uniformly compute a name for $\mathsf {WF}_{\mathbb {S}}(T)$ .

Proof. Since clearly $\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {W}}\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ , by Theorem 3.5 we obtain ${\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} {}^1{\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}} \le _{\mathrm {W}} {}^1{\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}$ . For the opposite direction, notice that the proof of ${}^1{\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}} \le _{\mathrm {W}} {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ in Theorem 3.5 actually shows that ${}^1{\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}} \le _{\mathrm {W}} {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ .

Theorem 2.18 tells us that ${\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} <_{\mathrm {W}}{}^1{\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}}\equiv _{\mathrm {W}} {\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ . Recall that, by Theorem 2.14, if f is first-order then ${}^1{\widehat {f}}\equiv _{\mathrm {W}} f^{u*}$ . In particular, ${}^1{\widehat {\mathsf {WF}}}\equiv _{\mathrm {W}} \mathsf {WF}^{u*}$ . Besides, since $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ is parallelizable, ${\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} ({\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} )^{u*}$ . Since $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}<_{\mathrm {W}} \widehat {\mathsf {WF}}$ (Theorem 4.3), we obtain $ {\boldsymbol {\Sigma }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} <_{\mathrm {W}}\mathsf {WF}^{u*}$ .

Proof. Given $T \in \mathbf {Tr}$ , $\mathsf {PK}(T)$ is a name for $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}(\left [{T}\right ])$ : therefore, $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {W}}\mathsf {PK}$ ; strictness follows from Theorem 4.10. By Theorem 4.2, $\widehat {\mathsf {WF}}\equiv _{\mathrm {W}} \mathsf {PK}$ .

To prove the last reduction, by Theorems 4.5 and 4.2, we have that $\mathsf {PK}{\restriction }\mathbf {Tr}_2\equiv _{\mathrm {W}} \widehat {\mathsf {WF}}$ and $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {W}} \mathsf {PK}_{2^{\mathbb {N}}}$ , hence, to finish the proof, it suffices to show that $\mathsf {PK}{\restriction }\mathbf {Tr}_2 \le _{\mathrm {W}} \mathsf {lim}*\mathsf {PK}_{2^{\mathbb {N}}}$ . From [Reference Nobrega and Pauly21, Lemma 4.46], we know that $\mathsf {lim}$ is equivalent to the function that prunes a binary tree. So let $T\in \mathbf {Tr}_2$ and let P be a name for $\mathsf {PK}_{2^{\mathbb {N}}}(\left [{T}\right ])$ : pruning P with $\mathsf {lim}$ is enough to obtain $\mathsf {PK}{\restriction }\mathbf {Tr}_2(T)$ .

Proof. The fact that $\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {W}} \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ is trivial. By Theorem 4.11, $\widehat {\mathsf {WF}}\le _{\mathrm {W}}\mathsf {lim}*\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ while, by the closure of $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ under compositional product, we get $\mathsf {lim}*\mathsf {C}_{\mathbb {N}^{\mathbb {N}}} \equiv _{\mathrm {W}} \mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ : hence by Theorem 4.3 $ \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}\not \le _{\mathrm {W}}\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ and a fortiori $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}\not \le _{\mathrm {W}}\mathsf {PST}_{\mathbb {N}^{\mathbb {N}}}$ . For the opposite non-reduction, just notice that by Theorem 4.10 we have that ${}^1{\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}} \not \le _{\mathrm {W}} {}^1{\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}$ .

Proof. From $\mathsf {WF}_{\mathbb {S}}\le _{\mathrm {W}}\mathsf {T}\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ using Theorem 4.9, we obtain $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {W}} \widehat {\mathsf {T}\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}}$ . Strictness follows from Theorem 4.12 as $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}} \not \le _{\mathrm {W}} \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ but clearly $\mathsf {C}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {W}} \mathsf {T}\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}$ .

Proof. For the right to left direction, notice that $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ is single-valued and, by Theorems 3.4 and 4.12 we have that $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}} <_{\mathrm {W}}\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ . For the converse, observe that ${}^1{\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}\equiv _{\mathrm {W}} {\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} $ (Theorem 4.10) and $\widehat {{\boldsymbol {\Pi }_1^1}\text {-}\mathsf {C}^{\vphantom {g}\mathsf {}}_{{\mathbb {N}}} }\equiv _{\mathrm {W}}\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ (Theorem 2.16). This, together with $\mathsf {Det}(\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}})\le _{\mathrm {W}} \widehat {{}^1{\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}}$ [Reference Le Goh, Pauly and Valenti18, Corollary 3.7], concludes the proof.

Proof. By Theorem 4.9 we get $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}} \equiv _{\mathrm {W}} \widehat {\mathsf {WF}_{\mathbb {S}}}$ and, by Theorem 4.17, $\mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}$ is parallelizable. So it suffices to show that $\mathsf {WF}_{\mathbb {S}}\le _{\mathrm {W}} \mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}$ .

Given an input $T \in \mathbf {Tr}$ for $\mathsf {WF}_{\mathbb {S}}$ , let . If $T \in \mathcal {WF}$ then $\mathsf {Expl}(T) \in \mathcal {WF}$ , so that by Theorem 2.3, $\left [{S}\right ]=\{0^{\mathbb {N}}\}$ . If instead $T \in \mathcal {IF}$ , $\left [{\mathsf {Expl}(T)}\right ]$ is perfect and therefore $0^{\mathbb {N}} \in \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}(\left [{S}\right ])$ and $\left [{S}\right ]$ is perfect, so that the scattered part of $\left [{S}\right ]$ is empty.

Hence, for every $(b_i,x_i)_{i \in \mathbb {N}} \in \mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}(\left [{S}\right ])$ we obtain $\mathsf {WF}_{\mathbb {S}}(T)=1_{\mathbb {S}}$ iff $(\exists i)( b_i=1)$ . Hence, a name for $\mathsf {WF}_{\mathbb {S}}(T)$ can be uniformly computed from $(b_i,x_i)_{i \in \mathbb {N}}$ .

Proof. A computable realizer $\Phi '$ for F can be defined recursively as follows. Suppose we have defined $\Phi '(e,p)[s]$ and let $t_s=\left |{\{t<s:\Phi _e(p)(t)>0\}}\right |$ . Then set

$$\begin{align*}\Phi'(e,p)(s)= \begin{cases} \Phi_e(p)(t_{s})+1 & \text{ if } \Phi_e(p)(t_{s})\downarrow \text{in less than } s \text{ steps},\\ 0& \text{ otherwise. } \end{cases}\end{align*}$$

It is easy to check that this works.

Proof. Since $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {W}} \mathsf {PK}_{2^{\mathbb {N}}}$ is parallelizable (Theorems 4.5 and 4.6), it suffices to show that $\overline {\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}}\le _{\mathrm {W}} \widehat {\mathsf {PK}_{2^{\mathbb {N}}}}$ .

By [Reference Brattka and Gherardi6, Lemma 5.1], $\mathcal {A}({\mathbb {N}^{\mathbb {N}}})$ is multi-retraceable, i.e., there is a computable multi-valued function ${r}: {\overline {\mathcal {A}({\mathbb {N}^{\mathbb {N}}})}}\rightrightarrows {{\mathcal {A}({\mathbb {N}^{\mathbb {N}}})}}$ such that its restriction to $\mathcal {A}({\mathbb {N}^{\mathbb {N}}})$ is the identity. Given $A\in \overline {\mathcal {A}({\mathbb {N}^{\mathbb {N}}})}$ , let G be the set of global $\mathsf {mCB}$ -certificates of $r(A)\in \mathcal {A}({\mathbb {N}^{\mathbb {N}}})$ . By [Reference Kihara, Marcone and Pauly15, Lemma 6.7], G is a $\Sigma _1^{1,A}$ subset of $\mathbb {N}^{\mathbb {N}}$ and, in case $\left |{r(A)}\right |\leq \aleph _0$ , by [Reference Kihara, Marcone and Pauly15, Corollary 6.9], G is a singleton.

Let T be a name for G as described in Section 2, i.e., $T\in \mathbf {Tr}$ is such that $G=\{x:(\exists y)(\forall n)(x[n]*y[n]\in T)\}$ . Then, for every m, compute the tree

$$ \begin{align*}T^{*m}:=\mathbb{N}^m &\cup \{\sigma:\langle \sigma(m),\dots,\sigma({\left|{\sigma}\right|-1}) \rangle\in T \land (\forall i<m)(m+2i<\left|{\sigma}\right|\\ & \quad\implies \sigma(i)=\sigma(m+2i))\}.\end{align*} $$

Notice that $\left [{T^{*m}}\right ]=\{\langle p(0),p(2),\dots ,p(2m-2) \rangle p:p \in \left [{T}\right ]\}$ ; therefore, every path in $\left [{T^{*m}}\right ]$ begins with the first m coordinates of some element of the analytic set G. In particular, if $G=\{p_0\}$ then every path in $\left [{T^{*m}}\right ]$ extends $p_0[m]$ . Let $U^m$ be a name for $\mathsf {PK}_{2^{\mathbb {N}}}(\rho _{2^{\mathbb {N}}}(\mathsf {Expl}(T^{*m})))$ . If $G=\{p_0\}$ then every path in $\left [{U^m}\right ]$ extends $\rho _{2^{\mathbb {N}}}(p_0[m]*\sigma )$ for some $\sigma \in 2^m$ . We now describe how to compute an element $x \in \mathbb {N}^{\mathbb {N}} \cup \mathbb {N}^{<\mathbb {N}}$ from the sequence $(U^m)_{m \in \mathbb {N}}$ such that $x=p_0$ when $G=\{p_0\}$ .

The procedure is similar to the one used in the proof of Theorem 3.4. Looking first at $U^1$ , we search for $n_0$ such that

$$ \begin{align*} (\forall \tau \in 2^{n_0+1})(U_\tau^1 \in \mathcal{IF}_2 \implies \tau=0^{n_0}1). \end{align*} $$

Since $\mathcal {IF}_2$ is $\Sigma _1^0$ (Theorem 2.11(i)), the above condition is $\Pi _1^{0}$ . If we find such an $n_0$ , we set $x(0)=n_0$ and we move to the next step. Notice that, in case $G=\{p_0\}$ , the unique $n_0$ satisfying the above condition is $p_0(0)$ .

Suppose we have computed $x[m-1]:= n_0n_1\dots n_{m-1}$ . We generalize the previous strategy to compute $n_m$ . Let

$$ \begin{align*}A_m=\{0^{n_0} 1 \xi_0 0^{n_1} 1 \xi_1 \dots \xi_{m-2} 0^{n_{m-1}} 1 \xi_{m-1} \in U^m: (\forall j<m) (\xi_j \in \{1,01\})\}.\end{align*} $$

We search for $n_m$ satisfying the $\Sigma _1^{0}$ property

$$ \begin{align*}(\forall \sigma \in A_m)(\forall \tau \in 2^{n_m+1})(U_{\sigma\tau}^m \in \mathcal{IF}_2 \implies \tau=0^{n_m}1 ).\end{align*} $$

As before, if we find such an $n_m$ we let $x(m):= n_m$ and move to the next step. Again, if $G=\{p_0\}$ , the unique $n_m$ satisfying the above condition is $p_0(m)$ .

The proof of [Reference Kihara, Marcone and Pauly15, Theorem 6.4] gives us a computable function $\Phi _e$ such that, in case $\left |{r(A)}\right |\leq \aleph _0$ , $\Phi _e(x)$ is a name for a member of $\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}(r(A))$ . If F is the function of Theorem 4.22 then, identifying the completion of the codomain of $\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}$ with $\overline {\mathbb {N}^{\mathbb {N}}}$ , we obtain $F(e,x) \in \overline {\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}}(r(A))$ .

Summing up, if $A \in \mathcal {A}({\mathbb {N}^{\mathbb {N}}})$ is countable then $F(e,x)$ is a name in $\overline {\mathbb {N}^{\mathbb {N}}}$ for an element of $\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}(A)$ . If instead $A \in \overline {\mathcal {A}({\mathbb {N}^{\mathbb {N}}})}$ does not belong to $\operatorname {dom}(\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}})$ , then $F(e,x)$ is anyway a name for some member of $\overline {\mathbb {N}^{\mathbb {N}}}$ .

Proof. Let $T \in \mathbf {Tr}$ be a name for an element of $\mathcal {A}({\mathbb {N}^{\mathbb {N}}})$ and recall that, by Theorem 2.11(ii), $\{\sigma : T_\sigma \in \mathcal {T}^{\leq \aleph _0}\}$ is $\Pi _1^{1,T}$ . Hence, using Theorem 2.11(i), we can compute $(S(\sigma ))_{\sigma \in \mathbb {N}^{<\mathbb {N}}} \in \mathbf {Tr}^{\mathbb {N}}$ such that $ S(\sigma ) \in \mathcal {WF}$ iff $T_\sigma \in \mathcal {T}^{\leq \aleph _0}$ . For any $\sigma \in T$ , let $S(\sigma )$ and $\left [{T_{\sigma }}\right ]$ be the inputs for the $\sigma $ -th instance of $\mathsf {WF}_{\mathbb {S}}$ and $\overline {\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}}$ , respectively. Let $L_\sigma \in \overline {\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}}(\left [{T_\sigma }\right ])$ .

For any $\sigma $ , when we see that $\mathsf {WF}_{\mathbb {S}}(S(\sigma ))=1_{\mathbb {S}}$ then, we know that $S(\sigma ) \in \mathcal {WF}$ and hence $T_\sigma \in \mathcal {T}^{\leq \aleph _0}$ : we need to include a list of $\left [{T_\sigma }\right ]$ in $\mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}(\left [{T}\right ])$ . We compute a name for $L \in \mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}(\left [{T}\right ])$ combining all $L_\sigma $ such that $\mathsf {WF}_{\mathbb {S}}(S(\sigma ))=1_{\mathbb {S}}$ .

Proof. The right-to-left direction is Theorem 4.18. For the opposite direction, notice that, by Theorems 4.9 and 4.23, we have that $\mathsf {WF}_{\mathbb {S}},\overline {\mathsf {wList}_{\mathbb {N}^{\mathbb {N}}}}\le _{\mathrm {W}} \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ , By Theorem 4.24 and the fact that $\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ is parallelizable (Theorem 4.6), we conclude that $\mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {W}} \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ .

Proof. Let $(T^m)_{m\leq n} \in \mathbf {Tr}^n$ be an input for $\mathsf {WF}^*$ . For every $T^m$ compute the tree $S^m := \{j^n\tau :j<2^m \land n \in \mathbb {N} \land \tau \in \mathsf {Expl}(T^m)\} $ . Notice that if $T^m\in \mathcal {WF}$ , then $\mathsf {Expl}(T^m) \in \mathcal {WF}$ , and, in this case, $\left |{\left [{S^m}\right ]}\right |=2^m$ . On the other hand, if $T^m \in \mathcal {IF}$ then $\left [{S^m}\right ]$ is perfect. Now let $k := \mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}}\left (\left [{\bigsqcup _{{m\leq n}}{S^m}}\right ]\right )$ . Notice that $k>0$ (as the scattered part of $\left [{\bigsqcup _{{m\leq n}}{S^m}}\right ]$ is always finite) and

$$\begin{align*}k-1 = \sum_{T^m \in \mathcal{WF}} 2^m. \end{align*}$$

Hence, the binary expansion of $k-1$ contains the information about which $T^m$ ’s are well-founded.

Proof. Since $\mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {W}}\mathsf {ScList}_{\mathbb {N}^{\mathbb {N}}}$ is trivial, Theorem 4.25 immediately implies the reduction.

For strictness, first notice that $\mathsf {WF} \not \le _{\mathrm {W}} {}^1{\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}$ : indeed, by Theorem 4.3 and the fact that $\mathsf {WF}$ is first-order, we obtain that $\mathsf {WF} \not \le _{\mathrm {W}} {}^1{\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}}$ and by Theorem 4.10, we get that ${}^1{\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}}\le _{\mathrm {W}} {}^1{\mathsf {C}_{\mathbb {N}^{\mathbb {N}}}}$ . Hence, $\mathsf {WF}\not \le _{\mathrm {W}} \mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}$ . On the other hand, clearly $\mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {W}} \mathsf {ScList}_{\mathbb {N}^{\mathbb {N}}}$ and $\mathsf {WF}^* \le _{\mathrm {W}} \mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}}$ by Theorem 4.26, so that $\mathsf {WF}\le _{\mathrm {W}} \mathsf {ScList}_{\mathbb {N}^{\mathbb {N}}}$ .

Proof. To prove the reduction notice that $\mathsf {ScList}_{\mathbb {N}^{\mathbb {N}}} \le _{\mathrm {W}} \mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}} \times \mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}$ . By Theorems 4.25 and 4.11, $\mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}\equiv _{\mathrm {W}}\mathsf {PK}_{\mathbb {N}^{\mathbb {N}}}<_{\mathrm {W}}\widehat {\mathsf {WF}}$ . As $\widehat {\mathsf {WF}}$ is clearly parallelizable, it suffices to prove that $\mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {W}}\widehat {\mathsf {WF}}$ . Let $T \in \mathbf {Tr}$ be a name for an input of $\mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}}$ : by Theorem 4.28, we can compute $(S^n)_{n \in \mathbb {N}} \in \mathbf {Tr}^{\mathbb {N}}$ such that $S^0 \in \mathcal {WF}$ iff the scattered part of $\left [{T}\right ]$ has infinitely many elements and,for $n>0$ , $S^n \in \mathcal {WF}$ iff the scattered part of $\left [{T}\right ]$ has at least n elements. Then,

$$ \begin{align*}\mathsf{ScCount}_{\mathbb{N}^{\mathbb{N}}}(\left[{T}\right])=\begin{cases} 0 & \text{if } \mathsf{WF}(S^0)=1,\\ \min\{n>0:\mathsf{WF}(S^{n})=0\} & \text{if } \mathsf{WF}(S^0)=0. \end{cases}\end{align*} $$

For strictness, notice that $\mathsf {ScList}_{\mathbb {N}^{\mathbb {N}}}\le _{\mathrm {W}} \mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}*\mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}}$ . By Theorem 3.9 of [Reference Le Goh, Pauly and Valenti18], $\mathsf {Det}(f*g)\le _{\mathrm {W}}\mathsf {Det}(f)*g$ and so

$$ \begin{align*} \mathsf{Det}(\mathsf{wScList}_{\mathbb{N}^{\mathbb{N}}}*\mathsf{ScCount}_{\mathbb{N}^{\mathbb{N}}})\le_{\mathrm{W}}\mathsf{Det}(\mathsf{wScList}_{\mathbb{N}^{\mathbb{N}}})*\mathsf{ScCount}_{\mathbb{N}^{\mathbb{N}}}\equiv_{\mathrm{W}} \mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}*\mathsf{ScCount}_{\mathbb{N}^{\mathbb{N}}}, \end{align*} $$

where the equivalence follows from Theorems 4.25 and 4.14. Since the output of $\mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}}$ is a natural number and the solution of $\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}$ is always hyperarithmetical relative to the input [Reference Kihara, Marcone and Pauly15, Corollary 3.4], while $\widehat {\mathsf {WF}}$ has instances with no hyperarithmetical solutions in the input, we conclude that $\mathsf {Det}(\widehat {\mathsf {WF}})\equiv _{\mathrm {W}}\widehat {\mathsf {WF}}\not \le _{\mathrm {W}}\mathsf {UC}_{\mathbb {N}^{\mathbb {N}}}*\mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}} $ (the equivalence is immediate as $\widehat {\mathsf {WF}}$ is single-valued). Therefore, $ \widehat {\mathsf {WF}} \not \le _{\mathrm {W}}\mathsf {wScList}_{\mathbb {N}^{\mathbb {N}}}*\mathsf {ScCount}_{\mathbb {N}^{\mathbb {N}}}$ and, a fortiori, $\widehat {\mathsf {WF}} \not \le _{\mathrm {W}} \mathsf {ScList}_{\mathbb {N}^{\mathbb {N}}}$ .