We study the uniform computational content of Ramsey’s theorem in the Weihrauch lattice. Our central results provide information on how Ramsey’s theorem behaves under product, parallelization, and jumps. From these results we can derive a number of important properties of Ramsey’s theorem. For one, the parallelization of Ramsey’s theorem for cardinalityn≥ 1 and an arbitrary finite number of colorsk≥ 2 is equivalent to then-th jump of weak Kőnig’s lemma. In particular, Ramsey’s theorem for cardinalityn≥ 1 is${\bf{\Sigma }}_{n + 2}^0$-measurable in (...) the effective Borel hierarchy, but not${\bf{\Sigma }}_{n + 1}^0$-measurable. Secondly, we obtain interesting lower bounds, for instance then-th jump of weak Kőnig’s lemma is Weihrauch reducible to Ramsey’s theorem of cardinalityn+ 2 forn≥ 2. We prove that with strictly increasing numbers of colors Ramsey’s theorem forms a strictly increasing chain in the Weihrauch lattice. Our study of jumps also shows that certain uniform variants of Ramsey’s theorem that are indistinguishable from a nonuniform perspective play an important role. For instance, the colored version of Ramsey’s theorem explicitly includes the color of the homogeneous set as output information, and the jump of this problem is equivalent to the stable version of Ramsey’s theorem of the next greater cardinality. Finally, we briefly discuss the particular case of Ramsey’s theorem for pairs, and we provide some new separation techniques for problems that involve jumps in this context. In particular, we study uniform results regarding the relation of boundedness and induction problems to Ramsey’s theorem, and we show that there are some significant differences with the nonuniform situation in reverse mathematics. (shrink)

We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete metric space cannot be decomposed into countably many nowhere dense pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical versions of (...) the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is “given.” Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets. (shrink)

We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total (...) Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete. (shrink)

We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice is complete for dimension greater than (...) or equal to two in the sense that it is computably equivalent to Weak Kőnig’s Lemma. While we can present two independent proofs for dimension three and upward that are either based on a simple geometric construction or a combinatorial argument, the proof for dimension two is based on a more involved inverse limit construction. The connected choice operation in dimension one is known to be equivalent to the Intermediate Value Theorem; we prove that this problem is not idempotent in contrast to the case of dimension two and upward. We also prove that Lipschitz continuity with Lipschitz constants strictly larger than one does not simplify finding fixed points. Finally, we prove that finding a connectedness component of a closed subset of the Euclidean unit cube of any dimension greater than or equal to one is equivalent to Weak Kőnig’s Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes. (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)

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)

There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.

Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded learnability is equivalent to finite View the MathML source2-piecewise computability 2 denotes the difference of two View the MathML sourceΠ10 sets), error-bounded learnability is equivalent to finite View (...) the MathML sourceΔ20-piecewise computability, and learnability is equivalent to countable View the MathML sourceΠ10-piecewise computability . Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/ Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games. (shrink)

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π10 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π10 subsets of Cantor space, we show the existence of a finite-Δ20-piecewise degree containing infinitely many finite-2-piecewise degrees, and a finite-2-piecewise degree containing infinitely many finite-Δ20-piecewise degrees 2 denotes the difference of two Πn0 sets), whereas the greatest degrees in (...) these three “finite-Γ-piecewise” degree structures coincide. Moreover, as for nonempty Π10 subsets of Cantor space, we also show that every nonzero finite-2-piecewise degree includes infinitely many Medvedev degrees, every nonzero countable-Δ20-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-2-countable-Δ20-piecewise degree includes infinitely many countable-Δ20-piecewise degrees, and every nonzero Muchnik degree includes infinitely many finite-2-countable-Δ20-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-Δ20-piecewise degree of a nonempty Π10 subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev degree structure and the finite-Γ-piecewise degree structure of all subsets of Baire space by showing that none of the finite-Γ-piecewise structures is Brouwerian, where Γ is any of the Wadge classes mentioned above. (shrink)

Kierstead showed that every computable marriage problem has a computable matching under the assumption of computable expanding Hall condition and computable local finiteness for boys and girls. The strength of the marriage theorem reaches or if computable expanding Hall condition or computable local finiteness for girls is weakened. In contrast, the provability of the marriage theorem is maintained in even if local finiteness for boys is completely removed. Using these conditions, we classify the strength of variants of marriage theorems in (...) the context of reverse mathematics. Furthermore, we introduce another condition that also makes the marriage theorem provable in, and investigate the sequential and Weihrauch strength of marriage theorems under that condition. (shrink)

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [math] principles over [math]-models of [math]. They also introduced a version of this game that similarly captures provability over [math]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [math] between two (...) principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [math] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [math], uncovering new differences between their logical strengths. (shrink)