Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T23:24:07.672Z Has data issue: false hasContentIssue false

Jump inversions inside effectively closed sets and applications to randomness

Published online by Cambridge University Press:  12 March 2014

George Barmpalias
Affiliation:
Institute for Logic, Language and Computation, Universiteit van Amsterdam, P.O. Box 94242, 1090 Ge Amsterdam, The, Netherlands, E-mail: barmpalias@gmail.com 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: Rod.Downey@msor.vuw.ac.nz
Keng Meng Ng
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA, E-mail: selwyn.km.ng@gmail.com

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.

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable