## 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, - 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, - 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, - 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**
β, - 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$ - 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**
β, - 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
β, - 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

*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).

*Weak truth table reducibility and the pointwise ordering of the 1-1 recursive functions*, Doctoral Dissertation, Univ. of Illinois, Urbana, Ill., 1975.

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

*Intervals and sublattices in the recursively enumerable*$wtt$

*-degrees*(submitted).

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

*Relationships between recursively enumerable*$tt\text {-}$

*- and*$w$

*-degrees*, Bull. Akad. Sci. Georgian SSR

**84**(1976), 585-587.

*Classical recursion theory*(to appear).

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