Index sets and Boolean operations

Author:
Douglas E. Miller

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

MSC:
Primary 03D25; Secondary 03D55

MathSciNet review:
643751

Full-text PDF Free Access

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]**Louise Hay,*Index sets universal for differences of arithmetic sets*, Z. Math. Logik Grundlagen Math.**20**(1974), 239–254. MR**0429518****[4]**Louise Hay,*A noninitial segment of index sets*, J. Symbolic Logic**39**(1974), 209–224. MR**0354333****[5]**Louise Hay, Alfred B. Manaster, and Joseph G. Rosenstein,*Small recursive ordinals, many-one degrees, and the arithmetical difference hierarchy*, Ann. Math. Logic**8**(1975), 297–343. MR**0403939****[6]**P. Hinman, Ph. D. Dissertation, Univ. of California, Berkeley, 1966.**[7]**Peter G. Hinman,*Recursion-theoretic hierarchies*, Springer-Verlag, Berlin-New York, 1978. Perspectives in Mathematical Logic. MR**499205****[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]**Piergiorgio Odifreddi,*Strong reducibilities*, Bull. Amer. Math. Soc. (N.S.)**4**(1981), no. 1, 37–86. MR**590818**, 10.1090/S0273-0979-1981-14863-1**[10]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[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