Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Hyperarithmetical index sets in recursion theory

Author: Steffen Lempp
Journal: Trans. Amer. Math. Soc. 303 (1987), 559-583
MSC: Primary 03D25; Secondary 03D55
MathSciNet review: 902785
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We define a family of properties on hyperhypersimple sets and show that they yield index sets at each level of the hyperarithmetical hierarchy. An extension yields a $ \Pi _1^1$-complete index set. We also classify the index set of quasimaximal sets, of coinfinite r.e. sets not having an atomless superset, and of r.e. sets major in a fixed nonrecursive r.e. set.

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

  • [Fr58] R. M. Friedberg, Three theorems on recursive enumeration: I. Decomposition, II. Maximal set, III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309-316. MR 0109125 (22:13)
  • [Je78] T. Jech, Set theory, Academic Press, New York, 1978. MR 506523 (80a:03062)
  • [JLSSta] C. G. Jockusch, Jr., M. Lerman, R. I. Soare and R. M. Solovay, Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion, in preparation.
  • [La68] A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1-37. MR 0227009 (37:2594)
  • [Ro67] H. Rogers, Jr., Theory of recursive functions and effective computability, McGrawHill, New York, 1967. MR 0224462 (37:61)
  • [Sota] R. I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, Heidelberg, 1987. MR 882921 (88m:03003)
  • [Tu71] R. E. Tulloss, Some complexities of simplicity concerning grades of simplicity of recursively enumerable sets, Ph.D. Dissertation, Univ. of California, Berkeley, 1971.

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society