I'm currently learning about computability theory, specifically about Martin-Löf randomness. In this paper by M. Pancia, I came across an interesting result called Solovay's lemma (below, I give the relevant definitions needed to understand this lemma):
Let $V_1,V_2,\ldots$ be a sequence of uniformly $\Sigma_0^1$ sets and $X\in 2^\mathbb{N}$ Martin-Löf random. If $\sum_{n=1}^{\infty}\mu(V_n) < \infty$, then $X$ lies in only finitely many $V_n$.
The paper cites this other paper as its source for this lemma. However in this paper, they make the additional assumption that $S=\sum_{n=1}^{\infty}\mu(V_n)$ is computable.
When I tried to prove this lemma in the setting of Pancia's paper, I also seem to need that $S$ is computable. The reason I need this is because in the original proof, they essentially construct an algorithm which, given input $M$, computes a $k$ such that $\sum_{n=k}^{\infty}\mu(V_n)<1/M$ and such an algorithm seems impossible to construct if $S$ is not computable.
So my question is: Is this an oversight by the author, meaning that $S$ does need to be computable, or is there some way to prove Solovay's lemma without this computability assumption?
Thanks in advance!
--
Some definitions used in the paper:
- Fix a Gödel numbering and let $\varphi_{e}(x)$ be the output of the program with Gödel number $e$ running with input $x$ (if it halts).
- Letting $X$ be an element of $2^\mathbb{N}$, we define $\varphi_{e}^X(x)$ as above, except $X$ is used as an oracle in the computation.
- For any Gödel number $e$, define $$S_e = \{ X\in 2^\mathbb{N}: \varphi_{e}^X \text{ halts on input }0 \}$$
- We say a sequence $V_n$ of $\Sigma_0^1$ sets is effectively open or uniformly $\Sigma_0^1$ if $V_n = S_{f(n)}$, where $f$ is a total recursive function.
- A set $S$ is effectively null if $S \subseteq \cap_{n} V_n$, where $V_n$ are uniformly $\Sigma_0^1$ and $\mu(V_n)<2^{-n}$.
- $X\in 2^\mathbb{N}$ is Martin-Löf random if $X$ does not lie in any effectively null set.
You do not need the assumption that $\Sigma_{n = 1}^\infty \mu(V_n)$ is computable. This is a standard result in algorithmic randomness and you can find the result in any textbook on the field. For instance, it is theorem 6.2.8 in Algorithmic Randomness and Complexity by Downey and Hirschfeldt.
Here's the idea of the proof. First, let's assume that $\Sigma_{n = 1}^\infty \mu(V_n) < 1$ (if not, just throw away a finite number of the $V_n$'s so that the sum is less than 1). Now set $U_n$ to be the set of reals which occur in at least $2^n$ of the $V_m$'s. This sequence of $U_n$'s is uniformly $\Sigma^0_1$ and its intersection contains all those reals which occur in infinitely many $V_m$'s. And $\mu(U_n) < 2^{-n}$, basically because each element of $U_n$ gets "counted" $2^n$ times in $\Sigma_{m = 1}^\infty \mu(V_m) < 1$. So the $U_n$'s form a Martin-Löf test.