On pairs of recursively enumerable degrees
HTML articles powered by AMS MathViewer
- by Klaus Ambos-Spies PDF
- Trans. Amer. Math. Soc. 283 (1984), 507-531 Request permission
Abstract:
Lachlan and Yates proved that some, but not all, pairs of incomparable recursively enumerable (r.e.) degrees have an infimum. We answer some questions which arose from this situation. We show that not every nonzero incomplete r.e. degree is half of a pair of incomparable r.e. degrees which have an infimum, whereas every such degree is half of a pair without infimum. Further, we prove that every nonzero r.e. degree can be split into a pair of r.e. degrees which have no infimum, and every interval of r.e. degrees contains such a pair of degrees.References
-
K. Ambos-Spies, On the structure of the recursively enumerable degrees, Dissertation, Universität München, 1980.
—, An extension of the non-diamond theorem in classical and $\alpha$-recursion theory, J. Symbolic Logic 49 (1984).
- S. B. Cooper, Minimal upper bounds for sequences of recursively enumerable degrees, J. London Math. Soc. (2) 5 (1972), 445–450. MR 357092, DOI 10.1112/jlms/s2-5.3.445
- Carl G. Jockusch Jr., Three easy constructions of recursively enumerable sets, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin-New York, 1981, pp. 83–91. MR 619863
- A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 204282, DOI 10.1112/plms/s3-16.1.537
- Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307–365. MR 409150, DOI 10.1016/0003-4843(76)90016-4
- A. H. Lachlan, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), no. 4, 629–634. MR 572317, DOI 10.1090/S0002-9939-1980-0572317-9
- Robert W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285–314. MR 274286, DOI 10.2307/1970776
- Robert I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), no. 2, 513–530. MR 429521, DOI 10.2307/2272252
- Robert I. Soare, Fundamental methods for constructing recursively enumerable degrees, Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979) London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge-New York, 1980, pp. 1–51. MR 598302
- C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807
- C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249–266. MR 241295, DOI 10.1090/S0002-9947-1969-0241295-4
Additional Information
- © Copyright 1984 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 283 (1984), 507-531
- MSC: Primary 03D25
- DOI: https://doi.org/10.1090/S0002-9947-1984-0737882-5
- MathSciNet review: 737882