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)

 

 

Many-one reducibility within the Turing degrees of the hyperarithmetic sets $ H\sb{a}(x)$


Author: G. C. Nelson
Journal: Trans. Amer. Math. Soc. 191 (1974), 1-44
MSC: Primary 02F30
MathSciNet review: 0349367
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Spector [13] has proven that the hyperarithmetic sets $ {H_a}(x)$ and $ {H_b}(x)$ have the same Turing degree iff $ \vert a\vert = \vert b\vert$. Y. Moschovakis has proven that the sets $ {H_a}(x)$ under many-one reducibility for $ \vert a\vert = \gamma $ and $ a \in \mathcal{O}$ have nontrivial reducibility properties if $ \gamma $ is not of the form $ \alpha + 1$ or $ \alpha + \omega $ for any ordinal a. In particular, he proves that there are chains of order type $ {\omega _1}$ and incomparable many-one degrees within these Turing degrees. In Chapter II, we extend this result to show that any countable partially ordered set can be embedded in the many-one degrees within these Turing degrees. In Chapter III, we prove that if $ \gamma $ is also not of the form $ \alpha + {\omega ^2}$ for some ordinal a, then there is no minimal many-one degree of the form $ {H_a}(x)$ in this Turing degree, answering a question of Y. Moschovakis posed in [8]. In fact, we prove that given $ {H_a}(x)$ there are $ {H_b}(x)$ and $ {H_c}(x)$ both many-one reducible to $ {H_a}(x)$ with incomparable many-one degrees, $ \vert a\vert = \vert b\vert = \vert c\vert = \gamma $.


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


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F30

Retrieve articles in all journals with MSC: 02F30


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1974-0349367-2
Keywords: Constructive ordinal notations, many-one degrees, Turing degrees, recursively majorized
Article copyright: © Copyright 1974 American Mathematical Society