In this work we investigate the Weihrauch degree of the problem Decreasing Sequence of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$, despite being hard to solve, 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 Baire hierarchy and show that they do not collapse at any finite level. (shrink)

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly (...) stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$. (shrink)

We study the existence and the distribution of “long” chains in the Weihrauch degrees, mostly focusing on chains with uncountable cofinality. We characterize when such chains have an upper bound and prove that there are no cofinal chains (of any order type) in the Weihrauch degrees. Furthermore, we show that the existence of coinitial sequences of non-zero degrees is equivalent to CH $\mathrm {CH}$ upper C upper H. Finally, we explore the extendibility of antichains, providing some necessary conditions for maximality.

We explore the Weihrauch degree of the problems “find a bad sequence in a non-well quasi order” ( $\mathsf {BS}$ ) and “find a descending sequence in an ill-founded linear order” ( $\mathsf {DS}$ ). We prove that $\mathsf {DS}$ is strictly Weihrauch reducible to $\mathsf {BS}$, correcting our mistaken claim in [18]. This is done by separating their respective first-order parts. On the other hand, we show that $\mathsf {BS}$ and $\mathsf {DS}$ have the same finitary and deterministic parts, (...) confirming that $\mathsf {BS}$ and $\mathsf {DS}$ have very similar uniform computational strength. We prove that König’s lemma $\mathsf {KL}$ and the problem $\mathsf {wList}_{{2^{\mathbb {N}}},\leq \omega }$ of enumerating a given non-empty countable closed subset of ${2^{\mathbb {N}}}$ are not Weihrauch reducible to $\mathsf {DS}$ or $\mathsf {BS}$, resolving two main open questions raised in [18]. We also answer the question, raised in [12], on the existence of a “parallel quotient” operator, and study the behavior of $\mathsf {BS}$ and $\mathsf {DS}$ under the quotient with some known problems. (shrink)

This paper continues the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. In particular, we consider problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. In the framework of reverse mathematics, these theorems are equivalent, respectively, to $\mathsf {ATR}_0$ and $\boldsymbol {\Pi }^1_1{-}\mathsf{CA}_0$, the two strongest subsystems of second order arithmetic among the so-called big five. As far as we know, this is (...) the first systematic study of problems at the level of $\boldsymbol {\Pi }^1_1{-}\mathsf{CA}_0$ in the Weihrauch lattice. We show that the strength of some of the problems we study depends on the topological properties of the Polish space under consideration, while others have the same strength once the space is rich enough. (shrink)

We study versions of the tree pigeonhole principle, $\mathsf {TT}^1$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether $\mathsf {TT}^1$ is $\Pi ^1_1$ -conservative over the ordinary pigeonhole principle, $\mathsf {RT}^1$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination (...) with other results, we use this to show that unlike $\mathsf {RT}^1$, the problem $\mathsf {TT}^1$ is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of $\mathsf {TT}^1$. (shrink)

This thesis is devoted to the exploration of the complexity of some mathematical problems using the framework of computable analysis and descriptive set theory. We will especially focus on Weihrauch reducibility as a means to compare the uniform computational strength of problems. After a short introduction of the relevant background notions, we investigate the uniform computational content of problems arising from theorems that lie at the higher levels of the reverse mathematics hierarchy.We first analyze the strength of the open and (...) clopen Ramsey theorems. Since there is not a canonical way to phrase these theorems as multi-valued functions, we identify eight different multi-valued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility.We then discuss some new operators on multi-valued functions and study their algebraic properties and the relations with other previously studied operators on problems. In particular, we study the first-order part and the deterministic part of a problem f, capturing the Weihrauch degree of the strongest multi-valued problem that is reducible to f and that, respectively, has codomain $\mathbb {N}$ or is single-valued.These notions proved to be extremely useful when exploring the Weihrauch degree of the problem $\mathsf {DS}$ of computing descending sequences in ill-founded linear orders. They allow us to show that $\mathsf {DS}$, and the Weihrauch equivalent problem $\mathsf {BS}$ of finding bad sequences through non-well quasi-orders, while being very “hard” to solve, are rather weak in terms of uniform computational strength. 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 Baire hierarchy and show that they do not collapse at any finite level.Finally, we work in the context of geometric measure theory and we focus on the characterization, from the point of view of descriptive set theory, of some conditions involving the notions of Hausdorff/Fourier dimension and Salem sets. We first work in the hyperspace $\mathbf {K}$ of compact subsets of $[0,1]$ and show that the closed Salem sets form a $\boldsymbol {\Pi }^0_3$ -complete family. This is done by characterizing the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. We also show that the complexity does not change if we increase the dimension of the ambient space and work in $\mathbf {K}$. We also generalize the results by relaxing the compactness of the ambient space and show that the closed Salem sets are still $\boldsymbol {\Pi }^0_3$ -complete when we endow $\mathbf {F}$ with the Fell topology. A similar result holds also for the Vietoris topology.We conclude by analyzing the same notions from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity, and show that the complexities remain the same also in the lightface case. In particular, we show that the family of all the closed Salem sets is $\Pi ^0_3$ -complete. We furthermore characterize the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets.prepared by Manlio Valenti.E-mail:[email protected]. (shrink)