zbMATH — the first resource for mathematics

The degrees of bi-hyperhyperimmune sets. (English) Zbl 1323.03054
The study of the upward closure of collections of Turing degrees is an interesting topic of computability theory, beginning with the work of W. Miller and D. A. Martin [Z. Math. Logik Grundlagen Math. 14, 159–166 (1968; Zbl 0216.29102)] and several works of C. G. Jockusch jun. [Z. Math. Logik Grundlagen Math. 15, 135–140 (1969; Zbl 0184.02002); J. Symb. Log. 34, 489–493 (1969; Zbl 0181.30601); Z. Math. Logik Grundlagen Math. 18, 285–287 (1972; Zbl 0257.02033); Isr. J. Math. 15, 332–335, (1973; Zbl 0279.02024)]. Thanks to these works we know of the upward closure of immune, bi-immune, hyperimmune, bi-hyperimmune and hyperhyperimmune Turing degrees. The case of the bi-hyperhyperimmune degrees remained open. In the paper under review, the authors close this gap by proving the upward closure of the bi-hyperhyperimmune Turing degrees. The strategy is to prove the following characterizations of the bi-hyperhyperimmune Turing degrees, from which the upward closure follows. Given a Turing degree \(\mathbf d\):
(1) \(\mathbf d\) computes a \(\Delta^0_2\) escaping function,
(2) \(\mathbf d\) computes a weakly 2-generic sequence,
(3) \(\mathbf d\) contains a blockwise bi-hyperhyperimmune set,
(4) \(\mathbf d\) contains a blockwise hyperhyperimmune set,
(5) \(\mathbf d\) contains a bi-hyperhyperimmune set.

The paper ends by negatively answering to Question 6.6 posed in [B. F. Csima and I. S. Kalimullin, Math. Log. Q. 56, No. 1, 67–77 (2010; Zbl 1184.03025)].

03D28 Other Turing degree structures
Full Text: DOI
[1] Barry Cooper, S., Jump equivalence of the \(\operatorname{\Delta}_2^0\) hyperhyperimmune sets, J. Symbolic Logic, 37, 598-600, (1972) · Zbl 0278.02037
[2] Barry Cooper, S.; Lewis, Andrew E. M.; Yang, Yue, Properly \(\Sigma_2\) minimal degrees and \(0''\) complementation, MLQ Math. Log. Q., 51, 3, 274-276, (2005) · Zbl 1065.03023
[3] Csima, Barbara F.; Kalimullin, Iskander S., Degree spectra and immunity properties, MLQ Math. Log. Q., 56, 1, 67-77, (2010) · Zbl 1184.03025
[4] Downey, Rodney G.; Jockusch, Carl G.; Schupp, Paul, Asymptotic density and computably enumerable sets, J. Math. Log., 13, 2, (2013), 1350005 (43 pages) · Zbl 1326.03048
[5] Downey, Rodney G.; Jockusch, Carl G.; Stob, Michael, Array nonrecursive sets and multiple permitting arguments, (Recursion Theory Week, Oberwolfach, 1989, Lecture Notes in Math., vol. 1432, (1990), Springer Berlin), 141-173
[6] Jockusch, Carl G., The degrees of bi-immune sets, Z. Math. Log. Grundl. Math., 15, 135-140, (1969) · Zbl 0184.02002
[7] Jockusch, Carl G., The degrees of hyperhyperimmune sets, J. Symbolic Logic, 34, 489-493, (1969) · Zbl 0181.30601
[8] Jockusch, Carl G., Upward closure of bi-immune degrees, Z. Math. Log. Grundl. Math., 18, 285-287, (1972) · Zbl 0257.02033
[9] Jockusch, Carl G., Upward closure and cohesive degrees, Israel J. Math., 15, 332-335, (1973) · Zbl 0279.02024
[10] Jockusch, Carl G., Degrees of generic sets, (Recursion Theory: Its Generalisation and Applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979), London Math. Soc. Lecture Note Ser., vol. 45, (1980), Cambridge Univ. Press Cambridge), 110-139
[11] Kurtz, Stuart A., Randomness and genericity in the degrees of unsolvability, (1981), University of Illinois Urbana, Ph.D. dissertation
[12] Kurtz, Stuart A., Notions of weak genericity, J. Symbolic Logic, 48, 3, 764-770, (1983) · Zbl 0549.03042
[13] Miller, Webb; Martin, D. A., The degrees of hyperimmune sets, Z. Math. Log. Grundl. Math., 14, 159-166, (1968) · Zbl 0216.29102
[14] Shore, Richard A., Minimal degrees which are \(\Sigma_2^0\) but not \(\operatorname{\Delta}_2^0\), Proc. Amer. Math. Soc., 132, 2, 563-565, (2004), (electronic) · Zbl 1033.03026
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.