PARTITION GENERICITY AND PIGEONHOLE BASIS THEOREMS
- 3 October 2022
- journal article
- research article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
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.Keywords
This publication has 16 references indexed in Scilit:
- A variant of Mathias forcing that preserves $${\mathsf{ACA}_0}$$Archive for Mathematical Logic, 2012
- RT22 does not imply WKL0The Journal of Symbolic Logic, 2012
- A STRONG LAW OF COMPUTATIONALLY WEAK SUBSETSJournal of Mathematical Logic, 2011
- Kolmogorov complexity and the Recursion TheoremTransactions of the American Mathematical Society, 2011
- Lowness for Kurtz randomnessThe Journal of Symbolic Logic, 2009
- Ramsey's theorem and cone avoidanceThe Journal of Symbolic Logic, 2009
- Infinite Subsets of Random Sets of IntegersMathematical Research Letters, 2009
- THE STRENGTH OF SOME COMBINATORIAL PRINCIPLES RELATED TO RAMSEY'S THEOREM FOR PAIRSPublished by World Scientific Pub Co Pte Ltd ,2008
- Lowness for Weakly 1-generic and Kurtz-RandomLecture Notes in Computer Science, 2006
- A Δ20 set with no infinite low subset in either it or its complementThe Journal of Symbolic Logic, 2001