We show that every non-low c.e. set joins all Δ20 diagonally non-computable functions to ∅′. We give two proofs: a direct argument, and a proof using an analysis of functions that are DNC relative to an oracle, extending work by Day and Reimann. The latter proof is also presented in the language of Kolmogorov complexity.

Abstract We show that there is a lowT-upper bound for the class ofK-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in T-degrees for which there is a lowT-upper bound.

One recursively enumerable real $\alpha$ dominates another one $\beta$ if there are nondecreasing recursive sequences of rational numbers $(a[n]:n\in\omega)$ approximating $\alpha$ and $(b[n]:n\in\omega)$ approximating $\beta$ and a positive constant C such that for all n, $C(\alpha-a[n])\geq(\beta-b[n])$. See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin's Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350--359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the $\Omega$-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350--359]. Second, we show that the sets in a universal Martin-Löf test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Löf test.

Abstract A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RANDA.

Abstract It is shown that the low basis theorem is meaningful and provable in IΣ1 and that the priority-free solution to Post's problem formalizes in this theory.