The reverse mathematics of the pigeonhole hierarchy

The infinite pigeonhole principle for $k$ colors (${\mathsf{R}\mathsf{T}}_k$) states, for every $k$-partition $A_0\bigsqcup \cdots \bigsqcup 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{R}\mathsf{C}\mathsf{A}}_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.