Pigeons do not jump high

DOI10.1016/J.AIM.2019.06.026zbMATH Open1441.03013arXiv1803.09771OpenAlexW2963621191MaRDI QIDQ2313367FDOQ2313367

Authors: Benoit Monin, Ludovic Patey 

Publication date: 19 July 2019

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: The infinite pigeonhole principle for 2-partitions asserts the existence, for every set $A$, of an infinite subset of $A$ or of its complement. In this paper, we develop a new notion of forcing enabling a fine analysis of the computability-theoretic features of the pigeonhole principle. We deduce various consequences, such as the existence, for every set $A$, of an infinite subset of it or its complement of non-high degree. We also prove that every $Delt{a}_3^0$ set has an infinite low${}_3$ solution and give a simpler proof of Liu's theorem that every set has an infinite subset in it or its complement of non-PA degree.

Full work available at URL: https://arxiv.org/abs/1803.09771

Recommendations

• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• A packed Ramsey’s theorem and computability theory
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• The thin set theorem for pairs implies DNR
• scientific article; zbMATH DE number 7377981
• Partial orders and immunity in reverse mathematics
• Partial orders and immunity in reverse mathematics
• The weakness of being cohesive, thin or free in reverse mathematics

zbMATH Keywords

reverse mathematicsRamsey's theoremMathias forcingSRTpigeonhole principle

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35)

Cites Work

• Subsystems of second order arithmetic
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• ∏ 0 1 Classes and Degrees of Theories
• On the strength of Ramsey's theorem for pairs
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• A cohesive set which is not high
• Ramsey's theorem and recursion theory
• On the strength of Ramsey's theorem
• Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom
• The strength of the rainbow Ramsey Theorem
• Cohesive sets and rainbows
• Title not available (Why is that?)
• A \(\Delta_2^0\) set with no infinite low subset in either it or its complement
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• Generics for computable Mathias forcing
• Some logically weak Ramseyan theorems
• The definability strength of combinatorial principles
• Partition Theorems and Computability Theory
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• Reverse mathematics and a Ramsey-type König's lemma
• The thin set theorem for pairs implies DNR
• Ramsey's theorem and cone avoidance
• The weakness of being cohesive, thin or free in reverse mathematics
• The polarized Ramsey's theorem
• Cone avoiding closed sets
• Combinatorial principles between \(\text{RRT}_2^2\) and \(\text{RT}_2^2\)
• Iterative forcing and hyperimmunity in reverse mathematics
• Open questions about Ramsey-type statements in reverse mathematics

Cited In (6)

• Computing sets from all infinite subsets
• Isols and the pigeonhole principle
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• Ramsey-like theorems and moduli of computation
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma

This page was built for publication: Pigeons do not jump high

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