Pigeons do not jump high

DOI10.1016/J.AIM.2019.06.026MaRDI QIDQ2313367zbMATHOpenAlexFDO

Authors Benoit Monin, Ludovic Patey

Publication date 19 July 2019

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

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

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)

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.

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

Cites work

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

Cited in

(6)

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

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)