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

Schwarz, Steven

doi:10.1090/S0002-9947-1984-0735425-3

The quotient semilattice of the recursively enumerable degrees modulo the cappable degrees
HTML articles powered by AMS MathViewer

by Steven Schwarz PDF

Trans. Amer. Math. Soc. 283 (1984), 315-328 Request permission

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 $\underline {R} /\underline {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 $\underline {R} /\underline {M}$ counterpart to Sack’s splitting theorem.

References

On the structure of the recursively enumerable degrees

An algebraic decomposition of the recursively enumerable degrees and classes equal to the promptly simple degrees

Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. MR 84474, DOI 10.1073/pnas.43.2.236
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
Wolfgang Maass, Recursively enumerable generic sets, J. Symbolic Logic 47 (1982), no. 4, 809–823 (1983). MR 683156, DOI 10.2307/2273100
Wolfgang Maass, Richard A. Shore, and Michael Stob, Splitting properties and jump classes, Israel J. Math. 39 (1981), no. 3, 210–224. MR 636890, DOI 10.1007/BF02760850
A. A. Mučnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR (N.S.) 108 (1956), 194–197 (Russian). MR 0081859
Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 146078, DOI 10.2307/1970214
Gerald E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300–312. MR 166089, DOI 10.2307/1970393

Degrees of unsolvability

J. R. Shoenfield, Applications of model theory to degrees of unsolvability, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 359–363. MR 0200154
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, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR 508451, DOI 10.1090/S0002-9904-1978-14552-2
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
Robert I. Soare, Computational complexity of recursively enumerable sets, Inform. and Control 52 (1982), no. 1, 8–18. MR 693993, DOI 10.1016/S0019-9958(82)80082-X
C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807