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

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*, W. B. Saunders Co., Philadelphia-London, 1965. MR**0194337****[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**0009757****[4]**Stephen Cole Kleene,*Introduction to metamathematics*, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR**0051790****[5]**S. C. Kleene,*Arithmetical predicates and function quantifiers*, Trans. Amer. Math. Soc.**79**(1955), 312–340. MR**0070594**, 10.1090/S0002-9947-1955-0070594-4**[6]**S. C. Kleene,*On the forms of the predicates in the theory of constructive ordinals. II*, Amer. J. Math.**77**(1955), 405–428. MR**0070595****[7]**S. C. Kleene and Emil L. Post,*The upper semi-lattice of degrees of recursive unsolvability*, Ann. of Math. (2)**59**(1954), 379–407. MR**0061078****[8]**Yiannis N. Moschovakis,*Many-one degrees of the predicates 𝐻ₐ(𝑥)*, Pacific J. Math.**18**(1966), 329–342. MR**0225654****[9]**A. Mostowski,*Über gewisse universelle Relationen*, Ann. Soc. Polon. Math.**17**(1938), 117-118.**[10]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[11]**Emil L. Post,*Recursively enumerable sets of positive integers and their decision problems*, Bull. Amer. Math. Soc.**50**(1944), 284–316. MR**0010514**, 10.1090/S0002-9904-1944-08111-1**[12]**Gerald E. Sacks,*Degrees of unsolvability*, Princeton University Press, Princeton, N.J., 1963. MR**0186554****[13]**Clifford Spector,*Recursive well-orderings*, J. Symb. Logic**20**(1955), 151–163. MR**0074347**

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