Let $\Omega$ be the halting probability (see (http://en.wikipedia.org/wiki/Chaitin's_constant) and R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity for reference). If A is Martin-Löf random with respect to $\Omega$ (so A is 2-random), does A compute an infinite set $G\subseteq \Omega$ or $G\subseteq 2^\omega-{\Omega}$ ? This was motivated by the idea of constructing models using random sets to avoid $SRT_2^2$ in the reverse mathematics context.
1 Answer
$\begingroup$
$\endgroup$
0
No. Since $A$ is ML-random relative to $\Omega$, by van Lambalgen's theorem it follows that $\Omega$ is ML-random relative to $A$. If $A$ could compute such a set $G = \{g_0 < g_1 < g_2 < \dots \}$, then $A$ could form the ML-test $(V_n)_{n \in \omega}$, where $V_n = \{ X : (\forall i < n )[X(g_i) = 1]\}$. Note that $\mu(V_n) = 2^{-n}$. This would capture $\Omega$, a contradiction.
Replace $X(g_i) = 1$ with $X(g_i) = 0$ for the case $G \subseteq 2^{\omega} - \Omega$.