Π10 classes with complex elements
Π10 classes with complex elements
复制标题
具有复杂元素的 Π10 类
DOI：
10.2178/jsl/1230396923
复制
发表时间：
2008
影响因子：
0.6
通讯作者：
S. Binns
中科院分区：
文献类型：
--
作者：
S. Binns
一个无限二元序列是复的，如果它的初始段的Kolmogorov复杂度被一个可计算函数下界。我们证明了类P包含复元当且仅当它包含Cantor集的wtt-覆盖。也就是说，当且仅当对于每个Y <$ω，在P中存在X使得X ≥wttY。我们表明，这也相当于类的大在某种意义上。我们给出了一个例子，这个结果可以用于研究分散的线性订单。
Abstract An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y ⊆ ω there is an X in P such that X ≥wttY. We show that this is also equivalent to the class's being large in some sense. We give an example of how this result can be used in the study of scattered linear orders.