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.

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

We prove an isomorphism theorem between the canonical denotation systems for large natural numbers and large countable ordinal numbers, linking two fundamental concepts in Proof Theory. The first one is fast-growing hierarchies. These are sequences of functions on $\mathbb {N}$ obtained through processes such as the ones that yield multiplication from addition, exponentiation from multiplication, etc. and represent the canonical way of speaking about large finite numbers. The second one is ordinal collapsing functions, which represent the best-known method of describing large computable ordinals.

We observe that fast-growing hierarchies can be naturally extended to functors on the categories of natural numbers and of linear orders. The isomorphism theorem asserts that the categorical extensions of binary fast-growing hierarchies to ordinals are isomorphic to denotation systems given by cardinal collapsing functions. As an application of this fact, we obtain a restatement of the subsystem $\Pi ^1_1$-${\mathsf {CA_0}}$ of analysis as a higher-type well-ordering principle asserting that binary fast-growing hierarchies preserve well-foundedness.

On the basis of Poincaré and Weyl’s view of predicativity as invariance, we develop an extensive framework for predicative, type-free first-order set theory in which $\Gamma _0$ and much bigger ordinals can be defined as von Neumann ordinals. This refutes the accepted view of $\Gamma _0$ as the “limit of predicativity”.

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.

There exist two main notions of typicality in computability theory, namely, Cohen genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity, which is at the intersection of these two notions of typicality, and show that many basis theorems apply to partition genericity. More precisely, we prove that every co-hyperimmune set and every Kurtz random is partition generic, and that every partition generic set admits weak infinite subsets, for various notions of weakness. In particular, we answer a question of Kjos-Hanssen and Liu by showing that every Kurtz random admits an infinite subset which does not compute any set of positive effective Hausdorff dimension. Partition genericity is a partition regular notion, so these results imply many existing pigeonhole basis theorems.

Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing Jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof theoretic principles which are THAs. Until Barnes, Goh, and Shore [ta] revealed an array of theorems in graph theory living in this neighborhood, there was only one mathematical denizen. In this paper we introduce a new neighborhood of theorems which are almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own they are very weak. We generalize several conservativity classes ( $\Pi _{1}^{1}$ , r- $\Pi _{2}^{1}$ , and Tanaka) and show that all our examples (and many others) are conservative over RCA $_{0}$ in all these senses and weak in other recursion theoretic ways as well. We provide denizens, both mathematical and logical. These results answer a question raised by Hirschfeldt and reported in Montalbán [2011] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second order arithmetic.

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

We consider fragments of uniform reflection for formulas in the analytic hierarchy over theories of second order arithmetic. The main result is that for any second order arithmetic theory $T_0$ extending $\mathsf {RCA}_0$ and axiomatizable by a $\Pi ^1_{k+2}$ sentence, and for any $n\geq k+1$ ,

$$\begin{align*}T_0+ \mathrm{RFN}_{\varPi^1_{n+2}}(T) \ = \ T_0 + \mathrm{TI}_{\varPi^1_n}(\varepsilon_0), \end{align*}$$

$$\begin{align*}T_0+ \mathrm{RFN}_{\varSigma^1_{n+1}}(T) \ = \ T_0+ \mathrm{TI}_{\varPi^1_n}(\varepsilon_0)^{-}, \end{align*}$$

$T_0$

$\mathrm {TI}_{\varPi ^1_n}(\varepsilon _0)^{-}$

$\varepsilon _0$

$\varPi ^1_n$

Neo-Fregean logicists claim that Hume’s Principle (HP) may be taken as an implicit definition of cardinal number, true simply by fiat. A long-standing problem for neo-Fregean logicism is that HP is not deductively conservative over pure axiomatic second-order logic. This seems to preclude HP from being true by fiat. In this paper, we study Richard Kimberly Heck’s Two-Sorted Frege Arithmetic (2FA), a variation on HP which has been thought to be deductively conservative over second-order logic. We show that it isn’t. In fact, 2FA is not conservative over n-th order logic, for all $n \geq 2$. It follows that in the usual one-sorted setting, HP is not deductively Field-conservative over second- or higher-order logic.

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.

Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion-theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof-theoretic principles which are THAs. Until the papers reported on in this communication, there was only one mathematical example. Barnes, Goh, and Shore [1] analyze an array of ubiquity theorems in graph theory descended from Halin’s [9] work on rays in graphs. They seem to be typical applications of ACA $_{0}$ but are actually THAs. These results answer Question 30 of Montalbán’s Open Questions in Reverse Mathematics [19] and supply several other natural principles of different and unusual levels of complexity.

This work led in [25] to a new neighborhood of the reverse mathematical zoo: almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own are very weak. Denizens both mathematical and logical are provided. Generalizations of several conservativity classes ( $\Pi _{1}^{1}$ , r- $\Pi _{1}^{1}$ , and Tanaka) are defined and these ATHAs as well as many other principles are shown to be conservative over RCA $_{0}$ in all these senses and weak in other recursion-theoretic ways as well. These results answer a question raised by Hirschfeldt and reported in [19] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second-order arithmetic.

In this paper I argue for an association between impurity and explanatory power in contemporary mathematics. This proposal is defended against the ancient and influential idea that purity and explanation go hand-in-hand (Aristotle, Bolzano) and recent suggestions that purity/impurity ascriptions and explanatory power are more or less distinct (Section 1). This is done by analyzing a central and deep result of additive number theory, Szemerédi’s theorem, and various of its proofs (Section 2). In particular, I focus upon the radically impure (ergodic) proof due to Furstenberg (Section 3). Furstenberg’s ergodic proof is striking because it utilizes intuitively foreign and infinitary resources to prove a finitary combinatorial result and does so in a perspicuous fashion. I claim that Furstenberg’s proof is explanatory in light of its clear expression of a crucial structural result, which provides the “reason why” Szemerédi’s theorem is true. This is, however, rather surprising: how can such intuitively different conceptual resources “get a grip on” the theorem to be proved? I account for this phenomenon by articulating a new construal of the content of a mathematical statement, which I call structural content (Section 4). I argue that the availability of structural content saves intuitive epistemic distinctions made in mathematical practice and simultaneously explicates the intervention of surprising and explanatorily rich conceptual resources. Structural content also disarms general arguments for thinking that impurity and explanatory power might come apart. Finally, I sketch a proposal that, once structural content is in hand, impure resources lead to explanatory proofs via suitably understood varieties of simplification and unification (Section 5).

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