Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-28T11:32:48.308Z Has data issue: false hasContentIssue false
  • English
  • Français

Jump inversions inside effectively closed sets and applications to randomness

Published online by Cambridge University Press:  12 March 2014

George Barmpalias ,
Rod Downey  and
Keng Meng Ng
George Barmpalias
Affiliation:
Institute for Logic, Language and Computation, Universiteit van Amsterdam, P.O. Box 94242, 1090 Ge Amsterdam, The, Netherlands, E-mail: [email protected] URL: http://www.barmpalias.net/
Rod Downey
Affiliation:
School of Mathematics, Statistics and Operations Research, Victoria University, P.O. Box 600, Wellington, New Zealand, E-mail: [email protected]
Keng Meng Ng
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study inversions of the jump operator on classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A further application is the complete solution of [24, Problem 3.6.9]: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails.

Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 2 , June 2011 , pp. 491 - 518
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]Barmpalias, George, Miller, Joseph S., and Nies, André, Randomness notions and partial relativization, submitted.Google Scholar
[2]Cenzer, D. and Remmel, J. B., classes in mathematics, Handbook of recursive mathematics – Volume 2, Recursive algebra, analysis and combinatorics (Ershov, Yu. L., Goncharov, S. S., Nerode, A., Remmel, J. B., and Marek, V. W., editors), Studies in Logic and the Foundations of Mathematics, 139, Elsevier, 1998, pp. 623–821.CrossRefGoogle Scholar
[3]Cenzer, Douglas, classes in computability theory, Handbook of computability theory (Griffor, E. R., editor), Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland, Amsterdam, 1999, pp. 37–85.CrossRefGoogle Scholar
[4]Cooper, S. B., Minimal degrees and the jump operator, this Journal, vol. 38 (1973), pp. 249–271.Google Scholar
[5]Downey, Rod and Greenberg, Noam, Turing degrees of reals of positive packing dimension, Information Processing Letters, vol. 108 (2008), pp. 198–203.CrossRefGoogle Scholar
[6]Downey, Rod and Hirschfeldt, Denis, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer-Verlag, 2010.CrossRefGoogle Scholar
[7]Downey, Rod, Jockusch, Carl G. Jr., and Stob, Michael, Array nonrecursive sets andgenericity, Computability, enumerability, unsolvability: Directions in recursion theory, London Mathematical Society Lecture Notes Series, vol. 224, Cambridge University Press, 1996, pp. 93–104.CrossRefGoogle Scholar
[8]Downey, Rod and Miller, Joseph S., A basis theorem for classes of positive measure and jump inversion for random reals, Proceedings of the American Mathematical Society, vol. 134 (2006), no. 1, pp. 283–288, (electronic).CrossRefGoogle Scholar
[9]Downey, Rod, Nies, André, Weber, Rebecca, and Yu, Liang, Lowness and null sets, this Journal, vol. 71 (2006), pp. 1044–1052.Google Scholar
[10]Friedberg, R. M., A criterion for completeness of degrees of unsolvability, this Journal, vol. 22 (1957), pp. 159–160.Google Scholar
[11]Gács, Péter, Every sequence is reducible to a random one, Information and Control, vol. 70 (1986), no. 2–3, pp. 186–192.CrossRefGoogle Scholar
[12]Gaifman, Haim and Snir, Marc, Probabilities over rich languages, testing and randomness, this Journal, vol. 47 (1982), no. 3, pp. 495–548.Google Scholar
[13]Jockusch, C. Jr. and Stephan, Frank, A cohesive set which is not high, Mathematical Logic Quarterly, vol. 39 (1993), pp. 515–530.CrossRefGoogle Scholar
[14]Jockusch, C. Jr. and Stephan, Frank, Correction to “a cohesive set which is not high”, Mathematical Logic Quarterly, vol. 43 (1997), p. 569.CrossRefGoogle Scholar
[15]Jockusch, Carl G. Jr. and Soare, Robert I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[16]Kautz, S., Degrees of random sets, Ph.D. Dissertation, Cornell University, 1991.Google Scholar
[17]Kučera, Antonín, Measure, -classes and complete extensions of PA, Recursion theory week (Oberwolfach, 1984) (Ambos-Spies, K., Sacks, G. E., and Müller, G. H., editors), Lecture Notes in Mathematics, vol. 1141, Springer, Berlin, 1985, pp. 245–259.CrossRefGoogle Scholar
[18]Kučera, Antonín, An alternative, priority-free, solution to Post's problem, Mathematical foundations of computer science, 1986 (Bratislava, 1986) (Gruska, J. and Wiedermann, J.Rovan, B., editors), Lecture Notes in Computer Science, vol. 233, Springer, Berlin, 1986, pp. 493–500.Google Scholar
[19]Kurtz, S., Randomness and genericity in the degrees of unsolvability, Ph.D. Dissertation, University of Illinois, Urbana, 1981.Google Scholar
[20]Martin, D., Measure, category, and degrees of unsolvability, unpublished manuscript, 1960s.Google Scholar
[21]Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[22]Merkle, W., Miller, J., Nies, A., Reimann, J., and Stephan, F., Kolmogorov–Loveland randomness and stochasticity, Annals of Pure and Applied Logic, vol. 138 (2006), pp. 183–210.CrossRefGoogle Scholar
[23]Miller, Joseph S. and Nies, André, Randomness and computability: open questions, The Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 390–410.CrossRefGoogle Scholar
[24]Nies, André, Computability and randomness, Oxford University Press, 2009.CrossRefGoogle Scholar
[25]Nies, André, Stephan, Frank, and Terwijn, Sebastiaan A., Randomness, relativizalion and Turing degrees, this Journal, vol. 70 (2005), no. 2, pp. 515–535.Google Scholar
[26]Posner, David, The upper semilattice of degrees below 0′ is complemented, this Journal, vol. 46 (1981), pp. 705–713.Google Scholar
[27]Sacks, G. E., Degrees of unsolvability, Annals of Mathematical Studies, vol. 55, Princeton University Press, 1963.Google Scholar
[28]Shoenfield, J., On degrees of unsolvability, Annals of Mathematics. Second Series, vol. 69 (1959), pp. 644–653.CrossRefGoogle Scholar
[29]Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[30]Stephan, F. and Yu, L., Lowness for weakly 1-generic and Kurtz-random, Proceedings of Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 3959, Springer, 2006, pp. 756–764.CrossRefGoogle Scholar
[31]Stephan, Frank, Martin-Löf random and PK-complete sets, Logic colloquium '02 (Chatzidakis, Z., Koepke, P., and Pohlers, W., editors), Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 342–348.Google Scholar
[32]Stillwell, John, Decidability of the “almost all” theory of degrees, this Journal, vol. 37 (1972), pp. 501–506.Google Scholar
[33]Yu, Liang, When van Lambalgen's theorem fails, Proceedings of the American Mathematical Society, vol. 135 (2007), no. 3, pp. 861–864, (electronic).CrossRefGoogle Scholar