Advanced search
1 file | 333.90 KB Add to list

Where pigeonhole principles meet Koenig lemmas

(2020) arXiv.
Author
Organization
Abstract
We study the pigeonhole principle for Σ2-definable injections with domain twice as large as the codomain, and the weak König lemma for Δ02-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.

Downloads

  • 1912.03487.pdf
    • full text (Author's original)
    • |
    • open access
    • |
    • PDF
    • |
    • 333.90 KB

Citation

Please use this url to cite or link to this publication:

MLA
Bélanger, David, et al. “Where Pigeonhole Principles Meet Koenig Lemmas.” ArXiv, 2020.
APA
Bélanger, D., Chong, C., Wang, W., Wong, T. L., & Yang, Y. (2020). Where pigeonhole principles meet Koenig lemmas. arXiv.
Chicago author-date
Bélanger, David, Chitat Chong, Wei Wang, Tin Lok Wong, and Yue Yang. 2020. “Where Pigeonhole Principles Meet Koenig Lemmas.” ArXiv.
Chicago author-date (all authors)
Bélanger, David, Chitat Chong, Wei Wang, Tin Lok Wong, and Yue Yang. 2020. “Where Pigeonhole Principles Meet Koenig Lemmas.” ArXiv.
Vancouver
1.
Bélanger D, Chong C, Wang W, Wong TL, Yang Y. Where pigeonhole principles meet Koenig lemmas. arXiv. 2020.
IEEE
[1]
D. Bélanger, C. Chong, W. Wang, T. L. Wong, and Y. Yang, “Where pigeonhole principles meet Koenig lemmas,” arXiv. 2020.
@misc{8669009,
  abstract     = {We study the pigeonhole principle for Σ2-definable injections with domain twice as large as the codomain, and the weak König lemma for Δ02-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.},
  author       = {Bélanger, David and Chong, Chitat and Wang, Wei and Wong, Tin Lok and Yang, Yue},
  language     = {eng},
  pages        = {33},
  series       = {arXiv},
  title        = {Where pigeonhole principles meet Koenig lemmas},
  url          = {https://arxiv.org/abs/1912.03487},
  year         = {2020},
}