EDIT: This has now been crossposted at MO: https://mathoverflow.net/questions/219366/antirandom-reals.

This is partially motivated by my question at mathoverflow: https://mathoverflow.net/questions/218810/relative-null-ness.

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}$. (This is sadly not the same as effective strong measure zero, a notion introduced by Kihara in his thesis; see also Higuchi and Kihara 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.

TECHNICAL NOTE: the set of antirandom reals is countable - this is because 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, it can be forced that every strong measure zero set is countable, and antirandomness is a $\Pi^1_1$ property (so "there are countably many antirandom reals" is absolute assuming large cardinals).

  • 1
    $\begingroup$ I lost you when you got to csmz, because you used a term $e$ and then put it into another term $\Phi_e^f$. I'm not sure what set $e$ is being chosen from and what $\Phi_e^f$ means. $\endgroup$ Sep 22, 2015 at 15:20
  • 1
    $\begingroup$ This is standard notation in computability theory: $e$ is a natural number, and $\Phi_e^f$ is the $e$th Turing machine run with oracle $f$. $\endgroup$ Sep 22, 2015 at 15:23
  • $\begingroup$ Thanks for explaining, I only took an intro theory of computation class. Unfortunately now that I have a better understanding of what you're asking, I have no idea how to characterize your antirandom reals. Looks like a good question though, I upvoted. =) $\endgroup$ Sep 22, 2015 at 15:28
  • 1
    $\begingroup$ Thanks! (For your amusement: the old notation for "the $e$th Turing machine" was "$\{e\}$." Clearly, this never led to any confusion. :P) $\endgroup$ Sep 22, 2015 at 15:35
  • 1
    $\begingroup$ If you restrict your definition to $f$ computable, that gives a broader condition - there exists $e$ and computable $g$ so that for $f=\Phi_i$ then $\Phi_{g(e,i)}$ computes such a sequence when $f$ is total. Call such a set "c-csmz." Any "csmz" set is "c-csmz," but not necessarily visa-versa. It might be worth trying to first find a non-computable $\{x\}$ which is c-csmz. $\endgroup$ Sep 22, 2015 at 16:10


Your Answer

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

Browse other questions tagged or ask your own question.