The weakness of the pigeonhole principle under hyperarithmetical reductions.

The infinite pigeonhole principle for 2-partitions ( R T 2 1 ) 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 R T 2 1 admits strong cone avoidance for arithmetical and hyperarithmetical reductions. We also prove the existence, for every Δ n 0 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. [ABSTRACT FROM AUTHOR]