We show that there exists a recursive coloring function c such that any $\Pi ^0_3$ set is not a solution to c for Hindman’s theorem. We also show that there exists a recursive coloring function c such that any $\Delta ^0_3$ set is not a solution to c for Hindman’s theorem restricted to sums of at most three numbers.

In this thesis, we study the complexity of some mathematical problems: in particular, those arising in computable analysis and algorithmic learning theory for algebraic structures. Our study is not limited to these two areas: indeed, in both cases, the results we obtain are tightly connected to ideas and tools coming from different areas of mathematical logic, including for example descriptive set theory and reverse mathematics.

After giving the necessary preliminaries, we first study the uniform computational strength of the Cantor–Bendixson theorem in the Weihrauch lattice. This work falls into the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. We concentrate on problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. As far as we know, this is the first systematic study of problems at the level of $\mathbf {\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.

We continue considering problems related to (induced) subgraphs. We provide results on the (effective) Wadge complexity of sets of graphs, that are also used to determine the Weihrauch degree of certain decision problems. The decision problems we consider are defined for a fixed graph G, and they take as input a graph H, answering whether G is an (induced) subgraph of H: we also consider the opposite problem (i.e., answering whether H is an induced subgraph of G). We conclude this part on (induced) subgraphs considering the Weihrauch degree of “search problems.”These problems are defined for a fixed graph G, and they take as input a graph H such that G is an (induced) subgraph H: the output is a copy of G in H. In both cases, we highlight differences and analogies between the subgraph and the induced subgraph relation.

We then move our attention to algorithmic learning theory, and we present the framework we use to study the learnability of families of algebraic structures: here, given a countable family of pairwise nonisomorphic structures $\mathfrak {K}$, a learner receives larger and larger pieces of an arbitrary copy of a structure in $\mathfrak {K}$ and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. We say that $\mathfrak {K}$ is learnable if there exists a learner which eventually stabilizes to a correct guess. The framework was lacking a method for comparing the complexity of nonlearnable families, and so we propose a solution to this problem using tools coming from invariant descriptive set theory. To do so, we first prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation $E_0$ of eventual agreement on infinite binary sequences and then, replacing $E_0$ with Borel equivalence relations of higher complexity, we obtain a new hierarchy of learning problems. This leads to the notion of E-learnability, where a family of structures $\mathfrak {K}$ is E-learnable, for a Borel equivalence relation E, if there is a continuous reduction from the isomorphism relation associated with $\mathfrak {K}$ to E. It is then natural to ask how the notion of E-learnability interacts with “classical” learning paradigms.

Finally, we study the number of mind changes that a learner needs to learn a given family, both from a topological and a combinatorial point of view, and we consider how the complexity of a learner (in terms of Turing reducibility) affects the number of mind changes for learning a given family.

Abstract prepared by Vittorio Cipriani.

E-mail: [email protected].

URL: https://air.uniud.it/handle/11390/1252226.

This paper initiates the reverse mathematics of social choice theory, studying Arrow’s impossibility theorem and related results including Fishburn’s possibility theorem and the Kirman–Sondermann theorem within the framework of reverse mathematics. We formalise fundamental notions of social choice theory in second-order arithmetic, yielding a definition of countable society which is tractable in ${\mathsf {RCA}}_0$. We then show that the Kirman–Sondermann analysis of social welfare functions can be carried out in ${\mathsf {RCA}}_0$. This approach yields a proof of Arrow’s theorem in ${\mathsf {RCA}}_0$, and thus in $\mathrm {PRA}$, since Arrow’s theorem can be formalised as a $\Pi ^0_1$ sentence. Finally we show that Fishburn’s possibility theorem for countable societies is equivalent to ${\mathsf {ACA}}_0$ over ${\mathsf {RCA}}_0$.

The smooth development of large parts of mathematics hinges on the idea that some sets are ‘small’ or ‘negligible’ and can therefore be ignored for a given purpose. The perhaps most famous smallness notion, namely ‘measure zero’, originated with Lebesgue, while a second smallness notion, namely ‘meagre’ or ‘first category’, originated with Baire around the same time. The associated Baire category theorem is a central result governing the properties of meagre (and related) sets, while the same holds for Tao’s pigeonhole principle for measure spaces and measure zero sets. In this paper, we study these theorems in Kohlenbach’s higher-order Reverse Mathematics, identifying a considerable number of equivalent and robust theorems. The latter involve most basic properties of semi-continuous and pointwise discontinuous functions, Blumberg’s theorem, Riemann integration, and Volterra’s early work circa 1881. All the aforementioned theorems fall (far) outside of the Big Five of Reverse Mathematics, and we investigate natural restrictions like Baire 1 and quasi-continuity that make these theorems provable again in the Big Five (or similar). Finally, despite the fundamental differences between measure and category, the proofs of our equivalences turn out to be similar.

The notion of countable well order admits an alternative definition in terms of embeddings between initial segments. We use the framework of reverse mathematics to investigate the logical strength of this definition and its connection with Fraïssé’s conjecture, which has been proved by Laver. We also fill a small gap in Shore’s proof that Fraïssé’s conjecture implies arithmetic transfinite recursion over $\mathbf {RCA}_0$, by giving a new proof of $\Sigma ^0_2$-induction.

The uncountability of $\mathbb {R}$ is one of its most basic properties, known far outside of mathematics. Cantor’s 1874 proof of the uncountability of $\mathbb {R}$ even appears in the very first paper on set theory, i.e., a historical milestone. In this paper, we study the uncountability of ${\mathbb R}$ in Kohlenbach’s higher-order Reverse Mathematics (RM for short), in the guise of the following principle:

$$\begin{align*}\mathit{for \ a \ countable \ set } \ A\subset \mathbb{R}, \mathit{\ there \ exists } \ y\in \mathbb{R}\setminus A. \end{align*}$$

An important conceptual observation is that the usual definition of countable set—based on injections or bijections to ${\mathbb N}$—does not seem suitable for the RM-study of mainstream mathematics; we also propose a suitable (equivalent over strong systems) alternative definition of countable set, namely union over ${\mathbb N}$ of finite sets; the latter is known from the literature and closer to how countable sets occur ‘in the wild’. We identify a considerable number of theorems that are equivalent to the centred theorem based on our alternative definition. Perhaps surprisingly, our equivalent theorems involve most basic properties of the Riemann integral, regulated or bounded variation functions, Blumberg’s theorem, and Volterra’s early work circa 1881. Our equivalences are also robust, promoting the uncountability of ${\mathbb R}$ to the status of ‘big’ system in RM.

In their logical analysis of theorems about disjoint rays in graphs, Barnes, Shore, and the author (hereafter BGS) introduced a weak choice scheme in second-order arithmetic, called the $\Sigma ^1_1$ axiom of finite choice (hereafter finite choice). This is a special case of the $\Sigma ^1_1$ axiom of choice ($\Sigma ^1_1\text {-}\mathsf {AC}_0$) introduced by Kreisel. BGS showed that $\Sigma ^1_1\text {-}\mathsf {AC}_0$ suffices for proving many of the aforementioned theorems in graph theory. While it is not known if these implications reverse, BGS also showed that those theorems imply finite choice (in some cases, with additional induction assumptions). This motivated us to study the proof-theoretic strength of finite choice. Using a variant of Steel forcing with tagged trees, we show that finite choice is not provable from the $\Delta ^1_1$-comprehension scheme (even over $\omega $-models). We also show that finite choice is a consequence of the arithmetic Bolzano–Weierstrass theorem (introduced by Friedman and studied by Conidis), assuming $\Sigma ^1_1$-induction. Our results were used by BGS to show that several theorems in graph theory cannot be proved using $\Delta ^1_1$-comprehension. Our results also strengthen results of Conidis.

${\mathsf {CAC\ for\ trees}}$ is the statement asserting that any infinite subtree of $\mathbb {N}^{<\mathbb {N}}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a reverse mathematical viewpoint. We prove that ${\mathsf {CAC\ for\ trees}}$ is robust, that is, there exist several characterizations, some of which already appear in the literature, namely, the statement $\mathsf {SHER}$ introduced by Dorais et al. [8], and the statement $\mathsf {TAC}+\mathsf {B}\Sigma ^0_2$ where $\mathsf {TAC}$ is the tree antichain theorem introduced by Conidis [6]. We show that ${\mathsf {CAC\ for\ trees}}$ is computationally very weak, in that it admits probabilistic solutions.

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

Reverse Mathematics (RM hereafter) is a program in the foundations of mathematics where the aim is to identify the minimal axioms needed to prove a given theorem from ordinary, i.e., non-set theoretic, mathematics. This program has unveiled surprising regularities: the minimal axioms are very often equivalent to the theorem over the base theory, a weak system of ‘computable mathematics’, while most theorems are either provable in this base theory, or equivalent to one of only four logical systems. The latter plus the base theory are called the ‘Big Five’ and the associated equivalences are robust following Montalbán, i.e., stable under small variations of the theorems at hand. Working in Kohlenbach’s higher-order RM, we obtain two new and long series of equivalences based on theorems due to Bolzano, Weierstrass, Jordan, and Cantor; these equivalences are extremely robust and have no counterpart among the Big Five systems. Thus, higher-order RM is much richer than its second-order cousin, boasting at least two extra ‘Big’ systems.

We study the first-order consequences of Ramsey’s Theorem for k-colourings of n-tuples, for fixed $n, k \ge 2$ , over the relatively weak second-order arithmetic theory $\mathrm {RCA}^*_0$ . Using the Chong–Mourad coding lemma, we show that in a model of $\mathrm {RCA}^*_0$ that does not satisfy $\Sigma ^0_1$ induction, $\mathrm {RT}^n_k$ is equivalent to its relativization to any proper $\Sigma ^0_1$ -definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe.

We give a complete axiomatization of the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^n_k$ for $n \ge 3$ . We show that they form a non-finitely axiomatizable subtheory of $\mathrm {PA}$ whose $\Pi _3$ fragment coincides with $\mathrm {B} \Sigma _1 + \exp $ and whose $\Pi _{\ell +3}$ fragment for $\ell \ge 1$ lies between $\mathrm {I} \Sigma _\ell \Rightarrow \mathrm {B} \Sigma _{\ell +1}$ and $\mathrm {B} \Sigma _{\ell +1}$ . We also give a complete axiomatization of the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^2_k + \neg \mathrm {I} \Sigma _1$ . In general, we show that the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^2_k$ form a subtheory of $\mathrm {I} \Sigma _2$ whose $\Pi _3$ fragment coincides with $\mathrm {B} \Sigma _1 + \exp $ and whose $\Pi _4$ fragment is strictly weaker than $\mathrm {B} \Sigma _2$ but not contained in $\mathrm {I} \Sigma _1$ .

Additionally, we consider a principle $\Delta ^0_2$ - $\mathrm {RT}^2_2$ which is defined like $\mathrm {RT}^2_2$ but with both the $2$ -colourings and the solutions allowed to be $\Delta ^0_2$ -sets rather than just sets. We show that the behaviour of $\Delta ^0_2$ - $\mathrm {RT}^2_2$ over $\mathrm {RCA}_0 + \mathrm {B}\Sigma ^0_2$ is in many ways analogous to that of $\mathrm {RT}^2_2$ over $\mathrm {RCA}^*_0$ , and that $\mathrm {RCA}_0 + \mathrm {B} \Sigma ^0_2 + \Delta ^0_2$ - $\mathrm {RT}^2_2$ is $\Pi _4$ - but not $\Pi _5$ -conservative over $\mathrm {B} \Sigma _2$ . However, the statement we use to witness failure of $\Pi _5$ -conservativity is not provable in $\mathrm {RCA}_0 +\mathrm {RT}^2_2$ .

Cantor’s first set theory paper (1874) establishes the uncountability of ${\mathbb R}$ . We study this most basic mathematical fact formulated in the language of higher-order arithmetic. In particular, we investigate the logical and computational properties of ${\mathsf {NIN}}$ (resp. ${\mathsf {NBI}}$ ), i.e., the third-order statement there is no injection resp. bijection from  $[0,1]$ to ${\mathbb N}$ . Working in Kohlenbach’s higher-order Reverse Mathematics, we show that ${\mathsf {NIN}}$ and ${\mathsf {NBI}}$ are hard to prove in terms of (conventional) comprehension axioms, while many basic theorems, like Arzelà’s convergence theorem for the Riemann integral (1885), are shown to imply ${\mathsf {NIN}}$ and/or ${\mathsf {NBI}}$ . Working in Kleene’s higher-order computability theory based on S1–S9, we show that the following fourth-order process based on ${\mathsf {NIN}}$ is similarly hard to compute: for a given $[0,1]\rightarrow {\mathbb N}$ -function, find reals in the unit interval that map to the same natural number.

The thin set theorem for n-tuples and k colors ( $\operatorname {\mathrm {\sf {TS}}}^n_k$ ) states that every k-coloring of $[\mathbb {N}]^n$ admits an infinite set of integers H such that $[H]^n$ avoids at least one color. In this paper, we study the combinatorial weakness of the thin set theorem in reverse mathematics by proving neither $\operatorname {\mathrm {\sf {TS}}}^n_k$ , nor the free set theorem ( $\operatorname {\mathrm {\sf {FS}}}^n$ ) imply the Erdős–Moser theorem ( $\operatorname {\mathrm {\sf {EM}}}$ ) whenever k is sufficiently large (answering a question of Patey and giving a partial result towards a question of Cholak Giusto, Hirst and Jockusch). Given a problem $\mathsf {P}$ , a computable instance of $\mathsf {P}$ is universal iff its solution computes a solution of any other computable $\mathsf {P}$ -instance. It has been established that most of Ramsey-type problems do not have a universal instance, but the case of Erdős–Moser theorem remained open so far. We prove that Erdős–Moser theorem does not admit a universal instance (answering a question of Patey).

In previous work, the author has shown that $\Pi ^1_1$ -induction along $\mathbb N$ is equivalent to a suitable formalization of the statement that every normal function on the ordinals has a fixed point. More precisely, this was proved for a representation of normal functions in terms of Girard’s dilators, which are particularly uniform transformations of well orders. The present paper works on the next type level and considers uniform transformations of dilators, which are called 2-ptykes. We show that $\Pi ^1_2$ -induction along $\mathbb N$ is equivalent to the existence of fixed points for all 2-ptykes that satisfy a certain normality condition. Beyond this specific result, the paper paves the way for the analysis of further $\Pi ^1_4$ -statements in terms of well ordering principles.

The Jordan decomposition theorem states that every function $f \colon \, [0,1] \to \mathbb {R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf {RCA}_{0}$ , a stronger version of Jordan’s result where all functions are continuous is equivalent to $\mathsf {ACA}_0$ , while the version stated is equivalent to ${\textsf {WKL}}_{0}$ . The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to ${\textsf {WWKL}}_{0}$ . To state this equivalence in a meaningful way, we develop a theory of Martin–Löf randomness over $\mathsf {RCA}_0$ .

In this work we investigate the Weihrauch degree of the problem Decreasing Sequence ( $\mathsf {DS}$ ) of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence ( $\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.

Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$ , there exists a computable k-coloring of $[\omega ]^n$ whose solutions compute the halting set. On the other hand, for every computable k-coloring of $[\omega ]^2$ and every noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _T H$ . The latter property is known as cone avoidance.

In this article, we design a natural class of Ramsey-like theorems encompassing many statements studied in reverse mathematics. We prove that this class admits a maximal statement satisfying cone avoidance and use it as a criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every k-coloring of $[\omega ]^n$ , of an infinite subdomain $H \subseteq \omega $ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions.

A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$ , to find a solution relative to which A is still noncomputable.

In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting.

In a recent paper by M. Rathjen and the present author it has been shown that the statement “every normal function has a derivative” is equivalent to $\Pi ^1_1$ -bar induction. The equivalence was proved over $\mathbf {ACA_0}$ , for a suitable representation of normal functions in terms of dilators. In the present paper, we show that the statement “every normal function has at least one fixed point” is equivalent to $\Pi ^1_1$ -induction along the natural numbers.