×

A note on the enumeration degrees of 1-generic sets. (English) Zbl 1388.03041

The authors use a priority argument to prove that if \(A\) is a \(\Delta^0_2\) set of nonzero e-degree, then there is a set \(B \leq_e A\) such that \(B\) is \(1\)-generic. Using results from T. F. Kent and A. Sorbi [J. Symb. Log. 72, No. 4, 1405–1417 (2007; Zbl 1131.03019)], they show that that the \(1\)-generic e-degrees below \(0^\prime_e\) are not downwards closed, answering Question 4.13 of S. B. Cooper [Lect. Notes Math. 1432, 57–110 (1990; Zbl 0707.03034)].

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Badillo, L., Harris, C.M.: An application of 1-genericity in the \({Π^{0}_{2}}\) enumeration degrees. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 7287, pp. 604-620. Springer, Heidelberg (2012) · Zbl 1354.03055
[2] Badillo, L., Harris, C.M., Soskova, M.I.: Enumeration 1-genericity in the local enumeration degrees. Preprint. http://www.maths.bris.ac.uk/ hh12242/papers/pdfversions/genericityPaperModified.pdf (2012) · Zbl 0135.00702
[3] Bianchini, C.: Bounding Enumeration Degrees. PhD thesis, University of Siena (2000) · Zbl 1131.03019
[4] Case, J., Enumeration reducibility and partial degrees, Ann. Math. Log., 2, 419-439, (1971) · Zbl 0223.02046
[5] Cooper, S.B., Partial degrees and the density problem. part 2: the enumeration degrees of the \({Σ_{2}}\) sets are dense, J. Symb. Log., 49, 503-513, (1984) · Zbl 0574.03027
[6] Cooper, S.B.: Enumeration reducibility, nondeterministic computations and relative computability of partial functions. In: Ambos-Spies, K., Müller, G., Sacksm, G.E. (eds.) Recursion Theory Week, Oberwolfach 1989. Lecture Notes in Mathematics vol. 1432, pp. 57-110. Springer, Heidelberg (1990)
[7] Cooper S.B.: Computability Theory. Chapman & Hall/CRC Mathematics, Boca Raton (2004) · Zbl 1041.03001
[8] Copestake, K., 1-genericity in the enumeration degrees, J. Symb. Log., 53, 878-887, (1988) · Zbl 0663.03030
[9] Copestake, K.: 1-generic enumeration degrees below \({\mathbf{0}'_e}\). In: Proceedings of the Conference dedicated to the 90th Anniversary of Arend Heyting, Chaika, Bulgaria, 1988, pp. 257-265 (1990) · Zbl 0784.03026
[10] Feferman, S.: Some applications of the notions of forcing and generic sets. In: Addison, J.W., Henkin, L., Tarski, A. (eds.) The Theory of Models. Proceedings of the 1963 International Symposium at Berkeley, Studies in Logic and the Foundations of Mathematics, pp. 89-95. North-Holland Publishing Co., Amsterdam (1965) · Zbl 0129.26401
[11] Haught, C.A., The degrees below a 1-generic degree and less than 0′, J. Symb. Log., 51, 770-777, (1986) · Zbl 0633.03039
[12] Hinman, P.G., Some applications of forcing to hierarchy problems in arithmetic, Z. Math. Log. Grund. Math., 15, 341-352, (1969) · Zbl 0191.30601
[13] Jockusch, C.G. Jr.: Degrees of generic sets. In: Drake, F.R., Wainer, S.S. (eds.) Recursion Theory: Its Generalizations and Applications. Proceedings of Logic Colloquium ’79, Leeds, August 1979, pp. 110-139. Cambridge University Press, Cambridge (1980)
[14] Kent, T.F.; Sorbi, A., Bounding nonsplitting enumeration degrees, J. Symb. Log., 72, 1405-1417, (2007) · Zbl 1131.03019
[15] Posner, D.: High Degrees. PhD thesis, University of California, Berkeley (1977) · Zbl 0223.02046
[16] Sacks, G.E., The recursively enumerable degrees are dense, Ann. Math., 80, 300-312, (1964) · Zbl 0135.00702
[17] Slaman, T.A.: Mathematical definability. In: Dales, H.G., Oliveri, G. (eds.) Truth in Mathematics (Mussomeli, 1995), pp. 233-251. Oxford University Press, New York (1998) · Zbl 0932.03054
[18] Soare, R.I.: Recursively enumerable sets and degrees. In: Dales, H.G., Oliveri, G. (eds.) Perspectives in Mathematical Logic, Omega Series. Springer, Heidelberg (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.