{
  "id": "2407.01236",
  "version": "v1",
  "published": "2024-07-01T12:26:37.000Z",
  "updated": "2024-07-01T12:26:37.000Z",
  "title": "The reverse mathematics of the pigeonhole hierarchy",
  "authors": [
    "Quentin Le Houérou",
    "Ludovic Levy Patey",
    "Ahmed Mimouni"
  ],
  "categories": [
    "math.LO",
    "cs.LO"
  ],
  "abstract": "The infinite pigeonhole principle for $k$ colors ($\\mathsf{RT}_k$) states, for every $k$-partition $A_0 \\sqcup \\dots \\sqcup A_{k-1} = \\mathbb{N}$, the existence of an infinite subset~$H \\subseteq A_i$ for some~$i < k$. This seemingly trivial combinatorial principle constitutes the basis of Ramsey's theory, and plays a very important role in computability and proof theory. In this article, we study the infinite pigeonhole principle at various levels of the arithmetical hierarchy from both a computability-theoretic and reverse mathematical viewpoint. We prove that this hierarchy is strict over~$\\mathsf{RCA}_0$ using an elaborate iterated jump control construction, and study its first-order consequences. This is part of a large meta-mathematical program studying the computational content of combinatorial theorems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-01T12:26:37.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03B30",
      "03F30",
      "05D10",
      "03D80",
      "F.4.1"
    ],
    "keywords": [
      "pigeonhole hierarchy",
      "reverse mathematics",
      "infinite pigeonhole principle",
      "seemingly trivial combinatorial principle constitutes",
      "elaborate iterated jump control construction"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}