An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees

Ambos-Spies, Klaus; Jockusch, Carl G.; Shore, Richard A.; Soare, Robert I.

doi:10.1090/S0002-9947-1984-0719661-8

An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees
HTML articles powered by AMS MathViewer

by Klaus Ambos-Spies, Carl G. Jockusch, Richard A. Shore and Robert I. Soare PDF

Trans. Amer. Math. Soc. 281 (1984), 109-128 Request permission

Abstract:

We specify a definable decomposition of the upper semilattice of recursively enumerable (r.e.) degrees $\mathbf {R}$ as the disjoint union of an ideal $\mathbf {M}$ and a strong filter $\mathbf {NC}$. The ideal $\mathbf {M}$ consists of $\mathbf {0}$ together with all degrees which are parts of r.e. minimal pairs, and thus the degrees in $\mathbf {NC}$ are called noncappable degrees. Furthermore, $\mathbf {NC}$ coincides with five other apparently unrelated subclasses of $\mathbf {R: ENC}$, the effectively noncappable degrees; $\mathbf {PS}$, the degrees of promptly simple sets; $\mathbf {LC}$, the r.e. degrees cuppable to ${\mathbf {0}}’$ by a low r.e. degree; ${\mathbf {SP\bar H}}$, the degrees of non-$hh$-simple r.e. sets with the splitting property; and $\mathbf {G}$, the degrees in the orbit of an r.e. generic set under automorphisms of the lattice of r.e. sets.

References

On the structure of the recursively enumerable degrees

An extension of the non-diamond theorem in classical and

recursion theory

Non-cappability in the r.e. weak truth table and Turing degrees

The structure of definable subclasses of the recursively enumerable degrees

Peter A. Fejer and Robert I. Soare, The plus-cupping theorem for the recursively enumerable degrees, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin, 1981, pp. 49–62. MR 619860
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
A. H. Lachlan, Degrees of recursively enumerable sets which have no maximal supersets, J. Symbolic Logic 33 (1968), 431–443. MR 236016, DOI 10.2307/2270328
A. H. Lachlan, Bounding minimal pairs, J. Symbolic Logic 44 (1979), no. 4, 626–642. MR 550390, DOI 10.2307/2273300
Richard E. Ladner and Leonard P. Sasso Jr., The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), no. 4, 429–448. MR 379157, DOI 10.1016/0003-4843(75)90007-8
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
David P. Miller, High recursively enumerable degrees and the anticupping property, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin, 1981, pp. 230–245. MR 619872
Robert W. Robinson, Jump restricted interpolation in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 586–596. MR 313037, DOI 10.2307/1970889
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
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

Index sets of recursively enumerable sets, quotient lattices, and recursive linear orderings

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
J. R. Shoenfield, Degrees of classes of RE sets, J. Symbolic Logic 41 (1976), no. 3, 695–696. MR 485293, DOI 10.2307/2272046
Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2) 100 (1974), 80–120. MR 360235, DOI 10.2307/1970842
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, Computational complexity, speedable and levelable sets, J. Symbolic Logic 42 (1977), no. 4, 545–563. MR 485278, DOI 10.2307/2271876
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, Automorphisms of the lattice of recursively enumerable sets. II. Low sets, Ann. Math. Logic 22 (1982), no. 1, 69–108. MR 661478, DOI 10.1016/0003-4843(82)90016-X
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

A hierarchy of families of recursively enumerable degrees and a theorem on bounding minimal pairs

C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807