Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-30T19:42:10.697Z Has data issue: false hasContentIssue false
  • English
  • Français

Π10 classes with complex elements

Published online by Cambridge University Press:  12 March 2014

Stephen Binns
Stephen Binns*
Affiliation:
Department of Mathematics and Statistics, King Fahd University of Petroleum and Minerals, PO BOX 5046 Dhahran 31261, Saudi Arabia, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Π10 classcomplexrandomnessrankedscattered linear ordercomputably growingMuchnik
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 4 , December 2008 , pp. 1341 - 1353
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Binns, Stephen, The Medvedev and Muchnik lattices of Π10 classes, Ph.D. thesis, The Pennsylvania State University, 2003.Google Scholar
[2]Binns, Stephen, Hyper immunity in 2ω, Notre Dame Journal of Formal Logic, vol. 48 (2007), no. 2, pp. 293–316.Google Scholar
[3]Cenzer, Douglas, Clote, Peter, Smith, Rick L., Soare, Robert I., Shore, Richard A., and Wainer, Stanley S., Members of countable Π10 classes, Annals of Pure and Applied Logic, vol. 31 (1986), no. 2–3, pp. 145–163.CrossRefGoogle Scholar
[4]Chisholm, John, Chubb, Jennifer, Harizanov, Valentina S., Hirschfeldt, Denis R., Jockusch, Carl G. Jr., McNicholl, Timothy, and Pingrey, Sarah, Π10classes and strong degree spectra of relations, preprint.Google Scholar
[5]Ebbinghaus, H. D., Müller, G. H., and Sacks, G. E. (editors), Recursion Theory Week, Lecture Notes in Mathematics, vol. 1141, Springer-Verlag, 1985.CrossRefGoogle Scholar
[6]Gács, P., Every sequence is reducible to a random one, Information and Control, vol. 70 (1986), pp. 186–192.CrossRefGoogle Scholar
[7]Hertling, Peter, Surjective functions on computably growing Cantor sets. Journal of Universal Computer Science, vol. 3 (1997), no. 11, pp. 1126–1240.Google Scholar
[8]Jockusch, Carl G. Jr., and Soare, Robert I., Π10 classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 35–56.Google Scholar
[9]Kjos-Hanssen, Bjørn, Merkle, Wolgang, and Stephan, Frank, Komolgorov complexity and the recursion theorem. Lecture Notes in Computer Science, 3884, 2006.Google Scholar
[10]Kučera, Antonín, Measure, Π10 classes and complete extensions of PA, In Ebbinghaus, et al. [5], 1985, pp. 245–259.CrossRefGoogle Scholar
[11]Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Information Processing Letters, vol. 84 (2002), no. 2, pp. 1–3.CrossRefGoogle Scholar
[12]Reimann, Jan, Computability and fractal dimension, Ph.D. thesis, Ruprecht-Karls-Universität, Heidelberg, 2004.Google Scholar
[13]Simpson, Stephen G., Mass problems and randomness, The Bulletin of Symbolic Logic, vol. 11 (2005), no. 1, pp. 1–27.CrossRefGoogle Scholar
[14]Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, 1987.CrossRefGoogle Scholar