   ISSN 1088-6850(online) ISSN 0002-9947(print)

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

[Enhancements On Off] (What's this?)

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D30, 03D20, 03D25

Retrieve articles in all journals with MSC: 03D30, 03D20, 03D25