Discrete -sequences of index sets

Author:
Louise Hay

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

MSC:
Primary 02F25

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

MathSciNet review:
0349365

Full-text PDF

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**20**#3780. MR**0097310 (20:3780)****[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]**L. Hay,*A discrete chain of degrees of index sets*, J. Symbolic Logic**37**(1972), 139-149. MR**0319728 (47:8270)****[4]**-,*Index sets of finite classes of recursively enumerable sets*, J. Symbolic Logic**34**(1969), 39-44. MR**40**#4103. MR**0250871 (40:4103)****[5]**L. Hay,*A non-initial segment of index sets*(to appear).**[6]**J. Myhill,*Creative sets*, Math. Logik Grundlagen Math.**1**(1955), 97-108. MR**17**, 118. MR**0071379 (17:118g)****[7]**H. Rogers, Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill, New York, 1967. MR**37**#61. MR**0224462 (37:61)**

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

Retrieve articles in all journals with MSC: 02F25

Additional Information

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