The weakness of the pigeonhole principle under hyperarithmetical reductions
Benoît Monin, Ludovic Patey · arXiv (Cornell University) · 2019
The infinite pigeonhole principle for 2-partitions ($\\mathsf{RT}^1_2$) asserts the existence, for every set $A$, of an infinite subset of $A$ or of its complement. In this paper, we study the infinite pigeonhole principle from a computability-theoretic viewpoint. We prove in particular that $\\mathsf{RT}^1_2$ admits strong cone avoidance for arithmetical and hyperarithmetical reductions. We also prove the existence, for every $\\Delta^0_n$ set, of an infinite low${}_n$ subset of it or its complement. This answers a question of Wang. For this, we design a new notion of forcing which generalizes the first and second-jump control of Cholak, Jockusch and Slaman.