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)

 
 

 

The quotient semilattice of the recursively enumerable degrees modulo the cappable degrees


Author: Steven Schwarz
Journal: Trans. Amer. Math. Soc. 283 (1984), 315-328
MSC: Primary 03D25; Secondary 03D30
DOI: https://doi.org/10.1090/S0002-9947-1984-0735425-3
MathSciNet review: 735425
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we investigate the quotient semilattice $ \underline R /\underline M $ of the r.e. degrees modulo the cappable degrees. We first prove the $ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} /\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{M} $ counterpart of the Friedberg-Muchnik theorem. We then show that minimal elements and minimal pairs are not present in $ \underline R /\underline M $. We end with a proof of the $ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{R} /\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{M} $ counterpart to Sack's splitting theorem.


References [Enhancements On Off] (What's this?)

  • [K] Ambos-Spies, On the structure of the recursively enumerable degrees, Ph. D. thesis, University of Munich, 1980.
  • [K] Ambos-Spies, C. Jockusch, R. Shore and R. Soare, An algebraic decomposition of the recursively enumerable degrees and classes equal to the promptly simple degrees (to appear).
  • [R] Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Acad. Sci. U.S.A. 43 (1957). MR 0084474 (18:867a)
  • [A] Lachlan, Lower bounds for pairs of r.e. degrees, Proc. London Math. Soc. 16 (1966). MR 0204282 (34:4126)
  • [W] Maass, Recursively enumerable generic sets, J. Symbolic Logic (to appear). MR 683156 (84e:03051)
  • [W] Maass, R. Shore and M. Stob, Splitting properties and jump classes, Israel J. Math. 39 (1981). MR 636890 (84i:03083)
  • [A] A. Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR 108 (1956). (Russian) MR 0081859 (18:457a)
  • [G] Sacks. On the degrees less than $ 0'$, Ann. of Math. (2) 77 (1963). MR 0146078 (26:3604)
  • 1. -, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964). MR 0166089 (29:3367)
  • 2. -, Degrees of unsolvability, rev. ed., Ann. of Math. Studies, no. 55, Princeton Univ. Press, Princeton, N. J., 1966.
  • [J] Shoenfield, Application of model theory to degrees of unsolvability, Sympos. Theory of Models, North-Holland, Amsterdam, 1965. MR 0200154 (34:53)
  • [R] Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976). MR 0429521 (55:2534)
  • 3. -, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978). MR 508451 (81g:03050)
  • 4. -, Fundamental methods for constructing recursively enumerable degrees, Recursion Theory, Its Generalizations and Applications (Eds., F. Drake and S. Wainer), Cambridge Univ. Press, New York, 1980. MR 598302 (82j:03051)
  • [R] Soare, Computational complexity of recursively enumerable sets (to appear). MR 693993 (85b:03063)
  • [C] E. M. Yates, A minimal pair of r.e. degrees, J. Symbolic Logic 31 (1966). MR 0205851 (34:5677)

Similar Articles

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

Retrieve articles in all journals with MSC: 03D25, 03D30


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1984-0735425-3
Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society