Discrete -sequences of index sets

Author:
Louise Hay

Journal:
Trans. Amer. Math. Soc. **183** (1973), 293-311

MSC:
Primary 02F25

MathSciNet review:
0349365

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define a discrete -sequence of index sets to be a sequence , of index sets of classes of recursively enumerable sets, such that for each *n*, is an immediate successor of in the partial order of degrees of index sets under one-one reducibility. The main result of this paper is that if *S* is any set to which the complete set *K* is not Turing-reducible, and is the class of recursively enumerable subsets of *S*, then is at the bottom of *c* discrete -sequences. It follows that every complete Turing degree contains *c* discrete -sequences.

**[1]**J. C. E. Dekker and J. Myhill,*Some theorems on classes of recursively enumerable sets*, Trans. Amer. Math. Soc.**89**(1958), 25–59. MR**0097310**, 10.1090/S0002-9947-1958-0097310-7**[2]**Y. L. Eršov,*A hierarchy of sets*. I, Algebra i Logika**7**(1968), 47-74 = Algebra and Logic**7**(1968), 25-43. MR**42**#5794.**[3]**Louise Hay,*A discrete chain of degrees of index sets*, J. Symbolic Logic**37**(1972), 139–149. MR**0319728****[4]**Louise Hay,*Index sets of finite classes of recursively enumerable sets*, J. Symbolic Logic**34**(1969), 39–44. MR**0250871****[5]**L. Hay,*A non-initial segment of index sets*(to appear).**[6]**John Myhill,*Creative sets*, Z. Math. Logik Grundlagen Math.**1**(1955), 97–108. MR**0071379****[7]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462**

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

Retrieve articles in all journals with MSC: 02F25

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9947-1973-0349365-8

Keywords:
Index sets,
classes of recursively enumerable sets,
one-one reducibility,
complete degrees

Article copyright:
© Copyright 1973
American Mathematical Society