Relative Randomness and Cardinality
George Barmpalias · Notre Dame Journal of Formal Logic · 2010
A set B ⊆ N 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 Δ 2 0 set B is low for Martin-Löf random if and only if the class of oracles which compress less efficiently than B, namely, the class 𝒞 B = { A | ∀ n K B ( n ) ≤ + K A ( n ) } is countable (where K denotes the prefix-free complexity and ≤ + denotes inequality modulo a constant. It follows that Δ 2 0 is the largest arithmetical class with this property and if 𝒞 B is uncountable, it contains a perfect Π 1 0 set of reals. The proof introduces a new method for constructing nontrivial reals below a Δ 2 0 set which is not low for Martin-Löf random.