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 Delta02 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 Delta02 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.