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
DOI: https://doi.org/10.1090/S0002-9947-1974-0349367-2
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?)

  • 1. Alexander Abian, The theory of sets and transfinite arithmetic, Saunders, Philadelphia and London, 1965. MR 0194337 (33:2547)
  • [1] Martin Davis, On the theory of recursive unsolvability, Ph.D. thesis, Princeton University, Princeton, N. J., 1950.
  • [2] -, Relatively recursive functions and the extended Kleene hierarchy, Proc. Internat. Congress Math., 1952, vol. 1, p. 723.
  • [3] S. C. Kleene, On the forms of the predicates in the theory of constructive ordinals, Amer. J. Math. 66 (1944), 41-58. MR 5, 197. MR 0009757 (5:197e)
  • [4] -, Introduction to metamathematics, Van Nostrand, Princeton, N. J., 1952. MR 14, 525. MR 0051790 (14:525m)
  • [5] -, Arithmetical predicates and function qualifiers, Trans. Amer. Math. Soc. 79 (1955), 312-340. MR 17, 4. MR 0070594 (17:4g)
  • [6] -, On the forms of the predicates in the theory of constructive ordinals. II, Amer. J. Math. 77 (1955), 405-428. MR 17, 5. MR 0070595 (17:5a)
  • [7] S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379-407. MR 15, 772. MR 0061078 (15:772a)
  • [8] Y. N. Moschovakis, Many-one degrees of the predicates $ {H_a}(x)$, Pacific J. Math. 18 (1966), 329-342. MR 37 #1247. MR 0225654 (37:1247)
  • [9] A. Mostowski, Über gewisse universelle Relationen, Ann. Soc. Polon. Math. 17 (1938), 117-118.
  • [10] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [11] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316. MR 6, 29. MR 0010514 (6:29f)
  • [12] G. E. Sacks, Degrees of unsolvability, Princeton Univ. Press, Princeton, N. J., 1963. MR 32 #4013. MR 0186554 (32:4013)
  • [13] C. Spector, Recursive well-orderings, J. Symbolic Logic 20 (1955), 151-163. MR 17, 570, 1437. MR 0074347 (17:570b)

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: https://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

American Mathematical Society