Pigeons do not jump high (Q2313367): Difference between revisions

The authors prove new computability theoretic results related to the pigeonhole principle for two colors. They show that for every set \(A\) there is an infinite non-high set \(H\) with \(H \subseteq A\) or \(H \subseteq \bar A\). Also, they show that for every \(\Delta^0_3\) set \(A\) there is an infinite \(\text{low}_3\) set \(H\) with \(H \subseteq A\) or \(H \subseteq \bar A\). The proofs use a new notion of forcing particularly adapted to the fine analysis of computability theoretic aspects of the pigeonhole principle. This forcing is used to succinctly prove that for every set \(A\) there is an infinite non-PA set \(H\) with \(H \subseteq A\) or \(H \subseteq \bar A\), the main combinatorial lemma of \textit{J. Liu} [J. Symb. Log. 77, No. 2, 609--620 (2012; Zbl 1245.03095)]. The paper explains the connections between computability theoretic results and a number of open questions in reverse mathematics. Subsequently, the authors announced an answer to Question 1.1 in [``\(\mathsf{SRT}^2_2\) does not imply \(\mathsf{RT}^2_2\) in \(\omega\)-models'', Preprint, \url{arxiv:1905.08427}].