Hyperarithmetical index sets in recursion theory
Author:
Steffen Lempp
Journal:
Trans. Amer. Math. Soc. 303 (1987), 559-583
MSC:
Primary 03D25; Secondary 03D55
DOI:
https://doi.org/10.1090/S0002-9947-1987-0902785-2
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.
- Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309–316. MR 109125, DOI https://doi.org/10.2307/2964290
- Thomas Jech, Set theory, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. Pure and Applied Mathematics. MR 506523 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.
- A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI https://doi.org/10.1090/S0002-9947-1968-0227009-1
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921 R. E. Tulloss, Some complexities of simplicity concerning grades of simplicity of recursively enumerable sets, Ph.D. Dissertation, Univ. of California, Berkeley, 1971.
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