Partition Genericity and Pigeonhole Basis Theorems

Journal of Symbolic Logic:1-29 (forthcoming)
  Copy   BIBTEX

Abstract

There exist two main notions of typicality in computability theory, namely, Cohen genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity, which is at the intersection of these two notions of typicality, and show that many basis theorems apply to partition genericity. More precisely, we prove that every co-hyperimmune set and every Kurtz random is partition generic, and that every partition generic set admits weak infinite subsets, for various notions of weakness. In particular, we answer a question of Kjos-Hanssen and Liu by showing that every Kurtz random admits an infinite subset which does not compute any set of positive effective Hausdorff dimension. Partition genericity is a partition regular notion, so these results imply many existing pigeonhole basis theorems.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

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

Through your library

Similar books and articles

Partition-theorems for causal decision theories.Jordan Howard Sobel - 1989 - Philosophy of Science 56 (1):70-93.
Pigeonhole and Choice Principles.Wolfgang Degen - 2000 - Mathematical Logic Quarterly 46 (3):313-334.
Dynamic notions of genericity and array noncomputability.Benjamin Schaeffer - 1998 - Annals of Pure and Applied Logic 95 (1-3):37-69.
Lowness for genericity.Liang Yu - 2006 - Archive for Mathematical Logic 45 (2):233-238.
On the Indecomposability of $\omega^{n}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.
Introduction.Alda Mari, Claire Beyssade & Fabio Del Prete - 2012 - In Alda Mari, Claire Beyssade & Fabio Del Prete (eds.), Genericity. Oxford: Oxford University Press. pp. 1-92.
The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
A Pigeonhole Property for Relational Structures.Anthony Bonato & Dejan Delić - 1999 - Mathematical Logic Quarterly 45 (3):409-413.
Canonical partition relations.James E. Baumgartner - 1975 - Journal of Symbolic Logic 40 (4):541-554.
Genericity sans Gen.John Collins - 2018 - Mind and Language 33 (1):34-64.

Analytics

Added to PP
2022-10-05

Downloads
5 (#1,344,154)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

RT₂² does not imply WKL₀.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.
RT2 2 does not imply WKL0.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.
Ramsey's Theorem and Cone Avoidance.Damir D. Dzhafarov & Carl G. Jockusch - 2009 - Journal of Symbolic Logic 74 (2):557-578.
Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.

View all 9 references / Add more references