Proof Fix a single-valued h with codomain $\mathbf {X}$ and assume, without loss of generality, that $\operatorname {dom}(h)\subset {\mathbb {N}^{\mathbb {N}}}$ (if h is single-valued then the map $p\mapsto h\circ \delta _{}(p)$ is single-valued as well, where $\delta _{}$ is the representation map for the domain of h). Assume also, for the sake of readability, that f and g are cylinders (if not we can just replace f with $f \times \operatorname {id}{}$ , as $\mathrm {Det}_{ \mathbf {X} }(\cdot )$ is a degree-theoretic operation).

By the cylindrical decomposition lemma, there is a computable function $\Phi _e$ s.t.

$$ \begin{align*} h \le_{\mathrm{sW}} f \circ \Phi_e\circ g. \end{align*} $$

Let $\Phi ,\Psi $ be two maps witnessing this strong reduction. Define $\phi $ as the restriction of $\delta _{\mathbf {X}}\circ \Psi \circ f \circ \Phi _e$ to $\operatorname {dom}(g \circ \Phi \circ h)$ . The choice of the domain of $\phi $ guarantees that $\phi $ is single-valued: intuitively $\phi $ witnesses the “second part” of the reduction $h\le _{\mathrm {sW}} f \circ \Phi _e\circ g$ , and the fact that h is single-valued implies that so is $\phi $ . In particular, $\phi \le _{\mathrm {W}} \mathrm {Det}_{ \mathbf {X} }(f)$ (as $\phi \le _{\mathrm {W}} f$ trivially). Since $h\le _{\mathrm {W}} \phi * g$ we have that $h\le _{\mathrm {W}} \mathrm {Det}_{ \mathbf {X} } (f)* g$ .⊣

Proof This follows from Theorem 3.9, as $\mathrm {Det} (f) * \mathrm {Det}(g)\le _{\mathrm {W}}\mathrm {Det}(f* g)$ always holds and $\mathrm {Det}(g)\equiv _{\mathrm {W}} g$ as g is single-valued with codomain ${\mathbb{N}^{\mathbb{N}}}$ .⊣

Proof The left-to-right reduction is straightforward as

$$ \begin{align*} \mathrm{Det}_{ }(f)^{(k)} \le_{\mathrm{W}} \mathrm{Det}_{ }(f)*\mathsf{lim}^{[k]} \le_{\mathrm{W}} f *\mathsf{lim}^{[k]} \equiv_{\mathrm{W}} f^{(k)},\end{align*} $$

where the last equality follows from the fact that f is a cylinder. Since $\mathrm {Det}_{ }(f)^{(k)}$ is single-valued, this implies $\mathrm {Det}_{ }(f)^{(k)}\le _{\mathrm {W}} \mathrm {Det}_{ }(f^{(k)})$ .

The right-to-left reduction follows from Theorem 3.9 as

$$ \begin{align*} \mathrm{Det}_{ }(f^{(k)}) \equiv_{\mathrm{W}} \mathrm{Det}_{ }(f*\mathsf{lim}^{[k]})\le_{\mathrm{W}}\mathrm{Det}_{ }(f) *\mathsf{lim}^{[k]} \equiv_{\mathrm{W}}\mathrm{Det}_{ }(f)^{(k)},\end{align*} $$

where the last equality follows from the fact that $\mathrm {Det}_{ }(f)$ is a cylinder. ⊣

Proof To show that $\mathsf {DS}\le _{\mathrm {W}}\mathsf {C}_{{\mathbb {N}^{\mathbb {N}}}}$ it is enough to notice that being a descending sequence in a linear order L is a $\Pi ^{0,L}_1$ property. In other words, we can obtain a descending sequence through L by choosing a path through the tree

$$ \begin{align*} \{ \sigma\in {\mathbb{N}^{<\mathbb{N}}} : (\forall i<|\sigma|-1)(\sigma(i+1)<_L \sigma(i)) \}. \end{align*} $$

To show that $\mathsf {DS}\not \le _{\mathrm {W}}\mathsf {UC}_{{\mathbb {N}^{\mathbb {N}}}}$ , recall that there is a computable linear order with no hyperarithmetic descending sequence (see e.g., [Reference Sacks38, Lemma III.2.1]). A reduction $\mathsf {DS}\le _{\mathrm {W}}\mathsf {UC}_{{\mathbb {N}^{\mathbb {N}}}}$ would therefore contradict Theorem 2.1.⊣

Proof The reduction $\mathsf {lim}* \mathsf {DS}\le _{\mathrm {W}} \mathsf {C}_{{\mathbb {N}^{\mathbb {N}}}}$ follows from the fact that both $\mathsf {lim}$ and $\mathsf {DS}$ are reducible to $\mathsf {C}_{{\mathbb {N}^{\mathbb {N}}}}$ and that $\mathsf {C}_{{\mathbb {N}^{\mathbb {N}}}}$ is closed under compositional product.

To prove the left-to-right reduction notice that, given a tree T, we can computably build the linear order $\mathrm {KB}(T)$ . It is known that $[T]\neq \emptyset $ iff $\mathrm {KB}(T)$ is ill-founded (see e.g., [Reference Simpson41, Lemma V.1.3]). Moreover, given a infinite descending sequence $(\sigma _n)_{n\in \mathbb {N}}$ in $\mathrm {KB}(T)$ , the sequence $(\sigma _n^{\smallfrown } 0^\omega )_{n\in \mathbb {N}}$ converges to some $x\in [T]$ , and therefore the claim follows. ⊣

Proof The left-to-right reduction is trivial, so we only need to show that $\mathsf {BS}\le _{\mathrm {W}}\mathsf {DS}$ . Let P be a non-well quasi-order. We will first compute an extension R of P s.t. every two elements of P are R-comparable, then we will computably pick an element from each R-equivalence class, so as to obtain a linear order.

We define R iteratively as follows: at every stage s s.t. $s\in P$ , we define the R-relation between s and t, for every $t\in P$ s.t. $t<s$ . If $t \,|_{P}\, s$ then we define $s \prec _R t$ . Otherwise we define the R-relation between s and t so as to extend P.

It is easy to see that if $(p_i)_{i\in \mathbb {N}}$ is an $\prec _R$ -descending sequence then it is a P-bad sequence. Indeed, for every $i,j$ s.t. $i<j$ , if $p_i \preceq _P p_j$ then $p_i \preceq _R p_j$ (as R extends P), contradicting the fact that $(p_i)_{i\in \mathbb {N}}$ is an $\prec _R$ -descending sequence. Moreover R is ill-founded: indeed every $\prec _P$ -descending sequence is also an $\prec _R$ -descending sequence. On the other hand, every P-antichain $(q_i)_{i\in \mathbb {N}}$ has a subsequence $(q_{i_k})_{k\in \mathbb {N}}$ that is an $\prec _R$ -descending sequence (define $q_{i_k}$ inductively by letting $i_k$ be the smallest integer s.t. $q_{i_k}>q_j$ , for every $j<k$ ).

To conclude the proof it is enough to show that we can uniformly compute a linear order L by choosing an element from each R-equivalence class. We define L as the restriction of R to the set

$$ \begin{align*} \{ p\in R : (\forall q < p)( p\not\equiv_R q) \}.\end{align*} $$

Clearly L is isomorphic to the quotient order induced by R on the set of R-equivalence classes, hence it is ill-founded. Moreover, every $<_L$ -descending sequence is an $\prec _R$ -descending sequence, and therefore $\mathsf {DS}(L)\subset \mathsf {BS}(P)$ .⊣

Proof Let $p\in {\mathbb {N}^{\mathbb {N}}}$ and L be an ill-founded linear order. Define

$$ \begin{align*} M:&=\{ (p[n],n): n\in L \},\\ (p[n],n) &\le_M (p[m],m) :\hspace{-1mm}\iff n \le_L m. \end{align*} $$

It is easy to see that M is computably isomorphic to L, and hence it is a valid input for $\mathsf {DS}$ . In particular, letting $((p[n_i],n_i))_{i\in \mathbb {N}}\in \mathsf {DS}(M)$ , we have that $(n_i)_{i\in \mathbb {N}}$ is a descending sequence in L and $p = \bigcup _{i\in \mathbb {N}} p[n_i]$ .⊣

Proof Let X be a $\boldsymbol {\Pi }^1_1$ initial segment of $\mathbb {N}$ . By considering the Kleene-Brouwer ordering, we can think of a name for X as a sequence $(L_n)_{n\in \mathbb {N}}$ of linear orders s.t. $n\in X$ iff $L_n$ is well-founded.

Define the linear order $L:=\bigcup _n \{n\}\times L_n$ , ordered lexicographically. Notice that L is ill-founded as X is not all of $\mathbb {N}$ . Moreover, for every $<_L$ -descending sequence $((n_i,a_i))_{i\in \mathbb {N}}$ , we have that $n_0\in {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}(X)$ . Indeed, for every $n\in X$ and every $a\in L_n$ , the pair $(n,a)$ lies in the well-founded part of L.

The fact that the reduction is strict follows from the fact that every solution to ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ is computable, whereas there is a computable input for $\mathsf {DS}$ with no hyperarithmetic solution. ⊣

Proof Fix an f-instance X and run $\Phi ^X$ for s steps. This produces a finite linear order $\le ^X_s$ . Define

$$ \begin{align*} D_s := \{F \subseteq\, \le^X_s : {}&{} F \text{ is a} <^X_s\text{-descending sequence and } |F|\ge 1 \text{ and } \\ & \Psi^{X \oplus F} \text{ outputs some } j \in \mathbb{N} \text{ in }s \text{ steps}\}. \end{align*} $$

Note that $D_s$ is finite and $t<s$ implies $D_t\subset D_s$ . If $D_s\neq \emptyset $ we define $F_s$ to be the $<_{\mathbb {N}}$ -least element of $D_s$ such that

$$ \begin{align*} \textstyle (\forall F \in D_s)\left(\min_{<^X}(\,F) \le^X_s \min_{<^X}(\,F_s)\right). \end{align*} $$

This ensures that if any $F \in D_s$ extends to an infinite $<^X$ -descending sequence, then so does $F_s$ . Observe that $(\,F_s)_{s}$ is uniformly computable from X. If $D_s=\emptyset $ we define $F_s:=F_t$ where t is the first index greater than s s.t. $D_t\neq \emptyset $ . (We will show below that such t exists, so we can computably search for it.)

Notice that for cofinitely many s, $D_s\neq \emptyset $ . Indeed, let S be an infinite $<^X$ -descending sequence (there must exist one because $<^X$ is a $\mathsf {DS}$ -instance). Since $\Psi ^{X \oplus S}$ outputs some f-solution j of X, there is some finite nonempty initial segment F of S and some $t \in \mathbb {N}$ such that $\Psi ^{X \oplus F}$ outputs j in t steps. Hence for all sufficiently large s, we have that $F \in D_s$ . This shows that the sequence $(\,F_s)_{s\in \mathbb {N}}$ is well-defined. Moreover, as already observed, for every $t\ge s$ , $F_t$ extends to an infinite $<^X$ -descending sequence.

The fact that, for every s, $\Psi ^{X\oplus F_s}$ outputs some $j\in \mathbb {N}$ follows from the definition of $D_s$ .⊣

Proof If $f \le _{\mathrm {W}} {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ , then $f \le _{\mathrm {W}} \mathsf {DS}$ by Proposition 4.8. Since ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ is first order, $f \le _{\mathrm {W}} {}^1{\mathsf {DS}}$ .

To prove the converse reduction, suppose that $f \le _{\mathrm {W}} \mathsf {DS}$ as witnessed by the maps $\Phi $ and $\Psi $ . Given an f-instance X, let $(\,F_s)_{s\in \mathbb {N}}$ be as in Lemma 4.9. Let $\le ^X$ denote the linear order represented by $\Phi ^X$ . Define the following $\Pi ^{1,X}_1$ set:

$$ \begin{align*} A := \{s \in \mathbb{N}: F_s \notin \mathrm{Ext} \}, \end{align*} $$

where $\mathrm {Ext}$ denotes the set of finite sequences that extend to an infinite $<^X$ -descending sequence.

Notice that A is finite as, for cofinitely many s, $F_s$ is extendible. In particular A is a valid instance of ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ and, for every $b\in {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}(A)$ , $F_b$ is extendible to an infinite $<^X$ -descending sequence. By construction, $\Psi ^{X\oplus F_b}$ commits to some $j\in \mathbb {N}$ . The fact that $F_b$ is extendible guarantees that j is a valid f-solution of X.⊣

Proof If $\mathsf {C}_{{\mathbb {N}^{\mathbb {N}}}}\le _{\mathrm {W}}\mathsf {DS}$ then, by Proposition 2.4, ${\boldsymbol {\Sigma }^1_1}\text {-}\mathsf {C}_{\mathbb {N}}\le _{\mathrm {W}} {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ . However, this would imply that $\widehat {{\boldsymbol {\Sigma }^1_1}\text {-}\mathsf {C}_{\mathbb {N}}}\le _{\mathrm {W}} \widehat {{\boldsymbol {\Pi }^1_1}\mathsf {-Bound}}$ , contradicting [Reference Astor, Dzhafarov, Solomon and Suggs1, Corollary 3.23]. ⊣

Proof Let g be a single-valued function with codomain $\mathbb {N}$ and suppose that $g \le _{\mathrm {W}} f$ as witnessed by $\Phi , \Psi $ . Given a name p for a g-instance x, we use $\mathsf {C}_{\mathbb {N}}$ to guess some $n, t$ such that $\Psi (p,n)$ converges to some k in at most t steps, and such that for no $m> n$ it ever happens that $\Psi (p,m)$ converges to anything but k. Since f is upwards-closed and g is single-valued, such $n,t$ must exist. Moreover, the associated k is equal to $g(x)$ . ⊣

Proof Let us first notice that $\mathsf {C}_{\mathbb {N}}\equiv _{\mathrm {W}}\mathsf {UC}_{\mathbb {N}}$ [Reference Brattka and Gherardi5, Proposition 6.2] and therefore $\mathrm {Det}_{ \mathbb {N} }(\mathsf {C}_{\mathbb {N}}) \equiv _{\mathrm {W}} \mathsf {C}_{\mathbb {N}}$ . The fact that $\mathrm {Det}_{ \mathbb {N} }({\boldsymbol {\Pi }^1_1}\mathsf {-Bound})\le _{\mathrm {W}} \mathsf {C}_{\mathbb {N}}$ follows from Lemma 4.13. To prove the converse reduction it is enough to show that $\mathsf {UC}_{\mathbb {N}}\le _{\mathrm {W}} {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ .

Let $(n_i)_{i\in \mathbb {N}}$ be an enumeration of the complement of $\{x\}\subset \mathbb {N}$ . Define

$$ \begin{align*} m(s)&:=\min\{j\in\mathbb{N} : (\forall i<s)(n_i \neq j) \},\\ A&:=\{ s \in\mathbb{N} : (\exists t>s )(m(t)\neq m(s)) \}. \end{align*} $$

Clearly $\lim _{s\to \infty } m(s) =x$ , which implies that A is finite. Since m is computable (relative to $(n_i)_{i\in \mathbb {N}}$ ), A is a valid input for ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ . Moreover, for every $b\in {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}(A)$ we have $m(b)=x$ .

This implies that $\mathsf {C}_{\mathbb {N}}\le _{\mathrm {W}} \mathrm {Det}_{ \mathbb {N} }(\mathsf {DS})$ . To conclude the proof we notice that, for every single-valued g with codomain $\mathbb {N}$ we have

$$ \begin{align*} g\le_{\mathrm{W}} \mathsf{DS} \Rightarrow g \le_{\mathrm{W}} {\boldsymbol{\Pi}^1_1}\mathsf{-Bound} \Rightarrow g\le_{\mathrm{W}} \mathrm{Det}_{ \mathbb{N} }({\boldsymbol{\Pi}^1_1}\mathsf{-Bound})\equiv_{\mathrm{W}} \mathsf{C}_{\mathbb{N}}. \end{align*} $$

⊣

Proof To prove that $\mathsf {C}_{\mathbb {N}}$ satisfies point 1, consider $\mathsf {UC}_{\mathbb {N}}$ , which is Weihrauch equivalent to $\mathsf {C}_{\mathbb {N}}$ [Reference Brattka and Gherardi5, Proposition 6.2]. To prove that $\mathsf {C}_{\mathbb {N}}$ satisfies point $2$ , consider the problem ${\boldsymbol {\Sigma }^0_1}\mathsf {-Bound}$ that produces a bound for a finite $\boldsymbol {\Sigma }^0_1$ subset of $\mathbb {N}$ . Clearly ${\boldsymbol {\Sigma }^0_1}\mathsf {-Bound}$ is upwards closed. The reduction ${\boldsymbol {\Sigma }^0_1}\mathsf {-Bound}\le _{\mathrm {W}}\mathsf {C}_{\mathbb {N}}$ follows from the fact that, for every $A\in \operatorname {dom}({\boldsymbol {\Sigma }^0_1}\mathsf {-Bound})$ , the set

$$ \begin{align*} \{ n\in\mathbb{N} : (\forall m \ge n)( m\notin A ) \} \end{align*} $$

is a $\Pi ^{0,A}_1$ subset of ${\boldsymbol {\Sigma }^0_1}\mathsf {-Bound}(A)$ . To prove the converse reduction, let p be a name for some $B\in \operatorname {dom}(\mathsf {C}_{\mathbb {N}})$ . Define $m(s)$ to be the least number not enumerated in p by stage s. Clearly $\lim _{s\to \infty } m(s) = \min B$ . In particular this implies that there are only finitely many stages s s.t. $m(s)\neq \min B$ . Using ${\boldsymbol {\Sigma }^0_1}\mathsf {-Bound}$ we can obtain a stage b s.t. $m(b)=\min B$ , hence solving $\mathsf {C}_{\mathbb {N}}$ .

Finally the maximality of $\mathsf {C}_{\mathbb {N}}$ follows from Lemma 4.13: indeed suppose $f: \textbf {X} \to \mathbb {N}$ is Weihrauch equivalent to some g which is upwards-closed. By Lemma 4.13, we have $\mathrm {Det}_{ \mathbb {N} }(g)\le _{\mathrm {W}} \mathsf {C}_{\mathbb {N}}$ . By definition of $\mathrm {Det}_{ }(\cdot )$ , we have $f \le _{\mathrm {W}} \mathrm {Det}_{ \mathbb {N} }(g)$ , hence $f \le _{\mathrm {W}} \mathsf {C}_{\mathbb {N}}$ .⊣

Proof Let us first prove that $\mathsf {lim}\le _{\mathrm {W}}\mathsf {DS}$ . Let $\mathsf {J}$ be the Turing jump operator, i.e., $\mathsf {J}(p)(e)=1$ iff $\varphi _e^p(e)$ halts. It is known that $\mathsf {J}\equiv _{\mathrm {sW}} \mathsf {lim}$ (see [Reference Brattka, Hölzl, Kuyper, Vollmer and Vallée11, Theorem 6.7]). By relativizing the construction in [Reference Marcone and Shore31, Lemma 4.2] we have that, for every p, we can p-computably build a linear order L of type $\omega +\omega ^*$ s.t. every descending sequence through L computes $\mathsf {J}(p)$ . This shows that $\mathsf {lim}\equiv _{\mathrm {W}}\mathsf {J}\le _{\mathrm {W}} \mathsf {DS}$ .

To prove that $\mathrm {Det}_{ }(\mathsf {DS}) \le _{\mathrm {W}} \mathsf {lim}$ , suppose that $f :\subseteq \textbf {X} \to {\mathbb {N}^{\mathbb {N}}}$ is single-valued and $f\le _{\mathrm {W}}\mathsf {DS}$ as witnessed by the maps $\Phi $ , $\Psi $ . For every n, define $f_n$ by $f_n(X):=f(X)(n)$ . The maps $\Phi $ and $\Psi $ witness that $f_n\le _{\mathrm {W}}\mathsf {DS}$ as well (modulo a trivial coding). Given an f-instance X, consider the sequences $(F_{s,n}\!)_{s\in \mathbb {N}}$ obtained by applying Lemma 4.9 to each $f_n$ . Define the sequence $(p_s\!)_{s\in \mathbb {N}}$ in ${\mathbb {N}^{\mathbb {N}}}$ as $p_s(n):= \Psi ^{X\oplus F_{s,n}}(0)$ . Notice that, by Lemma 4.9, for every n, $\Psi ^{X\oplus F_{s,n}}$ outputs some number, therefore $p_s(n)$ is well-defined and is uniformly computable from X. Moreover, since $f_n$ is single-valued and, for cofinitely many s, $F_{s,n}$ is extendible, the sequence $(\Psi ^{X\oplus F_{s,n}}(0))_{s\in \mathbb {N}}$ is eventually constant and equal to $f_n(X)$ . In particular this shows that, letting $p:=\lim _{s\to \infty } p_s$ , for each n we have $p(n)=f_n(X)$ , i.e., $p=f(X)$ . ⊣

Proof Since $ \mathsf {LPO} $ is single-valued, so is $ \mathsf {LPO} '$ . Since $ \mathsf {LPO} '\not \le _{\mathrm {W}} \mathsf {lim}$ (see [Reference Brattka, Gherardi and Pauly10, Corollary 12.3 and Theorem 12.7]), it follows from Theorem 4.16 that $ \mathsf {LPO} '\not \le _{\mathrm {W}} \mathsf {DS}$ . On the other hand, $\mathsf {DS}\not \le _{\mathrm {W}} \mathsf {LPO} '$ , as $ \mathsf {LPO} '$ always has computable solutions.⊣

Proof Let $(p_n)_{n\in \mathbb {N}}$ be a sequence in ${\mathbb {N}^{\mathbb {N}}}$ converging to an instance p of $ \mathsf {LPO} $ . For each s define

$$ \begin{align*} g(s):= \begin{cases} i+1 & \text{if } i\le s \land p_s(i)\neq 0 \land (\forall j<i)(p_s(j)=0),\\ 0 & \text{otherwise.} \end{cases}\end{align*} $$

Let us define a linear order L inductively: at stage $s=0$ we put $0$ into L. At stage $s+1$ we do the following:

1. 1. if $g(s)=g(s+1)$ we put $2(s+1)$ immediately below $2s$ ;

2. 2. if $g(s)\neq g(s+1)$ and $g(s+1)=0$ we put $2(s+1)$ at the bottom; and

3. 3. if $g(s)\neq g(s+1)$ and $g(s+1)>0$ we put $2(s+1)$ at the top and we put $2s+1$ immediately above $0$ .

This construction produces a linear order on a computable subset of $\mathbb {N}$ . It is clear that g and L are uniformly computable in $(p_n)_{n\in \mathbb {N}}$ . Notice that if $ \mathsf {LPO} (p)=1$ then there is an s s.t. for every $t\ge s$ , $g(t)=g(s)$ (this follows by definition of limit in the Baire space). In particular, L has order type $n+\omega ^*$ . On the other hand, if $ \mathsf {LPO} (p)=0$ we distinguish three cases: if $g(s)$ is eventually constantly $0$ then L has order type $\omega ^*$ . If there are infinitely many s s.t. $g(s)>0$ then g is unbounded (because for each i, $\lim _s p_s(i) = p(i) = 0$ so g eventually stays above i). In particular, if there are infinitely many s and infinitely many t s.t. $g(s)=0$ and $g(t)>0$ then L has order type $\omega ^*+\zeta $ , where $\zeta :=\omega ^*+\omega $ is the order type of the integers. If instead $g(s)> 0$ for all sufficiently large s, then L has order type $n+\zeta $ . In all cases, L is ill-founded.

We consider the input $(L,(p_n)_{n\in \mathbb {N}})$ for $\mathsf {DS}\times \mathsf {lim}$ . Given an $<_L$ -descending sequence $(q_n)_{n\in \mathbb {N}}$ , we compute a solution for $ \mathsf {LPO} '((p_n)_{n\in \mathbb {N}})= \mathsf {LPO} (p)$ as follows: if $q_0$ is odd or $g(q_0/2)=0$ then we return $0$ , otherwise we return $p(i)$ where i is s.t. $g(q_0/2)=i+1$ .

Notice that if $ \mathsf {LPO} (p)=1$ then the $\omega ^*$ part of $\leq _L$ is the final segment of the even numbers that starts with the first index $2s$ s.t. for every $t\ge s$ , $g(t)=i+1$ and $p(i)=1$ . In particular every $<_L$ -descending sequence starts with some even $q_0$ s.t. $g(q_0/2)>0$ . On the other hand, if $ \mathsf {LPO} (p)=0$ then, by definition of $ \mathsf {LPO} $ , we have that $p=0^{\mathbb {N}}$ . In this case, the above procedure must return $0$ so it produces the correct solution. This proves that $ \mathsf {LPO} ' \le _{\mathrm {W}} \mathsf {DS} \times \mathsf {lim}$ .

The fact that $\mathsf {DS}$ is not closed under product follows from the fact that $\mathsf {lim} \le _{\mathrm {W}} \mathsf {DS}$ (Theorem 4.16) and Corollary 4.17. ⊣

Proof Let $(p_i)_{i\in \mathbb {N}}$ be a sequence in ${\mathbb {N}^{\mathbb {N}}}$ converging to an instance p of $ \mathsf {LPO} $ . For every $s\in \mathbb {N}$ we define (as we did in the proof of Theorem 4.18)

$$ \begin{align*} g(s):= \begin{cases} i+1 & \text{if } i\le s \land p_s(i)\neq 0 \land (\forall j<i)(p_s(j)=0),\\ 0 & \text{otherwise.} \end{cases} \end{align*} $$

Let us define a linear order $\le _L$ on $\mathbb {N}$ inductively: for each stage s we define a linear order on $\{0,\ldots ,s\}$ . At stage $s=0$ there are no decisions to make. At stage $s+1$ we do the following:

1. 1. if $0=g(s)=g(s+1)$ we put $s+1$ immediately above s;

2. 2. if $0<g(s)=g(s+1)$ we put $s+1$ immediately below s; and

3. 3. if $g(s)\neq g(s+1)$ we put $s+1$ at the top.

It is clear that g and $\leq _L$ are uniformly computable in $(p_n)_{n\in \mathbb {N}}$ . Notice that if $ \mathsf {LPO} (p)=1$ then there is an s s.t. for every $t\ge s$ , $g(t)=i+1$ , where i is the smallest integer s.t. $p(i)=1$ (this follows by definition of limit in the Baire space). In particular, $\le _L$ has order type $n+\omega ^*$ . On the other hand, if $ \mathsf {LPO} (p)=0$ then g is either eventually constantly $0$ or unbounded. In both cases the linear order $\le _L$ has order type $\omega $ .

In other words $(\mathbb {N},\le _L)$ has order type $\omega $ iff $ \mathsf {LPO} '((p_i)_{i\in \mathbb {N}})=0$ . Since the output of $\mathsf {FindS}^{\{\omega ,n+\omega ^*\}}((\mathbb {N},\le _L))$ comes with an indication of the order type of the solution, this defines a reduction from $ \mathsf {LPO} '$ to $\mathsf {FindS}^{\{\omega ,n+\omega ^\ast \}}.$ ⊣

Proof The fact that $\mathsf {FindS}^{\{\omega , n+\omega ^*\}} \not \le _{\mathrm {W}} \mathsf {DS}$ follows from Proposition 4.20 and the fact that $ \mathsf {LPO} '\not \le _{\mathrm {W}}\mathsf {DS}$ (Corollary 4.17). Moreover, since $\mathsf {FindS}^{\{\omega , n+\omega ^*\}}$ is a restriction of $\mathsf {General}\text {-}\mathsf {SADS}$ , we have $\mathsf {General}\text {-}\mathsf {SADS}\not \le _{\mathrm {W}}\mathsf {DS}$ .

To show that the converse reduction cannot hold it is enough to notice that $\mathsf {General}\text {-}\mathsf {SADS}$ is an arithmetic problem, while $\mathsf {DS}\not \le _{\mathrm {W}}\mathsf {UC}_{{\mathbb {N}^{\mathbb {N}}}}$ (Proposition 4.2). ⊣

Proof Given a linear order $(L,\le _L)$ we can computably build the linear order $Q:=L+L^*$ . Formally we define $(Q,\le _Q)$ as $Q:=\{0\}\times L \cup \{1\}\times L$ and

$$ \begin{align*} (a,p)\le_Q (b,q) :\hspace{-1mm}\iff a<b \lor (a=b=0 \land p\le_L q) \lor (a=b=1 \land q \le_L p). \end{align*} $$

Notice that Q is always ill-founded, hence it is a valid input for $\mathsf {DS}$ . Given $(q_i)_{i\in \mathbb {N}}\in \mathsf {DS}(Q)$ , we computably build the sequence $(x_i)_{i\in \mathbb {N}}$ defined by $x_i:=\pi _1 q_i$ where $\pi _i:= (a_0,a_1)\mapsto a_i$ .

We distinguish three cases:

1. 1. if $\pi _0 q_i =0$ for every i then $(x_i)_{i\in \mathbb {N}}$ is an $\omega ^*$ -sequence in L;

2. 2. if $\pi _0 q_i =1$ for every i then $(x_i)_{i\in \mathbb {N}}$ is an $\omega $ -sequence in L; and

3. 3. if there is a k s.t. for all $i<k$ we have $\pi _0 q_i = 1$ and for all $j\ge k$ we have $\pi _0 q_j = 0$ then, by point $1$ , $(x_j)_{j\ge k}$ is an $\omega ^*$ -sequence in L, hence $(x_i)_{i\in \mathbb {N}}$ is of type $n+\omega ^*$ , with $n\le k$ .

In any case the sequence $(x_i)_{i\in \mathbb {N}}$ is a valid solution for $\mathsf {FindC}^{{}}_{{\{ \omega ,n+\omega ^*\}}}$ .⊣

Proof Given a coloring $c\colon \mathbb {N}\to k$ , consider the $\Sigma ^{0,c}_2$ set

$$ \begin{align*} X:= \{ n \in \mathbb{N} : (\exists i)(\forall j>i)(c(n) \neq c(j)) \}. \end{align*} $$

It is easy to see that X is finite, as $\operatorname {ran}(c)\subset k$ and if there is no c-homogeneous set with color i then there are finitely many $j\in \mathbb {N}$ s.t. $c(j)=i$ . In particular, given a bound b for X there is a homogeneous solution with color $c(b)$ .

The separation follows from the fact that ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}\not \le _{\mathrm {W}}\mathsf {UC}_{{\mathbb {N}^{\mathbb {N}}}}$ (as $\widehat {{\boldsymbol {\Pi }^1_1}\mathsf {-Bound}}\not \le _{\mathrm {W}}\mathsf {UC}_{{\mathbb {N}^{\mathbb {N}}}}$ , see [Reference Astor, Dzhafarov, Solomon and Suggs1, Fact 3.25]), while $\mathsf {RT}^{{1}}_{{\mathbb {N}}} <_{\mathrm {W}}\mathsf {UC}_{{\mathbb {N}^{\mathbb {N}}}}$ (in particular $\mathsf {RT}^{{1}}_{{\mathbb {N}}} <_{\mathrm {W}} \mathsf {C}_{\mathbb {N}}'$ , see [Reference Anglès D'Auriac and Kihara1, Proposition 7.2 and Corollary 7.6]). The fact that $\mathsf {RT}^{{1}}_{{\mathbb {N}}} <_{\mathrm {W}}\mathsf {DS}$ follows from ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}<_{\mathrm {W}}\mathsf {DS}$ (Proposition 4.8). ⊣

Proof Suppose that $f \le _{\mathrm {W}} g$ as witnessed by $\Phi , \Psi $ . Let p be the name for the f-instance x we are given.

We define a coloring c as follows: we dove-tail all computations $\Psi (p,n)$ for $n \in \mathbb {N}$ . Whenever some computation converges to some $j \in \mathbb {N}$ , we define $c(i):=j$ where i is the first element on which c is not defined yet. Since g is upwards-closed, we know that for all but finitely many n, $\Psi (p,n)$ has to converge to some $j_n \in f(x)$ . This implies that $\operatorname {ran}(c)$ contains only finitely many distinct elements. Moreover, any element repeating infinitely often is a correct solution to $f(x)$ , therefore we can find a $y\in f(x)$ by applying $\mathsf {RT}^{{1}}_{{\mathbb {N}}} $ to c and returning the color of the solution.⊣

Proof The right-to-left implication always holds as $\mathsf {RT}^{{1}}_{{\mathbb {N}}} <_{\mathrm {W}}\mathsf {DS}$ (Proposition 4.24). On the other hand, if f is pointwise finite and $f\le _{\mathrm {W}}\mathsf {DS}$ then, by Theorem 4.10 we have $f\le _{\mathrm {W}}{\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ . Since ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ is upwards-closed, by Lemma 4.26 we have $f\le _{\mathrm {W}}\mathsf {RT}^{{1}}_{{\mathbb {N}}} $ .⊣

Proof Point 1 holds because $\mathsf {cRT}^{{1}}_{{\mathbb {N}}} $ is pointwise finite and $\mathsf {cRT}^{{1}}_{{\mathbb {N}}} \equiv _{\mathrm {W}} \mathsf {RT}^{{1}}_{{\mathbb {N}}} $ . Point 2 holds because $\mathsf {RT}^{{1}}_{{\mathbb {N}}} <_{\mathrm {W}}{\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ (Proposition 4.24) and ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ is upwards-closed. Finally, the maximality follows from Lemma 4.26.⊣

Proof Recall that $\mathsf {RT}^{{1}}_{{\mathbb {N}}} \equiv _{\mathrm {W}}\mathsf {cRT}^{{1}}_{{\mathbb {N}}} $ and let $\Phi ,\Psi $ be two computable maps witnessing $f\le _{\mathrm {W}}\mathsf {cRT}^{{1}}_{{\mathbb {N}}} $ . Let p be a name for some $x\in \operatorname {dom}(f)$ and let c be the coloring represented by $\Phi (p)$ . We define the following $\Pi ^{0,p}_1$ set

$$ \begin{align*} A:= \{\langle n,c_0,\ldots,c_k,s \rangle: {}&{} (\forall i)(\exists j\le k)(c(i)=c_j) \text{ and }\\ & (\forall j\le k)(\exists i<s)(c(i)=c_j) \text{ and }\\ & (\forall j\le k)(\Psi(p,c_j)\downarrow \rightarrow \Psi(p,c_j)\le n) \}. \end{align*} $$

Notice that, if $\langle n,c_0,\ldots ,c_k,s \rangle \in A$ then, by the first two conditions, there is a $j\le k$ s.t. $c_j$ is a valid solution for $\mathsf {cRT}^{{1}}_{{\mathbb {N}}} (c)$ . In particular $\Psi (p,c_j)\downarrow $ and is a correct solution for $f(x)$ (as $\Phi $ and $\Psi $ witness that $f \le _{\mathrm {W}} \mathsf {cRT}^{{1}}_{{\mathbb {N}}} $ ). Since f is upwards-closed, every number greater than $\Psi (p,c_j)$ is a valid solution. In particular, the third condition implies that $n\ge \Psi (p,c_j)$ and therefore $n\in f(x)$ .⊣

Proof The right-to-left implication is trivial, so let us prove the left-to-right one. Since $\mathsf {RT}^{{1}}_{{\mathbb {N}}} \le _{\mathrm {W}} {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ and ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ is upwards-closed, it suffices to show that if g is upwards-closed and $f \le _{\mathrm {W}} g$ , then $f \le _{\mathrm {W}} \mathsf {RT}^{{1}}_{{k}} $ . The proof closely follows the one of Lemma 4.26. Suppose that $f \le _{\mathrm {W}} g$ as witnessed by $\Phi , \Psi $ . Let p be the name for the f-instance x we are given. We define a k-coloring c as follows: we dove-tail all computations $\Psi (p,n)$ for $n \in \mathbb {N}$ . Whenever some computation converges to some $j < k$ , we define $c(i):=j$ where i is the first element on which c is not defined yet. Since g is upwards-closed, we know that for all but finitely many n, $\Psi (p,n)$ has to converge to some $j_n < k$ which lies in $f(x)$ . Moreover, any element repeating infinitely often is a correct solution to $f(x)$ , therefore we can find a $y\in f(x)$ by applying $\mathsf {RT}^{{1}}_{{k}} $ to c and returning the color of the solution. ⊣

Proof The right-to-left implication always holds as $\mathsf {RT}^{{1}}_{{k}} \le _{\mathrm {W}}\mathsf {RT}^{{1}}_{{\mathbb {N}}} $ trivially and $\mathsf {RT}^{{1}}_{{\mathbb {N}}} <_{\mathrm {W}}\mathsf {DS}$ (Proposition 4.24). The left-to-right implication follows from Theorem 4.27 and Lemma 4.30.⊣

Proof The left-to-right implication is trivial as $\mathsf {lim}_k\le _{\mathrm {W}}\mathsf {RT}^{{1}}_{{k}} $ . To prove the converse direction recall that $\mathsf {RT}^{{1}}_{{k}} \equiv _{\mathrm {W}}\mathsf {cRT}^{{1}}_{{k}} $ and let the reduction $f\le _{\mathrm {W}}\mathsf {cRT}^{{1}}_{{k}} $ be witnessed by the maps $\Phi ,\Psi $ . Let p be a name for some $x\in \operatorname {dom}(f)$ and let c be the coloring represented by $\Phi (p)$ . Notice that, since f is single-valued, for every solution $j\in \mathsf {cRT}^{{1}}_{{k}} (c)$ we have $\Psi (p,j)=f(x)$ . Furthermore, since the range of c is finite, there are only finitely many i such that $c(i)$ is not a solution. If we then define

$$ \begin{align*} n_i:= \begin{cases} \Psi(p,c(i)) & \text{if } \Psi(p,c(i)) \text{ converges in }i\text{ steps and } \Psi(p,c(i))<k, \\ 0 & \text{otherwise,} \end{cases}\end{align*} $$

we have that the sequence $(n_i)_{i\in \mathbb {N}} \in k^{\mathbb {N}}$ converges to $f(x)$ . Therefore we can use $\mathsf {lim}_k$ to obtain $f(x)$ .⊣

Proof The left-to-right implication follows from the fact that $\mathsf {lim}<_{\mathrm {W}}\mathsf {DS}$ (Theorem 4.16), while the other direction follows from Theorem 4.31 and Lemma 4.32.⊣

Proof Fix Turing functionals $\Phi $ and $\Psi $ which witness that $f \le _{\mathrm {W}} {\boldsymbol {\Delta }^0_k}\text {-}\mathsf {DS}$ . Given an f-instance with name x, $\Phi ^x$ is a $\Delta ^{0,x}_k$ -code for the linear order $\le ^x$ . Consider the $\Sigma ^{0,x}_k$ set

$$ \begin{align*} D := \{F \in \mathbb{N} : {}&{} F \text{ codes a non-empty finite} <^x\!\!\text{-descending sequence and } \\ & \Psi^{x \oplus F} \text{ outputs some } j \in \mathbb{N}\}. \end{align*} $$

We can uniformly express D as the increasing union over $s \in \mathbb {N}$ of finite sets $D_s \subseteq \{0,\ldots ,s\}$ , which are uniformly $\Pi ^{0,x}_{k-1}$ .

We now define the set

$$ \begin{align*} A:= \{ s \in\mathbb{N} : (\forall F\in D_s)( F \notin \mathrm{Ext}_x) \}, \end{align*} $$

where $\mathrm {Ext}_x$ is the set of finite sequences that extend to an infinite $<^x$ -descending sequence. It is easy to see that A is $\Pi ^{1,x}_1,$ as being extendible in a $\Delta ^0_k$ -linear order is a $\Sigma ^1_1$ property.

We show that A is finite. Since $\le ^x$ is a ${\boldsymbol {\Delta }^0_k}\text {-}\mathsf {DS}$ -instance, we can fix an infinite $<^x$ -descending sequence S. By definition of Weihrauch reducibility, $\Psi ^{x \oplus S}$ outputs some f-solution $j \in \mathbb {N}$ . By the continuity of $\Psi $ , there is some finite non-empty initial segment F of S such that $\Psi ^{x \oplus F}$ outputs j. Hence for all sufficiently large s, we have $F \in D_s$ .

This shows that we can apply ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ to A to obtain some $b \in \mathbb {N}$ which bounds A. Note that $D_b$ must be nonempty. We now define the following non-empty subset of $D_b$ :

$$ \begin{align*} B:=\left\{ F \in D_b : (\forall G\in D_b)\left(\min_{<^x}(G) \le^x \min_{<^x}(\,F)\right) \right\}.\end{align*} $$

Notice that all the quantifications are bounded. In particular, B is a (non-empty) $\Delta ^{0,x}_k$ subset of $D_b$ because $D_b$ is $\Pi ^{0,x}_{k-1}$ and $\le ^x$ is $\Delta ^{0,x}_k$ . Notice also that the definition of B ensures that each of its elements is extendible (as we know that there is some extendible element in $D_b$ ). In particular, this shows that, for every $F\in B$ , it is enough to run $\Psi ^{x \oplus F}$ to compute an f-solution for the original instance. We can find such $F \in B$ by applying $\left (\bigsqcup _s {\boldsymbol {\Delta }^0_k}\text {-}\mathsf {C}_{s}\right )(b,B)$ .⊣

Proof Using the cylindrical decomposition we can write

$$ \begin{align*} \left(\bigsqcup_{s \in \mathbb{N}} {\boldsymbol{\Delta}^0_k}\text{-}\mathsf{C}_{s}\right) * {\boldsymbol{\Pi}^1_1}\mathsf{-Bound} \equiv_{\mathrm{W}} \left(\left(\bigsqcup_{s \in \mathbb{N}} {\boldsymbol{\Delta}^0_k}\text{-}\mathsf{C}_{s}\right) \times \operatorname{id}\right) \circ \Phi_e \circ ({\boldsymbol{\Pi}^1_1}\mathsf{-Bound}\times \operatorname{id}{}) \end{align*} $$

for some computable map $\Phi _e$ . Let $\Phi _1,\Phi _2$ be computable maps s.t. $\Phi _e(p) = \langle \Phi _1(p),\Phi _2(p) \rangle $ . Then we have

$$ \begin{align*} \left(\left(\bigsqcup_{s \in \mathbb{N}} {\boldsymbol{\Delta}^0_k}\text{-}\mathsf{C}_{s}\right) \times \operatorname{id}{}\right) \circ \Phi_e \circ ({\boldsymbol{\Pi}^1_1}\mathsf{-Bound}\times \operatorname{id}{})(\langle p_1,p_2 \rangle) \\ = \left\langle \left(\bigsqcup_{s \in \mathbb{N}} {\boldsymbol{\Delta}^0_k}\text{-}\mathsf{C}_{s}\right)\Phi_1({\boldsymbol{\Pi}^1_1}\mathsf{-Bound}(p_1),p_2), \Phi_2({\boldsymbol{\Pi}^1_1}\mathsf{-Bound}(p_1),p_2) \right\rangle. \end{align*} $$

Given an instance $\langle p_1,p_2 \rangle $ of the above composition, we can think of $p_1$ as coding an input A to ${\boldsymbol {\Pi }^1_1}\mathsf {-Bound}$ via a tree T s.t. for each i, $i\in A$ iff the subtree $T_i:=\{ \sigma \in T : \sigma (0)=i \}$ of T is well-founded. For any $b \in {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}(p_1)$ , $\Phi _1(b,p_2)$ must be a name for an instance of $\bigsqcup _{s \in \mathbb {N}} {\boldsymbol {\Delta }^0_k}\text {-}\mathsf {C}_{s}$ . Then $\pi _1\Phi _1(b,p_2)$ is a number s and $\pi _2\Phi _1(b,p_2)$ is a $\boldsymbol {\Delta }^0_k$ -name for a non-empty subset $A_s$ of $\{0,\ldots , s-1\}$ , where $\pi _i(\langle p_1,p_2 \rangle )=p_i$ denotes the projection on the i-th component. Regardless of whether $b \in {\boldsymbol {\Pi }^1_1}\mathsf {-Bound}(p_1)$ , we will interpret $\pi _1\Phi _1(b,p_2)$ and $\pi _2\Phi _1(b,p_2)$ as above.