Ramsey’s theorem states that for any coloring of then-element subsets of ℕ with finitely many colors, there is an infinite setHsuch that alln-element subsets ofHhave the same color. The strength of consequences of Ramsey’s theorem has been extensively studied in reverse mathematics and under various reducibilities, namely, computable reducibility and uniform reducibility. Our understanding of the combinatorics of Ramsey’s theorem and its consequences has been greatly improved over the past decades. In this paper, we state some questions which naturally arose (...) during this study. The inability to answer those questions reveals some gaps in our understanding of the combinatorics of Ramsey’s theorem. (shrink)

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

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω (...) with its set of predecessors, so n = {0, 1, 2, …, n − 1}. (shrink)

Let the chain antichain principle (CAC) be the statement that each partial order on $\mathbb{N}$ possesses an infinite chain or an infinite antichain. Chong, Slaman, and Yang recently proved using forcing over nonstandard models of arithmetic that CAC is $\Pi^1_1$-conservative over $\text{RCA}_0+\Pi^0_1\text{-CP}$ and so in particular that CAC does not imply $\Sigma^0_2$-induction. We provide here a different purely syntactical and constructive proof of the statement that CAC (even together with WKL) does not imply $\Sigma^0_2$-induction. In detail we show using a (...) refinement of Howard's ordinal analysis of bar recursion that $\text{WKL}_0^\omega+\text{CAC}$ is $\Pi^0_2$-conservative over PRA and that one can extract primitive recursive realizers for such statements. Moreover, our proof is finitary in the sense of Hilbert's program. CAC implies that every sequence of $\mathbb{R}$ has a monotone subsequence. This Bolzano-Weierstraß}-like principle is commonly used in proofs. Our result makes it possible to extract primitive recursive terms from such proofs. We also discuss the Erdős-Moser principle, which—taken together with CAC—is equivalent to $\text{RT}^2_2$. (shrink)

The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ but not (...) in general. We also answer the analogs of two well-known questions about the stable Ramsey's theorem by showing that our weaker principle does not imply COH or WKL 0 in the context of reverse mathematics. (shrink)

We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for ${\Sigma^0_2}$ formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs.

We study the reverse mathematics of pigeonhole principles for finite powers of the ordinal $\omega$ . Four natural formulations are presented, and their relative strengths are compared. In the analysis of the pigeonhole principle for $\omega^{2}$ , we uncover two weak variants of Ramsey’s theorem for pairs.