# Finding descending sequences through ill-founded linear orders

Jun Le Goh  Department of Mathematics
University of Wisconsin, Madison<EMAIL_ADDRESS>,  Arno Pauly  Department
of Computer Science
University of Swansea<EMAIL_ADDRESS>and  Manlio Valenti  Department
of Mathematics, Computer Science and Physics
University of Udine<EMAIL_ADDRESS>
###### Abstract.

In this work we investigate the Weihrauch degree of the problem $\mathsf{DS}$
of finding an infinite descending sequence through a given ill-founded linear
order, which is shared by the problem $\mathsf{BS}$ of finding a bad sequence
through a given non-well quasi-order. We show that $\mathsf{DS}$, despite
being hard to solve (it has computable inputs with no hyperarithmetic
solution), is rather weak in terms of uniform computational strength. To make
the latter precise, we introduce the notion of the deterministic part of a
Weihrauch degree. We then generalize $\mathsf{DS}$ and $\mathsf{BS}$ by
considering $\boldsymbol{\Gamma}$-presented orders, where
$\boldsymbol{\Gamma}$ is a Borel pointclass or $\boldsymbol{\Delta}^{1}_{1}$,
$\boldsymbol{\Sigma}^{1}_{1}$, $\boldsymbol{\Pi}^{1}_{1}$. We study the
obtained $\mathsf{DS}$-hierarchy and $\mathsf{BS}$-hierarchy of problems in
comparison with the (effective) Baire hierarchy and show that they do not
collapse at any finite level.

###### Key words and phrases:

Weihrauch reducibility, computable analysis, well-quasiorders, reverse
mathematics

###### 2020 Mathematics Subject Classification:

Primary: 03D78; Secondary: 03D30, 03B30, 05C55.

###### 2020 Mathematics Subject Classification:

Primary: 03D30; Secondary: 03D78, 06A75.

The second author is grateful to Mathieu Hoyrup for answering a question on
the impact of the codomain on the deterministic part, and to Linda Westrick
for several helpful discussions. The third author thanks Alberto Marcone for
many valuable suggestions during the preparation of the draft. He also thanks
Damir Dzhafarov, Giovanni Soldà and Vittorio Cipriani for useful discussions
on the topics of the paper. His research was partially supported by the
Italian PRIN 2017 Grant “Mathematical Logic: models, sets, computability”. The
authors made significant progress while all attending the BIRS-CMO workshop
“Reverse Mathematics of Combinatorial Principles (19w5111)”.

###### Contents

  1. 1 Introduction
    1. 1.1 Summary of our results
    2. 1.2 Structure of the paper
  2. 2 Background
  3. 3 The deterministic part of a problem
    1. 3.1 Impact of the codomain space
    2. 3.2 The deterministic part and the first-order part
    3. 3.3 Interaction with other operations on Weihrauch degrees
    4. 3.4 Previous appearances in the literature
  4. 4 Finding descending sequences
    1. 4.1 The uniform strength of $\mathsf{DS}$
    2. 4.2 Combinatorial principles on linear orders
    3. 4.3 Relations with Ramsey theorems
  5. 5 Presentation of orders
    1. 5.1 $\Gamma$${}^{0}_{k}$-$\mathsf{DS}$ and $\Gamma$${}^{0}_{k}$-$\mathsf{BS}$
    2. 5.2 $\Gamma$${}^{1}_{1}$-$\mathsf{DS}$ and $\Gamma$${}^{1}_{1}$-$\mathsf{BS}$
  6. 6 Conclusions

##  1\. Introduction

We study the difficulty of the following two (Weihrauch equivalent)
computational problems:

  * •

Given an ill-founded countable linear order, find an infinite decreasing
sequence in it ($\mathsf{DS}$)

  * •

Given a countable quasi-order which is not well, find a bad sequence in it
($\mathsf{BS}$).

Motivation for the first stems from the treatment of ordinals in reverse
mathematics. When working within submodels of second order arithmetic, the
notion of well-order depends on the fixed model. This leads to the so-called
pseudo-well-orders, i.e. ill-founded linear orders s.t. no descending sequence
exists within the model itself. Such a linear order would appear to be well-
founded from the point of view of the model. As a classic example of a pseudo-
well-order, consider Kleene’s computable linear order with no hyperarithmetic
descending sequence ([38, Lem. III.2.1]). Such a linear order is a well-order
when seen within the $\omega$-model $\mathrm{HYP}$ consisting exactly of the
hyperarithmetic sets. Pseudo-well-orders were first studied in [23] and proved
to be a powerful tool in reverse mathematics, especially when working at the
level of $\mathrm{ATR}_{0}$ (see [41, Sec. V.4]). Our first task can
essentially be rephrased as being concerned with the difficulty of revealing a
pseudo-ordinal as not actually being an ordinal.

Our second task can be seen as a abstraction of the computational content of
theorems in well-quasi-order (wqo) theory. There are many famous theorems
asserting that wqo’s are closed under certain operations. Examples such as
Kruskal’s tree theorem, as well as Extended Kruskal’s theorem and Higman’s
theorem, have been well-studied in proof theory via their proof-theoretic
ordinals (see [39]). However, in their usual form these results lack
computational content. Indeed, these theorems state that a certain quasi-order
$(Q,\preceq_{Q})$ is a wqo. Phrasing a result of this kind in the classical
$\Pi^{1}_{2}$-form would yield a statement of the type “given an infinite
sequence $(q_{n})_{n\in\mathbb{N}}$ in $Q$, find a pair of indexes $i<j$ s.t.
$q_{i}\preceq_{Q}q_{j}$”. Such a pair $(i,j)$ would be a witness of the fact
that the sequence $(q_{n})_{n\in\mathbb{N}}$ is not bad. However, while
proving that $(Q,\preceq_{Q})$ is a wqo can be “hard” (in particular Extended
Kruskal’s theorem is not provable in
$\boldsymbol{\Pi}^{1}_{1}\mathrm{-CA}_{0}$ [39]), producing a pair of
witnesses for each infinite sequence is a $\preceq_{Q}$-computable problem (as
it can be solved by an extensive search)!

These theorems are very extreme examples of a well-known difference between
reverse mathematics and computable analysis: quoting [19] “the computable
analyst is allowed to conduct an unbounded search for an object that is
guaranteed to exist by (nonconstructive) mathematical knowledge, whereas the
reverse mathematician has the burden of an existence proof with limited
means”.

On the other hand, considering the contrapositives of the above theorems can
reveal some (otherwise hidden) computational content. For example, to show
that a given quasi-order is not a wqo it suffices to produce a bad sequence in
it. Extended Kruskal’s theorem or Higman’s theorem can be stated in the form
“given a bad sequence for the derived quasi-order, find a bad sequence for the
original quasi-order”. Our second problem trivially is an upper bound for all
these statements, as we disregard any particular reason for why the given
quasi-order is not a wqo, and just start with the promise that it is not. Our
results thus lay the groundwork for a future exploration of the computational
content of individual theorems from wqo theory.

We use the framework of Weihrauch reducibility for our investigation. This
means that we compare the problems under investigation to a scaffolding of
benchmark problems by asking whether there is an otherwise computable uniform
procedure that solves one problem while invoking a single oracle call to the
other problem. We are not constrained to particular weak systems in proving
that these procedures are actually correct, but rather use whatever proof
techniques of ordinary mathematics are suitable. In particular, we can take
aspects like the ill-foundedness of the given linear order as external
promises not represented in the coding of the input. We can use the fact
freely in reasoning about the correctness of our procedure, but there is no
evidence provided as input of the procedure.

###  1.1. Summary of our results

There are a number of problems whose degrees are milestones in the Weihrauch
lattice and are often used as benchmarks to calibrate the uniform strength of
the multi-valued function under analysis. Some of them roughly correspond to
the so-called big five subsystems of second order arithmetic: computable
problems correspond to $\mathrm{RCA}_{0}$, $\mathsf{C}_{2^{\mathbb{N}}}$
(closed choice on the Cantor space) corresponds to $\mathrm{WKL}_{0}$,
$\mathsf{lim}$ (limit in the Baire space) and its iterations correspond to
$\mathrm{ACA}_{0}$, $\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ (closed choice on
the Baire space) and its variants $\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$ and
$\mathsf{TC}_{\mathbb{N}^{\mathbb{N}}}$ correspond to $\mathrm{ATR}_{0}$,
${\boldsymbol{\Pi}^{1}_{1}}\text{-}\mathsf{CA}$ corresponds to
$\boldsymbol{\Pi}^{1}_{1}\mathrm{-CA}_{0}$.

We show that $\mathsf{DS}$ does not belong to this “explored” part of the
lattice. To put it in a nutshell, our results show that it is difficult to
solve $\mathsf{DS}$, but that $\mathsf{DS}$ is rather weak in solving other
problems. For example, $\mathsf{DS}$ has computable inputs without any
hyperarithmetic solutions. On the other hand, $\mathsf{DS}$ uniformly computes
only the limit computable functions. We provide a few characterizations that
tell us what the greatest Weihrauch degree with representatives of particular
types below $\mathsf{DS}$ is, and include some general observations on this
approach. The diagram in Figure 1 shows the relations between $\mathsf{DS}$
and several other Weihrauch degrees. Dashed arrows represent Weihrauch
reducibility in the direction of the arrow, solid arrows represent strict
Weihrauch reducibility.

$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}\equiv_{\mathrm{W}}\mathsf{lim}*\mathsf{DS}$$\mathsf{lim}$$\mathsf{LPO}^{\prime}$$\mathsf{RT}^{{1}}_{{\mathbb{N}}}$$\mathsf{KL}$$\mathsf{General}\text{-}\mathsf{SADS}$$\mathsf{lim}^{\prime}$$\mathsf{lim}^{\prime\prime}$$\mathsf{RT}^{{1}}_{{2}}$$\mathsf{LPO}$$\mathsf{C}_{\mathbb{N}}$$\mathsf{C}_{2^{\mathbb{N}}}$$\mathsf{ADS}$$\mathsf{RT}^{{2}}_{{2}}$
Figure 1. An overview of some parts of the Weihrauch lattice. The solid frame
collects the degrees belonging to the lower cone of $\mathsf{DS}$, while the
dashed frame collects principles that are not Weihrauch reducible to
$\mathsf{DS}$. The only principle shown which is above $\mathsf{DS}$ is
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$. We do not know whether $\mathsf{KL}$
is reducible to $\mathsf{DS}$.

Next, we generalize our results by exploring how different presentations of
the same order can affect the uniform strength of the same computational task
(finding descending sequences in it). We study the problems
${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}$ and
${\boldsymbol{\Gamma}}\text{-}\mathsf{BS}$, where the name of the input order
carries “less accessible information” on the order itself (namely $a\leq_{L}b$
is assumed to be a $\Gamma$-condition relative to the name of the order). We
summarize the results in Figure 2.

$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}\equiv_{\mathrm{W}}\mathsf{lim}*\mathsf{DS}$$\mathsf{lim}$$\mathsf{LPO}^{\prime}$$\mathsf{RT}^{{1}}_{{\mathbb{N}}}$$\mathsf{KL}$$\mathsf{General}\text{-}\mathsf{SADS}$$\mathsf{lim}^{\prime}$$\mathsf{lim}^{\prime\prime}$$\mathsf{RT}^{{1}}_{{2}}$$\mathsf{LPO}$$\mathsf{C}_{\mathbb{N}}$$\mathsf{C}_{2^{\mathbb{N}}}$$\mathsf{ADS}$$\mathsf{RT}^{{2}}_{{2}}$$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$$\mathsf{DS}\equiv_{\mathrm{W}}\mathsf{BS}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{1}}\text{-}\mathsf{DS}$
${\boldsymbol{\Sigma}^{0}_{2}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{2}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{2}}\text{-}\mathsf{BS}$
${\boldsymbol{\Pi}^{0}_{1}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{1}}\text{-}\mathsf{BS}$
${\boldsymbol{\Sigma}^{0}_{2}}\text{-}\mathsf{BS}$${\boldsymbol{\Delta}^{1}_{1}}\text{-}\mathsf{DS}$${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{DS}$${\boldsymbol{\Pi}^{1}_{1}}\text{-}\mathsf{DS}$${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{BS}$${\boldsymbol{\Pi}^{1}_{1}}\text{-}\mathsf{CA}$${\boldsymbol{\Sigma}^{0}_{1}}\text{-}\mathsf{BS}$
Figure 2. Diagram presenting the relations between the various generalizations
of $\mathsf{DS}$.

###  1.2. Structure of the paper

After a short introduction on the preliminary notions on represented spaces
and Weihrauch reducibility (Section 2), we define the deterministic part of a
multi-valued function and explore the algebraic properties of the operator
$\mathrm{Det}_{\mathbf{X}}(\cdot)$ (Section 3). These results will be very
useful in the study of the problems $\mathsf{DS}$ and $\mathsf{BS}$ (Section
4) and their generalizations ${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}$ and
${\boldsymbol{\Gamma}}\text{-}\mathsf{BS}$ (Section 5).

##  2\. Background

For an introduction to Weihrauch reducibility, we point the reader to [10];
for represented spaces to [36]. Below we briefly introduce the notions we will
need, as well as state useful results. Those familiar with Weihrauch
reducibility should read 2.2 where we define the first-order part of a
problem, recently studied by Dzhafarov, Solomon, Yokoyama [17].

A _represented space_ X is a set $X$ together with a (possibly partial)
surjection $\delta_{\textbf{X}}:\subseteq{\mathbb{N}^{\mathbb{N}}}\to X$. We
can transfer notions of computability from ${\mathbb{N}^{\mathbb{N}}}$ to X as
follows. For each $x\in X$, we say that $p$ is a ($\delta_{\textbf{X}}$-)name
of $x$ if $\delta_{\textbf{X}}(p)=x$. We say that $x\in X$ is
($\delta_{\mathbf{X}}$-)computable if it has a computable
($\delta_{\textbf{X}}$-)name.

We list some relevant examples. Let
$\mathbf{LO}=(\mathrm{LO},\delta_{\mathbf{LO}})$ be the represented space of
linear orders with domain contained in $\mathbb{N}$, where each linear order
$(L,\leq_{L})$ is represented by the characteristic function of the set
$\\{\langle a,b\rangle\in\mathbb{N}:a\leq_{L}b\\}$. Let
$\textbf{WO}=(\mathrm{WO},\delta_{\mathbf{WO}})$ be the represented space of
well-orders with domain contained in $\mathbb{N}$, where
$\delta_{\mathrm{WO}}$ is the restriction of $\delta_{\mathrm{LO}}$ to codes
of well-orders. Similarly, let
$\mathbf{QO}=(\mathrm{QO},\delta_{\mathbf{QO}})$ be the represented space of
quasi-orders (represented via the characteristic function of the relation).
Let also $\mathbf{Tr}$ be the space of subtrees of
${\mathbb{N}^{<\mathbb{N}}}$, represented by characteristic functions. For
every string $\sigma\in{\mathbb{N}^{<\mathbb{N}}}$ we denote with $\sigma[n]$
the prefix of length $n$ of $\sigma$.

We will formalize the problems under investigation as partial multi-valued
functions between represented spaces
$f:\subseteq\textbf{X}\rightrightarrows\textbf{Y}$. For each $x\in X$, $f(x)$
denotes the set of possible outputs corresponding to the input $x$. The
_domain_ $\operatorname{dom}(f)$ is the set of all $x\in X$ such that $f(x)$
is nonempty. We often refer to each $x\in\operatorname{dom}(f)$ as an _$f$
-instance_ and each $y\in f(x)$ as an _$f$ -solution to $x$_. When we define a
problem, we will often not specify its domain explicitly, in which case its
domain should be taken to be as large as possible. The _codomain_ of
$f:\subseteq\textbf{X}\rightrightarrows\textbf{Y}$ is Y. If
$f:\subseteq\textbf{X}\rightrightarrows\textbf{Y}$ is such that $f(x)$ is a
singleton for each $x\in\operatorname{dom}(f)$, then we say that $f$ is
_single-valued_. We indicate that by writing
$f:\subseteq\textbf{X}\to\textbf{Y}$. In this case we will write $f(x)=y$
instead of (the formally correct) $f(x)=\\{y\\}$. An example of a single-
valued problem is the identity function
$\operatorname{id}:{\mathbb{N}^{\mathbb{N}}}\to{\mathbb{N}^{\mathbb{N}}}$.

We can define the computability or continuity of problems via realizers: we
say that a function
$F:\subseteq{\mathbb{N}^{\mathbb{N}}}\to{\mathbb{N}^{\mathbb{N}}}$ is a
_realizer_ of a problem $f:\subseteq\textbf{X}\rightrightarrows\textbf{Y}$ if
whenever $p$ is a name for some $x\in\operatorname{dom}(f)$, $F(p)$ is a name
for some $y\in f(x)$. A problem is _computable_ (respectively _continuous_) if
it has a computable (respectively continuous) realizer.

In order to measure the relative uniform computational strength of problems,
we use Weihrauch reducibility. A problem $f$ is _Weihrauch reducible_ to a
problem $g$, written $f\leq_{\mathrm{W}}g$, if there are computable maps
$\Phi,\Psi:\subseteq{\mathbb{N}^{\mathbb{N}}}\to{\mathbb{N}^{\mathbb{N}}}$
such that if $p$ is a name for some $x\in\operatorname{dom}(f)$, then

  1. (1)

$\Phi(p)$ is a name for some $y\in\operatorname{dom}(g)$;

  2. (2)

if $q$ is a name for some element of $g(y)$, then $\Psi(p,q)$ is a name for
some element of $f(x)$.

This means that there is a procedure for solving $f$ which is computable
except for a single invocation to an oracle for $g$. Equivalently, there is a
computable procedure which transforms realizers for $g$ into realizers for
$f$. A problem $f$ is _strongly Weihrauch reducible_ to a problem $g$, written
$f\leq_{\mathrm{sW}}g$, if there are computable maps $\Phi$ and $\Psi$ as
above, except that $\Psi$ is not allowed access to $p$ in its computation.

Weihrauch reducibility and strong Weihrauch reducibility are quasi-orders, so
they define a degree structure on problems: $f\equiv_{\mathrm{W}}g$ if
$f\leq_{\mathrm{W}}g$ and $g\leq_{\mathrm{W}}f$ (likewise for
$\leq_{\mathrm{sW}}$). Both the Weihrauch degrees and the strong Weihrauch
degrees form lattices (see [10, Thm. 3.9 and Thm. 3.10]). There are several
natural operations on problems which also lift to the
$\equiv_{\mathrm{W}}$-degrees and the $\equiv_{\mathrm{sW}}$-degrees. Below we
present the operations that we need in this paper.

The parallel product $f\times g$ is defined by $(f\times g)(x,y)=f(x)\times
g(y)$. We call $f$ a cylinder if
$f\equiv_{\mathrm{sW}}f\times\operatorname{id}$. If $f$ is a cylinder, then
$g\leq_{\mathrm{W}}f$ if and only if $g\leq_{\mathrm{sW}}f$ ([5, Cor. 3.6]).
This is useful for establishing nonreductions because if $f$ is a cylinder,
then it suffices to diagonalize against all strong Weihrauch reductions from
$g$ to $f$ in order to show that $g\not\leq_{\mathrm{W}}f$. Cylinders will
also be useful when working with compositional products (discussed below).
Observe that for every problem $f$, $f\times\operatorname{id}$ is a cylinder
which is Weihrauch equivalent to $f$.

The _parallelization_ $\widehat{f}$ is defined by
$\widehat{f}((x_{n})_{n\in\mathbb{N}})=\prod_{n\in\mathbb{N}}f(x_{n})$. In
other words, given a countable sequence of $f$-instances, $\widehat{f}$ asks
for an $f$-solution for each given $f$-instance.

The _composition_ of $f:\subseteq\textbf{Y}\rightrightarrows\textbf{Z}$ and
$g:\subseteq\textbf{X}\rightrightarrows\textbf{Y}$ is defined by
$\operatorname{dom}(f\circ
g)=\\{x\in\operatorname{dom}(g):g(x)\subseteq\operatorname{dom}(f)\\}$ and
$(f\circ g)(x)=\bigcup_{y\in g(x)}f(y)$ for $x\in\operatorname{dom}(f\circ
g)$. The composition does _not_ respect $\leq_{\mathrm{W}}$ or
$\leq_{\mathrm{sW}}$. Instead, for any problems $f$ and $g$ (regardless of
domain and codomain), we can consider the _compositional product_ $f*g$, which
satisfies the following property:

$f*g\equiv_{\mathrm{W}}\max_{\leq_{\mathrm{W}}}\\{f_{1}\circ
g_{1}:f_{1}\leq_{\mathrm{W}}f\land g_{1}\leq_{\mathrm{W}}g\\}.$

This captures what can be achieved by first applying $g$, possibly followed by
some computation, and then applying $f$. The compositional product was first
introduced in [9], and proven to be well-defined in [12]. A useful tool is the
_cylindrical decomposition lemma_ ([12, Lem. 3.10]): for all problems $f$ and
$g$, if $F\equiv_{\mathrm{W}}f$ and $G\equiv_{\mathrm{W}}g$ are both
cylinders, then there is some computable map $\Phi$ such that
$f*g\equiv_{\mathrm{W}}F\circ\Phi\circ G$. For each problem $f$, let $f^{[n]}$
denote the $n$-fold iteration of the compositional product of $f$ with itself,
i.e., $f^{[1]}=f$, $f^{[2]}=f*f$, and so on.

The jump of $f:\subseteq\textbf{X}\rightrightarrows\textbf{Y}$ is the problem
$f^{\prime}:\subseteq\textbf{X}^{\prime}\rightrightarrows\textbf{Y}$ defined
by $f^{\prime}(x):=f(x)$, where $\textbf{X}^{\prime}$ is the represented space
$(X,\delta_{\mathbf{X}^{\prime}})$ and $\delta_{\mathbf{X}^{\prime}}$ takes in
input a convergent sequence $(p_{n})_{n\in\mathbb{N}}$ in
${\mathbb{N}^{\mathbb{N}}}$ and returns
$\delta_{\mathbf{X}}(\lim_{n\to\infty}p_{n})$. In other words, $f^{\prime}$ is
the following task: given a sequence which converges to a name of an
$f$-instance, produce an $f$-solution to that instance. The jump respects
$\leq_{\mathrm{sW}}$ but does _not_ lift to the $\equiv_{\mathrm{W}}$-degrees.
We use $f^{(n)}$ to denote the $n$-th jump of a problem. If we define
$\mathsf{lim}:\subseteq({\mathbb{N}^{\mathbb{N}}})^{\mathbb{N}}\to{\mathbb{N}^{\mathbb{N}}}$
by $\mathsf{lim}((p_{n})_{n\in\mathbb{N}}):=\lim_{n\to\infty}p_{n}$ then it is
straightforward from the definition that
$f^{(n)}\leq_{\mathrm{W}}f*\mathsf{lim}^{[n]}$. The converse reduction does
not hold in general. However if $f$ is a cylinder, then for each $n$,
$f^{(n)}$ is a cylinder and $f^{(n)}\equiv_{\mathrm{W}}f*\mathsf{lim}^{[n]}$
(see [10, Prop. 6.14]). In particular, since $\mathsf{lim}$ is a cylinder,
$\mathsf{lim}^{(n)}\equiv_{\mathrm{W}}\mathsf{lim}^{[n+1]}$ for each $n$. We
say that a problem is _arithmetic_ if it is Weihrauch reducible to
$\mathsf{lim}^{(n)}$ for some $n$.

Next we introduce some problems which are milestones in the Weihrauch lattice.
Apart from $\mathsf{lim}$ and its jumps, most prominent is the family of
problems of (closed) choice
$\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}$ defined below. For a
represented space $\mathbf{X}$, let $\mathcal{A}(X)$ denote the space of
closed subsets of $\mathbf{X}$. These are given by the ability to recognize
membership in the complement. We define
$\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}:\subseteq\mathcal{A}(X)\rightrightarrows
X$ by $\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}(A):=A$. In other
words, $\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}$ is the task of
producing an element of $\mathbf{X}$ given a way to recognize wrong answers.
Define _unique choice_ $\mathsf{UC}_{\textbf{X}}$ to be the restriction of
$\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}$ to closed sets which are
singletons. By definition, $\mathsf{UC}_{\textbf{X}}$ is single-valued.

Of particular interest to us are $\mathsf{C}_{\mathbb{N}}$,
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ and
$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$. We can view elements of
$\mathcal{A}(\mathbb{N})$ to be given as an enumeration of its complement.
Thus, $\mathsf{C}_{\mathbb{N}}$ is the task of finding a natural number not
occurring in a given list. Given a name for a closed set
$A\subseteq{\mathbb{N}^{\mathbb{N}}}$, we can compute a tree
$T\subseteq{\mathbb{N}^{<\mathbb{N}}}$ such that the set $[T]$ of (infinite)
paths on $T$ is $A$. Conversely, given a tree
$T\subseteq{\mathbb{N}^{<\mathbb{N}}}$, we can compute a name for the closed
set $[T]$. Therefore we can view $\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ as the
problem of computing a path on a given ill-founded subtree of
${\mathbb{N}^{<\mathbb{N}}}$. Similarly, we can view
$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$ as the problem of computing the unique
path on a given subtree of ${\mathbb{N}^{<\mathbb{N}}}$. Both
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ and
$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$ are closed under compositional product
[4, Thm. 7.3]. We have:

######  Theorem 2.1 ([26, Cor. 3.4]).

If $f:\subseteq{\mathbb{N}^{\mathbb{N}}}\rightrightarrows\mathbf{X}$ is
Weihrauch reducible to $\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$, then for every
$x\in\operatorname{dom}(f)$, $f(x)$ contains some $y$ hyperarithmetical
relative to $x$.

Another prominent problem is
$\mathsf{LPO}:{\mathbb{N}^{\mathbb{N}}}\to\\{0,1\\}$, defined by
$\mathsf{LPO}(p):=0$ if $p=0^{\mathbb{N}}$ and $\mathsf{LPO}(p):=1$ otherwise.
Its jump $\mathsf{LPO}^{\prime}$ (and its iterated jumps $\mathsf{LPO}^{(k)}$)
will play an important technical role. We notice that
$\mathsf{lim}^{(n)}\equiv_{\mathrm{W}}\widehat{\mathsf{LPO}^{(n)}}$ (see e.g.
[10, Thm. 6.7 and Prop. 6.10]).

Next we define the represented space $\boldsymbol{\Gamma}(\textbf{X})$ of all
$\boldsymbol{\Gamma}$-definable subsets of a computable metric space $X$,
where
$\boldsymbol{\Gamma}\in\\{\boldsymbol{\Sigma}^{0}_{k},\boldsymbol{\Pi}^{0}_{k},\boldsymbol{\Delta}^{0}_{k},\boldsymbol{\Sigma}^{1}_{1},\boldsymbol{\Pi}^{1}_{1},\boldsymbol{\Delta}^{1}_{1}\\}$.
This is based on the well-known concept of Borel codes [33]. For a more
detailed development in the context of computable analysis we refer to [22]. A
more abstract and general treatment is provided in [37]. A
$\delta_{\boldsymbol{\Sigma}^{0}_{1}}$-name for a set $B\subseteq X$ is a
sequence of indices of rational open balls whose union is $B$. A
$\delta_{\boldsymbol{\Pi}^{0}_{k}}$-name for a set is a
$\delta_{\boldsymbol{\Sigma}^{0}_{k}}$-name for its complement. (Note that
$\delta_{\boldsymbol{\Pi}^{0}_{1}}$ agrees with how we represented closed sets
previously.) A $\delta_{\boldsymbol{\Delta}^{0}_{k}}$-name for a set is a pair
of $\delta_{\boldsymbol{\Sigma}^{0}_{k}}$-names, one for the set itself and
one for its complement. A $\delta_{\boldsymbol{\Sigma}^{0}_{k+1}}$-name for a
set $B\subseteq X$ is a sequence of names for $\boldsymbol{\Pi}^{0}_{k}$ sets
whose union is $B$.

A $\delta_{\boldsymbol{\Sigma}^{1}_{1}}$-name for a set $S\subseteq X$ is a
$\delta_{\boldsymbol{\Pi}^{0}_{1}}$-name for a set
$P\subseteq{\mathbb{N}^{\mathbb{N}}}\times X$ such that $S=\\{x\in X:(\exists
g)((g,x)\in P)\\}$. We define $\delta_{\boldsymbol{\Pi}^{1}_{1}}$ and
$\delta_{\boldsymbol{\Delta}^{1}_{1}}$ similarly to
$\delta_{\boldsymbol{\Pi}^{0}_{k}}$ and
$\delta_{\boldsymbol{\Delta}^{0}_{k}}$. If $X$ is $\mathbb{N}$, we can think
of a $\delta_{\boldsymbol{\Sigma}^{1}_{1}}$-name for $S\subseteq\mathbb{N}$ as
a sequence $(T_{n})_{n\in\mathbb{N}}$ of subtrees of
${\mathbb{N}^{<\mathbb{N}}}$ such that $n\in S$ if and only if $T_{n}$ is ill-
founded.

In practice, we rarely construct $\delta_{\boldsymbol{\Gamma}}$-names
explicitly. If we want to construct a $\delta_{\boldsymbol{\Gamma}}$-name for
a set $A\subseteq X$, we typically only check that there is a
$\boldsymbol{\Gamma}$-formula which defines $A$. By invoking computable
closure properties, one can construct a computable map which takes a
$\boldsymbol{\Gamma}$-formula $\phi$ and its parameter $p$ to a
$\delta_{\boldsymbol{\Gamma}}$-name for the set defined by $\phi$. Conversely,
one can construct a computable map which takes a
$\delta_{\boldsymbol{\Gamma}}$-name $p$ for a set $A$ to a
$\boldsymbol{\Gamma}$-formula $\phi$ with parameter $p$ which defines $A$.

We define the (single-valued) functions
${\boldsymbol{\Gamma}}\text{-}\mathsf{CA}:\subseteq\boldsymbol{\Gamma}(\mathbb{N})\to{2^{\mathbb{N}}}$
corresponding to comprehension principles: given a
$\delta_{\boldsymbol{\Gamma}}$-name $p$ for a subset $A$ of $\mathbb{N}$,
produce its characteristic function. Notice that, for each $k$ and each
$A\in\boldsymbol{\Sigma}^{0}_{k+1}$, we can use $\mathsf{LPO}^{(k)}$ to check
whether $n\in A$ (intuitively, for every $p$ we can use $\mathsf{LPO}^{(k)}$
to answer a $\Sigma^{0,p}_{k+1}$ question). This shows that, for each $k$,

$\mathsf{lim}^{(k)}\equiv_{\mathrm{W}}\widehat{\mathsf{LPO}^{(k)}}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k+1}}\text{-}\mathsf{CA},$

somewhat implicitly written in [3]. The problem
${\boldsymbol{\Pi}^{1}_{1}}\text{-}\mathsf{CA}$ can be seen as the analogue of
$\boldsymbol{\Pi}^{1}_{1}\mathrm{-CA}_{0}$. It is Weihrauch equivalent to the
parallelization of $\chi_{\Pi^{1}_{1}}$, which is the characteristic function
of a $\Pi^{1}_{1}$-complete set. It is convenient to think of
$\chi_{\Pi^{1}_{1}}$ as the function that takes in input a subtree of
${\mathbb{N}^{<\mathbb{N}}}$ and checks whether it is well-founded.

We can also define $\boldsymbol{\Gamma}$-choice
${\boldsymbol{\Gamma}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}:\subseteq\boldsymbol{\Gamma}(\textbf{X})\rightrightarrows\textbf{X}$
by
${\boldsymbol{\Gamma}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}(A):=A$.
In other words,
${\boldsymbol{\Gamma}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\textbf{X}}}$
is the task of producing an element of a nonempty $\boldsymbol{\Gamma}$-set
$A$, given a $\delta_{\boldsymbol{\Gamma}}$-name of $A$. We can define
$\boldsymbol{\Gamma}\text{-}\mathsf{UC}_{\textbf{X}}:\subseteq\boldsymbol{\Gamma}(\textbf{X})\to\textbf{X}$
analogously. When reducing problems to $\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$
and $\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$, the following facts are helpful:
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{{\mathbb{N}^{\mathbb{N}}}}}\equiv_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$
and
$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}\equiv_{\mathrm{W}}\boldsymbol{\Sigma}^{1}_{1}\text{-}\mathsf{UC}_{{\mathbb{N}^{\mathbb{N}}}}$
(see [26]).

We define the represented spaces $\boldsymbol{\Gamma}(\textbf{LO})$ and
$\boldsymbol{\Gamma}(\textbf{QO})$ by restricting the codomain of
$\delta_{\boldsymbol{\Gamma}}$ to the set of subsets of $\mathbb{N}$ which are
characteristic functions of linear orders and quasiorders respectively. This
will be used in Section 5.

We will often construct linear orders using the following method. For every
tree $T\subseteq{\mathbb{N}^{<\mathbb{N}}}$, we define the _Kleene-Brouwer
order_ $\mathrm{KB}(T)$ on $T$ as follows: $\sigma\leq_{\mathrm{KB}}\tau$ if
and only if $\tau\sqsubseteq\sigma$ or $\sigma\leq_{lex}\tau$. The map
$T\mapsto\mathrm{KB}(T)$ from $\mathbf{Tr}$ to LO is computable. It is known
that $\mathrm{KB}(T)$ is a well-order if and only if $T$ is well-founded (see
e.g. [41, Lem. V.1.3]).

Finally we present a notion recently studied by Dzhafarov, Solomon, Yokoyama
[17]:

######  Definition 2.2.

Let $\mathcal{F}$ be the set of first-order problems, i.e. the set of problems
with codomain $\mathbb{N}$. For every problem
$f:\subseteq\mathbf{Y}\rightrightarrows\mathbf{Z}$, the first-order part of
$f$ is the multi-valued function
${}^{1}{f}:\subseteq{\mathbb{N}^{\mathbb{N}}}\times\mathbf{Y}\rightrightarrows\mathbb{N}$
defined as follows:

  * •

instances are pairs $(p,y)$ s.t. $y\in\operatorname{dom}(f)$ and for every
$z\in f(y)$ and every name $t$ for $z$, $\Phi_{p}(t)(0)\downarrow$, where
$\Phi_{(\cdot)}$ is a fixed universal Turing functional;

  * •

a solution for $(p,y)$ is any $n$ s.t. there is a name $t$ for a solution
$z\in f(y)$ s.t. $\Phi_{p}(t)(0)\downarrow=n$.

The motivation for this notion comes from the following fact:

######  Proposition 2.3 ([17]).

For every problem $f$,

${}^{1}{f}\equiv_{\mathrm{W}}\max_{\leq_{\mathrm{W}}}\\{g\in\mathcal{F}:g\leq_{\mathrm{W}}f\\}.$

We conclude this section with the following proposition:

######  Proposition 2.4.

${}^{1}{\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\mathbb{N}}}$.

###### Proof.

It is known that
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\mathbb{N}}}<_{\mathrm{W}}\widehat{{\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\mathbb{N}}}}<_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$
([1, Thm. 3.34]). On the other hand, if
$f:\subseteq\mathbf{X}\rightrightarrows\mathbb{N}$ is s.t.
$f\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ via $\Phi,\Psi$ then,
for every name $p$ of some $x\in\operatorname{dom}(f)$, $\Phi(p)$ is the name
of an ill-founded tree $T_{p}$ and, for every $t\in[T_{p}]$ we have
$\Psi(t)(0)\in f(x)$. This means that we can compute a solution choosing an
element from

$\\{n\in\mathbb{N}:(\exists
t\in{\mathbb{N}^{\mathbb{N}}})(t\in[T_{p}]\land\Psi(t)(0)=n)\\},$

which is a $\Sigma^{1,p}_{1}$ subset of $\mathbb{N}$. ∎

We will characterize the first-order part of $\mathsf{DS}$ in 4.10.

##  3\. The deterministic part of a problem

######  Definition 3.1.

Let $\mathbf{X}$ be a represented space and
$f:\subseteq\mathbf{Y}\rightrightarrows\mathbf{Z}$ be a multi-valued function.
We define
$\mathrm{Det}_{\mathbf{X}}(f):\subseteq{\mathbb{N}^{\mathbb{N}}}\times\mathbf{Y}\to\mathbf{X}$
by

$\mathrm{Det}_{\mathbf{X}}(f)(p,y)=x:\iff(\forall
z\in\delta_{\mathbf{Z}}^{-1}(f(y)))(\delta_{\mathbf{X}}(\Phi_{p}(z))=x),$

where $\Phi_{(\cdot)}$ is a universal Turing functional. The domain of
$\mathrm{Det}_{\mathbf{X}}(f)$ is maximal for this to be well-defined. We just
write $\mathrm{Det}(f)$ for $\mathrm{Det}_{{\mathbb{N}^{\mathbb{N}}}}(f)$.

Notice that $\mathrm{Det}(f)$ is always a cylinder. This is not true for all X
(if $\mathbf{X}=\mathbb{N}$ then $\mathrm{Det}_{\mathbf{X}}(f)$ always has
computable solutions, and therefore
$\operatorname{id}\not\leq_{\mathrm{sW}}\mathrm{Det}_{\mathbf{X}}(f)$).

Our interest in the principle $\mathrm{Det}_{\mathbf{X}}(f)$ lies in the fact
that it has the maximal Weihrauch degree of all (single-valued!) functions
with codomain $\mathbf{X}$ that are Weihrauch below $f$:

######  Theorem 3.2.

$\mathrm{Det}_{\mathbf{X}}(f)\equiv_{\mathrm{W}}\max_{\leq_{\mathrm{W}}}\\{g:\subseteq\mathbf{W}\to\mathbf{X}:g\leq_{\mathrm{W}}f\\}$.

###### Proof.

Clearly, $\mathrm{Det}_{\mathbf{X}}(f)$ is itself present in the set on the
right hand side. Assume $g:\subseteq\mathbf{W}\to\mathbf{X}$ satisfies
$g\leq_{\mathrm{W}}f$ with reduction witnesses $\Phi$ and $\Psi$. Given a name
$q$ for an input to $g$, let $y=\delta_{\mathbf{Y}}(\Phi(q))$ be the value $f$
is called on, and let $p$ be a name for the function $\Psi(q,\cdot)$. Then
$\mathrm{Det}_{\mathbf{X}}(f)(p,y)=g(\delta_{\mathbf{W}}(q))$. ∎

In the same spirit, we can identify several other operators
$\Lambda_{\mathcal{Y}}$ of the type
$\Lambda_{\mathcal{Y}}(f):=\max_{\leq_{\mathrm{W}}}\\{g\in\mathcal{Y}:g\leq_{\mathrm{W}}f\\}$.
In particular the proof strategy used in 3.2 can be used to prove that
$\Lambda_{\mathcal{U}_{N}}$ and $\Lambda_{\mathcal{V}_{N}}$ are total, where
$\mathcal{U}_{N}$ is the set of first-order problems with codomain $N$, and
$\mathcal{V}_{N}$ is the set of problems in $\mathcal{U}_{N}$ which are also
single-valued. This will come into play in 4.31 and in 4.33.

######  Corollary 3.3.

$\mathrm{Det}_{\mathbf{X}}(\cdot)$ is an interior degree-theoretic operator on
Weihrauch degrees, i.e.

$\displaystyle\mathrm{Det}_{\mathbf{X}}(\mathrm{Det}_{\mathbf{X}}(f))\equiv_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(f)\leq_{\mathrm{W}}f;$
$\displaystyle
f\leq_{\mathrm{W}}g\Rightarrow\mathrm{Det}_{\mathbf{X}}(f)\leq_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(g).$

###  3.1. Impact of the codomain space

We make some basic observations on how the space $\mathbf{X}$ impacts the
degrees $\mathrm{Det}_{\mathbf{X}}(f)$ for arbitrary $f$. Clearly, whenever
$\mathbf{Y}$ computably embeds into $\mathbf{X}$ (i.e. there is a computable
injection $\mathbf{Y}\to\mathbf{X}$ with computable inverse), then
$\mathrm{Det}_{\mathbf{Y}}(f)\leq_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(f)$.
In general, we obtain many different operations. To see this, we consider the
point degree spectrum of a represented space as introduced by Kihara and P.
[28]. The point degree spectrum of $(X,\delta_{\mathbf{X}})$ is the set of
Medvedev degrees of the form $\delta^{-1}_{\mathbf{X}}(x)$ for $x\in X$.

The spectrum of $\mathbf{Y}$ is included in that of $\mathbf{X}$ iff
$\mathbf{Y}$ can be decomposed into countably many parts each of which embeds
into $\mathbf{X}$ ([28, Lem. 3.6]). If the spectrum of $\mathbf{Y}$ is not
included in that of $\mathbf{X}$, we can consider a constant function $y$
witnessing this. Then
$\mathrm{Det}_{\mathbf{X}}(y)<_{\mathrm{W}}\mathrm{Det}_{\mathbf{Y}}(y)\equiv_{\mathrm{W}}y$.
We have thus seen that if
$\mathrm{Det}_{\mathbf{X}}(f)\equiv_{\mathrm{W}}\mathrm{Det}_{\mathbf{Y}}(f)$
for all $f$, then $\mathbf{X}$ and $\mathbf{Y}$ must have the same point
degree spectrum. Miller [32] has shown that the spectrum of $[0,1]^{\omega}$
is not contained in the Turing degrees (i.e. the spectrum of
${2^{\mathbb{N}}}$), which was extended in [28] to the result that the
spectrum of a computable Polish space is contained in the Turing degrees
relative to some oracle iff that space is countably dimensional. The spectra
of further spaces have been explored in [27].

We can extend the separation arguments based on the spectrum by considering
sequences rather than just constant functions111The ideas in this paragraph
were pointed out to us by Mathieu Hoyrup.. Whenever we have a sequence
$f_{0}:\mathbb{N}\to\mathbf{X}_{0}$ and a function
$g_{0}:\subseteq{\mathbb{N}^{\mathbb{N}}}\to\mathbf{X}_{1}$ with
$f_{0}\equiv_{\mathrm{W}}g_{0}$, then there is a sequence
$h:\mathbb{N}\to\mathbf{X}_{1}$ with $f_{0}\equiv_{\mathrm{W}}h$. A Weihrauch
reduction $f\leq_{\mathrm{W}}g$ for $f:\mathbb{N}\to\mathbf{X}$ and
$g:\mathbb{N}\to\mathbf{Y}$ gives rise to a computable partial function
$F:\subseteq\mathbf{Y}^{\mathbb{N}}\to\mathbf{X}^{\mathbb{N}}$ with $F(g)=f$.
It follows that it suffices to separate $\mathbf{Y}^{\mathbb{N}}$ and
$\mathbf{X}^{\mathbb{N}}$ via their spectrum to conclude that
$\mathrm{Det}_{\mathbf{X}}(\cdot)$ and $\mathrm{Det}_{\mathbf{Y}}(\cdot)$ are
distinct operators. In particular, Miller’s result implies that there is a
function with codomain $\mathbb{R}$ that is not equivalent to any function
with codomain ${\mathbb{N}^{\mathbb{N}}}$.

###  3.2. The deterministic part and the first-order part

Let us now explore the interplay between the deterministic part and the first-
order part.

######  Proposition 3.4.

${}^{1}{\mathrm{Det}(f)}\equiv_{\mathrm{W}}\mathrm{Det}_{\mathbb{N}}(f)\leq_{\mathrm{W}}\mathrm{Det}({}^{1}{f})$.

###### Proof.

By considering what the relevant maxima in the characterizations are taken
about, it is clear that
$\mathrm{Det}_{\mathbb{N}}(f)\leq_{\mathrm{W}}{}^{1}{\mathrm{Det}(f)}$ and
$\mathrm{Det}_{\mathbb{N}}(f)\leq_{\mathrm{W}}\mathrm{Det}({}^{1}{f})$. To see
that ${}^{1}{\mathrm{Det}(f)}\leq_{\mathrm{W}}\mathrm{Det}_{\mathbb{N}}(f)$,
we consider a function
$f:\subseteq{\mathbb{N}^{\mathbb{N}}}\to{\mathbb{N}^{\mathbb{N}}}$ and a
multi-valued function
$g:\subseteq{\mathbb{N}^{\mathbb{N}}}\rightrightarrows\mathbb{N}$ with
$g\leq_{\mathrm{W}}f$. But this reduction actually yields some choice function
of $g$, showing that $g\leq_{\mathrm{W}}\mathrm{Det}_{\mathbb{N}}(f)$. ∎

######  Open Question 3.5.

Is there some $f$ with
$\mathrm{Det}_{\mathbb{N}}(f)<_{\mathrm{W}}\mathrm{Det}({}^{1}{f})$?

The question above asks whether whenever there is a countable cover making a
partial function on Baire space piecewise computable, there also is a
partition of the same or lower complexity that renders the function piecewise
computable. The complexity here is not merely the complexity of the individual
pieces, but the Weihrauch degree of the map that assigns the piece to any
Baire space element.

######  Proposition 3.6.

$\mathrm{Det}(f)\leq_{\mathrm{W}}\widehat{\mathrm{Det}_{\mathbb{N}}(f)}$.

###### Proof.

A function $f:\subseteq{\mathbb{N}^{\mathbb{N}}}\to{\mathbb{N}^{\mathbb{N}}}$
is reducible to the parallelization of its uncurried form
$F:\subseteq\mathbb{N}\times{\mathbb{N}^{\mathbb{N}}}\to\mathbb{N}$ where
$F(n,p)=f(p)(n)$. ∎

######  Corollary 3.7.

$\mathrm{Det}(f)\leq_{\mathrm{W}}\widehat{{}^{1}{f}}$.

###  3.3. Interaction with other operations on Weihrauch degrees

A first straightforward observation is that
$\mathrm{Det}(f)\,\square\,\mathrm{Det}(g)\leq_{\mathrm{W}}\mathrm{Det}(f\,\square\,g)$
whenever $\square$ is a degree-theoretic operator that preserves single-
valuedness. We will look at the interaction with the usual well-studied
operations on Weihrauch degrees. Besides those introduced in Section 2, we
consider $\sqcup$ and $\sqcap$, the join and meet in the Weihrauch lattice,
and the finite parallelization ∗ (which essentially is closure under
$\times$). See [10, Section 3] for definitions. The diamond operator ⋄ was
introduced in [34], and corresponds to the possibility of using the oracle an
arbitrary (but finite) number of times (essentially closure under
compositional product).

It is imminent from the definition that
$\mathrm{Det}(f)\sqcup\mathrm{Det}(g)\equiv_{\mathrm{W}}\mathrm{Det}(f\sqcup
g)$.

Moreover $\mathrm{Det}(f\sqcap g)\leq_{\mathrm{W}}\mathrm{Det}(f)$ and
$\mathrm{Det}(f\sqcap g)\leq_{\mathrm{W}}\mathrm{Det}(g)$ by monotonicity,
hence $\mathrm{Det}(f\sqcap
g)\leq_{\mathrm{W}}\mathrm{Det}(f)\sqcap\mathrm{Det}(g)$, as $\sqcap$ is the
meet on Weihrauch degrees ([5, Prop. 3.11]). To see that the inequality can be
strict, let $p,q\in{2^{\mathbb{N}}}$ be a minimal pair of Turing degrees
(which we identify with the constant functions returning these values). Then
$\mathrm{Det}(p\sqcap
q)\equiv_{\mathrm{W}}\operatorname{id}_{\mathbb{N}^{\mathbb{N}}}<_{\mathrm{W}}\mathrm{Det}(p)\sqcap\mathrm{Det}(q)\equiv_{\mathrm{W}}p\sqcap
q$.

Our principle $\mathsf{DS}$ (to be defined) already witnesses that the
deterministic part does not distribute over $\times$ and $*$, and does not
commute with ∗, ⋄ and $\widehat{\phantom{f}}$: we will prove that
$\mathrm{Det}(\mathsf{DS})\equiv_{\mathrm{W}}\mathsf{lim}$ (4.16), while
$\mathsf{LPO}^{\prime}\leq_{\mathrm{W}}\mathsf{DS}\times\mathsf{DS}$ (4.18).
Here we also give another example with a more computability-theoretic flavour:

######  Example 3.8.

There is a Weihrauch degree $f$ such that:

$\mathrm{Det}(f)\equiv_{\mathrm{W}}\operatorname{id}<_{\mathrm{W}}f<_{\mathrm{W}}f\times
f\equiv_{\mathrm{W}}f^{\diamond}\equiv_{\mathrm{W}}\widehat{f}\equiv_{\mathrm{W}}\mathrm{Det}(f\times
f).$

Indeed, consider the degrees of points in the spaces $\mathbb{R}_{<}$,
$\mathbb{R}_{>}$ and $\mathbb{R}$ (see [27] for details). Let $x\in\mathbb{R}$
be neither left-c.e. nor right-c.e.; i.e. it lacks computable names in both
$\mathbb{R}_{<}$ and $\mathbb{R}_{>}$. Then $x\in\mathbb{R}_{<}$ and
$x\in\mathbb{R}_{>}$ have quasi-minimal degrees, that is do not compute any
non-computable elements of Cantor space. We define
$f\colon\mathbf{2}\to\mathbb{R}_{<}+\mathbb{R}_{>}$ by
$f(0)=x\in\mathbb{R}_{<}$ and $f(1)=x\in\mathbb{R}_{>}$. The quasi-minimality
implies that $\mathrm{Det}(f)\equiv_{\mathrm{W}}\operatorname{id}$. However,
$f\times f$ is equivalent to the constant function returning $x\in\mathbb{R}$,
which is also equivalent to the constant function returning the decimal
expansion of $x$. Thus, $f\times f\equiv_{\mathrm{W}}\mathrm{Det}(f\times f)$.
Any of $f^{*}$, $f*f$, $f^{\diamond}$ and $\widehat{f}$ clearly share the same
degree.

######  Theorem 3.9.

For every represented space $\mathbf{X}$ and every problems $f,g$,

$\mathrm{Det}_{\mathbf{X}}(f*g)\leq_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(f)*g.$

###### 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.

$h\leq_{\mathrm{sW}}f\circ\Phi_{e}\circ g.$

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\leq_{\mathrm{sW}}f\circ\Phi_{e}\circ g$, and
the fact that $h$ is single-valued implies that so is $\phi$. In particular,
$\phi\leq_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(f)$ (as
$\phi\leq_{\mathrm{W}}f$ trivially). Since $h\leq_{\mathrm{W}}\phi*g$ we have
that $h\leq_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(f)*g$. ∎

Notice that this implies the choice elimination theorem [10, Thm. 7.25], as
$\mathrm{Det}(\mathsf{C}_{2^{\mathbb{N}}})\equiv_{\mathrm{W}}\operatorname{id}{}$
([5, Cor. 8.8]).

######  Corollary 3.10.

If $g$ is single-valued then
$\mathrm{Det}_{\mathbf{X}}(f*g)\equiv_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(f)*g$.

###### Proof.

This follows from 3.9, as
$\mathrm{Det}_{\mathbf{X}}(f)*\mathrm{Det}_{\mathbf{X}}(g)\leq_{\mathrm{W}}\mathrm{Det}_{\mathbf{X}}(f*g)$
always hold and $\mathrm{Det}_{\mathbf{X}}(g)\equiv_{\mathrm{W}}g$ as $g$ is
single-valued. ∎

######  Corollary 3.11.

For every cylinder $f$ and every $k\in\mathbb{N}$

$\mathrm{Det}(f)^{(k)}\equiv_{\mathrm{W}}\mathrm{Det}(f^{(k)}).$

###### Proof.

The left-to-right reduction is straightforward as

$\mathrm{Det}(f)^{(k)}\leq_{\mathrm{W}}\mathrm{Det}(f)*\mathsf{lim}^{[k]}\leq_{\mathrm{W}}f*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}f^{(k)},$

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)}\leq_{\mathrm{W}}\mathrm{Det}(f^{(k)})$.

The right-to-left reduction follows from 3.9 as

$\mathrm{Det}(f^{(k)})\equiv_{\mathrm{W}}\mathrm{Det}(f*\mathsf{lim}^{[k]})\leq_{\mathrm{W}}\mathrm{Det}(f)*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}
\mathrm{Det}(f)^{(k)},$

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

The previous corollary can be generalized in a straightforward way to any
represented space $\mathbf{X}$ s.t. $\mathrm{Det}_{\mathbf{X}}(f)$ is a
cylinder. Notice that it is false (in general) if $f$ is not a cylinder: take
$f=\mathsf{C}^{\vphantom{g}\mathsf{}}_{{2}}$ and $k=1$. Since
$\mathsf{C}_{2}^{\prime}\equiv_{\mathrm{W}}\mathsf{RT}^{{1}}_{{2}}$ (see e.g.
[13, Fact 2.3 and Prop. 3.4]) we have
$\mathrm{Det}(\mathsf{C}_{2}^{\prime})\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{2}}$,
hence in particular
$\mathsf{lim}\not\leq_{\mathrm{W}}\mathrm{Det}(\mathsf{C}_{2}^{\prime})$. On
the other hand
$\mathsf{lim}\leq_{\mathrm{W}}\mathrm{Det}(\mathsf{C}^{\vphantom{g}\mathsf{}}_{{2}})^{\prime}$
(as $\mathrm{Det}(\mathsf{C}^{\vphantom{g}\mathsf{}}_{{2}})$ is a cylinder).

######  Definition 3.12.

Given some
$f:\subseteq{\mathbb{N}^{\mathbb{N}}}\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
let
$?f:\subseteq{\mathbb{N}^{\mathbb{N}}}\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
be defined by $0^{\omega}\in?f(0^{\omega})$ and $0^{n}1p\in?f(0^{n}1q)$ iff
$p\in f(q)$.

It is easy to see that $?$ defines an operation on Weihrauch degrees, and
represents the idea of being able to maybe ask a question to $f$ – but never
having to decide to forgo this (which would be the case for $1\sqcup f$). Many
well-studied principles are equivalent to their maybe-variants, this in
particular holds for all pointed fractals. We introduce the operation here to
be able to express how the deterministic part interacts with the notion of
completion $\overline{(\cdot)}$ introduced by Brattka and Gherardi [6, 7].

######  Proposition 3.13.

$\mathrm{Det}(\overline{f})\equiv_{\mathrm{W}}\mathrm{Det}(?f)\equiv_{\mathrm{W}}?\mathrm{Det}(f)$.

###### Proof.

To show that $\mathrm{Det}(\overline{f})\leq_{\mathrm{W}}\mathrm{Det}(?f)$,
wlog assume that
$f:\subseteq{\mathbb{N}^{\mathbb{N}}}\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
and consider a function
$g:\subseteq{\mathbb{N}^{\mathbb{N}}}\to{\mathbb{N}^{\mathbb{N}}}$ with
$g\leq_{\mathrm{W}}\overline{f}$ witnessed by $\Phi,\Psi$. Now if for some
prefix $w$ the computation of $\Psi(w,\cdot)$ outputs two different things
depending on the second part of the input, then in order for $g$ to be a
function, we have the guarantee that all extensions of $w$ in the domain of
$g$ will be mapped to inputs in the domain of $f$, i.e. we are actually
calling $f$ rather than making use of $\overline{f}$. On the other hand, if
$\Psi(w,\cdot)$ would output the same thing regardless of the second argument,
we can postpone actually calling $f$ (which $?f$ lets us do) and go with that
output for the time being. This reasoning establishes that
$g\leq_{\mathrm{W}}?f$.

To see that $\mathrm{Det}(?f)\leq_{\mathrm{W}}?\mathrm{Det}(f)$, we just
inspect the technical definition of $\mathrm{Det}(\cdot)$.

Finally, for $?\mathrm{Det}(f)\leq_{\mathrm{W}}\mathrm{Det}(\overline{f})$ we
observe that $?\mathrm{Det}(f)$ is single-valued with codomain
${\mathbb{N}^{\mathbb{N}}}$, thus it suffices to show
$?\mathrm{Det}(f)\leq_{\mathrm{W}}\overline{f}$. But already
$?f\leq_{\mathrm{W}}\overline{f}$ holds: $\overline{f}$ accepts an input that
is completely void of information. We provide this as long as our $?f$
instance does not want to use $f$; if it ever does, we have the relevant
$f$-instance which we can then feed into $\overline{f}$. Note that we do not
get a strong reduction here, in general. ∎

###  3.4. Previous appearances in the literature

While the deterministic part as such has not been introduced before, and in
particular the observation that it is always well-defined is new, there are
several results in the literature on Weihrauch degrees that implicitly use it.
Already in the first paper introducing the modern definition of Weihrauch
reducibility [19], it was shown that
$\mathrm{Det}(\mathsf{C}_{2^{\mathbb{N}}})\equiv_{\mathrm{W}}\operatorname{id}$.
It was observed in [29] that the argument actually even establishes that
$\mathrm{Det}_{\mathbf{X}}(\mathsf{C}_{2^{\mathbb{N}}})\equiv_{\mathrm{W}}\operatorname{id}$
for any computably admissible space $\mathbf{X}$.

In [26] the principle $\mathsf{wList}_{{2^{\mathbb{N}}},\leq\omega}$ which
produces an enumeration of the elements of a countable closed subset of Cantor
space was introduced, and [26, Prop. 6.14] states that
$\mathrm{Det}(\mathsf{wList}_{{2^{\mathbb{N}}},\leq\omega})\equiv_{\mathrm{W}}\mathsf{lim}$.
The authors also proved the following result, which will be useful in 5.18:

######  Theorem 3.14 ([26, Thm. 8.5]).

$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}\equiv_{\mathrm{W}}\mathrm{Det}(\mathsf{C}_{\mathbb{N}^{\mathbb{N}}})\equiv_{\mathrm{W}}\mathrm{Det}(\widehat{\mathsf{TC}_{\mathbb{N}^{\mathbb{N}}}})$.

This, in particular, shows that $\mathrm{Det}(\cdot)$ is not useful to
separate principles that are between $\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$
and $\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$.

In the context of probabilistic computation [8, 11], the fact that the upper
cones of non-trivial enumeration degrees are measure zero is equivalent to the
statement that if
$f:\subseteq{\mathbb{N}^{\mathbb{N}}}\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
has the property that $f(p)$ has positive measure for every
$p\in\operatorname{dom}(f)$ and $\mathbf{X}$ is an effectively countably based
space, then there is some $g$ with
$\mathrm{Det}_{\mathbf{X}}(f)\leq_{\mathrm{W}}{}^{1}{g}$.

##  4\. Finding descending sequences

Let us formally define the problem of finding descending sequences in an ill-
founded linear order as a multi-valued function.

######  Definition 4.1.

Let
$\mathsf{DS}:\subseteq\mathbf{LO}\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
be the multi-valued function defined as

$\mathsf{DS}(L):=\\{x\in{\mathbb{N}^{\mathbb{N}}}:(\forall
i)(x(i+1)<_{L}x(i))\\},$

with $\operatorname{dom}(\mathsf{DS}):=\mathrm{LO}\backslash\mathrm{WO}$.

###  4.1. The uniform strength of $\mathsf{DS}$

We can immediately notice the following:

######  Proposition 4.2.

$\mathsf{DS}\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ but
$\mathsf{DS}\not\leq_{\mathrm{W}}\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$.

###### Proof.

To show that
$\mathsf{DS}\leq_{\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

$\\{\sigma\in{\mathbb{N}^{<\mathbb{N}}}:(\forall
i<|\sigma|-1)(\sigma(i+1)<_{L}\sigma(i))\\}.$

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

In particular, this shows that $\mathsf{DS}$ is not an arithmetic problem
(i.e. $\mathsf{DS}\not\leq_{\mathrm{W}}\mathsf{lim}^{(n)}$, for any $n$).

######  Proposition 4.3.

$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}\equiv_{\mathrm{W}}\mathsf{lim}*\mathsf{DS}$.

###### Proof.

The reduction
$\mathsf{lim}*\mathsf{DS}\leq_{\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. [41, Lem.
V.1.3]). Moreover, given a infinite descending sequence
$(\sigma_{n})_{n\in\mathbb{N}}$ in $\mathrm{KB}(T)$, the sequence
$(\sigma_{n}\raisebox{3.87495pt}{$\smallfrown$}0^{\omega})_{n\in\mathbb{N}}$
converges to some $x\in[T]$, and therefore the claim follows. ∎

We can generalize the problem $\mathsf{DS}$ to the context of quasi-orders. It
is easy to see that the problem of finding descending sequences in a quasi-
order is Weihrauch equivalent to $\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$.
Indeed, on the one hand, being a descending sequence in a quasi-order $P$ is a
$\Pi^{0,P}_{1}$ property. On the other hand, every tree, ordered by the prefix
relation, is a partial order where the descending sequences provide
arbitrarily long prefixes of a path.

When working with non-well quasi-orders, it is more natural to ask for bad
sequences instead.

######  Definition 4.4.

We define the multi-valued function
$\mathsf{BS}:\subseteq\mathbf{QO}\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
as

$\mathsf{BS}(P):=\\{x\in{\mathbb{N}^{\mathbb{N}}}:(\forall i)(\forall
j>i)(x(i)\not\preceq_{P}x(j))\\},$

where $\operatorname{dom}(\mathsf{BS})$ is the set of quasi-orders that are
not well-quasi-orders.

It follows from the definition that every ill-founded linear order is a non-
well quasi-order and that every bad sequence through an ill-founded linear
order is indeed a descending sequence.

By expanding a bit on a classical argument we can prove that the two problems
are uniformly equivalent.

######  Proposition 4.5.

$\mathsf{DS}\equiv_{\mathrm{W}}\mathsf{BS}$.

###### Proof.

The left-to-right reduction is trivial, so we only need to show that
$\mathsf{BS}\leq_{\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

$\\{p\in R:(\forall q<p)(p\not\equiv_{R}q)\\}.$

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)$. ∎

We will show that $\mathsf{DS}$ (and hence $\mathsf{BS}$) is quite weak in
terms of uniform computational strength (a fortiori
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}\not\leq_{\mathrm{W}}\mathsf{DS}$). Let
us first underline the following useful proposition.

######  Proposition 4.6.

$\mathsf{DS}$ is a cylinder.

###### Proof.

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

$\displaystyle M:=\\{(p[n],n):n\in L\\},$
$\displaystyle(p[n],n)\leq_{M}(p[m],m):\iff n\leq_{L}m.$

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}]$. ∎

######  Definition 4.7.

Let
${\boldsymbol{\Gamma}}\mathsf{-Bound}:\subseteq\boldsymbol{\Gamma}(\mathbb{N})\rightrightarrows\mathbb{N}$
be the first-order problem that takes as input a finite $\boldsymbol{\Gamma}$
subset of the natural numbers and returns a bound for it. Formally

$\displaystyle\operatorname{dom}({\boldsymbol{\Gamma}}\mathsf{-Bound}):=\\{A\in\boldsymbol{\Gamma}(\mathbb{N}):(\forall^{\infty}n)(A(n)=0)\\},$
$\displaystyle{\boldsymbol{\Gamma}}\mathsf{-Bound}(A):=\\{n\in\mathbb{N}:(\forall
m\geq n)(A(m)=0)\\}.$

The principle ${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$ has been studied in
[1] under the name
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{cof}}_{{\mathbb{N}}}$:
notice indeed that the reduction
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{cof}}_{{\mathbb{N}}}\leq_{\mathrm{sW}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$
is trivial. On the other hand, given a finite $\boldsymbol{\Pi}^{1}_{1}$
subset $X$ of $\mathbb{N}$ we can consider the set

$Y:=\\{n\in\mathbb{N}:(\exists m\geq n)(m\in X)\\}.$

Clearly $Y$ is a $\boldsymbol{\Pi}^{1}_{1}$ initial segment of $\mathbb{N}$,
and therefore ${\mathbb{N}}\backslash{Y}$ is a valid input for
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{cof}}_{{\mathbb{N}}}$.
Moreover a name for $Y$ can be uniformly computed from a name of $X$ and
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{cof}}_{{\mathbb{N}}}({\mathbb{N}}\backslash{Y})\subset{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}(X)$.
This shows that
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\leq_{\mathrm{sW}}{\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{cof}}_{{\mathbb{N}}}$
and hence the two problems are (strongly) Weihrauch equivalent.

In other words, given an instance $X$ of
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$ we can, without loss of
generality, assume that $X$ is an initial segment of $\mathbb{N}$.

######  Proposition 4.8.

${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}<_{\mathrm{W}}\mathsf{DS}$.

###### 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. ∎

We now show that
${}^{1}{\mathsf{DS}}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$.
Let us first prove the following lemma, which will also be useful to prove
4.16.

######  Lemma 4.9.

Suppose that $f$ is a problem which is Weihrauch reducible to $\mathsf{DS}$
via the computable maps $\Phi,\Psi$. For every $f$-instance $X$, let
$\leq^{X}$ be the linear order defined by $\Phi^{X}$. We can uniformly compute
a sequence $(F_{s})_{s\in\mathbb{N}}$ of finite $<^{X}$-descending sequences
s.t. (1) for every $s$, $\Psi^{X\oplus F_{s}}$ outputs some $j\in\mathbb{N}$;
(2) for cofinitely many $s$, $F_{s}$ extends to an infinite $<^{X}$-descending
sequence.

###### Proof.

Fix an $f$-instance $X$ and run $\Phi^{X}$ for $s$ steps. This produces a
finite linear order $\leq^{X}_{s}$. Define

$\displaystyle D_{s}:=\\{F\subseteq\,\leq^{X}_{s}:{}$ $\displaystyle{}F\text{
is a}<^{X}_{s}\text{-descending sequence and }|F|\geq 1\text{ and }$
$\displaystyle\Psi^{X\oplus F}\text{ outputs some }j\in\mathbb{N}\text{ in
}s\text{ steps}\\}.$

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

$\textstyle(\forall F\in
D_{s})\left(\min_{<^{X}}(F)\leq^{X}_{s}\min_{<^{X}}(F_{s})\right).$

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\geq 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}$. ∎

In particular, if $f$ has codomain $\mathbb{N}$ the above lemma implies that,
for cofinitely many $s$, $\Psi^{X\oplus F_{s}}$ outputs some $f$-solution for
$X$.

######  Theorem 4.10.

${}^{1}{\mathsf{DS}}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$.

###### Proof.

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

To prove the converse reduction, suppose that $f\leq_{\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 4.9. Let $\leq^{X}$ denote the linear
order represented by $\Phi^{X}$. Define the following $\Pi^{1,X}_{1}$ set:

$A:=\\{s\in\mathbb{N}:F_{s}\notin\mathrm{Ext}\\},$

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$. ∎

######  Corollary 4.11.

$\mathsf{DS}<_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$.

###### Proof.

If $\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}\leq_{\mathrm{W}}\mathsf{DS}$ then, by
2.4,
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\mathbb{N}}}\leq_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$.
However, this would imply that
$\widehat{{\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{\mathbb{N}}}}\leq_{\mathrm{W}}\widehat{{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}}$,
contradicting [1, Cor. 3.23]. ∎

######  Definition 4.12.

Let $f:\subseteq\mathbf{X}\rightrightarrows\mathbb{N}$ be a multi-valued
function. We say that $f$ is upwards-closed if whenever $n\in f(x)$, then
$m\in f(x)$ for all $m>n$.

It is straightforward from the definition that
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$ is upwards-closed.

######  Lemma 4.13.

If $f$ is upwards-closed then
$\mathrm{Det}_{\mathbb{N}}(f)\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$.

###### Proof.

Let $g$ be a single-valued function with codomain $\mathbb{N}$ and suppose
that $g\leq_{\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)$. ∎

######  Proposition 4.14.

$\mathrm{Det}_{\mathbb{N}}({\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound})\equiv_{\mathrm{W}}\mathrm{Det}_{\mathbb{N}}(\mathsf{C}_{\mathbb{N}})\equiv_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$,
and therefore
$\mathrm{Det}_{\mathbb{N}}(\mathsf{DS})\equiv_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$.

###### Proof.

Let us first notice that
$\mathsf{C}_{\mathbb{N}}\equiv_{\mathrm{W}}\mathsf{UC}_{\mathbb{N}}$ ([4,
Prop. 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})\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$
follows from 4.13. To prove the converse reduction it is enough to show that
$\mathsf{UC}_{\mathbb{N}}\leq_{\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

$\displaystyle m(s):=\min\\{j\in\mathbb{N}:(\forall i<s)(n_{i}\neq j)\\},$
$\displaystyle A:=\\{s\in\mathbb{N}:(\exists t>s)(m(t)\neq m(s))\\}.$

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}}\leq_{\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

$g\leq_{\mathrm{W}}\mathsf{DS}\Rightarrow
g\leq_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\Rightarrow
g\leq_{\mathrm{W}}\mathrm{Det}_{\mathbb{N}}({\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound})\equiv_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}.\qed$

Notice that
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\not\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$:
indeed $\widehat{\mathsf{C}_{\mathbb{N}}}\equiv_{\mathrm{W}}\mathsf{lim}$,
while
$\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}<_{\mathrm{W}}\widehat{{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}}$
(see 5.21). This implies that
$\mathrm{Det}_{\mathbb{N}}({\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound})<_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$.
In this regard, we observe the following:

######  Proposition 4.15.

The Weihrauch degree of $\mathsf{C}_{\mathbb{N}}$ is the highest Weihrauch
degree containing both of the following:

  1. (1)

a representative which is single-valued and has codomain $\mathbb{N}$;

  2. (2)

a representative which is upwards-closed.

###### 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}}$ ([4, Prop. 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}\leq_{\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

$\\{n\in\mathbb{N}:(\forall m\geq n)(m\notin A)\\}$

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 4.13: indeed
suppose $f:\textbf{X}\to\mathbb{N}$ is Weihrauch equivalent to some $g$ which
is upwards-closed. By 4.13, we have
$\mathrm{Det}_{\mathbb{N}}(g)\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$. By
definition of $\mathrm{Det}(\cdot)$, we have
$f\leq_{\mathrm{W}}\mathrm{Det}_{\mathbb{N}}(g)$, hence
$f\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$. ∎

Let us now characterize the deterministic part of $\mathsf{DS}$.

######  Theorem 4.16.

$\mathrm{Det}(\mathsf{DS})\equiv_{\mathrm{W}}\mathsf{lim}$.

###### Proof.

Let us first prove that $\mathsf{lim}\leq_{\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 [10, Thm. 6.7]). By
relativizing the construction in [31, Lem. 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}\leq_{\mathrm{W}}\mathsf{DS}$.

To prove that $\mathrm{Det}(\mathsf{DS})\leq_{\mathrm{W}}\mathsf{lim}$,
suppose that $f:\subseteq\textbf{X}\to{\mathbb{N}^{\mathbb{N}}}$ is single-
valued and $f\leq_{\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}\leq_{\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 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 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)$. ∎

This result shows that, despite the fact that $\mathsf{DS}$ can have very
complicated solutions, it is rather weak from the uniform point of view. In
fact, its lower Weihrauch cone misses many arithmetic problems. In particular
we have:

######  Corollary 4.17.

$\mathsf{DS}~{}|_{\mathrm{W}~{}}\mathsf{LPO}^{\prime}$.

###### Proof.

Since $\mathsf{LPO}$ is single-valued, so is $\mathsf{LPO}^{\prime}$. Since
$\mathsf{LPO}^{\prime}\not\leq_{\mathrm{W}}\mathsf{lim}$ (see [9, Cor. 12.3
and Thm. 12.7]), it follows from 4.16 that
$\mathsf{LPO}^{\prime}\not\leq_{\mathrm{W}}\mathsf{DS}$. On the other hand,
$\mathsf{DS}\not\leq_{\mathrm{W}}\mathsf{LPO}^{\prime}$, as
$\mathsf{LPO}^{\prime}$ always has computable solutions. ∎

Notice that 4.16 implies also that
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}\not\leq_{\mathrm{W}}\mathsf{C}_{2^{\mathbb{N}}}*\mathsf{DS}$.
Indeed, on the one hand
$\mathrm{Det}(\mathsf{C}_{\mathbb{N}^{\mathbb{N}}})\equiv_{\mathrm{W}}\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$
(3.14), while, on the other hand, by 3.9 if $f$ is single-valued and
$f\leq_{\mathrm{W}}\mathsf{C}_{2^{\mathbb{N}}}*\mathsf{DS}$ then
$f\leq_{\mathrm{W}}\mathsf{DS}$ (as
$\mathrm{Det}(\mathsf{C}_{2^{\mathbb{N}}})\equiv_{\mathrm{W}}\operatorname{id}{}$)
and hence
$\mathrm{Det}(\mathsf{C}_{2^{\mathbb{N}}}*\mathsf{DS})\equiv_{\mathrm{W}}\mathrm{Det}(\mathsf{DS})\equiv_{\mathrm{W}}\mathsf{lim}$.

Using 4.17 we can prove that $\mathsf{DS}$ is not closed under (parallel)
product:

######  Theorem 4.18.

$\mathsf{LPO}^{\prime}\leq_{\mathrm{W}}\mathsf{DS}\times\mathsf{lim}$ and
therefore $\mathsf{DS}$ is not closed under product.

###### 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

$g(s)=\begin{cases}i+1&\text{if }i\leq s\land p_{s}(i)\neq 0\land(\forall
j<i)(p_{s}(j)=0),\\\ 0&\text{otherwise.}\end{cases}$

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;

  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\geq 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}^{\prime}((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\geq 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}^{\prime}\leq_{\mathrm{W}}\mathsf{DS}\times\mathsf{lim}$.

The fact that $\mathsf{DS}$ is not closed under product follows from the fact
that $\mathsf{lim}\leq_{\mathrm{W}}\mathsf{DS}$ (4.16) and 4.17. ∎

###  4.2. Combinatorial principles on linear orders

We introduce the following notation to phrase many combinatorial principles
from reverse mathematics as multi-valued functions.

######  Definition 4.19.

Let
$\mathsf{FindC}^{{X}}_{{Y}}:\subseteq\mathbf{LO}\rightrightarrows\mathbf{LO}$
be the partial multi-valued function defined as

$\mathsf{FindC}^{{X}}_{{Y}}(L):=\\{M\in\mathrm{LO}:M\subset L\text{ and
}\operatorname{ordtype}(M)\in Y\\},$

with domain being the set of $L\in\mathrm{LO}$ s.t.
$\operatorname{ordtype}(L)\in X$ and there is some $M\subset L$ s.t.
$\operatorname{ordtype}(M)\in Y$.

Similarly we define
$\mathsf{FindS}^{X}:\subseteq\mathbf{LO}\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
to be the partial multi-valued function that takes as input a countable linear
order $L$ s.t. $\operatorname{ordtype}(L)\in X$ and produces a string $\langle
b,x_{0},x_{1},\ldots\rangle$ s.t. $b\in\\{0,1\\}$ and, for all $i$, if $b=0$
then $x_{i}<_{L}x_{i+1}$ while if $b=1$ then $x_{i+1}<_{L}x_{i}$.

If $X$ or $Y$ is not specified, we assume that it contains every countable
order type.

There is an extensive literature that studies the “ascending/descending
sequence principle” ($\mathrm{ADS}$) and the “chain/antichain principle”
($\mathrm{CAC}$) (see e.g. [24, 25]). These principles and, several of their
variations, have been studied from the point of view of Weihrauch reducibility
in [2].

Notice that, in particular, the problem $\mathsf{ADS}$ (given a linear order,
produce an infinite ascending sequence or infinite descending sequence)
corresponds to $\mathsf{FindS}$. Similarly the problem
$\mathsf{General}\text{-}\mathsf{SADS}$ (given a stable — i.e. of order type
$\omega+n,n+\omega^{*}$ or $\omega+\omega^{*}$ — linear order, produce an
infinite ascending or descending sequence), corresponds to
$\mathsf{FindS}^{X}$, where $X=\\{\omega+n,n+\omega^{*},\omega+\omega^{*}\\}$.

######  Proposition 4.20.

$\mathsf{LPO}^{\prime}\leq_{\mathrm{W}}\mathsf{FindS}^{\\{\omega,n+\omega^{*}\\}}$.

###### 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 4.18)

$g(s)=\begin{cases}i+1&\text{if }i\leq s\land p_{s}(i)\neq 0\land(\forall
j<i)(p_{s}(j)=0),\\\ 0&\text{otherwise.}\end{cases}$

Let us define a linear order $\leq_{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$;

  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\geq 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, $\leq_{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 $\leq_{L}$ has order type $\omega$.

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

######  Corollary 4.21.

$\mathsf{FindS}^{\\{\omega,n+\omega^{*}\\}}~{}|_{\mathrm{W}~{}}\mathsf{DS}$,
and hence
$\mathsf{General}\text{-}\mathsf{SADS}~{}|_{\mathrm{W}~{}}\mathsf{DS}$.

###### Proof.

The fact that
$\mathsf{FindS}^{\\{\omega,n+\omega^{*}\\}}\not\leq_{\mathrm{W}}\mathsf{DS}$
follows from 4.20 and the fact that
$\mathsf{LPO}^{\prime}\not\leq_{\mathrm{W}}\mathsf{DS}$ (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\leq_{\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\leq_{\mathrm{W}}\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$ (4.2).
∎

In particular this implies that $\mathsf{ADS}$, as well as the stable
chain/antichain principle $\mathsf{SCAC}$, and the weakly stable
chain/antichain principle $\mathsf{WSCAC}$ are Weihrauch incomparable with
$\mathsf{DS}$ (as they are all arithmetic problems, and
$\mathsf{General}\text{-}\mathsf{SADS}$ is reducible to all of them, see [2]).

######  Proposition 4.22.

$\mathsf{FindC}_{{\\{\omega,n+\omega^{*}\\}}}\leq_{\mathrm{W}}\mathsf{DS}$.

###### Proof.

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

$(a,p)\leq_{Q}(b,q):\iff a<b\lor(a=b=0\land p\leq_{L}q)\lor(a=b=1\land
q\leq_{L}p).$

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 $3$ 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$;

  3. (3)

if there is a $k$ s.t. for all $i<k$ we have $\pi_{0}q_{i}=1$ and for all
$j\geq k$ we have $\pi_{0}q_{j}=0$ then, by point $1$, $(x_{j})_{j\geq k}$ is
an $\omega^{*}$-sequence in $L$, hence $(x_{i})_{i\in\mathbb{N}}$ is of type
$n+\omega^{*}$, with $n\leq k$.

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

###  4.3. Relations with Ramsey theorems

We now explore the relations between $\mathsf{DS}$ and Ramsey’s theorem for
$n$-tuples and $k$ colors. Let us recall the basic definitions.

######  Definition 4.23.

For every $A\subset\mathbb{N}$, let $[A]^{n}:=\\{B\subset A:|B|=n\\}$ be the
set of subsets of $A$ with cardinality $n$. A map $c\colon[\mathbb{N}]^{n}\to
k$ is called a $k$-coloring of $[\mathbb{N}]^{n}$, where $k\geq 2$. An
infinite set $H$ s.t. $c([H]^{n})=\\{i\\}$ for some $i<k$ is called a
homogeneous solution for $c$, or simply homogeneous.

The set $\mathcal{C}_{n,k}$ of $k$-colorings of $[\mathbb{N}]^{n}$ can be seen
as a represented space, where a name for a coloring $c$ is the string
$p\in{\mathbb{N}^{\mathbb{N}}}$ s.t. for each
$(i_{0},\ldots,i_{n-1})\in[\mathbb{N}]^{n}$, $p(\langle
i_{0},\ldots,i_{n-1}\rangle)=c(i_{0},\ldots,i_{n-1})$.

We define
$\mathsf{RT}^{{n}}_{{k}}:\mathcal{C}_{n,k}\rightrightarrows{2^{\mathbb{N}}}$
as the total multi-valued function that maps a coloring $c$ to the set of all
homogeneous sets for $c$. Similarly we define
$\mathsf{RT}^{{n}}_{{\mathbb{N}}}:\bigcup_{k\geq
1}\mathcal{C}_{n,k}\rightrightarrows{2^{\mathbb{N}}}$ as
$\mathsf{RT}^{{n}}_{{\mathbb{N}}}(c):=\mathsf{RT}^{{n}}_{{k}}(c)$, where $k-1$
is the maximum of the range of $c$. Note that the input for
$\mathsf{RT}^{{n}}_{{\mathbb{N}}}$ does not include information on which color
appears in the range of the coloring.

We also define $\mathsf{cRT}^{{n}}_{{k}}:\mathcal{C}_{n,k}\rightrightarrows k$
as the multi-valued function that produces only the color of a homogeneous
solution. We define $\mathsf{cRT}^{{n}}_{{\mathbb{N}}}$ analogously.

Notice that
$\mathsf{cRT}^{{n}}_{{k}}\equiv_{\mathrm{W}}\mathsf{RT}^{{n}}_{{k}}$ iff
$n=1$. Indeed the output of $\mathsf{cRT}^{{n}}_{{k}}$ is always computable,
while for $n>1$ there are computable $k$-colorings with no computable
homogeneous solutions. Similarly
$\mathsf{cRT}^{{n}}_{{\mathbb{N}}}\equiv_{\mathrm{W}}\mathsf{RT}^{{n}}_{{\mathbb{N}}}$
iff $n=1$. Moreover the equivalence cannot be lifted to a strong Weihrauch
equivalence. Indeed $\mathsf{RT}^{{1}}_{{k}}$ and $\mathsf{cRT}^{{1}}_{{k}}$
are incomparable from the point of view of strong Weihrauch reducibility. The
uniform computational content of Ramsey’s theorems is well-studied (see e.g.
[13, 14, 16, 35]).

In comparing $\mathsf{RT}^{{n}}_{{k}}$ with $\mathsf{DS}$, we immediately
notice that $\mathsf{RT}^{{2}}_{{2}}\not\leq_{\mathrm{W}}\mathsf{DS}$. This
follows from the fact that
$\mathsf{ADS}\leq_{\mathrm{W}}\mathsf{RT}^{{2}}_{{2}}$ (see e.g. [24]), while
$\mathsf{ADS}\not\leq_{\mathrm{W}}\mathsf{DS}$ (see the remarks after 4.21).
Hence $\mathsf{RT}^{{n}}_{{k}}\not\leq_{\mathrm{W}}\mathsf{DS}$ for all
$n,k\geq 2$.

######  Proposition 4.24.

$\mathsf{RT}^{{1}}_{{\mathbb{N}}}<_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$,
and hence $\mathsf{RT}^{{1}}_{{\mathbb{N}}}<_{\mathrm{W}}\mathsf{DS}$.

###### Proof.

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

$X:=\\{n\in\mathbb{N}:(\forall^{\infty}j)(c(n)\neq c(j))\\}.$

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\leq_{\mathrm{W}}\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$
(as
$\widehat{{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}}\not\leq_{\mathrm{W}}\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$,
see [1, 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}}^{\prime}$,
see [13, Prop. 7.2 and Cor. 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}$ (4.8). ∎

We now show that $\mathsf{RT}^{{1}}_{{\mathbb{N}}}$ is the strongest problem
among those that are reducible to $\mathsf{DS}$ and whose instances always
have finitely many solutions.

######  Definition 4.25.

Let $f:\subseteq\mathbf{X}\rightrightarrows\mathbb{N}$. We say that $f$ is
pointwise finite if, for each $x\in\operatorname{dom}(f)$, $|f(x)|$ is finite.

Notice that $\mathsf{cRT}^{{1}}_{{k}}$ and $\mathsf{cRT}^{{1}}_{{\mathbb{N}}}$
are pointwise finite, as for each $k$-coloring $c$ we have
$|\mathsf{cRT}^{{1}}_{{k}}(c)|=|\mathsf{cRT}^{{1}}_{{\mathbb{N}}}(c)|\leq k$.

######  Lemma 4.26.

Let $g$ be upwards-closed and let $f$ be pointwise finite. If
$f\leq_{\mathrm{W}}g$ then
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{\mathbb{N}}}$.

###### Proof.

Suppose that $f\leq_{\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. ∎

######  Theorem 4.27.

If $f$ is pointwise finite then $f\leq_{\mathrm{W}}\mathsf{DS}$ iff
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{\mathbb{N}}}$.

###### Proof.

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

By 4.26 we also have the following:

######  Proposition 4.28.

The Weihrauch degree of $\mathsf{RT}^{{1}}_{{\mathbb{N}}}$ is the highest
Weihrauch degree such that:

  1. (1)

it contains a representative which is pointwise finite;

  2. (2)

it is Weihrauch reducible to some problem which is upwards-closed.

###### 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}$
(4.24) and ${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$ is upwards-closed.
Finally, the maximality follows from 4.26. ∎

######  Lemma 4.29.

If $f$ is upwards-closed and
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{\mathbb{N}}}$ then
$f\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$.

###### 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\leq_{\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

$\displaystyle A:=\\{\langle n,c_{0},\ldots,c_{k},s\rangle:{}$
$\displaystyle{}(\forall i)(\exists j\leq k)(c(i)=c_{j})\text{ and }$
$\displaystyle(\forall j\leq k)(\exists i<s)(c(i)=c_{j})\text{ and }$
$\displaystyle(\forall j\leq
k)(\Psi(p,c_{j})\downarrow\rightarrow\Psi(p,c_{j})\leq n)\\}.$

Notice that, if $\langle n,c_{0},\ldots,c_{k},s\rangle\in A$ then, by the
first two conditions, there is a $j\leq 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\leq_{\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\geq\Psi(p,c_{j})$ and therefore $n\in f(x)$. ∎

Notice that the previous lemma provides an alternative proof for the fact that
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\not\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{\mathbb{N}}}$,
as
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\not\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}}$.

If we consider only bounded pointwise finite functions, we can improve 4.27 by
replacing $\mathsf{RT}^{{1}}_{{\mathbb{N}}}$ with $\mathsf{RT}^{{1}}_{{k}}$.

######  Lemma 4.30.

If $f$ has codomain $k$, then
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{\mathbb{N}}}$ iff
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{k}}$.

###### Proof.

The right-to-left implication is trivial, so let us prove the left-to-right
one. Since
$\mathsf{RT}^{{1}}_{{\mathbb{N}}}\leq_{\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\leq_{\mathrm{W}}g$, then
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{k}}$. The proof closely follows the one
of 4.26. Suppose that $f\leq_{\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. ∎

######  Theorem 4.31.

If $f$ has codomain $k$, then $f\leq_{\mathrm{W}}\mathsf{DS}$ iff
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{k}}$.

###### Proof.

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

To conclude the section we notice how we can improve the results if we
restrict our attention to single-valued functions. Define the problem
$\mathsf{lim}_{k}:\subseteq k^{\mathbb{N}}\to k$ as the limit in the discrete
space $k$.

######  Lemma 4.32.

If $f$ has codomain $k$ and is single-valued, then
$f\leq_{\mathrm{W}}\mathsf{lim}_{k}$ iff
$f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{k}}$.

###### Proof.

The left-to-right implication is trivial as
$\mathsf{lim}_{k}\leq_{\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\leq_{\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

$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}$

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)$.
∎

######  Theorem 4.33.

If $f$ has codomain $k$ and is single-valued, then
$f\leq_{\mathrm{W}}\mathsf{lim}_{k}$ iff $f\leq_{\mathrm{W}}\mathsf{DS}$.

###### Proof.

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

##  5\. Presentation of orders

In this section we study how the presentation of a linear/quasi order can
influence the uniform computational strength of the problems $\mathsf{DS}$ and
$\mathsf{BS}$.

######  Definition 5.1.

For every
$\boldsymbol{\Gamma}\in\\{\boldsymbol{\Sigma}^{0}_{k},\boldsymbol{\Pi}^{0}_{k},\boldsymbol{\Delta}^{0}_{k},\boldsymbol{\Sigma}^{1}_{1},\boldsymbol{\Pi}^{1}_{1},\boldsymbol{\Delta}^{1}_{1}\\}$
we define the problem
${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}:\subseteq\boldsymbol{\Gamma}(\mathbf{LO})\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
as ${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}(L):=\mathsf{DS}(L)$. Similarly we
define
${\boldsymbol{\Gamma}}\text{-}\mathsf{BS}:\subseteq\boldsymbol{\Gamma}(\mathbf{QO})\rightrightarrows{\mathbb{N}^{\mathbb{N}}}$
as ${\boldsymbol{\Gamma}}\text{-}\mathsf{BS}(P):=\mathsf{BS}(P)$.

Despite the fact that $\mathsf{DS}\equiv_{\mathrm{W}}\mathsf{BS}$ (4.5), it is
not the case that
${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}}\text{-}\mathsf{BS}$
in general. In particular, we will show that
${\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{BS}\not\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{DS}$
(5.14) and
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{BS}\not\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{DS}$
(5.24).

Furthermore, we strengthen 4.11 by showing that
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{DS}<_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$
(5.22). In other words, even if we are allowed to feed $\mathsf{DS}$ a code
for a $\boldsymbol{\Sigma}^{1}_{1}$ linear ordering, we still cannot compute
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$. On the other hand, we already showed
that if we are allowed to perform a relatively small amount of post-processing
(namely $\mathsf{lim}$) on the output of $\mathsf{DS}$, then we can compute
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ (4.3). In particular, the use of
$\mathsf{lim}$ absorbs any difference in uniform strength between
$\mathsf{DS}$ and ${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{DS}$ and
collapses the whole hierarchy (up to
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{DS}$) to
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$.

Many of our separations are derived by analyzing the first-order part of the
problems in question, or more generally by characterizing the problems
satisfying certain properties (such as single-valuedness or having restricted
codomain) which lie below the problems in question. On the contrary, we prove
5.22 using very different techniques due to Anglès d’Auriac and Kihara [1].

Before beginning our analysis, we record some preliminary observations. Note
that $\mathsf{DS}={\boldsymbol{\Delta}^{0}_{1}}\text{-}\mathsf{DS}$ and
$\mathsf{BS}={\boldsymbol{\Delta}^{0}_{1}}\text{-}\mathsf{BS}$. It is
straightforward to see that, for every $\boldsymbol{\Gamma}$,
${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}\leq_{\mathrm{W}}{\boldsymbol{\Gamma}}\text{-}\mathsf{BS}$.
Moreover, for every $\boldsymbol{\Gamma},\boldsymbol{\Gamma}^{\prime}$ s.t.
$\boldsymbol{\Gamma}(X)\subset\boldsymbol{\Gamma}^{\prime}(X)$ we have
${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}\leq_{\mathrm{W}}{\boldsymbol{\Gamma}^{\prime}}\text{-}\mathsf{DS}$
and
${\boldsymbol{\Gamma}}\text{-}\mathsf{BS}\leq_{\mathrm{W}}{\boldsymbol{\Gamma}^{\prime}}\text{-}\mathsf{BS}$.

Notice also that the set of bad sequences through a
$\boldsymbol{\Delta}^{1}_{1}$-quasi-order is $\boldsymbol{\Delta}^{1}_{1}$,
hence it is straightforward to see that
${\boldsymbol{\Delta}^{1}_{1}}\text{-}\mathsf{BS}\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{{\mathbb{N}^{\mathbb{N}}}}}\equiv_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$.
This shows also that
${\boldsymbol{\Gamma}}\text{-}\mathsf{BS}\leq_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$
for every arithmetic $\boldsymbol{\Gamma}$.

######  Proposition 5.2.

For every
$\boldsymbol{\Gamma}\in\\{\boldsymbol{\Sigma}^{0}_{k},\boldsymbol{\Pi}^{0}_{k},\boldsymbol{\Delta}^{0}_{k},\boldsymbol{\Sigma}^{1}_{1},\boldsymbol{\Pi}^{1}_{1},\boldsymbol{\Delta}^{1}_{1}\\}$
the problems ${\boldsymbol{\Gamma}}\text{-}\mathsf{DS}$ and
${\boldsymbol{\Gamma}}\text{-}\mathsf{BS}$ are cylinders.

###### Proof.

The proof is a straightforward generalization of the proof of 4.6. ∎

######  Theorem 5.3.

For every $k\in\mathbb{N}$ and every
$\boldsymbol{\Gamma}\in\\{\boldsymbol{\Sigma},\boldsymbol{\Pi},\boldsymbol{\Delta}\\}$

$\displaystyle{\boldsymbol{\Gamma}^{0}_{k+1}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}^{(k)},$
$\displaystyle{\boldsymbol{\Gamma}^{0}_{k+1}}\text{-}\mathsf{BS}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{BS}*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{BS}^{(k)}.$

###### Proof.

Fix $k$ and $\boldsymbol{\Gamma}$ as above. The reduction
${\boldsymbol{\Gamma}^{0}_{k+1}}\text{-}\mathsf{DS}\leq_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}*\mathsf{lim}^{[k]}$
follows from the fact that

$\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{CA}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{CA}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{CA},$

hence we can use $\mathsf{lim}^{[k]}$ to compute a
$\boldsymbol{\Gamma}^{0}_{1}$-name for the input linear order, and then apply
${\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}$ to get a descending
sequence.

Let us now prove the converse reduction. Since both $\mathsf{lim}^{[k]}$ and
${\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}$ are cylinders, by the
cylindrical decomposition there is an $e$ s.t.

${\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}\circ\Phi_{e}\circ\mathsf{lim}^{[k]}.$

Given any
$p\in\operatorname{dom}({\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}\circ\Phi_{e}\circ\mathsf{lim}^{[k]})$,
the string $q:=\Phi_{e}(\mathsf{lim}^{[k]}(p))$ is a
$\boldsymbol{\Gamma}^{0}_{1}$-name for a linear order $L_{p}$. Since $q$ is
$\Delta^{0,p}_{k+1}$, the condition $a\leq_{L_{p}}b$ is $\Gamma^{0,p}_{k+1}$
for every $a,b$. This shows that, given an input $p$ we can uniformly compute
a $\boldsymbol{\Gamma}^{0}_{k+1}$-name for the linear order $L_{p}$, and hence
use ${\boldsymbol{\Gamma}^{0}_{k+1}}\text{-}\mathsf{DS}$ to compute an
$<_{L_{p}}$-descending sequence.

The equivalence
${\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}^{(k)}$
follows from the fact that ${\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{DS}$
is a cylinder.

The same reasoning works, mutatis mutandis, to show that

${\boldsymbol{\Gamma}^{0}_{k+1}}\text{-}\mathsf{BS}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{BS}*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}{\boldsymbol{\Gamma}^{0}_{1}}\text{-}\mathsf{BS}^{(k)}.\qed$

Using this theorem, the relativized version of 4.5 can be proved explicitly as
follows:

######  Corollary 5.4.

For every $k\geq 1$,
${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{BS}.$

###### Proof.

Using 4.5 and 5.3 we immediately have

${\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{BS}\equiv_{\mathrm{W}}\mathsf{BS}*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}\mathsf{DS}*\mathsf{lim}^{[k]}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS},$

as $\mathsf{DS}={\boldsymbol{\Delta}^{0}_{1}}\text{-}\mathsf{DS}$ and
$\mathsf{BS}={\boldsymbol{\Delta}^{0}_{1}}\text{-}\mathsf{BS}$. ∎

This implies also that, for every $k$,
${\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{BS}\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}$
and
${\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{BS}\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}$.

###  5.1. $\Gamma$${}^{0}_{k}$-$\mathsf{DS}$ and
$\Gamma$${}^{0}_{k}$-$\mathsf{BS}$

We will now show that the hierarchy of $\boldsymbol{\Gamma}$-$\mathsf{DS}$
problems does not collapse at any finite level. First we study the hierarchy
of ${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$ problems by
characterizing their first-order parts (5.5). Then we prove the analogues of
4.31 and 4.33 for ${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$ (5.8).

For any sequence of problems
$f_{s}:\subseteq\textbf{X}_{s}\rightrightarrows\textbf{Y}_{s}$,
$s\in\mathbb{N}$, the _countable coproduct_ of the sequence is the problem
$\bigsqcup_{s\in\mathbb{N}}f_{s}:\subseteq\bigsqcup_{s}\textbf{X}_{i}\rightrightarrows\bigsqcup_{s}\textbf{Y}_{i}$
defined by $\left(\bigsqcup_{s\in\mathbb{N}}f_{s}\right)(s,x):=\\{s\\}\times
f_{s}(x)$. The problem $\bigsqcup_{s\in\mathbb{N}}f_{s}$ allows us access to
exactly one $f_{s}$ of our choice.

######  Theorem 5.5.

For every $k\geq 1$,

${}^{1}{{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}}\equiv_{\mathrm{W}}\left(\bigsqcup_{s\in\mathbb{N}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{s}}\right)*{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}.$

We split the proof into two lemmas.

######  Lemma 5.6.

For every $k\geq 1$, if $f:\subseteq\mathbf{X}\rightrightarrows\mathbb{N}$ and
$f\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$ then

$f\leq_{\mathrm{W}}\left(\bigsqcup_{s\in\mathbb{N}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{s}}\right)*{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}.$

###### Proof.

Fix Turing functionals $\Phi$ and $\Psi$ which witness that
$f\leq_{\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 $\leq^{x}$. Consider the $\Sigma^{0,x}_{k}$ set

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

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

$A:=\\{s\in\mathbb{N}:(\forall F\in D_{s})(F\notin\mathrm{Ext}_{x})\\},$

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 $\leq^{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}$:

$B:=\left\\{F\in D_{b}:(\forall G\in
D_{b})\left(\min_{<^{x}}(G)\leq^{x}\min_{<^{x}}(F)\right)\right\\}.$

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 $\leq^{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}^{\vphantom{g}\mathsf{}}_{{s}}\right)(b,B)$.
∎

Notice that
$(\bigsqcup_{s}{\boldsymbol{\Delta}^{0}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{s}})$
is computable, hence in case $k=1$ we obtain 4.5.

######  Lemma 5.7.

For every $k\geq 1$,

$\left(\bigsqcup_{s\in\mathbb{N}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{s}}\right)*{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}.$

###### Proof.

Using the cylindrical decomposition we can write

$\left(\bigsqcup_{s\in\mathbb{N}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{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}^{\vphantom{g}\mathsf{}}_{{s}}\right)\times\operatorname{id}\right)\circ\Phi_{e}\circ({\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\times\operatorname{id}{})$

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

$\displaystyle\left(\left(\bigsqcup_{s\in\mathbb{N}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{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)=$
$\displaystyle\langle\left(\bigsqcup_{s\in\mathbb{N}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{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})\rangle.$

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}^{\vphantom{g}\mathsf{}}_{{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.

We define a $\Delta^{0,\langle p_{1},p_{2}\rangle}_{k}$ linear order as
follows. First define

$\displaystyle L:=\\{(\sigma,n):{}$ $\displaystyle{}\sigma\in p_{1}\text{ and
}$ $\displaystyle\pi_{1}\Phi_{1}(\sigma(0),p_{2})\text{ outputs a number in
less than }|\sigma|\text{ steps and}$ $\displaystyle n\text{ lies in the set
named by }\pi_{2}\Phi_{1}(\sigma(0),p_{2})\\}.$

We order the elements of $L$ by

$(\sigma,n)\leq_{L}(\tau,m):\iff\sigma<_{\mathrm{KB}}\tau\lor(\sigma=\tau\land
n\leq m).$

It is easy to see that $(L,\leq_{L})$ is $\Delta^{0,\langle
p_{1},p_{2}\rangle}_{k}$. Notice that it is a linear order, as the pairs are
ordered lexicographically where the first components are ordered according to
the Kleene-Brouwer order on ${\mathbb{N}^{<\mathbb{N}}}$ and the second
components are ordered according to the order on $\mathbb{N}$.

Let $(q_{i})_{i\in\mathbb{N}}$ be an $<_{L}$-descending sequence, with
$q_{i}=(\sigma_{i},n_{i})$. Notice that for each $i$ there is a $j>i$ s.t.
$\sigma_{j}<_{\mathrm{KB}}\sigma_{i}$. Indeed, if there is an $i$ s.t. for all
$j>i$ we have $\sigma_{j}=\sigma_{i}$ then, by definition of $\leq_{L}$, the
sequence $(n_{j})_{j>i}$ would be a descending sequence in the natural
numbers, which is impossible.

This implies that there is a subsequence $(q_{i_{k}})_{k\in\mathbb{N}}$ s.t.
$(\sigma_{i_{k}})_{k\in\mathbb{N}}$ is a $<_{\mathrm{KB}}$-descending
sequence. In particular, this implies that $T_{\sigma_{0}(0)}$ is ill-founded,
i.e. $\sigma_{0}(0)\in{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}(p_{1})$.
Moreover, by definition of $L$, this implies that $n_{0}$ lies in the set
named by $\pi_{2}\Phi_{1}(\sigma_{0}(0),p_{2})$.

In other words, given an $<_{L}$-descending sequence
$(q_{i})_{i\in\mathbb{N}}$ we have that
$(\pi_{1}q_{0})(0)\in{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}(p_{1})$ and
$\pi_{2}q_{0}\in\left(\bigsqcup_{s\in\mathbb{N}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{s}}\right)\Phi_{1}({\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}(p_{1}),p_{2})$.
From this we can compute $\Phi_{2}(\pi_{1}q_{0},p_{2})$ as well. This
establishes the desired reduction. ∎

This completes the proof of 5.5.

With a small modification of the argument in the proof of 5.6 we can prove the
following:

######  Proposition 5.8.

Fix $k\geq 1$. For every $f:\subseteq\mathbf{X}\rightrightarrows\mathbb{N}$,

$f\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}\iff
f\leq_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\times\mathsf{lim}^{[k-1]}.$

If, in particular, $f$ has codomain $N$ for some $N\geq 1$ then

$ f\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}\iff
f\leq_{\mathrm{W}}\mathsf{RT}^{{1}}_{{N}}*\mathsf{lim}^{[k-1]}.$

If, additionally, $f$ is single-valued, then

$f\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}\iff
f\leq_{\mathrm{W}}\mathsf{lim}_{N}*\mathsf{lim}^{[k-1]}.$

###### Proof.

The right-to-left implication follows from 4.8 and 5.3:

$\displaystyle{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\times\mathsf{lim}^{[k-1]}$
$\displaystyle\leq_{\mathrm{W}}{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}*\mathsf{lim}^{[k-1]}$
$\displaystyle\leq_{\mathrm{W}}\mathsf{DS}*\mathsf{lim}^{[k-1]}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}.$

To prove the left-to-right implication, fix a pair of Turing functionals
$\Phi$ and $\Psi$ witnessing the reduction
$f\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$. Fix an
$f$-instance with name $x$ and let $\leq^{x}$ be the $\Delta^{0,x}_{k}$ linear
order defined by $\Phi^{x}$.

Define $D$, $D_{s}$ and $A$ as in the proof of 5.6. In that proof, we applied
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$ to $A$ to obtain $b\in\mathbb{N}$.
Then we restricted our attention to $B\subseteq D_{b}$. Here we will still
apply ${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}$ to $A$, but we will
concurrently consider a subset $B_{s}$ of each $D_{s}$. For each $s$, define

$\displaystyle B_{s}:=\left\\{F\in D_{s}:(\forall G\in
D_{s})\left(\min_{<^{x}}(G)\leq^{x}\min_{<^{x}}(F)\right)\right\\},$
$\displaystyle F_{s}:=\min B_{s},$

where $F_{s}$ is intended to be the empty sequence if $B_{s}$ (and hence
$D_{s}$) is empty.

Notice that $B_{s}\subset\\{0,\ldots,s-1\\}$ is $\boldsymbol{\Delta}^{0}_{k}$
(as each $D_{s}$ is $\boldsymbol{\Pi}^{0}_{k-1}$) and therefore $F_{s}$ is
$\boldsymbol{\Delta}^{0}_{k}$. Since
$\mathsf{lim}^{[k-1]}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{CA}$,
it can determine which $B_{s}$ is nonempty, and compute $F_{s}$ if $B_{s}$ is
nonempty. Therefore the sequence $(F_{s})_{s\in\mathbb{N}}$ can be computed
using $\mathsf{lim}^{[k-1]}$. For every
$b\in{\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}(A)$ we have that $F_{b}$ is
extendible to an infinite $<^{x}$-descending sequence and that $\Psi^{x\oplus
F_{s}}$ converges to some $f$-solution $j$ (see also the proof of 5.6).

Assume now that $f$ has codomain $N$ for some $N\geq 1$. We can modify the
above argument as follows: after computing the sequence
$(F_{s})_{s\in\mathbb{N}}$, we consider the $\mathsf{RT}^{{1}}_{{N}}$-instance
$c$ defined as

$c(s):=\begin{cases}0&\text{if }F_{s}=\langle\rangle,\\\ \Psi^{x\oplus
F_{s}}(0)&\text{otherwise}.\end{cases}$

Since $F_{s}$ is nonempty and extendible for cofinitely many $s$, if $c(s)=i$
for infinitely many $s$ (i.e., $c$ has an $\mathsf{RT}^{{1}}_{{N}}$-solution
of color $i$), then there is an extendible $F_{s}$ s.t. $\Psi^{x\oplus
F_{s}}(0)=i$, hence $i$ is an $f$-solution.

If, additionally, $f$ is single-valued, then there is only one possible $i$
s.t. $c$ has a homogeneous solution with color $i$. This shows that the
sequence $(c(s))_{s\in\mathbb{N}}$ has a limit, and therefore it suffices to
use $\mathsf{lim}_{N}$ to get the solution.

The fact that $\mathsf{RT}^{{1}}_{{N}}*\mathsf{lim}^{[k-1]}$ and
$\mathsf{lim}_{N}*\mathsf{lim}^{[k-1]}$ are reducible to
${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$ follows from the fact that
the compositional product is a degree theoretic operation, as
$\mathsf{RT}^{{1}}_{{N}}\leq_{\mathrm{W}}\mathsf{DS}$ (4.31),
$\mathsf{lim}_{N}\leq_{\mathrm{W}}\mathsf{DS}$ (4.16) and
${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}\mathsf{DS}*\mathsf{lim}^{[k-1]}$
(5.3). ∎

Notice that
${\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\times\mathsf{lim}^{[k-1]}$ is not a
first-order problem, so the first statement in 5.8 is not an alternative
characterization of
${}^{1}{{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}}$. It can be
rephrased as

${}^{1}{{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}}\equiv_{\mathrm{W}}{}^{1}{({\boldsymbol{\Pi}^{1}_{1}}\mathsf{-Bound}\times\mathsf{lim}^{[k-1]})}.$

This concludes our discussion of the first-order problems that are Weihrauch
reducible to ${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$. As for the
deterministic part of ${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$:

######  Corollary 5.9.

For every $k\geq 1$,
$\mathrm{Det}({\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS})\equiv_{\mathrm{W}}\mathsf{lim}^{[k]}$.

###### Proof.

This follows from $\mathrm{Det}(\mathsf{DS})\equiv_{\mathrm{W}}\mathsf{lim}$
(4.16) and the fact that, for cylinders, the jump commutes with the
deterministic part (3.11). ∎

######  Theorem 5.10.

For every $k\geq 1$,

${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}<_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}.$

In particular this shows that the
$\boldsymbol{\Gamma}$-$\mathsf{DS}$-hierarchy does not collapse at any finite
level.

###### Proof.

This follows directly from 5.8 or, alternatively, from 5.9. Indeed it suffices
to notice that, for every $k\geq 1$,
$\mathsf{LPO}^{(k)}\leq_{\mathrm{W}}\mathsf{lim}^{[k+1]}$ but
$\mathsf{LPO}^{(k)}\not\leq_{\mathrm{W}}\mathsf{lim}^{[k]}$, as
$\mathsf{LPO}^{(k)}$ is the characteristic function of a
$\Sigma^{0}_{k+1}$-complete set while $\mathsf{lim}^{[k]}$ is
$\Sigma^{0}_{k+1}$-measurable. ∎

######  Theorem 5.11.

For every $k\geq 1$,
${\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{DS}$.

###### Proof.

The right-to-left reduction is trivial. To prove the left-to-right one it
suffices to show that
${\boldsymbol{\Delta}^{0}_{1}}\text{-}\mathsf{DS}^{\prime}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{1}}\text{-}\mathsf{DS}$
and the proof will follow from 5.3 as

${\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{1}}\text{-}\mathsf{DS}^{\prime}*\mathsf{lim}^{[k-1]}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{1}}\text{-}\mathsf{DS}*\mathsf{lim}^{[k-1]}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{DS}.$

Let $p=(p_{n})_{n\in\mathbb{N}}$ be a sequence in ${\mathbb{N}^{\mathbb{N}}}$
converging to the characteristic function of an ill-founded linear order $L$.
In the following it is convenient to consider also the sequence
$q=(q_{n})_{n\in\mathbb{N}}$, where $q_{n}(i):=p_{n}(\langle i,i\rangle)$.
Clearly $q$ converges to the characteristic function of
$\operatorname{dom}(L)$ and is uniformly computable from $p$.

For sake of readability, define the formula

$\varphi((x_{n})_{n\in\mathbb{N}},\sigma):=(\forall
i<|\sigma|)(x_{\sigma(i)}(i)\neq x_{\sigma(i)+1}(i)\land(\forall
j>\sigma(i))(x_{j}(i)=x_{j+1}(i))).$

Intuitively $\varphi$ says that, for each $i<|\sigma|$, $\sigma(i)$ codes the
positions in which the sequence $(x_{n})_{n\in\mathbb{N}}$ changes for the
last time in the $i$-th row. Let us also write $x_{\sigma}:=|\sigma|-1$. We
define

$\displaystyle
M:=\\{(\sigma,\tau)\in{\mathbb{N}^{<\mathbb{N}}}\times{\mathbb{N}^{<\mathbb{N}}}:{}$
$\displaystyle\varphi(q,\sigma)\land{}$ $\displaystyle
q_{\sigma(x_{\sigma})+1}(x_{\sigma})=1\land{}$
$\displaystyle\varphi(p,\tau)\land|\tau|=\langle
x_{\sigma},x_{\sigma}\rangle+1\\}$

Notice that the first two conditions imply that $x_{\sigma}\in L$. Intuitively
$x_{\sigma}$ is the $\leq_{\mathbb{N}}$-largest element that is witnessed by
$\sigma$ to enter in $L$. The last line says that $\tau$ is exactly as long as
needed to witness all the relations between the elements of $L$ that are
$\leq_{\mathbb{N}}x_{\sigma}$.

We order the set $M$ as follows:

$(\sigma_{0},\tau_{0})\leq_{M}(\sigma_{1},\tau_{1}):\iff
x_{\sigma_{0}}\leq_{L}x_{\sigma_{1}}$

Notice that $M$ is a $\Pi^{0,p}_{1}$ linear order as $M$ is $\Pi^{0,p}_{1}$
and the order $\leq_{M}$ is $p$-computable: indeed, given two pairs
$(\sigma_{0},\tau_{0}),(\sigma_{1},\tau_{1})\in M$, we can use the longer
string between $\tau_{0}$ and $\tau_{1}$ to $p$-compute whether
$x_{\sigma_{0}}\leq_{L}x_{\sigma_{1}}$. Notice also that, for each $l$, there
is exactly one string $\sigma$ of length $l$ witnessing $\varphi(q,\sigma)$
(by minimality). The third line in the definition of $M$ implies that if
$\sigma$ satisfies the first two conditions then there is a unique $\tau$ s.t.
$(\sigma,\tau)\in M$. The linearity of $M$ follows by the linearity of $L$.

To conclude the proof it is enough to notice that if
$((\sigma_{i},\tau_{i}))_{i\in\mathbb{N}}$ is an $<_{M}$-descending sequence
then $(x_{\sigma_{i}})_{i\in\mathbb{N}}$ is an $<_{L}$-descending sequence. ∎

The following is essentially a classical result (see e.g. [15, Thm. 2.4]). The
proof is simple enough that we can briefly sketch it.

######  Theorem 5.12.

For every $k\geq 1$,
${\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$.

###### Proof.

Given a $\boldsymbol{\Sigma}^{0}_{k}$ linear order $L$, we can uniformly
consider a sequence $((L_{s},\leq_{s}))_{s\in\mathbb{N}}$ of
$\boldsymbol{\Delta}^{0}_{k}$ linear orders approximating $L$. We then define

$\displaystyle M:=\\{(q,s):q\in L_{s}\text{ and }(\forall t<s)(q\notin
L_{t})\\},$ $\displaystyle(p,s)\leq_{M}(q,t):\iff p\leq_{L}q.$

Notice that $(p,s)\leq_{M}(q,t)$ can be written also as $p=q\lor(\forall
i)(q\not\leq_{i}p)$, hence $M$ is $\Delta^{0,L}_{k}$. Moreover, since for
every $q\in L$ there is a unique $s$ s.t. $(q,s)\in M$, it is easy to see that
$M$ is computably isomorphic to $L$. In particular, given an
$<_{M}$-descending sequence we can obtain an $<_{L}$-descending sequence by
projection. ∎

######  Corollary 5.13.

For every $k\geq 1$, we have

${\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{BS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{BS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k+1}}\text{-}\mathsf{DS}.$

###### Proof.

It is straightforward to see that
${\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{DS}\leq_{\mathrm{W}}{\boldsymbol{\Pi}^{0}_{k}}\text{-}\mathsf{BS}\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{BS}$.
By 5.4,
${\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{BS}\equiv_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}$.
It follows from 5.11 that the first four problems are equivalent. Finally,
${\boldsymbol{\Delta}^{0}_{k+1}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k+1}}\text{-}\mathsf{DS}$
by 5.12. ∎

######  Theorem 5.14.

For every $k\geq 1$,
$\mathsf{LPO}^{(k)}\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{BS}$
and therefore
${\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{BS}\not\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{DS}$.

###### Proof.

The second statement follows from the first because
$\mathsf{LPO}^{(k)}\not\leq_{\mathrm{W}}{\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}$
(proof of 5.10) and
${\boldsymbol{\Delta}^{0}_{k}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{DS}$
(5.12).

To prove the first statement, it is enough to show that
$\mathsf{LPO}^{\prime}\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{1}}\text{-}\mathsf{BS}$,
and the claim will follow by 5.3 as

$\mathsf{LPO}^{(k)}\leq_{\mathrm{W}}\mathsf{LPO}^{\prime}*\mathsf{lim}^{[k-1]}\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{1}}\text{-}\mathsf{BS}*\mathsf{lim}^{[k-1]}\equiv_{\mathrm{W}}{\boldsymbol{\Sigma}^{0}_{k}}\text{-}\mathsf{BS}.
$

Let $(p_{s})_{s\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 proofs of 4.18 and 4.20)

$g(s)=\begin{cases}i+1&\text{if }i\leq s\land p_{s}(i)\neq 0\land(\forall
j<i)(p_{s}(j)=0),\\\ 0&\text{otherwise.}\end{cases}$

Let us define a quasi-order $Q$ inductively: at stage $s=0$ we add $\langle
g(0),0\rangle$. At stage $s+1$ we do the following:

  1. (1)

if $g(s)=g(s+1)$ we put $\langle g(s),s+1\rangle$ immediately below $\langle
g(s),s\rangle$;

  2. (2)

if $g(s)\neq g(s+1)$ we put $\langle g(s+1),s+1\rangle$ at the top and we put
$\langle-1,s+1\rangle$ at the bottom. Moreover we collapse to a single
equivalence class all the elements $\langle g,t\rangle$ with $t\leq s$ and
$g\neq-1$.

This construction produces a quasi-order $(Q,\preceq_{Q})$ which is computable
in $(p_{s})_{s\in\mathbb{N}}$.

Notice that if there is an $s$ s.t. for every $t\geq s$, $g(t)=g(s)$ (in
particular, this is the case if $\mathsf{LPO}(p)=1$) then the equivalence
classes of $\preceq_{Q}$ form a linear order of type $n+\omega^{*}$ and every
$\preceq_{Q}$-bad sequence is a descending sequence of the form $(\langle
g(s),s_{n}\rangle)_{n\in\mathbb{N}}$ for some strictly increasing sequence
$(s_{n})_{n\in\mathbb{N}}$. On the other hand, if the sequence
$(g(s))_{s\in\mathbb{N}}$ does not stabilize then the equivalence classes of
$\preceq_{Q}$ are linearly ordered as $\omega^{*}$, where all the elements
$\langle g,s\rangle$ with $g\neq-1$ are equivalent and lie in the top
equivalence class. This shows that the construction produces a non-well quasi-
order.

For every $\preceq_{Q}$-bad sequence $(\langle
g_{n},s_{n}\rangle)_{n\in\mathbb{N}}$ produced by
${\boldsymbol{\Sigma}^{0}_{1}}\text{-}\mathsf{BS}(Q)$, we compute the solution
for $\mathsf{LPO}^{\prime}((p_{s})_{s\in\mathbb{N}})=\mathsf{LPO}(p)$ by
returning $0$ if $g_{1}\leq 0$ and $1$ otherwise. We consider two cases. If
the sequence $(g(s))_{s\in\mathbb{N}}$ stabilizes, then the sequence
$(g_{n})_{n\in\mathbb{N}}$ is constant. Furthermore, its value is $0$ if
$\mathsf{LPO}(p)=0$, otherwise its value is positive. On the other hand, if
the sequence $(g(s))_{s\in\mathbb{N}}$ does not stabilize, then
$\mathsf{LPO}(p)=0$. Furthermore, for every $n>0$, we have $g_{n}=-1\leq 0$.
(The first element $\langle g_{0},s_{0}\rangle$ may lie in the top equivalence
class, in which case $g_{0}$ may be positive. Hence we check $g_{1}$ instead
of $g_{0}$). ∎

###  5.2. $\Gamma$${}^{1}_{1}$-$\mathsf{DS}$ and
$\Gamma$${}^{1}_{1}$-$\mathsf{BS}$

We now turn our attention to the analytic classes. Notice first of all that
being a descending sequence through a $\boldsymbol{\Sigma}^{1}_{1}$ linear
order is a $\boldsymbol{\Sigma}^{1}_{1}$-property, hence
${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{DS}\leq_{\mathrm{W}}{\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{C}^{\vphantom{g}\mathsf{}}_{{{\mathbb{N}^{\mathbb{N}}}}}\equiv_{\mathrm{W}}\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$.
We will show that ${\boldsymbol{\Sigma}^{1}_{1}}\text{-}\mathsf{DS}$ is the
strongest $\mathsf{DS}$-principle that is still reducible to
$\mathsf{C}_{\mathbb{N}^{\mathbb{N}}}$ (5.25).

######  Proposition 5.15.

${\boldsymbol{\Delta}^{1}_{1}}\text{-}\mathsf{DS}\equiv_{\mathrm{W}}\mathsf{DS}*\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$
and
${\boldsymbol{\Delta}^{1}_{1}}\text{-}\mathsf{BS}\equiv_{\mathrm{W}}\mathsf{BS}*\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$.

###### Proof.

We will only prove the first statement. The proof of the second statement is
similar.

To prove the left-to-right reduction, given a $\boldsymbol{\Delta}^{1}_{1}$
name for $L$ we use ${\boldsymbol{\Delta}^{1}_{1}}\text{-}\mathsf{CA}$ (which
is known to be equivalent to $\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}$, see [26,
Thm. 3.11]) to compute a $\boldsymbol{\Delta}^{0}_{1}$ name for $L$. We can
then apply $\mathsf{DS}$ to find a descending sequence through $L$.

To prove the converse reduction, using the cylindrical decomposition we can
write

$\mathsf{DS}*\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}\equiv_{\mathrm{W}}\mathsf{DS}\circ\Phi_{e}\circ\mathsf{UC}_{\mathbb{N}^{\mathbb{N}}}
$

for some computable function $\Phi_{e}$. In particular, given
$T\subset{\mathbb{N}^{<\mathbb{N}}}$ with a unique path $x$, $\Phi_{e}(x)$ is