Abstract
We show that minimal pairs exist in the quotient structure of \(\mathcal{R}\) modulo the ideal of noncuppable degrees.
1991 Mathematics Subject Classification. 03D25.
A. Li is partially supported by National Distinguished Young Investigator Award no. 60325206 (China). Y. Yang is partially supported by NUS Academic Research Grant R-146-000-078-112 “Enumerability and Reducibility” (Singapore) and R-252-000-212-112. G. Wu is partially supported by a start-up grant from Nanyang Technological University (Singapore). All three authors are partially supported by NSFC grant no. 60310213 “New Directions in Theory and Applications of Models of Computation” (China). The work was done partially while the authors were visiting the Institute for Mathematical Sciences, National University of Singapore in 2005. The visit was supported by the Institute.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ambos-Spies, K., Jockusch Jr., C.G., Shore, R.A., Soare, R.I.: An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees. Trans. Amer. Math. Soc. 281, 109–128 (1984)
Jockusch Jr., C.G., Li, A., Yang, Y.: A join theorem for the computably enumerable degrees. Trans. Amer. Math. Soc. 356(7), 2557–2568(electronic) (2004)
Miller, D.: High recursively enumerable degrees and the anticupping property. In: Logic Year 1979–1980: University of Connecticut, pp. 230–245 (1981)
Nies, A.: Parameter definability in the recursively enumerable degrees. J. Math. Log. 3(1), 37–65 (2003)
Schwarz, S.: The quotient semilattice of the recursively enumerable degrees modulo the cappable degrees. Trans. Amer. Math. Soc. 283(1), 315–328 (1984)
Yi, X.: Extension of embeddings on the recursively enumerable degrees modulo the cappable degrees. In: Computability, enumerability, unsolvability. London Math. Soc. Lecture Note Ser., vol. 224, pp. 313–331. Cambridge Univ. Press, Cambridge (1996)
Yu, L., Yang, Y.: On the definable ideal generated by nonbounding c.e. degrees. J. Symbolic Logic 70(1), 252–270 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, A., Wu, G., Yang, Y. (2006). On the Quotient Structure of Computably Enumerable Degrees Modulo the Noncuppable Ideal. In: Cai, JY., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2006. Lecture Notes in Computer Science, vol 3959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11750321_69
Download citation
DOI: https://doi.org/10.1007/11750321_69
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34021-8
Online ISBN: 978-3-540-34022-5
eBook Packages: Computer ScienceComputer Science (R0)