\(\Pi _1^0\) classes with complex elements. (English) Zbl 1155.03032

Summary: 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 \(\Pi _1^0\) 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\subseteq \omega \) there is an \(X\) in \(P\) such that \(X\geqslant _{\text{wtt}} Y\). We show that this is also equivalent to the \(\Pi_1^0 \) 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.


03D80 Applications of computability and recursion theory
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI


[1] DOI: 10.1016/0168-0072(86)90067-9 · Zbl 0605.03020 · doi:10.1016/0168-0072(86)90067-9
[2] DOI: 10.1305/ndjfl/1179323269 · Zbl 1139.03029 · doi:10.1305/ndjfl/1179323269
[3] Recursively enumerable sets and degrees (1987)
[4] DOI: 10.2178/bsl/1107959497 · Zbl 1090.03015 · doi:10.2178/bsl/1107959497
[5] Recursion Theory Week 1141 (1985)
[6] DOI: 10.1016/S0020-0190(02)00343-5 · Zbl 1045.68570 · doi:10.1016/S0020-0190(02)00343-5
[7] Transactions of the American Mathematical Society 173 pp 35– (1972) · Zbl 0247.00014
[8] Journal of Universal Computer Science 3 pp 1126– (1997)
[9] DOI: 10.1016/S0019-9958(86)80004-3 · Zbl 0628.03024 · doi:10.1016/S0019-9958(86)80004-3
[10] Komolgorov complexity and the recursion theorem (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.