Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



On pairs of recursively enumerable degrees

Author: Klaus Ambos-Spies
Journal: Trans. Amer. Math. Soc. 283 (1984), 507-531
MSC: Primary 03D25
MathSciNet review: 737882
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] K. Ambos-Spies, On the structure of the recursively enumerable degrees, Dissertation, Universität München, 1980.
  • [2] -, An extension of the non-diamond theorem in classical and $ \alpha $-recursion theory, J. Symbolic Logic 49 (1984).
  • [3] S. B. Cooper, Minimal upper bounds for sequences of recursively enumerable degrees, J. London Math. Soc. 5 (1972), 445-450. MR 0357092 (50:9560)
  • [4] C. G. Jockusch, Three easy constructions of recursively enumerable sets, Logic Year 1979-80, Lectures Notes in Math., vol. 859, Springer-Verlag, Berlin and New York, 1981, pp. 83-91. MR 619863 (83a:03036)
  • [5] A. H. Lachlan, Lower bounds for pairs of r.e. degrees, Proc. London Math. Soc. (3) 16 (1966), 537-569. MR 0204282 (34:4126)
  • [6] -, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1975), 307-365. MR 0409150 (53:12912)
  • [7] -, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), 629-634. MR 572317 (81i:03065)
  • [8] R. W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285-314. MR 0274286 (43:51)
  • [9] R. I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), 513-530. MR 0429521 (55:2534)
  • [10] -, Fundamental methods for constructing recursively enumerable degrees, Recursion Theory: Its Generalisations and Applications, London Math. Soc. Lecture Notes Ser. 45, Cambridge, 1980, pp. 1-51. MR 598302 (82j:03051)
  • [11] C. E. M. Yates, A minimal pair of r.e. degrees, J. Symbolic Logic 31 (1966), 159-168. MR 0205851 (34:5677)
  • [12] -, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249-266. MR 0241295 (39:2637)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D25

Retrieve articles in all journals with MSC: 03D25

Additional Information

Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society