Pigeons do not jump high

Benoit Monin (1) , Ludovic Patey (2, 3)

1 LACL - Laboratoire d'Algorithmique Complexité et Logique
2 AGL - Algèbre, géométrie, logique
3 CNRS - Centre National de la Recherche Scientifique

The infinite pigeonhole principle for 2-partitions asserts the existence, for every set $A$, of an infinite subset of $A$ or of its complement. In this paper, we develop a new notion of forcing enabling a fine analysis of the computability-theoretic features of the pigeonhole principle. We deduce various consequences, such as the existence, for every set $A$, of an infinite subset of it or its complement of non-high degree. We also prove that every $\Delta^0_3$ set has an infinite low${}_3$ solution and give a simpler proof of Liu's theorem that every set has an infinite subset in it or its complement of non-PA degree.

Domaines: Logique [math.LO]

Benoit Monin, Ludovic Patey. Pigeons do not jump high. Advances in Mathematics, 2019, 352, pp.1066--1095. ⟨10.1016/j.aim.2019.06.026⟩. ⟨hal-01888793⟩