Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-15T09:11:09.270Z Has data issue: false hasContentIssue false
  • English
  • Français

Comparing the Medvedev and Turing degrees of Π0 1 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: kihara.takayuki.logic@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Every co-c.e. closed set (Π0 1 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 Π0 1 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 Π0 1 classes represented by incomplete co-c.e. sets are upward dense; the collection of all Π0 1 classes represented by K-trivial sets is Medvedev-bounded by a single Π0 1 class represented by an incomplete co-c.e. set; and the Π0 1 classes have neither nontrivial infinite suprema nor infima in the Medvedev lattice.

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