Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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 Free Access

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

DOI: http://dx.doi.org/10.1090/S0002-9947-1987-0902785-2
PII: S 0002-9947(1987)0902785-2
Article copyright: © Copyright 1987 American Mathematical Society