Where Pigeonhole Principles meet König Lemmas
David Belanger, C. T. Chong, Wei Wang, Wong, Tin Lok, Yue Yang · arXiv (Cornell University) · 2019
We study the pigeonhole principle for $Σ_2$-definable injections with domain twice as large as the codomain, and the weak König lemma for $Δ^0_2$-definable trees in which every level has at least half of the possible nodes. We show that the latter implies the existence of $2$-random reals, and is conservative over the former. We also show that the former is strictly weaker than the usual pigeonhole principle for $Σ_2$-definable injections.