A STRONG LAW OF COMPUTATIONALLY WEAK SUBSETS
Bjørn Kjos-Hanssen · Journal of Mathematical Logic · 2011
We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event [Formula: see text] such that if [Formula: see text] then X has an infinite subset Y such that no element of [Formula: see text] is Turing computable from Y.