Where pigeonhole principles meet König lemmas
Rattachement africain : sg, us, be. Niveau de preuve : code pays fourni par la source.
Le résumé fourni par la source
We study the pigeonhole principle for Σ 2 \Sigma _2 -definable injections with domain twice as large as the codomain, and the weak König lemma for Δ 2 0 \Delta ^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 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 \Sigma _2 -definable injections.
Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.
Le contrôle bibliographique ouvert
DOI retrouvé dans Crossref DOI retrouvé ; titre concordant.
- Titre Crossref
- Where pigeonhole principles meet König lemmas
- Date Crossref
- 25/08/2021
- Éditeur
- American Mathematical Society (AMS)
- Type
- journal-article
Ce recoupement confirme des métadonnées liées au DOI. Il ne confirme ni la méthode ni les conclusions de l’étude, et il ne compte pas comme une seconde source scientifique indépendante.
Où se fait cette recherche
-
National University of Singapore Department of Mathematics pays non établi dans la noticeUniversité ou école supérieure
-
Center for Discrete Mathematics and Theoretical Computer Science pays non établi dans la noticeStructure de recherche
-
Ghent University Department of Mathematics: Analysis pays non établi dans la noticeUniversité ou école supérieure
-
Sun Yat-Sen University Institute of Logic and Cognition and Department of Philosophy pays non établi dans la noticeUniversité ou école supérieure
Department of Mathematics — National University of Singapore, Center for Discrete Mathematics and Theoretical Computer Science et Department of Mathematics: Analysis — Ghent University, avec 1 autre affiliation.
Une affiliation ne permet pas de déduire la nationalité d’un auteur.