The infinite pigeonhole principle for 2-partitions (RT21) 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 RT21 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 et al.
展开▼
