Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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 $ 1$-complete for that class and that every index set is $ 1$-complete for some naturally defined class. We formalize "naturally defined" as "effective Boolean" and establish the thesis as a Metatheorem.


References [Enhancements On Off] (What's this?)

  • [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.

Similar Articles

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

American Mathematical Society