T-degrees, jump classes, and strong reducibilities
Authors:
R. G. Downey and C. G. Jockusch
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
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.2307/2272849
- J. C. E. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791β796. MR 63995, DOI https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0168-0072%2886%2990071-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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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, ${\rm wtt}$-complete sets are not necessarily ${\rm tt}$-complete, Proc. Amer. Math. Soc. 48 (1975), 429β434. MR 357087, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0003-4843%2875%2990007-8
- M. Lerman and J. B. Remmel, The universal splitting property. II, J. Symbolic Logic 49 (1984), no. 1, 137β150. MR 736609, DOI https://doi.org/10.2307/2274097
- Piergiorgio Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 37β86. MR 590818, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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
- Michael Stob, ${\rm wtt}$-degrees and ${\rm T}$-degrees of r.e. sets, J. Symbolic Logic 48 (1983), no. 4, 921β930 (1984). MR 727783, DOI https://doi.org/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 https://doi.org/10.1090/S0002-9947-1969-0241295-4
Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D30, 03D20, 03D25
Retrieve articles in all journals with MSC: 03D30, 03D20, 03D25
Additional Information
Article copyright:
© Copyright 1987
American Mathematical Society