Weak 2-randomness

1. A Martin-Löf test describes a null $\Pi^0_2$ class. Let $\bigcap_n \mathcal U_n$ be null, with decreasing $\mathcal U_n$. The relation $\lambda(\mathcal U_n) \leq 2^{-k}$ is $\Pi^0_1$, since $\lambda(\mathcal U_n)$ is left-c.e. uniformly in $n$; so $\emptyset'$ computes, for each $k$, the least $n_k$ with $\lambda(\mathcal U_{n_k}) \leq 2^{-k}$, which exists since $\lambda(\mathcal U_n)$ tends to $0$. The classes $\mathcal U_{n_k}$ form a Martin-Löf test relative to $\emptyset'$ containing $\bigcap_n \mathcal U_n$.
2. Let $A = \lim_s A_s$ with $(A_s)$ computable. The classes $\mathcal U_{\langle n, t \rangle} = \bigcup_{s > t} [A_s \uh n]$ are uniformly $\Sigma^0_1$, and their intersection is $\{ A \}$: a sequence $X$ in all of them agrees, for every $n$, with $A_s \uh n$ for infinitely many $s$, hence with $A \uh n$. This is a null $\Pi^0_2$ class containing $A$.
3. Let $\bigcap_n \mathcal U_n$ be null. Some $\mathcal U_n$ has measure less than $1$, so its complement is a non-empty $\Pi^0_1$ class, whose leftmost member is $\Delta^0_2$. By (2), it is not weakly 2-random, yet it is outside $\bigcap_n \mathcal U_n$.

(2 ⇒ 3) Every c.e. set is $\Delta^0_2$.

(3 ⇒ 1) Let $A = \lim_s A_s$ be non-computable and $\Delta^0_2$, with $\Phi^Z = A$. The classes $\mathcal U_{\langle n, t \rangle} = \bigcup_{s > t} \{ X : \Phi^X \uh n = A_s \uh n \}$ are uniformly $\Sigma^0_1$, and, as in Proposition 2.2 (2), their intersection is $\{ X : \Phi^X = A \}$, which is null by Sacks’s theorem (Sacks). It contains $Z$.

(1 ⇒ 2) Let $Z \in \bigcap_n \mathcal U_n$, a null $\Pi^0_2$ class with decreasing $\mathcal U_n$, and let $\mathcal U_{n,t}$ be the clopen approximation of $\mathcal U_n$ at stage $t$, generated by the strings enumerated by stage $t$; it increases with $t$, and $\mathcal U_n = \bigcup_t \mathcal U_{n,t}$. We enumerate a set $A$, together with classes $\mathcal V_e$. At stage $t$, for each $e \leq t$ such that no element has been enumerated for $e$ and $W_{e,t} \cap A_t = \emptyset$, if there is $n \in W_{e,t}$ with $n > 2e$ and $\lambda(\mathcal U_{n,t}) < 2^{-e}$, enumerate the least such $n$ into $A$, and let $\mathcal V_e = \mathcal U_{n,t}$. If $e$ never acts, $\mathcal V_e = \emptyset$.

$A$ is simple, hence not computable. Each $e$ enumerates at most one element, larger than $2e$, so $A$ has infinite complement. If $W_e$ is infinite, it contains $n > 2e$ with $\lambda(\mathcal U_n) < 2^{-e}$, since these measures tend to $0$, and then $\lambda(\mathcal U_{n,t}) < 2^{-e}$ for every $t$. At every stage $t \geq e$ with $n \in W_{e,t}$, either $W_{e,t}$ already meets $A_t$, or $e$ has already acted, or $e$ acts; in each case $A$ meets $W_e$ (when $e$ acts, it enumerates an element of $W_{e,t}$).

$Z$ computes $A$. The classes $\mathcal V_e$ are clopen, uniformly c.e. in $e$, with $\lambda(\mathcal V_e) < 2^{-e}$: a Solovay test. Since $Z$ is random, $Z$ belongs to $\mathcal V_e$ for finitely many $e$ only (Solovay), and these $e$ enumerate finitely many elements. Let $m$ exceed them. For $n \geq m$, if $n$ enters $A$ at stage $t$, then $Z \notin \mathcal U_{n,t}$. To decide whether $n \geq m$ belongs to $A$, search for the least stage $t$ with $Z \in \mathcal U_{n,t}$, which exists since $Z \in \mathcal U_n$; then $n \in A$ if and only if $n \in A_t$, since $\mathcal U_{n,t}$ increases with $t$.