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
- Trans. Amer. Math. Soc. 281 (1984), 109-128
- DOI: https://doi.org/10.1090/S0002-9947-1984-0719661-8
- PDF | 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
- K. Ambos-Spies, On the structure of the recursively enumerable degrees, Ph.D. dissertation, Univ. of Munich.
—, An extension of the non-diamond theorem in classical and $\alpha$-recursion theory, J. Symbolic Logic.
—, Non-cappability in the r.e. weak truth table and Turing degrees,
P. Fejer, The structure of definable subclasses of the recursively enumerable degrees, Ph.D. dissertation, Univ. of Chicago.
- 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-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, (rev. ed.), Ann. of Math. Studies, no. 55, Princeton Univ. Press, Princeton, N. J. S. Schwarz, Index sets of recursively enumerable sets, quotient lattices, and recursive linear orderings. Ph.D. dissertation, Univ. of Chicago.
- 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 L. Welch, A hierarchy of families of recursively enumerable degrees and a theorem on bounding minimal pairs, Ph.D. dissertation, Univ. of Illinois.
- C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807
Bibliographic Information
- © Copyright 1984 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 281 (1984), 109-128
- MSC: Primary 03D25; Secondary 03D30
- DOI: https://doi.org/10.1090/S0002-9947-1984-0719661-8
- MathSciNet review: 719661