Article contents
Diamond embeddings into the enumeration degrees
Published online by Cambridge University Press: 27 October 2010
Abstract
We show that the diamond lattice can be embedded into the Σ02 enumeration degrees preserving 0 and 1, with atoms one high and Π01, and the other one low.
- Type
- Paper
- Information
- Mathematical Structures in Computer Science , Volume 20 , Special Issue 5: Theory and Applications of Models of Computation (TAMC 2008–2009) , October 2010 , pp. 799 - 811
- Copyright
- Copyright © Cambridge University Press 2010
References
Ahmad, S. (1991) Embedding the diamond in the Σ2 enumeration degrees. J. Symbolic Logic 50 195–212.CrossRefGoogle Scholar
Ahmad, S. and Lachlan, A. H. (1998) Some special pairs of Σ2e-degrees. Math. Logic Quarterly 44 431–439.CrossRefGoogle Scholar
Arslanov, M. M., Cooper, S. B. and Kalimullin, I. Sh. (2003) Splitting properties of total enumeration degrees. Algebra and Logic 42 1–13.CrossRefGoogle Scholar
Cooper, S. B. (1984) Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense. J. Symbolic Logic 49 503–513.CrossRefGoogle Scholar
Lachlan, A. H. (1966) Lower bounds for pairs of recursively enumerable degrees. Proc. London Math. Soc. 16 537–569.CrossRefGoogle Scholar
Lempp, S. and Sorbi, A. (2002) Embedding finite lattices into the Σ02 enumeration degrees. J. Symbolic Logic 67 (1)69–90.CrossRefGoogle Scholar
McEvoy, K. and Cooper, S. B. (1985) On minimal pairs of enumeration degrees. J. Symbolic Logic 50 983–1001.CrossRefGoogle Scholar
Nies, A. and Sorbi, A. (1999) Branching in the enumeration degrees of Σ02 sets. Israel J. Math. 110 (1)29–59.CrossRefGoogle Scholar
Odifreddi, P. (1999) Classical Recursion Theory (Volume II). Studies in Logic and the Foundations of Mathematics 143, North-Holland, Amsterdam.Google Scholar
Shore, R. and Sorbi, A. (1999) Jumps of Σ02 high e-degrees and properly Σ02 e-degrees. In: Arslanov, M. M. and Lempp, S. (eds.) Recursion Theory and Complexity, De Gruyter Series in Logic and Its Applications, W. De Gruyter 157–172.CrossRefGoogle Scholar
Soare, R. I. (1987) Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag.CrossRefGoogle Scholar
Sorbi, A., Wu, G. and Yang, Y. (2009) High minimal pairs in the enumeration degrees. In: 6th Annual Conference, TAMC 2009 Changsha, China, May 2009. Springer-Verlag Lecture Notes in Computer Science 5532 335–344.CrossRefGoogle Scholar
- 1
- Cited by