Relative randomness and Cardinality

Relative randomness and Cardinality

by G. Barmpalias

Summary

A set B is called low for Martin-Löf random if every Martin-Löf random set is also Martin-Löf random relative to B. We show that a $\Delta^0_2$ set B is low for Martin-Löf random iff the class of oracles which compress less efficiently than B is countable. It follows that $\Delta^0_2$ is the largest arithmetical class with this property and if is uncountable, it contains an effectively closed perfect set of reals. The proof introduces a new method for constructing non-trivial reals below a set which is not low for Martin-Löf random.