T-degrees, jump classes, and strong reducibilities
HTML articles powered by AMS MathViewer
- by R. G. Downey and C. G. Jockusch PDF
- Trans. Amer. Math. Soc. 301 (1987), 103-136 Request permission
Abstract:
It is shown that there exist r.e. degrees other than 0 and $\mathbf {0}β$ which have a greatest r.e. $1$-degree. This solves an old question of Rogers and Jockusch. We call such degrees $1$-topped. We show that there exist incomplete $1$-topped degrees above any low r.e. degree, but also show that no nonzero low degree is $1$-topped. It then follows by known results that all incomplete $1$-topped degrees are low$_{2}$ but not low. We also construct cappable nonzero $1$-topped r.e. degrees and examine the relationships between $1$-topped r.e. degrees and high r.e. degrees. Finally, we give an analysis of the βlocalβ relationships of r.e. sets under various strong reducibilities. In particular, we analyze the structure of r.e. ${\text {wtt-}}$ and ${\text {tt}}$-degrees within a single r.e. ${\text {T}}$-degree. We show, for instance, that there is an r.e. degree which contains a greatest r.e. ${\text {wtt-}}$-degree and a least r.e. ${\text {tt}}$-degree yet does not consist of a single r.e. ${\text {wtt}}$-degree. This depends on a new construction of a nonzero r.e. ${\text {T}}$-degree with a least ${\text {tt}}$-degree, which proves to have several further applications.References
- Klaus Ambos-Spies, Contiguous r.e. degrees, Computation and proof theory (Aachen, 1983) Lecture Notes in Math., vol. 1104, Springer, Berlin, 1984, pp.Β 1β37. MR 775707, DOI 10.1007/BFb0099477 K. Ambos-Spies, S. B. Cooper, and C. Jockusch, Some relationships between Turing and weak truth table reducibilities (in preparation). K. Ambos-Spies and P. Fejer, Degree theoretic splitting properties of r. e. sets (to appear).
- Klaus Ambos-Spies, Carl G. Jockusch Jr., Richard A. Shore, and Robert I. Soare, An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. Soc. 281 (1984), no.Β 1, 109β128. MR 719661, DOI 10.1090/S0002-9947-1984-0719661-8 P. F. Cohen, Weak truth table reducibility and the pointwise ordering of the 1-1 recursive functions, Doctoral Dissertation, Univ. of Illinois, Urbana, Ill., 1975.
- S. B. Cooper, Minimal pairs and high recursively enumerable degrees, J. Symbolic Logic 39 (1974), 655β660. MR 371626, DOI 10.2307/2272849
- J. C. E. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791β796. MR 63995, DOI 10.1090/S0002-9939-1954-0063995-6 A. N. Degtev, Hereditary sets and tabular reducibility, Algebra and Logic 11 (1972), 145-152. β, Partially ordered sets of $1$-degrees contained in a recursively enumerable $m$-degree, Algebra and Logic 15 (1976), 153-164.
- R. G. Downey, The degrees of r.e. sets without the universal splitting property, Trans. Amer. Math. Soc. 291 (1985), no.Β 1, 337β351. MR 797064, DOI 10.1090/S0002-9947-1985-0797064-9
- R. G. Downey, $\Delta ^0_2$ degrees and transfer theorems, Illinois J. Math. 31 (1987), no.Β 3, 419β427. MR 892177 β, Intervals and sublattices in the recursively enumerable $wtt$-degrees (submitted).
- R. G. Downey and M. Stob, Structural interactions of the recursively enumerable T- and w-degrees, Ann. Pure Appl. Logic 31 (1986), no.Β 2-3, 205β236. Special issue: second Southeast Asian logic conference (Bangkok, 1984). MR 854294, DOI 10.1016/0168-0072(86)90071-0
- Paul Fischer, Pairs without infimum in the recursively enumerable weak truth table degrees, J. Symbolic Logic 51 (1986), no.Β 1, 117β129. MR 830078, DOI 10.2307/2273948
- Richard M. Friedberg and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117β125. MR 112831, DOI 10.1002/malq.19590050703 M. Ingrassia, $P$-genericity for recursively enumerable sets, Doctoral Dissertation, Univ. of Illinois, Urbana, Ill., 1981. C. G. Jockusch, Reducibilities in recursive function theory, Doctoral Dissertation, M.I.T., Cambridge, Mass., 1966.
- Carl G. Jockusch Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229β237. MR 245439, DOI 10.1090/S0002-9947-1969-0245439-X
- Carl G. Jockusch Jr., Degrees in which the recursive sets are uniformly recursive, Canadian J. Math. 24 (1972), 1092β1099. MR 321716, DOI 10.4153/CJM-1972-113-9
- Carl G. Jockusch Jr., Genericity for recursively enumerable sets, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp.Β 203β232. MR 820782, DOI 10.1007/BFb0076222
- G. N. Kobzev, btt-reducibility. I, II, Algebra i Logika 12 (1973), 190β204, 244; ibid. 12 (1973), 433β444, 492 (Russian). MR 0401447 β, Relationships between recursively enumerable $tt\text {-}$- and $w$-degrees, Bull. Akad. Sci. Georgian SSR 84 (1976), 585-587.
- G. N. Kobzev, The semilattice of tt-degrees, Sakharth. SSR Mecn. Akad. Moambe 90 (1978), no.Β 2, 281β283 (Russian, with English and Georgian summaries). MR 514301
- 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, Recursively enumerable many-one degrees, Algebra i Logika 11 (1972), 326β358, 362. MR 0309721
- A. H. Lachlan, $\textrm {wtt}$-complete sets are not necessarily $\textrm {tt}$-complete, Proc. Amer. Math. Soc. 48 (1975), 429β434. MR 357087, DOI 10.1090/S0002-9939-1975-0357087-X
- A. H. Lachlan, Bounding minimal pairs, J. Symbolic Logic 44 (1979), no.Β 4, 626β642. MR 550390, DOI 10.2307/2273300
- Richard E. Ladner, A completely mitotic nonrecursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479β507 (1974). MR 398805, DOI 10.1090/S0002-9947-1973-0398805-7
- 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
- M. Lerman and J. B. Remmel, The universal splitting property. II, J. Symbolic Logic 49 (1984), no.Β 1, 137β150. MR 736609, DOI 10.2307/2274097
- Piergiorgio Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no.Β 1, 37β86. MR 590818, DOI 10.1090/S0273-0979-1981-14863-1 β, Classical recursion theory (to appear).
- David B. Posner, The upper semilattice of degrees $\leq {\bf 0}^{\prime }$ is complemented, J. Symbolic Logic 46 (1981), no.Β 4, 705β713. MR 641484, DOI 10.2307/2273220
- Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284β316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
- Robert W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285β314. MR 274286, DOI 10.2307/1970776
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Robert I. Soare, Recursive theory and Dedekind cuts, Trans. Amer. Math. Soc. 140 (1969), 271β294. MR 242667, DOI 10.1090/S0002-9947-1969-0242667-4
- 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, Tree arguments in recursion theory and the $0''β$-priority method, Recursion theory (Ithaca, N.Y., 1982) Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp.Β 53β106. MR 791052, DOI 10.1090/pspum/042/791052
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- Michael Stob, $\textrm {wtt}$-degrees and $\textrm {T}$-degrees of r.e. sets, J. Symbolic Logic 48 (1983), no.Β 4, 921β930 (1984). MR 727783, DOI 10.2307/2273658
- C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249β266. MR 241295, DOI 10.1090/S0002-9947-1969-0241295-4
Additional Information
- © Copyright 1987 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 301 (1987), 103-136
- MSC: Primary 03D30; Secondary 03D20, 03D25
- DOI: https://doi.org/10.1090/S0002-9947-1987-0879565-X
- MathSciNet review: 879565