论文标题
分区通用性和鸽洞基础定理
Partition genericity and pigeonhole basis theorems
论文作者
论文摘要
计算理论中存在两个典型性的概念，即通用性和随机性。在本文中，我们介绍了一种新的通用概念，称为“分区通用”，它是在这两个典型概念的交集中，并表明许多基础定理适用于分区仿制处。更确切地说，我们证明每个共同摄影集和每个Kurtz随机都属于分区通用，并且每个分区通用集都允许弱的无限子集。特别是，我们通过表明每个库尔兹随机都接受一个无限的子集来回答kjos-Hanssen和Liu的问题，该子集未计算任何一组阳性的Hausdorff维度。分区中期是分区的常规概念，因此这些结果暗示了许多现有的Pigonhole基础定理。
There exist two notions of typicality in computability theory, namely, 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. 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 Hausdorff dimension. Partition genericty is a partition regular notion, so these results imply many existing pigeonhole basis theorems.
