Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-27T23:16:02.391Z Has data issue: false hasContentIssue false
  • English
  • Français

THE TURING DEGREES BELOW GENERICS AND RANDOMS

Published online by Cambridge University Press:  17 April 2014

RICHARD A. SHORE
RICHARD A. SHORE*
Affiliation:
DEPARTMENT OF MATHEMATICS, CORNELL UNIVERSITY, ITHACA NY 14853, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

If X0 and X1 are both generic, the theories of the degrees below X0 and X1 are the same. The same is true if both are random. We show that the n-genericity or n-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories (for generics and randoms) are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

Keywords

Turing degreesn-genericsn-randoms
Type
Articles
Information
The Journal of Symbolic Logic , Volume 79 , Issue 1 , March 2014 , pp. 171 - 178
Copyright
Copyright © Association for Symbolic Logic 2014 

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

Barmpalias, G., Day, A. R., and Lewis, A. E. M., The typical Turing degree. Proceedings of the London Mathematical Society, to appear, first published online December 15, 2013, doi:10.1112/plms/pdt065.Google Scholar
Chaitin, G. J., A theory of program size formally identical to information theory. Journal of the Association for Computing Machinery, vol. 22 (1975), pp. 329–340.Google Scholar
Chong, C. T. and Downey, R. G., Minimal degrees recursive in 1-generic degrees. Annals of Pure and Applied Logic, vol. 48 (1990), pp. 215–225.Google Scholar
Demuth, O. and Kučera, A., Remarks on 1-genericity, semigenericity and related concepts. Commentationes Mathematicae Universitatis Carolinae, vol. 28 (1987), pp. 85–94.Google Scholar
Downey, Rodney G. and Hirschfeldt, Denis R., Algorithmic randomness and complexity, theory and applications of computability, Springer, New York, 2010.Google Scholar
Gács, P., Every set is reducible to a random one. Information and Control, vol. 70 (1986),pp. 186–192.Google Scholar
Greenberg, N. and Montalbán, A., Embedding and coding below a 1-generic degree. Notre Dame Journal of Formal Logic, vol. 44 (2003), pp. 200–216.Google Scholar
Hodges, W., Model theory, Cambridge University Press, Cambridge UK, 1993.Google Scholar
Jockusch, C. G. Jr. Degrees of generic sets, Recursion theory: Its generalisation and applications, Proceedings of Logic Colloquium, University of Leeds, Leeds, 1979, London Mathematical Society Lecture Note Series, vol. 45, Cambridge University Press, Cambridge, New York, 1980, 110–139.Google Scholar
Kautz, A., Degrees of random sets, Ph.D. thesis, Cornell University, 1991.Google Scholar
Kurtz, S., Randomness and genericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois, 1981.Google Scholar
Kumabe, M., A 1-generic degree which bounds a minimal degree, this Journal, vol. 55 (1990),pp. 733–743.Google Scholar
Kuc̆era, A., Measure, ${\rm{\Pi }}_1^0 $ classes, and complete extensions of PA, Recursion theory week, Proceedings of the Conference Held at the Mathematisches Forschungsinstitut in Oberwolfach, April 15–21, 1984 , (Ebbinghaus, H.-D., Muller, G. H., and Sacks, G. E., editors), vol. 1141, Springer-Verlag, Berlin, 1985, pp. 245–259.Google Scholar
Nies, A., Shore, R. A., and Slaman, T. A., Interpretability and definability in the recursively enumerable degrees. Proceedings of the London Mathematical Society, vol. 77 (1998), no. 3, pp. 241–291.Google Scholar
Sacks, G. E., Degrees of unsolvability, Annals of Mathematics Studies, vol. 55, Princeton University Press, Princeton, NJ, 1966.Google Scholar
Shore, R. A., The theory of the degrees below $0{\rm{'}}$ . Journal of the London Mathematical Society , vol. 24 (1981), no. 3, pp. 1–14.Google Scholar
Shore, R. A., Direct and local definitions of the Turing jump. Journal of Mathematical Logic, vol. 7 (2007), pp. 229–262.Google Scholar
Shore, R. A., Biinterpretability up to double jump in the degrees below O’. Proceedings of the American Mathematical Society , vol. 142 (2014), pp. 351–360.Google Scholar
Shore, R. A., The Turing Degrees: An Introduction, in a volume of the Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore (Chi Tat, Chong, Qi, Feng, Yue, Yang, Slaman, Theodore, and Woodin, Hugh, editors), World Scientific Publishing, to appear.Google Scholar
Slaman, T. A. and Woodin, H. W., Definability in the Turing degrees. Illinois Journal of Mathematics, vol. 30 (1986), pp. 320–334.Google Scholar