Abstract ${\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.

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

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

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

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

Abstract No natural principle is currently known to be strictly between the arithmetic comprehension axiom (ACA 0 ) and Ramsey’s theorem for pairs ( $RT_2^2$ ) in reverse mathematics. The tree theorem for pairs ( $TT_2^2$ ) is however a good candidate. The tree theorem states that for every finite coloring over tuples of comparable nodes in the full binary tree, there is a monochromatic subtree isomorphic to the full tree. The principle $TT_2^2$ is known to lie between ACA 0 and $RT_2^2$ over RCA 0 , but its exact strength remains open. In this paper, we prove that $RT_2^2$ together with weak König’s lemma (WKL 0 ) does not imply $TT_2^2$ , thereby answering a question of Montálban. This separation is a case in point of the method of Lerman, Solomon and Towsner for designing a computability-theoretic property which discriminates between two statements in reverse mathematics. We therefore put the emphasis on the different steps leading to this separation in order to serve as a tutorial for separating principles in reverse mathematics.