Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T23:04:59.680Z Has data issue: false hasContentIssue false
  • English
  • Français

Relative enumerability and 1-genericity

Published online by Cambridge University Press:  12 March 2014

Wei Wang
Wei Wang*
Affiliation:
Institute of Logic and Cognition and Department of Philosophy, Sun Yat-Sen University, 135 Xingang Xi Road, Guangzhou 510275, Pr., China, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A set of natural numbers B is computably enumerable in and strictly above (or c.e.a. for short) another set C if C <TB and B is computably enumerable in C. A Turing degree b is c.e.a. c if b and c respectively contain B and C as above. In this paper, it is shown that if b is c.e.a. c then b is c.e.a. some 1-generic g.

Keywords

Turing degreesrelative enumerability1-generic
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 3 , September 2011 , pp. 897 - 913
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ambos-Spies, Klaus, Ding, Decheng, Wang, Wei, and Yu, Liang, Bounding non-GL2 and r.e.a., this Journal, vol. 74 (2009), no. 3, pp. 989–1000.Google Scholar
[2]Ambos-Spies, Klaus, Lachlan, Alistair H., and Soare, Robert I., The continuity of cupping to 0′, Annals of Pure and Applied Logic, vol. 64 (1993), no. 3, pp. 195–209.CrossRefGoogle Scholar
[3]Cai, Mingzhong and Shore, Richard, Domination, forcing, array nonrecursiveness and relative recursive enumerability, to appear.Google Scholar
[4]Dekker, J. C. E., A theorem on hypersimple sets, Proceedings of the American Mathematical Society, vol. 5 (1954), pp. 791–796.CrossRefGoogle Scholar
[5]Jockusch, Carl G. Jr., Degrees of generic sets, Recursion theory: Its generalizations and applications, Proceedings of Logic Colloquium '79, Leeds, August 1979 (Drake, F. R. and Wainer, S. S., editors), Cambridge University Press, Cambridge, U. K., 1980, pp. 110–139.Google Scholar
[6]Kumabe, Masahiro, Relative recursive enumerability of generic degrees, this Journal, vol. 56 (1991), no. 3, pp. 1075–1084.Google Scholar
[7]Kurtz, Stuart, Randomness and genericty in the degrees of unsolvability, Ph.D. thesis, University of Illinios at Urbana-Champaign, 1981.Google Scholar
[8]Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer–Verlag, Heidelberg, 1987.CrossRefGoogle Scholar
[9]Yu, Liang, Lowness for genericity, Archive for Mathematical Logic, vol. 45 (2006), no. 2, pp. 233–238.CrossRefGoogle Scholar