No CrossRef data available.
Article contents
Comparing the Medvedev and Turing degrees of Π01 classes
Published online by Cambridge University Press: 10 November 2014
Abstract
Every co-c.e. closed set (Π01 class) in Cantor space is represented by a co-c.e. tree. Our aim is to clarify the interaction between the Medvedev and Muchnik degrees of co-c.e. closed subsets of Cantor space and the Turing degrees of their co-c.e. representations. Among other results, we present the following theorems: if v and w are different c.e. degrees, then the collection of the Medvedev (Muchnik) degrees of all Π01 classes represented by v and the collection represented by w are also different; the ideals generated from such collections are also different; the collections of the Medvedev and Muchnik degrees of all Π01 classes represented by incomplete co-c.e. sets are upward dense; the collection of all Π01 classes represented by K-trivial sets is Medvedev-bounded by a single Π01 class represented by an incomplete co-c.e. set; and the Π01 classes have neither nontrivial infinite suprema nor infima in the Medvedev lattice.
- Type
- Paper
- Information
- Mathematical Structures in Computer Science , Volume 25 , Special Issue 8: Computing with Infinite Data: Topological and Logical Foundations Part 2 , December 2015 , pp. 1649 - 1668
- Copyright
- Copyright © Cambridge University Press 2014
References
Alfeld, C. P. (2007) Non-branching degrees in the Medvedev lattice of Π0
1 classes. Journal of Symbolic Logic
72
(1)
81–97.CrossRefGoogle Scholar
Barmpalias, G., Douglas, A. C., Jeffrey, B. R. and Weber, R. (2009)
K-triviality of closed sets and continuous functions. Journal of Logic and Computation
19
(1)
3–16.CrossRefGoogle Scholar
Barmpalias, G. and Nies, A. (2011) Upper bounds on ideals in the computably enumerable Turing degrees. Annals of Pure and Applied Logic
162
(6)
465–473.CrossRefGoogle Scholar
Binns, S. (2003) A splitting theorem for the Medvedev and Muchnik lattices. Mathematical Logic Quarterly
49
(4)
327–335.CrossRefGoogle Scholar
Binns, S. (2007) Hyperimmunity in
$2^\mathbb{N}$
. Notre Dame Journal of Formal Logic
48
(2)
293–316.Google Scholar
$2^\mathbb{N}$
. Notre Dame Journal of Formal Logic
48
(2)
293–316.Google ScholarCenzer, D. A. and Hinman, P. G. (2003) Density of the Medvedev lattice of Π0
1 classes. Archive for Mathematical Logic
42
(6)
583–600.CrossRefGoogle Scholar
Cholak, P., Coles, R., Downey, R. and Herrman, E. (2001) Automorphism of the lattice of Π0
1 classes: Perfect thin classes and anc degrees
Transactions of the American Mathematical Society
353
4899–4924.CrossRefGoogle Scholar
Jockusch, C. G. and Soare, R. I. (1972) Π0
1 classes and degrees of theories. Transactions of the American Mathematical Society
173
33–56.Google Scholar
Medvedev, Y. T. (1955) Degrees of difficulty of the mass problems. Doklady Akademii Nauk SSSR
104
501–504 (in Russian).Google Scholar
Melnikov, A. G. and Nies, A. (2013)
K-triviality in computable metric spaces. Proceedings of the American Mathematical Society
141
(8)
2885–2899.CrossRefGoogle Scholar
Muchnik, A. A. (1963) On strong and weak reducibility of algorithmic problems. Sibirskii Matematicheskii Zhurnal
4
1328–1341 (in Russian).Google Scholar
Nies, A. (2009) Computability and Randomness, Oxford Logic Guides. Oxford University Press 433.CrossRefGoogle Scholar
Simpson, S. G. (2005) Mass problems and randomness. Bulletin of Symbolic Logic
11
(1)
1–27.CrossRefGoogle Scholar
Simpson, S. G. (2011) Mass problems associated with effectively closed sets. Tohoku Mathematical Journal
63
(4)
489–517.CrossRefGoogle Scholar
Soare, R. I. (1987) Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer, Heidelberg XVIII+437 pp.CrossRefGoogle Scholar