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
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

Some relationships between Turing and weak truth table reducibilities

Degree theoretic splitting properties of r. e. sets

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

Weak truth table reducibility and the pointwise ordering of the 1-1 recursive functions

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

Hereditary sets and tabular reducibility

11

Partially ordered sets of

-degrees contained in a recursively enumerable

-degree

15

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

-degrees

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

-genericity for recursively enumerable sets

Reducibilities in recursive function theory

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

- and

-degrees

84

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

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