Journal of Logic and Computation

Journal of Logic and Computation Advance Access originally published online on August 14, 2008
Journal of Logic and Computation 2009 19(1):3-16; doi:10.1093/logcom/exn021

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Barmpalias, G. Articles by Weber, R. Search for Related Content Social Bookmarking          What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Articles

K-Triviality of Closed Sets and Continuous Functions

George Barmpalias

School of Mathematics, University of Leeds, Leeds LS2 9JT, England
E-mail: barmpalias{at}gmail.com

Douglas Cenzer

Department of Mathematics, University of Florida, P.O. Box 118105, Gainesville, Florida 32611
E-mail: cenzer{at}math.ufl.edu

Jeffrey B. Remmel

Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA
E-mail: jremmel{at}ucsd.edu

Rebecca Weber

Department of Mathematics, Dartmouth College, Hanover, NH 03755-3551
E-mail: Rebecca.A.Weber{at}Dartmouth.edu

Received 10 October 2007.

We investigate the notion of K-triviality for closed sets and continuous functions in 2. For every K-trivial degree d, there exists a closed set of degree d and a continuous function of degree d. Every K-trivial closed set contains a K-trivial real. There exists a K-trivial class with no computable elements. A closed set is K-trivial if and only if it is the set of zeroes of some K-trivial continuous function. We give a density result for the Medvedev degrees of K-trivial sets. If W _TA', then W can compute a path through every A'-decidable random closed set if and only if W _TA'.

Keywords: Computability; randomness; classes

References

1. Asarin EA, Prokovskiy V. Application of Kolmogorov complexity to the dynamics of controllable systems. Automatika i Telemekhanika (1986) 1:25–53.
2. Barmpalias G, Brodhead P, Cenzer D, Dashti S, Weber R. Algorithmic randomness of closed sets. Journal of Logic and Computation (2007) 17:1041–1062.[Abstract/Free Full Text]
3. Barmpalias G, Brodhead P, Cenzer D, Remmel JB, Weber R. Algorithmic randomness of continuous functions. Archive for Mathematical Logic (2008) 45:533–546.
4. Binns S. A splitting theorem for the Medvedev and Muchnik lattices. Math. Logic Q. (2003) 49:327–335.[CrossRef]
5. Brodhead P, Cenzer D, Dashti S. Random closed sets. Logical Approaches to Computational Barriers—Beckmann A, Berger U, Löwe B, Tucker JV, eds. (2006) 55–64. Vol. 3988 of Springer Lecture Notes in Computer Science.
6. Brodhead P, Cenzer D, Remmel JB. Random continuous functions. CCA 2006, Third International Conference on Computability and Complexity in Analysis—Cenzer D, Dillhage R, Grubb T, Weihrauch Klaus, eds. (2007) 167:275–287. Springer Electronic Notes in Computer Science.
7. Cenzer D. , Classes. |ASL Lecture Notes in Logic| (in preparation).
8. Cenzer D, Downey R, Jockusch CG, Shore R. Countable thin classes. Annals of Pure and Applied Logic (1993) 5:79–139.
9. Cenzer D, Hinman PG. Density of the Medvedev lattice of classes. Archive for Mathematical Logic (2003) 42:583–600.[CrossRef][Web of Science]
10. Cenzer D, Remmel JB. classes. Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics—Ersov Y, Goncharov S, Marek V, Nerode A, Remmel J, eds. (1998) 139:623–821. Elsevier Studies in Logic and Found. Math.[CrossRef]
11. Dekker J, Myhill J. Retraceable sets. Canadian Journal of Mathematics (1985) 10:357–373.
12. Downey R. Five Lectures on Algorithmic Randomness. Computational Prospects of Infinity—Chong CT, ed. (2008) 1–76. Proceedings of 2005 Singapore meeting, Lecture Notes 14, Inst. Math Sci, Natl U Singapore.
13. Downey R. Some computability-theoretic aspects of reals and randomness. The Notre Dame Lectures—Cholak P, ed. (2005) Vol. 18:97–147. ASL Lecture Notes in Logic.
14. Downey R, Hirschfeldt D, Nies A, Stephan F. Trivial reals. In. In: Proceedings of 7th and 8th Asian Logic Conference. (2003) Singapore: World Scientific Press. 101–131.
15. Fouche W. Arithmetical representations of Brownian motion. Journal of Symbolic Logic (2000) 65:421–442.[CrossRef][Web of Science]
16. Gács P. Uniform test of algorithmic randomness over a general space. Theoritical Computer Science (2005) 341:91–137.[CrossRef]
17. Kuera A. Measure, classes, and complete extensions of PA. Vol. 1141 of Springer Lecture Notes in Mathematics (1985) 245–259.
18. Kuera A, Slaman T. Low upper bounds of ideals. preprint.
19. Kuera A, Terwijn S. Lowness for the class of random sets. Journal of Symbolic Logic (1999) 64:1396–1402.[CrossRef][Web of Science]
20. Nies A. Lowness properties and randomness. Advances in Mathematics (2005) 197:274–305.[CrossRef][Web of Science]
21. Ohashi K. A stronger form of a theorem of Friedberg. Natre Dame Journal of Formal Logic (1964) 5:10–12.[CrossRef]
22. Simpson SG. Mass problems and randomness. Bulletin of Symbolic Logic (2005) 11:1–27.[CrossRef][Web of Science]

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Barmpalias, G. Articles by Weber, R. Search for Related Content Social Bookmarking          What's this?