# 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)].

##### MSC:
 03D28 Other Turing degree structures
##### Keywords:
bi-hyperhyperimmunity; weak 2-genericity; escaping
Full Text:
##### References:
  Barry Cooper, S., Jump equivalence of the $$\operatorname{\Delta}_2^0$$ hyperhyperimmune sets, J. Symbolic Logic, 37, 598-600, (1972) · Zbl 0278.02037  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  Csima, Barbara F.; Kalimullin, Iskander S., Degree spectra and immunity properties, MLQ Math. Log. Q., 56, 1, 67-77, (2010) · Zbl 1184.03025  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  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  Jockusch, Carl G., The degrees of bi-immune sets, Z. Math. Log. Grundl. Math., 15, 135-140, (1969) · Zbl 0184.02002  Jockusch, Carl G., The degrees of hyperhyperimmune sets, J. Symbolic Logic, 34, 489-493, (1969) · Zbl 0181.30601  Jockusch, Carl G., Upward closure of bi-immune degrees, Z. Math. Log. Grundl. Math., 18, 285-287, (1972) · Zbl 0257.02033  Jockusch, Carl G., Upward closure and cohesive degrees, Israel J. Math., 15, 332-335, (1973) · Zbl 0279.02024  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  Kurtz, Stuart A., Randomness and genericity in the degrees of unsolvability, (1981), University of Illinois Urbana, Ph.D. dissertation  Kurtz, Stuart A., Notions of weak genericity, J. Symbolic Logic, 48, 3, 764-770, (1983) · Zbl 0549.03042  Miller, Webb; Martin, D. A., The degrees of hyperimmune sets, Z. Math. Log. Grundl. Math., 14, 159-166, (1968) · Zbl 0216.29102  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.