Search

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 $\mathrm{CH}$. Finally, we explore the extendibility of antichains, providing some necessary conditions for maximality.

This paper classifies different fragments of the Galvin-Prikry theorem, an infinite dimensional generalization of Ramsey's theorem, in terms of their uniform computational content (Weihrauch degree). It can be seen as a continuation of arXiv:2003.04245v3, which focused on the Weihrauch classification of functions related to the open (and clopen) Ramsey theorem. We show that functions related to the Galvin-Prikry theorem for Borel sets of rank n are strictly between the (n+1)-th and n-th iterate of the hyperjump operator $\mathsf{HJ}$, which is in turn equivalent to the better known $\widehat{\mathsf{WF}}$, which corresponds to $\Pi^1_1$-$\mathsf{CA}_0$ in the Weihrauch lattice. To establish this classification we obtain the following computability theoretic result: a Turing jump ideal containing homogeneous sets for all $\Delta^0_{n+1}(X)$ sets must also contain the n-th hyperjump of X. We also extend our analysis to the transfinite levels of the Borel hierarchy. We further obtain some results about the reverse mathematics of the lightface fragments of the Galvin-Prikry theorem., Comment: 41 pages, 2 figures

A partial order $(P,\le)$ admits a jump operator if there is a map $j\colon P \to P$ that is strictly increasing and weakly monotone. Despite its name, the jump in the Weihrauch lattice fails to satisfy both of these properties: it is not degree-theoretic and there are functions $f$ such that $f\equiv_{\mathrm{W}} f'$. This raises the question: is there a jump operator in the Weihrauch lattice? We answer this question positively and provide an explicit definition for an operator on partial multi-valued functions that, when lifted to the Weihrauch degrees, induces a jump operator. This new operator, called the totalizing jump, can be characterized in terms of the total continuation, a well-known operator on computational problems. The totalizing jump induces an injective endomorphism of the Weihrauch degrees. We study some algebraic properties of the totalizing jump and characterize its behavior on some pivotal problems in the Weihrauch lattice.

Given a nonempty set $\mathcal{L}$ of linear orders, we say that the linear order $L$ is $\mathcal{L}$-convex embeddable into the linear order $L'$ if it is possible to partition $L$ into convex sets indexed by some element of $\mathcal{L}$ which are isomorphic to convex subsets of $L'$ ordered in the same way. This notion generalizes convex embeddability and (finite) piecewise convex embeddability (both studied in arXiv:2309.09910), which are the special cases $\mathcal{L} = \{\mathbf{1}\}$ and $\mathcal{L} = \mathsf{Fin}$. We focus mainly on the behavior of these relations on the set of countable linear orders, first characterizing when they are transitive, and hence a quasi-order. We then study these quasi-orders from a combinatorial point of view, and analyze their complexity with respect to Borel reducibility. Finally, we extend our analysis to uncountable linear orders., Comment: 34 pages

We consider countable linear orders and study the quasi-order of convex embeddability and its induced equivalence relation. We obtain both combinatorial and descriptive set-theoretic results, and further extend our research to the case of circular orders. These results are then applied to the study of arcs and knots, establishing combinatorial properties and lower bounds (in terms of Borel reducibility) for the complexity of some natural relations between these geometrical objects., Comment: 46 pages

It has recently been shown that fairly strong axiom systems such as $\mathsf{ACA}_0$ cannot prove that the antichain with three elements is a better quasi order ($\mathsf{bqo}$). In the present paper, we give a complete characterization of the finite partial orders that are provably $\mathsf{bqo}$ in such axiom systems. The result will also be extended to infinite orders. As an application, we derive that a version of the minimal bad array lemma is weak over $\mathsf{ACA_0}$. In sharp contrast, a recent result shows that the same version is equivalent to $\Pi^1_2$-comprehension over the stronger base theory $\mathsf{ATR}_0$.

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., Comment: 35 pages

In this paper, we study Hausdorff and Fourier dimension from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity. Working in the hyperspace $\mathbf{K}(X)$ of compact subsets of $X$, with $X=[0,1]^d$ or $X=\mathbb{R}^d$, we characterize the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. This, in turn, allows us to show that family of all the closed Salem sets is $\Pi^0_3$-complete. One of our main tools is a careful analysis of the effectiveness of a classical theorem of Kaufman. We furthermore compute the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets., Comment: 36 pages

We analyze the axiomatic strength of the following theorem due to Rival and Sands 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 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$.

Interval graphs and interval orders are deeply linked. In fact, edges of an interval graphs represent the incomparability relation of an interval order, and in general, of different interval orders. The question about the conditions under which a given interval graph is associated to a unique interval order (up to duality) arises naturally. Fishburn provided a characterisation for uniquely orderable finite connected interval graphs. We show, by an entirely new proof, that the same characterisation holds also for infinite connected interval graphs. Using tools from reverse mathematics, we explain why the characterisation cannot be lifted from the finite to the infinite by compactness, as it often happens., Comment: 13 pages v2: minor changes following referee's suggestions

In this paper we study the notion of Salem set from the point of view of descriptive set theory. We first work in the hyperspace $\mathbf{K}([0,1])$ 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}([0,1]^d)$. We then 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 the hyperspace of all closed subsets of $\mathbb{R}^d$ with the Fell topology. A similar result holds also for the Vietoris topology., Comment: Extended Lemma 3.1, fixed Lemma 5.3 and improved the presentation of the results. To appear in Fundamenta Mathematicae

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 8 different multivalued functions (5 corresponding to the open Ramsey theorem and 3 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$., Comment: Improved the presentation of lemmas 4.3 and 4.13. To appear in The Journal of Symbolic Logic

We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA_0 and hence is computably true., Comment: Only minor (non mathematical) changes introduced. To appear in Computability

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 ATR_0 has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.

We study Polish spaces for which a set of possible distances $A \subseteq \mathbb{R}^+$ is fixed in advance. We determine, depending on the properties of $A$, the complexity of the collection of all Polish metric spaces with distances in $A$, obtaining also example of sets in some Wadge classes where not many natural examples are known. Moreover we describe the properties that $A$ must have in order that all Polish spaces with distances in that set belong to a given class, such as zero-dimensional, locally compact, etc. These results lead us to give a fairly complete description of the complexity, with respect to Borel reducibility and again depending on the properties of $A$, of the relations of isometry and isometric embeddability between these Polish spaces., Comment: changes following the referee report; main results unchanged

In this paper we study the Weihrauch complexity of projection operators onto closed subsets of the Euclidean space. We show that some fundamental degrees of the Weihrauch lattice can be characterized in terms of such operators., Comment: A few changes following the referee report

In this paper we survey wqo and bqo theory from the reverse mathematics perspective. We consider both elementary results (such as the equivalence of different definitions of the concepts, and basic closure properties) and more advanced theorems. The classification from the reverse mathematics viewpoint of both kinds of results provides interesting challenges, and we cover also recent advances on some long standing open problems., Comment: version 5 corrects a mistake in the statement of Theorem 6.22 and updates the bibliography. To appear in: Well quasi-orders in computation, logic, language and reasoning (P. Schuster, M. Seisenberger, A. Weiermann, eds.), Trends in Logic, Springer

When a linear order has an order preserving surjection onto each of its suborders we say that it is strongly surjective. We prove that the set of countable strongly surjective linear orders is complete for the class of sets which are the union of an analytic and a coanalytic set. Using hypotheses beyond ZFC, we prove the existence of uncountable strongly surjective orders., Comment: 32 pages; v2 is the "accepted author manuscript" - an author-created version of the final journal article (to reflect changes made in peer review and editing)

Building on previous work by Mummert, Saadaoui and Sovine, we study the logic underlying the web of implications and nonimplications 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., Comment: 16 pages

A quasi-order $Q$ induces two natural quasi-orders on $P(Q)$, but if $Q$ is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq showed that moving from a well-quasi-order $Q$ to the quasi-orders on $P(Q)$ preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on $P(Q)$ are Noetherian, which means that they contain no infinite strictly descending sequences of closed sets. We analyze various theorems of the form "if $Q$ is a well-quasi-order then a certain topology on (a subset of) $P(Q)$ is Noetherian" in the style of reverse mathematics, proving that these theorems are equivalent to ACA_0 over RCA_0. To state these theorems in RCA_0 we introduce a new framework for dealing with second-countable topological spaces., Comment: minor changes suggested by referees, added table

We study the complexity with respect to Borel reducibility of the relations of isometry and isometric embeddability between ultrametric Polish spaces for which a set $D$ of possible distances is fixed in advance. These are, respectively, an analytic equivalence relation and an analytic quasi-order and we show that their complexity depends only on the order type of $D$. When $D$ contains a decreasing sequence, isometry is Borel bireducible with countable graph isomorphism and isometric embeddability has maximal complexity among analytic quasi-orders. If $D$ is well-ordered the situation is more complex: for isometry we have an increasing sequence of Borel equivalence relations of length $\omega_1$ which are cofinal among Borel equivalence relations classifiable by countable structures, while for isometric embeddability we have an increasing sequence of analytic quasi-orders of length at least $\omega+3$. We then apply our results to solve various open problems in the literature. For instance, we answer a long-standing question of Gao and Kechris by showing that the relation of isometry on locally compact ultrametric Polish spaces is Borel bireducible with countable graph isomorphism., Comment: Minor imprecisions corrected. Following the suggestion of the anonymous referee, the former Section 7 concerning arbitrary Polish spaces with fixed set of distances has been left out and will be posted as a separate paper soon. The title is changed as well to reflect this modification

We study the relation on linear orders induced by order preserving surjections. In particular we show that its restriction to countable orders is a bqo., Comment: 15 pages; in version 2 we corrected some typos and rewrote the paragraphs introducing the results of subsection 3.3 (statements and proofs are unchanged)

In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of the initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We show that the left to right directions of these theorems are equivalent to ACA_0 and ATR_0, respectively. On the other hand, the opposite directions are both provable in WKL_0, but not in RCA_0. We also prove the equivalence with ACA_0 of the following result of Erd\"os and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains., Comment: updated draft after referees' suggestions; simpler proof of Lemma 3.3; improved statement of Lemma 5.7 (former Lemma 5.6)

We introduce the notion of \tau-like partial order, where \tau is one of the linear order types \omega, \omega*, \omega+\omega*, and \zeta. For example, being \omega-like means that every element has finitely many predecessors, while being \zeta-like means that every interval is finite. We consider statements of the form "any \tau-like partial order has a \tau-like linear extension" and "any \tau-like partial order is embeddable into \tau" (when \tau\ is \zeta\ this result appears to be new). Working in the framework of reverse mathematics, we show that these statements are equivalent either to B\Sigma^0_2 or to ACA_0 over the usual base system RCA_0., Comment: 8 pages, minor changes suggested by referee. To appear in MLQ - Mathematical Logic Quarterly

In 1967 Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos. Wolk's original result actually shows that every wpo has a strongly maximal chain, which we define below. We show that a set computes strongly maximal chains in all computable wpo if and only if it computes all hyperarithmetic sets.

We classify the computational content of the Bolzano-Weierstrass Theorem and variants thereof in the Weihrauch lattice. For this purpose we first introduce the concept of a derivative or jump in this lattice and we show that it has some properties similar to the Turing jump. Using this concept we prove that the derivative of closed choice of a computable metric space is the cluster point problem of that space. By specialization to sequences with a relatively compact range we obtain a characterization of the Bolzano-Weierstrass Theorem as the derivative of compact choice. In particular, this shows that the Bolzano-Weierstrass Theorem on real numbers is the jump of Weak K\"onig's Lemma. Likewise, the Bolzano-Weierstrass Theorem on the binary space is the jump of the lesser limited principle of omniscience LLPO and the Bolzano-Weierstrass Theorem on natural numbers can be characterized as the jump of the idempotent closure of LLPO. We also introduce the compositional product of two Weihrauch degrees f and g as the supremum of the composition of any two functions below f and g, respectively. We can express the main result such that the Bolzano-Weierstrass Theorem is the compositional product of Weak K\"onig's Lemma and the Monotone Convergence Theorem. We also study the class of weakly limit computable functions, which are functions that can be obtained by composition of weakly computable functions with limit computable functions. We prove that the Bolzano-Weierstrass Theorem on real numbers is complete for this class. Likewise, the unique cluster point problem on real numbers is complete for the class of functions that are limit computable with finitely many mind changes. We also prove that the Bolzano-Weierstrass Theorem on real numbers and, more generally, the unbounded cluster point problem on real numbers is uniformly low limit computable. Finally, we also discuss separation techniques., Comment: This version includes an addendum by Andrea Cettolo, Matthias Schr\"oder, and the authors of the original paper. The addendum closes a gap in the proof of Theorem 11.2, which characterizes the computational content of the Bolzano-Weierstra\ss{} Theorem for arbitrary computable metric spaces

We show that the maximal linear extension theorem for well partial orders is equivalent over RCA_0 to ATR_0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR_0 over RCA_0., Comment: 18 pages. New proof of the maximal chain theorem in ATR_0

We introduce the notion of an invariantly universal pair (S,E) where S is an analytic quasi-order and E \subseteq S is an analytic equivalence relation. This means that for any analytic quasi-order R there is a Borel set B invariant under E such that R is Borel bireducible with the restriction of S to B. We prove a general result giving a sufficient condition for invariant universality, and we demonstrate several applications of this theorem by showing that the phenomenon of invariant universality is widespread. In fact it occurs for a great number of complete analytic quasi-orders, arising in different areas of mathematics, when they are paired with natural equivalence relations., Comment: 31 pages, 1 figure, to appear in Transactions of the American Mathematical Society

We study the computability-theoretic complexity and proof-theoretic strength of the following statements: (1) "If X is a well-ordering, then so is epsilon_X", and (2) "If X is a well-ordering, then so is phi(alpha,X)", where alpha is a fixed computable ordinal and phi the two-placed Veblen function. For the former statement, we show that omega iterations of the Turing jump are necessary in the proof and that the statement is equivalent to ACA_0^+ over RCA_0. To prove the latter statement we need to use omega^alpha iterations of the Turing jump, and we show that the statement is equivalent to Pi^0_{omega^alpha}-CA_0. Our proofs are purely computability-theoretic. We also give a new proof of a result of Friedman: the statement "if X is a well-ordering, then so is phi(X,0)" is equivalent to ATR_0 over RCA_0., Comment: 26 pages, 3 figures, to appear in Journal of Symbolic Logic

We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak Konig's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multi-valued function Sep and a natural notion of reducibility for multi-valued functions, we obtain a computational counterpart of the subsystem of second order arithmetic WKL_0. We study analogies and differences between WKL_0 and the class of Sep-computable multi-valued functions. Extending work of Brattka, we show that a natural multi-valued function associated with the Hahn-Banach Extension Theorem is Sep-complete., Comment: final version to appear in Notre Dame Journal of Formal Logic

We study the reverse mathematics of interval orders. We establish the logical strength of the implications between various definitions of the notion of interval order. We also consider the strength of different versions of the characterization theorem for interval orders: a partial order is an interval order if and only if it does not contain $2 \oplus 2$. We also study proper interval orders and their characterization theorem: a partial order is a proper interval order if and only if it contains neither $2 \oplus 2$ nor $3 \oplus 1$., Comment: 21 pages; to appear in Notre Dame Journal of Formal Logic; minor changes from the previous version

We study some natural sets arising in the theory of ordinary differential equations in one variable from the point of view of descriptive set theory and in particular classify them within the Borel hierarchy. We prove that the set of Cauchy problems for ordinary differential equations which have a unique solution is $\Pi^0_2$-complete and that the set of Cauchy problems which locally have a unique solution is $\Sigma^0_3$-complete. We prove that the set of Cauchy problems which have a global solution is $\Sigma^0_4$-complete and that the set of ordinary differential equation which have a global solution for every initial condition is $\Pi^0_3$-complete. We prove that the set of Cauchy problems for which both uniqueness and globality hold is $\Pi^0_2$-complete.

We study properties of complete separable metric spaces within the framework of subsystems of second order arithmetic. In particular we consider Lebesgue and Atsuji spaces. The former are those such that every open covering U has a Lebesgue number, i.e. a positive number q such that for every point x of the space, there exists an element of U which contains the ball of center x and radius q; the latter are those such that every continuous function into another complete separable metric space is uniformly continuous. The main results we obtain are the following: the statement "every compact space is Lebesgue" is equivalent to WKL_0; the statements "every perfect Lebesgue space is compact" and "every perfect Atsuji space is compact" are equivalent to ACA_0; the statement "every Lebesgue space is Atsuji" is provable in RCA_0; the statement "every Atsuji space is Lebesgue" is provable in ACA_0, but we do not know if it is equivalent to ACA_0. We also prove that the statement "the distance from a closed set is a continuous function" is equivalent to Pi^1_1-CA_0; the statements "there exists a complete separable metric space which is perfect and Heine-Borel compact (resp. Lebesgue, Atsuji)" are all equivalent to WKL_0.

We show that Nash-Williams' theorem asserting that the countable transfinite sequences of elements of a better-quasi-ordering ordered by embeddability form a better-quasi-ordering is provable in the subsystem of second order arithmetic Pi^1_1-CA_0 but is not equivalent to Pi^1_1-CA_0. We obtain some partial results towards the proof of this theorem in the weaker subsystem ATR_0 and we show that the minimality lemmas typical of wqo and bqo theory imply Pi^1_1-CA_0 and hence cannot be used in such a proof.

In this paper we prove that the set of countable bqos (viewed as a subset of the Cantor space) is Pi^1_2-complete. The notion of bqo or better quasi-ordering arises from combinatorics and is a generalization of the canonical example of a Pi^1_1-complete notion, i.e. that of countable well-ordering. The Pi^1_2-completeness of bqo was conjectured by Clote and proved by the author in his Ph.d. thesis: in this paper we prove it using Simpson's definition of bqo and as little bqo theory as possible.