Where Pigeonhole Principles meet K\"onig Lemmas

DOI10.1090/TRAN/8494MaRDI QIDQ6330656arXivFDO

Authors David R. Belanger, C. T. Chong, Wei Wang, Tin Lok Wong, Yue Yang

Publication date 7 December 2019

Published in arXiv

Full work available at URL https://doi.org/10.1090/TRAN/8494

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Foundations of classical theories (including reverse mathematics) (03B30) First-order arithmetic and fragments (03F30) Second- and higher-order arithmetic and fragments (03F35)

arXiv classification

math.LO

Abstract: We study the pigeonhole principle for $Sigm{a}_2$-definable injections with domain twice as large as the codomain, and the weak K"onig lemma for $Delt{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 $Sigm{a}_2$-definable injections.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330656)