Article contents
Decomposition and infima in the computably enumerable degrees
Published online by Cambridge University Press: 12 March 2014
Abstract
Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ∪ c) ∩ (b ∪ c), a ∪ c ∣ b ∪ c, and c < a ∪ b.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2003
References
REFERENCES
[1]Ambos-Spies, K., On pairs of recursively enumerable degrees. Transactions of the American Mathematical Society, vol. 283 (1984), pp. 507–531.CrossRefGoogle Scholar
[2]Downey, R., The 0′′′ priority method with special attention to density results. Recursion theory week: Proceedings, Oberwolfach, 1989 (Ambos-Spies, K.et al., editors). Springer, Berlin, 1990.Google Scholar
[3]Fejer, P., The density of the nonbranching degrees. Annals of Pure and Applied Logic, vol. 24 (1983), pp. 113–130.CrossRefGoogle Scholar
[4]Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, Second Series, vol. 59 (1954), pp. 370–407.CrossRefGoogle Scholar
[5]Lachlan, A., Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, Third Series, vol. 16 (1966), pp. 537–569.CrossRefGoogle Scholar
[6]Lachlan, A., A recursively enumerable degree which will not split over all lesser ones, Annals of Mathematical Logic, vol. 9 (1975), pp. 307–365.CrossRefGoogle Scholar
[7]Lachlan, A., Decomposition of recursively enumerable degrees. Proceedings of the American Mathematical Society, vol. 79 (1980), pp. 629–634.CrossRefGoogle Scholar
[8]Sacks, G., On the degrees less than 0′, Annals of Mathematics, Second Series, vol. 77 (1963), pp. 211–231.CrossRefGoogle Scholar
[9]Sacks, G., The recursively enumerable degrees are dense. Annals of Mathematics, Second Series, vol. 80 (1964), pp. 300–312.CrossRefGoogle Scholar
[10]Shore, R. A., A noninversion theorem for the jump operator, Annals of Pure and Applied Logic, vol. 40 (1988), pp. 277–303.CrossRefGoogle Scholar
[11]Shore, R. A. and Slaman, T. A., Working below a low2 recursively enumerably degree, Archive for Mathematical Logic, vol. 29 (1990), pp. 201–211.CrossRefGoogle Scholar
[12]Slaman, T. A., The density of infima in the recursively enumerable degrees, Annals of Pure and Applied Logic, vol. 52 (1991), pp. 155–179.CrossRefGoogle Scholar
[13]Soare, R., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[14]Spector, C., On degrees of recursive unsolvability, Annals of Mathematics, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[15]Yates, C. E. M., A minimal pair of recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 159–168.Google Scholar
- 3
- Cited by