Where Pigeonhole Principles meet K\"onig Lemmas

Publication date: 7 December 2019

Abstract: We study the pigeonhole principle for

S i g m a_{2}

-definable injections with domain twice as large as the codomain, and the weak K"onig lemma for

D e l t a_{2}^{0}

-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

S i g m a_{2}

-definable injections.

This page was built for publication: Where Pigeonhole Principles meet K\"onig Lemmas