Many-one reducibility within the Turing degrees of the hyperarithmetic sets

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 and have the same Turing degree iff . Y. Moschovakis has proven that the sets under many-one reducibility for and have nontrivial reducibility properties if is not of the form or for any ordinal *a*. In particular, he proves that there are chains of order type 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 is also not of the form for some ordinal *a*, then there is no minimal many-one degree of the form in this Turing degree, answering a question of Y. Moschovakis posed in [8]. In fact, we prove that given there are and both many-one reducible to with incomparable many-one degrees, .

**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*, 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)**

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