Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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

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

Similar Articles

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