The reverse mathematics of the pigeonhole hierarchy
Published:
The infinite pigeonhole principle for \( k \) colors \( \mathsf{RT}_{k}^1 \) 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.
Recommended citation: Q. Le Houérou, A. Mimouni and L. Levy Patey (2024). "The reverse mathematics of the pigeonhole hierarchy."
Download Paper