Antirandom reals

Question

This is a crossposting of https://math.stackexchange.com/questions/1446602/anti-random-reals, which has not gotten any answers; after thinking about the problem, I've become more convinced that it belongs here instead.

For a function $f: \mathbb{N}\rightarrow\mathbb{R}_{>0}$ and a set $X\subseteq \mathbb{R}$, an $f$-cover of $X$ is a sequence $(I_n)_{n\in\mathbb{N}}$ of open intervals with rational endpoints such that

• $X\subseteq\bigcup I_n$, and

• $\mu(I_n)<f(n)$.

Say that a set $X\subseteq\mathbb{R}$ is $f$-small if $X$ has an $f$-cover.

Talking about $f$-covers provides us with many different refinements of the notion of "measure zero": e.g., a set is strong measure zero if it has an $f$-cover for every function $f$.

Say that a set of reals $X$ is computably strong measure zero (csmz) if there is an $e$ such that $\Phi_e^f$ is an $f$-cover of $X$ whenever $f$ is a function from $\mathbb{N}$ to $\mathbb{R}_{>0}$. (This is sadly not the same as effective strong measure zero, a notion introduced by Kihara in his thesis; see also http://www.sciencedirect.com/science/article/pii/S016800721400044X.)

In computability theory, a real is said (informally) to be "random" if it is not in any "simple" measure-zero set; there are of course many ways to formalize this, but this is the basic theme. Csmz sets provide a very strong notion of non-randomness: say that an individual real $r$ is antirandom if $\{r\}$ is csmz - equivalently, if $r$ is contained in some csmz set. My question is:

What are the antirandom reals?

I strongly suspect that every antirandom real is computable, but I can't prove it. EDIT: As Joe Miller's answer below shows, my guess was really wrong!

---

Comment 1. The set of antirandom reals is countable, but the proof is surprisingly nontrivial. There is a countable set $\{A_i: i\in\omega\}$ of csmz sets such that every csmz set is contained in one of the $A_i$s; specifically, take $A_i$ to be the largest csmz set witnessed to be csmz by $\Phi_i$. Now, it can be forced that every strong measure zero set is countable (this is Borel's conjecture) - in such a forcing extension, the antirandoms are countable. Meanwhile, antirandomness is a $\Pi^1_1$ property. This means the statement "there are countably many antirandom reals" is $\Sigma^1_3$, and so absolute assuming large cardinals.

This argument is probably overkill, but (1) we do seem to need Borel's conjecture for coanalytic sets, which is independent of ZFC, and (2) we do seem to need $\Sigma^1_3$-absoluteness for proper forcing, which has nontrivial large cardinal strength (see http://www.logic.univie.ac.at/~sdf/papers/bagfried.pdf).

Comment 2. Thomas Andrews, in the comments section to the original question, proposed looking at "c-csmz" sets - these are sets which are csmz, but where we only allow computable sequences of epsilons. Say that a real $r$ is weakly antirandom if $\{r\}$ is a c-csmz set. I believe that there are noncomputable weakly antirandom reals, but I haven't been able to prove that yet; I would be interested in these reals as well. Note that the countability proof breaks down: a c-csmz set is not strong measure zero.

Answer 1

Let A be a c.e. set with the property that there are infinitely many stages $s$ such that $A_s\upharpoonright s = A\upharpoonright s$. Call such a stage "strongly true". Noncomputable $A$ with infinitely many strongly true stages can be produced using a movable marker construction.

I claim that any such $A$ is antirandom.

Define $\Phi_e^f$ as follows: First, we can compute from $f$ an increasing function $g$ such that $2^{-g(n)}<f(n)$ for all $n$. The $n$th interval in our cover should be $I_n = \left[\;A_{g(n+1)}\upharpoonright g(n)\;\right]$.

To verify that this works, just note that if $s\in[g(n),g(n+1)]$ is a strongly true stage, then $I_n$ covers $A$.

Improved Example: I claim that if $A$ is a rank 1 point in a $\Pi^0_1$ class, then $A$ is antirandom. It can be shown that this subsumes the previous answer, and furthermore, there is a rank 1 point $A\equiv_T\emptyset''$, so not all antirandom sets are $\Delta^0_2$.

To see the claim, let $P$ be a $\Pi^0_1$ class with exactly one limit point $A$. First, note that it is true that there is an $f$-cover of $P$ for every $f$, and in fact, one that uses only finitely many intervals. To see this, fix $f$ and start by covering $A$ with an interval $I_0$ of length $f(0)$. Now there are only finitely many points of $P$ not covered, and they can be covered by finitely many of the remaining $I_n$'s.

Now note that by compactness, we will eventually see that an $f$-cover of $P$ using only finitely many $I_n$'s is correct, so relative to $f$, we can search for such a cover.

Even Better: This argument can be improved to any member of any countable $\Pi^0_1$ class. This is because countable classes are strongly measure zero and, by compactness, only finitely many of the $I_n$'s are needed for any fixed $f$. So a search (relative to the given $f$) will find an $f$-cover.

This means that antirandom sets can have complexity as high as we would like in the hyperarithmetical hierarchy.

Suggestion: Maybe there is a nice relationship between antirandom and never continuously random (NCR)? After all, Kjos-Hanssen and Montalbán showed that members of countable $\Pi^0_1$ classes are NCR. I'm just copying their idea.

My Final Edit: Actually, it is easy to see that every antirandom $A$ is NCR. Given a name $m$ for a continuous measure $\mu$, we can find a function $f$ such that every interval of length $f(n)$ has $\mu$-measure at most $2^{-n}$. Now using the fact that $A$ is antirandom, we can build a $\mu$-ML test relative to $m$ covering $A$.

Note that Reimann and Slaman showed that every NCR is hyperarithmetic (which gives another proof that the collection of antirandom sets is countable).

So we are left with the following:

Question: If $A$ is NCR, must it be antirandom?

Answer 2

I don't have an answer to the main question, but there is a noncomputable weakly antirandom real; in fact we can build a perfect c-csmz $\Pi^0_1$-class $Q$.

We have strategies for every partial computable sequence of epsilons $\psi$. A strategy begins by choosing a large $n$ and waiting until $\psi$ has converged on the first $2^{n+1}$ elements. Let $\epsilon_0$ be the least of these first $2^{n+1}$ epsilons, and $s$ the stage at which we see this convergence. For every $\sigma \in 2^{n+1}$ with $[\sigma] \cap Q_s$ not empty, our strategy chooses a $\tau$ extending $\sigma$ with $[\tau] \cap Q_s$ not empty and $\mu([\tau]) < \epsilon_0$ and declares that $[\sigma] \cap Q_{s+1} = [\tau] \cap Q_s$. Arrange these strategies in a finite injury construction.

Now we can define $\Phi$. Given a sequence of epsilons as an oracle, it waits until it sees some strategy act with $\epsilon_0$ and $n$ such that $\epsilon_0$ is no more than the least of the first $2^{n+1}$ elements of the sequence. When this occurs, we can define $I_0, \dots, I_{2^{n+1}-1}$ such that they cover all of $Q_{s+1}$ by covering the appropriate $\tau$. We will eventually see such a strategy as long as the oracle is a computable sequence of epsilons. We can define the remaining $I_k$ in any way consistent with the sequence.

Edit: In fact, any weakly 1-generic will be weakly antirandom. Just have $\Phi$ choose intervals in some dense fashion.