A characterization of the \(\Delta _2^0\) hyperhyperimmune sets. (English) Zbl 1161.03026

Using the \(Q\)-reducibility of Tennenbaum and a related \(Q_1\)-subreducibility, the authors prove that if \(A\) is an infinite \(\Delta^0_2\) set and \(K\) is a creative set then \(K \leq_Q A\) if and only if \(K \leq_{Q_1}A\). Applying this, they obtain a new characterization of the hyperhyperimmune sets as those sets without \(S\)-complete \(\Delta^0_2\) subsets.


03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: DOI


[1] The degrees of hyperhyperimmune sets 34 pp 489– (1969)
[2] On subcreative sets and S-reducibility 39 pp 669– (1974)
[3] DOI: 10.1002/malq.19590050703 · Zbl 0108.00602 · doi:10.1002/malq.19590050703
[4] Recursion theory week, Oberwolfach 1989 1432 pp 57– (1990)
[5] Fundamenta Mathematicae 90 pp 45– (1975)
[6] Siberian Mathematical Journal 19 pp 613– (1978)
[7] Recursively enumerable sets and degrees (1987)
[8] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[9] DOI: 10.1007/s00153-006-0012-4 · Zbl 1110.03028 · doi:10.1007/s00153-006-0012-4
[10] Veroyatn. Metod. i Kibern. 10 pp 1974– (1974)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.