Hyperarithmetical index sets in recursion theory
HTML articles powered by AMS MathViewer
- by Steffen Lempp
- Trans. Amer. Math. Soc. 303 (1987), 559-583
- DOI: https://doi.org/10.1090/S0002-9947-1987-0902785-2
- PDF | Request permission
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
- 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 10.2307/2964290
- Thomas Jech, Set theory, Pure and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. 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 10.1090/S0002-9947-1968-0227009-1
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-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, DOI 10.1007/978-3-662-02460-7 R. E. Tulloss, Some complexities of simplicity concerning grades of simplicity of recursively enumerable sets, Ph.D. Dissertation, Univ. of California, Berkeley, 1971.
Bibliographic Information
- © Copyright 1987 American Mathematical Society
- 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