Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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}^{\prime} $ 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

DOI: http://dx.doi.org/10.1090/S0002-9947-1987-0879565-X
PII: S 0002-9947(1987)0879565-X
Article copyright: © Copyright 1987 American Mathematical Society