Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-03T08:36:56.797Z Has data issue: false hasContentIssue false
  • English
  • Français

Comparing the Medvedev and Turing degrees of Π01 classes

Published online by Cambridge University Press:  10 November 2014

TAKAYUKI KIHARA
TAKAYUKI KIHARA*
Affiliation:
Japan Advanced Institute of Science and Technology, Nomi, Japan Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 

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

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
Cenzer, 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