The weakness of the pigeonhole principle under hyperarithmetical reductions

&
Journal of Mathematical Logic 21 (3):2150013 (2020)
  Copy   BIBTEX

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 study the infinite pigeonhole pr...

Categories

Keywords

Reprint years

DOI

10.1142/s0219061321500136

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
An induction principle and pigeonhole principles for k-finite sets.Andreas Blass - 1995 - Journal of Symbolic Logic 60 (4):1186-1193.
Pigeonhole and Choice Principles.Wolfgang Degen - 2000 - Mathematical Logic Quarterly 46 (3):313-334.
On Tao's “finitary” infinite pigeonhole principle.Jaime Gaspar & Ulrich Kohlenbach - 2010 - Journal of Symbolic Logic 75 (1):355-371.
Maximal almost disjoint families, determinacy, and forcing.Karen Bakke Haga, David Schrittesser & Asger Törnquist - 2021 - Journal of Mathematical Logic 22 (1).
Guessing models and the approachability ideal.Rahman Mohammadpour & Boban Veličković - 2020 - Journal of Mathematical Logic 21 (2):2150003.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
Canonical fragments of the strong reflection principle.Gunter Fuchs - 2021 - Journal of Mathematical Logic 21 (3):2150023.
Isols and the pigeonhole principle.J. C. E. Dekker & E. Ellentuck - 1989 - Journal of Symbolic Logic 54 (3):833-846.
What causes failure to apply the Pigeonhole Principle in simple reasoning problems?Hugo Mercier, Guy Politzer & Dan Sperber - 2017 - Thinking and Reasoning 23 (2):184-189.
A note on the E1 collection scheme and fragments of bounded arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2010 - Mathematical Logic Quarterly 56 (2):126-130.
On the set-theoretic strength of the existence of disjoint cofinal sets in posets without maximal elements.Paul Howard, Denis I. Saveliev & Eleftherios Tachtsis - 2016 - Mathematical Logic Quarterly 62 (3):155-176.
Iterability for (transfinite) stacks.Farmer Schlutzenberg - 2021 - Journal of Mathematical Logic 21 (2):2150008.
An exponential separation between the parity principle and the pigeonhole principle.Paul Beame & Toniann Pitassi - 1996 - Annals of Pure and Applied Logic 80 (3):195-228.
A model-theoretic characterization of the weak pigeonhole principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.

Analytics

Added to PP
2020-10-02

Downloads
21 (#695,936)

6 months
12 (#178,599)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Partition Genericity and Pigeonhole Basis Theorems.Benoit Monin & Ludovic Patey - forthcoming - Journal of Symbolic Logic:1-29.

Add more citations

References found in this work

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
Recursive well-orderings.Clifford Spector - 1955 - Journal of Symbolic Logic 20 (2):151-163.
RT₂² does not imply WKL₀.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.

View all 10 references / Add more references