The weakness of the pigeonhole principle under hyperarithmetical\n reductions

2019/05/20 by Benoît Monin, Ludovic Patey, Monin, Benoit +1
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Advanced Topology and Set Theory #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1905.08425

Abstract

The infinite pigeonhole principle for 2-partitions (\RT¹₂)\nasserts the existence, for every set A, of an infinite subset of A or of\nits complement. In this paper, we study the infinite pigeonhole principle from\na computability-theoretic viewpoint. We prove in particular that\n\RT¹₂ admits strong cone avoidance for arithmetical and\nhyperarithmetical reductions. We also prove the existence, for every\n\Δ⁰_n set, of an infinite low_n subset of it or its complement. This\nanswers a question of Wang. For this, we design a new notion of forcing which\ngeneralizes the first and second-jump control of Cholak, Jockusch and Slaman.\n

Related

• Pigeons do not jump high
• 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