Index sets and Boolean operations

Author:
Douglas E. Miller

Journal:
Proc. Amer. Math. Soc. **84** (1982), 568-572

MSC:
Primary 03D25; Secondary 03D55

DOI:
https://doi.org/10.1090/S0002-9939-1982-0643751-5

MathSciNet review:
643751

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Hay's thesis asserts that every naturally defined class of sets of natural numbers contains an index set which is -complete for that class and that every index set is -complete for some naturally defined class. We formalize "naturally defined" as "effective Boolean" and establish the thesis as a Metatheorem.

**[1]**Y. L. Ershov,*Completely enumerated sets*, Algebra and Logic**9**(1970), 20-31.**[2]**-,*On a hierarchy of sets*. II, Algebra and Logic**7**(1968), 212-232.**[3]**L. Hay,*Index sets universal for differences of arithmetic sets*, Z. Math. Logik Grundlag. Math.**20**(1974), 239-254. MR**0429518 (55:2531)****[4]**-,*A noninitial segment of index sets*, J. Symbolic Logic**39**(1974), 209-224. MR**0354333 (50:6813)****[5]**L. Hay, A. Manaster and J. Rosenstein,*Small recursive ordinals, many one degrees, and the arithmetical difference hierarchy*, Ann. Math. Logic**8**(1975), 297-343. MR**0403939 (53:7748)****[6]**P. Hinman, Ph. D. Dissertation, Univ. of California, Berkeley, 1966.**[7]**-,*Recursion theoretic hierarchies*, Springer-Verlag, Berlin, 1978. MR**499205 (82b:03084)****[8]**L. Kantorevich and E. Livenson,*Memoir on the analytical operations and projective sets*, Fund. Math.**18**(1932), 214-279 and**20**(1933), 54-97.**[9]**P. Odifreddi,*Strong reducibilities*, Bull. Amer. Math. Soc.**4**(1981), 37-86. MR**590818 (82k:03064)****[10]**H. Rogers, Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill, New York, 1967. MR**0224462 (37:61)****[11]**J. Steel, Ph.D. Dissertation, Univ. of California, Berkeley, 1977.**[12]**R. Van Wesep, Ph.D. Dissertation, Univ. of California, Berkeley, 1977.

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
03D25,
03D55

Retrieve articles in all journals with MSC: 03D25, 03D55

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1982-0643751-5

Keywords:
Index sets,
many-one degrees,
hierarchies,
Boolean set operations

Article copyright:
© Copyright 1982
American Mathematical Society