Effective randomness for continuous measures

Abstract:

We investigate which infinite binary sequences (reals) are effectively random with respect to some continuous (i.e., non-atomic) probability measure. We prove that for every $n$, all but countably many reals are $n$-random for such a measure, where $n$ indicates the arithmetical complexity of the Martin-Löf tests allowed. The proof rests upon an application of Borel determinacy. Therefore, the proof presupposes the existence of infinitely many iterates of the power set of the natural numbers. In the second part of the paper we present a metamathematical analysis showing that this assumption is indeed necessary. More precisely, there exists a computable function $G$ such that, for any $n$, the statement “All but countably many reals are $G(n)$-random with respect to a continuous probability measure” cannot be proved in $\mathsf {ZFC}^-_n$. Here $\mathsf {ZFC}^-_n$ stands for Zermelo-Fraenkel set theory with the Axiom of Choice, where the Power Set Axiom is replaced by the existence of $n$-many iterates of the power set of the natural numbers. The proof of the latter fact rests on a very general obstruction to randomness, namely the presence of an internal definability structure.