T-degrees, jump classes, and strong reducibilities

Downey, R. G.; Jockusch, C. G.

doi:10.1090/S0002-9947-1987-0879565-X

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