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

Abstract We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ over $\mathsf {RCA}_0$ . For each fixed $k \geq 3$ , the Rival–Sands theorem for infinite partial orders of width $\leq \!k$ is equivalent to $\mathsf {ADS}$ over $\mathsf {RCA}_0$ . The Rival–Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to $\mathsf {SADS}$ over $\mathsf {RCA}_0$ . Here $\mathsf {RCA}_0$ denotes the recursive comprehension axiomatic system, $\mathsf {I}\Sigma ^0_{2}$ denotes the $\Sigma ^0_2$ induction scheme, $\mathsf {ADS}$ denotes the ascending/descending sequence principle, and $\mathsf {SADS}$ denotes the stable ascending/descending sequence principle. To the best of our knowledge, these versions of the Rival–Sands theorem for partial orders are the first examples of theorems from the general mathematics literature whose strength is exactly characterized by $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ , by $\mathsf {ADS}$ , and by $\mathsf {SADS}$ . Furthermore, we give a new purely combinatorial result by extending the Rival–Sands theorem to infinite partial orders that do not have infinite antichains, and we show that this extension is equivalent to arithmetical comprehension over $\mathsf {RCA}_0$ .

Abstract 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 (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) 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$ .

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

Building on previous work by Mummertet al.(2015, The modal logic of Reverse Mathematics.Archive for Mathematical54(3–4) 425–437), we study the logic underlying the web of implications and non-implications which constitute the so called reverse mathematics zoo. We introduce a tableaux system for this logic and natural deduction systems for important fragments of the language.

Abstract We study the computability-theoretic complexity and proof-theoretic strength of the following statements: (1) “If is a well-ordering, then so is ”, and (2) “If is a well-ordering, then so is φ(α, )”, where ∝ is a fixed computable ordinal and φ represents the two-placed Veblen function. For the former statement, we show that ω iterations of the Turing jump are necessary in the proof and that the statement is equivalent to over RCA0. To prove the latter statement we need to use ωα iterations of the Turing jump, and we show that the statement is equivalent to . Our proofs are purely computability-theoretic. We also give a new proof of a result of Friedman: the statement “if is a well-ordering, then so is φ( , 0)” is equivalent to ATR0 over RCA0.

In reverse mathematics, one formalizes theorems of ordinary mathematics in second order arithmetic and attempts to discover which set theoretic axioms are required to prove these theorems. Often, this project involves making choices between classically equivalent definitions for the relevant mathematical concepts. In this paper, we consider a number of equivalent definitions for the notions of well quasi-order and better quasi-order and examine how difficult it is to prove the equivalences of these definitions. As usual in reverse mathematics, we work in the context of subsystems of second order arithmetic and take RCA0 as our base system. RCA0 is the subsystem formed by restricting the comprehension scheme in second order arithmetic to formulas and adding a formula induction scheme for formulas. For the purposes of this paper, we will be concerned with fairly weak extensions of RCA0 (indeed strictly weaker than the subsystem ACA0 which is formed by extending the comprehension scheme in RCA0 to cover all arithmetic formulas) obtained by adjoining certain combinatorial principles to RCA0. Among these, the most widely used in reverse mathematics is Weak König's Lemma; the resulting theory WKL0 is extensively documented in [11] and elsewhere. We give three other combinatorial principles which we use in this paper. In these principles, we use k to denote not only a natural number but also the finite set {0, …, k − 1}.

Abstract. We show that the quasi-order of continuous embeddability between finitely branching dendrites (a natural class of fairly simple compacta) is -complete. We also show that embeddability between countable linear orders with infinitely many colors is -complete.