Hyperarithmetical index sets in recursion theory

Lempp, Steffen

doi:10.1090/S0002-9947-1987-0902785-2

Hyperarithmetical index sets in recursion theory
HTML articles powered by AMS MathViewer

by Steffen Lempp PDF

Trans. Amer. Math. Soc. 303 (1987), 559-583 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

Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion

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, 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, DOI 10.1007/978-3-662-02460-7

Some complexities of simplicity concerning grades of simplicity of recursively enumerable sets