×

Enumeration 1-genericity in the local enumeration degrees. (English) Zbl 1455.03054

Summary: We discuss a notion of forcing that characterizes enumeration 1-genericity, and we investigate the immunity, lowness, and quasiminimality properties of enumeration 1-generic sets and their degrees. We construct an enumeration operator \(\Delta\) such that, for any \(A\), the set \(\Delta^A\) is enumeration 1-generic and has the same jump complexity as \(A\). We deduce from this and other recent results from the literature that not only does every degree \(a\) bound an enumeration 1-generic degree \(b\) such that \(a'=b'\), but also that, if \(a\) is nonzero, then we can find such \(b\) satisfying \(0_e< b< a\). We conclude by proving the existence of both a nonzero low and a properly \(\Sigma_2^0\) nonsplittable enumeration 1-generic degree, hence proving that the class of 1-generic degrees is properly subsumed by the class of enumeration 1-generic degrees.

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03D28 Other Turing degree structures
PDF BibTeX XML Cite
Full Text: DOI Euclid Link

References:

[1] Ahmad, S., and A. H. Lachlan, “Some special pairs of \(Σ^{0}_{2}\) e-degrees,” Mathematical Logic Quarterly, vol. 44 (1998), pp. 431–49. · Zbl 0926.03045
[2] Badillo, L., C. Bianchini, H. Ganchev, T. F. Kent, and A. Sorbi, “A note on the enumeration degrees of \(1\)-generic sets,” Archive for Mathematical Logic, vol. 55 (2016), pp. 405–14. · Zbl 1388.03041
[3] Badillo, L., and C. M. Harris, “An application of \(1\)-genericity in the \({Π}^{0}_{2}\) enumeration degrees,” pp. 604–20 in Theory and Applications of Models of Computation (Beijing, 2012), edited by M. Agrawal, S. Cooper, and A. Li, vol. 7287 of Lecture Notes in Computer Science, Springer, Heidelberg, 2012. · Zbl 1354.03055
[4] Cooper, S. B., and C. S. Copestake, “Properly \(Σ_{2}\) enumeration degrees,” Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 34 (1988), pp. 491–522. · Zbl 0667.03034
[5] Cooper, S. B., A. Sorbi, and X. Yi, “Cupping and noncupping in the enumeration degrees of \(Σ^{0}_{2}\) sets,” Annals of Pure and Applied Logic, vol. 82 (1996), pp. 317–42. · Zbl 0874.03056
[6] Copestake, K., “\(1\)-Genericity in the enumeration degrees,” Journal of Symbolic Logic, vol. 53 (1988), pp. 878–87. · Zbl 0663.03030
[7] Friedberg, R. M., and H. Rogers, Jr., “Reducibility and completeness for sets of integers,” Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 117–25. · Zbl 0108.00602
[8] Ganchev, H., and A. Sorbi, “Initial segments of the \(Σ^{2}_{0}\) enumeration degrees,” Journal of Symbolic Logic, vol. 81 (2016), pp. 316–25. · Zbl 1348.03038
[9] Harris, C. M., “Goodness in the enumeration and singleton degrees,” Archive for Mathematical Logic, vol. 49 (2010), pp. 673–91. · Zbl 1202.03051
[10] Jockusch, C. G., Jr., “Semirecursive sets and positive reducibility,” Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–36. · Zbl 0198.32402
[11] Kent, T. F., “s-Degrees within e-degrees,” pp. 579–87 in Theory and Applications of Models of Computation, edited by M. Agrawal and D. Du, vol. 4978 of Lecture Notes in Computer Science, Springer, Berlin, 2008. · Zbl 1140.03316
[12] Kent, T. F., and A. Sorbi, “Bounding nonsplitting enumeration degrees,” Journal of Symbolic Logic, vol. 72 (2007), pp. 1405–17. · Zbl 1131.03019
[13] Lachlan, A. H., and R. A. Shore, “The \(n\)-rea enumeration degrees are dense,” Archive for Mathematical Logic, vol. 31 (1992), pp. 277–85. · Zbl 0848.03023
[14] McEvoy, K., “Jumps of quasiminimal enumeration degrees,” Journal of Symbolic Logic, vol. 50 (1985) pp. 839–48. · Zbl 0595.03043
[15] McEvoy, K., and S. B. Cooper, “On minimal pairs of enumeration degrees,” Journal of Symbolic Logic, vol. 50 (1985), pp. 983–1001. · Zbl 0615.03031
[16] Shore, R., “Lecture notes on the Turing degrees,” preprint, http://pi.math.cornell.edu/Shore/papers/pdf/SingLect2NS.pdf (accessed 23June 2018).
[17] Shore, R., and A. Sorbi, “Jumps of \(Σ^{0}_{2}\)-high \(e\)-degrees and properly \(Σ^{0}_{2}\) \(e\)-degrees,” pp. 157–72 in Recursion Theory and Complexity (Kazan, 1997), edited by M. Arslanov and S. Lempp, vol. 2 of De Gruyter Series in Logic and its Applications, De Gruyter, Berlin, 1999. · Zbl 0949.03036
[18] Soare, R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, in Perspectives in Mathematical Logic, Springer, Berlin, 1987. · Zbl 0667.03030
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.