20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do we know what $\Phi_e^f$ is? $\endgroup$ – Anthony Quas Sep 27 '15 at 3:24
  • $\begingroup$ $\Phi_e^f$ is the result of running the $e$th Turing machine with $f$ as an oracle. $\endgroup$ – Noah Schweber Sep 27 '15 at 3:27
  • $\begingroup$ What will $\hspace{.04 in}f\hspace{-0.04 in}$-cover mean when $\: \operatorname{Range}(\hspace{.04 in}f) \not\subseteq (0,\hspace{-0.04 in}\scriptsize+\normalsize\infty\hspace{-0.03 in}) \;$? $\;\;\;\;$ $\endgroup$ – user5810 Sep 27 '15 at 6:20
  • $\begingroup$ @RickyDemer It won't mean anything then, we're only interested in $f$ which are sequences of positive reals. Why do you ask? $\endgroup$ – Noah Schweber Sep 27 '15 at 7:10
  • $\begingroup$ Your definition of csmz says "whenever $\hspace{.04 in}f$ is a function from $\mathbb{N}$ to $\mathbb{R}$." $\;$ $\endgroup$ – user5810 Sep 27 '15 at 7:17
11
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice! This works for $\Delta^0_2$-approximations, too, right? (If $A=\lim a(x, s)$ with $a$ computable, then call $s$ "strongly true" if $A\upharpoonright s=\{x<s: a(x, s)=1\}$ - then everything still checks out.) But it seems to stop there. Can we get a non-$\Delta^0_2$ antirandom real? $\endgroup$ – Noah Schweber Sep 27 '15 at 19:52
  • $\begingroup$ In the $\Delta^0_2$ case, it may not be enough to assume that $A_s\upharpoonright s$ is correct (for infinitely many $s$). That's not clear to me. It would be enough to assume that $A_s\upharpoonright s = A_t\upharpoonright s$ for all $t>s$. $\endgroup$ – Joe Miller Sep 27 '15 at 20:06
  • $\begingroup$ Hi Joe, can you tell me the definition of "never continuously random". $\endgroup$ – Ashutosh Sep 27 '15 at 21:15
  • $\begingroup$ The notion was introduced by Reimann and Slaman. They say that $A$ is never continuously random (NCR) if there is no continuous measure $\mu$ such that $A$ is Martin-Löf random with respect to $\mu$, where $\mu$ is used both as an oracle for the test and to measure the size of the test elements. To be precise, we don't use $\mu$ as an oracle, but discrete "names" of $\mu$; if for every name $m$ of $\mu$ there is a $\mu$-ML test relative to $m$ that covers $A$, then $A$ is not Martin-Löf random with respect to $\mu$. $\endgroup$ – Joe Miller Sep 27 '15 at 21:26
  • $\begingroup$ @JoeMiller, in your final edit, your proof shows that every anti-random is not $\mu$-Schnorr random for any continuous measure $\mu$. New question: If $A$ is Schnorr NCR is it antirandom? Also, it is not obvious off hand to me how to show that NCR and Schnorr NCR are different---if they even are. Last, there are subtleties about what I mean by Schnorr randomness relative to a noncomptuable measure. I think in this case, you need to have the test depend on the oracle, but it can depend in a uniform way. (I really need to finish my paper on SR for noncomptuable measures!) $\endgroup$ – Jason Rute Sep 29 '15 at 1:40
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.