Pigeons do not jump high

2018/03/26 by Monin, Benoit, Patey, Ludovic
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1803.09771

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 Δ⁰₃ set has an infinite low₃ 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.

Related

• The weakness of the pigeonhole principle under hyperarithmetical\n reductions
• The reverse mathematics of the pigeonhole hierarchy
• Conservation Strength of The Infinite Pigeonhole Principle for Trees
• Models of Bounded Arithmetic and variants of Pigeonhole Principle
• Where Pigeonhole Principles meet König Lemmas