2
$\begingroup$

Let $A$ be a bi-immune set, that is, an immune set whose complement is also immune. An immune set (let's say $A$) is a set of natural numbers (the natural numbers include 0) such that: i. $A$ is infinite, and ii. for every infinite r.e. set $B$, $B$ $\cap$ $\overline A$ $\ne$ $\emptyset$.

Question: Are the finite subsets of bi-immune sets 'random', and if so, what is the proper notion of 'randomness' for such finite sets?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

List all the infinite r.e. sets as $E_n$ $(n\in\mathbb N)$. Define $A$ to be the set $\{a_n:n\in\mathbb N\}$, where the numbers $a_n$ are defined by induction on $n$ as follows: $a_0$ is the second element of $E_0$. $a_{n+1}$ is the second element $>a_n!!!$ in $E_{n+1}$. Then $A$ is bi-immune, because, for all $n$, $A\cap E_n$ contains $a_n$ while $\overline A\cap E_n$ contains the first element $>a_{n-1}!!!$ in $E_n$ (or, when $n=0$, the first element of $E_0$).

Because of the huge gaps between the $a_n$'s, nothing about this $A$ looks random to me.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How does $A$ not looking random square with the following statement made by Jockusch and Lewis in their paper, "Diagonally Non-computable Functions and Bi-Immunity": 'Finally, a set is bi-immune if neither $A$ nor its complement $\bar A$ contains an infinite c.e. set. This can be thought of as a very weak kind of randomness since it says that it is impossible to correctly predict for infinitely many $n$ whether or not $n$ belongs to $A$. It is easy to see that every that every 1[Martin-Lof]-random is Kurtz-random, and that every Kurtz-random set is bi-immune [implying that $\endgroup$
    – Thomas Benjamin
    Commented Apr 26, 2021 at 21:08
  • 1
    $\begingroup$ @ThomasBenjamin The "very weak kind of randomness" in that quotation is so weak that it applies not only to random things but also to generic things (e.g., Cohen-generic over some countable model of ZF), to sets like my example, and to lots of other things. In particular, it doesn't imply most of the phenomena that one usually views as implicit in randomness, like the law of large numbers. $\endgroup$
    – Andreas Blass
    Commented Apr 26, 2021 at 21:14
  • $\begingroup$ (cont.) every 1-random set is bi-immune]. Also, it is easily shown that these implications are strict'. It would seem, then, that (by your and Dr. Schweber's examples and your most recent comment) one should be able to partition the bi-immune sets into '1-random bi-immune sets', 'Cohen-generic bi-immune sets (is this really possible?), etc. True or false? $\endgroup$
    – Thomas Benjamin
    Commented Apr 26, 2021 at 21:21
  • 1
    $\begingroup$ @ThomasBenjamin False unless you're very generous with the "etc." at the end of your statement. For example, I see no reason for bi-immune sets to be generic for any notion of forcing over any countable models. And the use of ZF in my previous comment was unnecessarily strong. A real Cohen-generic over the smallest admissible set is already a lot more than bi-immune; it and its complement each meet every hyperarithmetic set, not just every r.e. set. $\endgroup$
    – Andreas Blass
    Commented Apr 26, 2021 at 21:40
1
$\begingroup$

Suppose $X$ is bi-immune and $f:\mathbb{N}\rightarrow\mathbb{N}$ is a strictly increasing computable function. Define sets $I_n$ as follows:

  • $I_0=[0,f(0)]$.

  • $I_{n+1}=(f(n), f(n+1)]$.

Now let $$X_f=\bigcup_{n\in X}I_n.$$ The set $X_f$ is also bi-immune, but by picking $f$ appropriately we can make $X_f$ look very far from random in any sense I can think of. So not only (per Andreas) can we construct some bi-immune set which is "far from random," we have a uniform procedure for constructing, given any bi-immune set, such an "unrandom" bi-immune set which is very similar to it (e.g. in the same $m$-degree).

Improve this answer
$\endgroup$
2
  • $\begingroup$ In regards to Prof. Blass's comment to me, do your and Prof. Blass's examples form a specific subclass of bi-immune sets? $\endgroup$
    – Thomas Benjamin
    Commented Apr 26, 2021 at 21:28
  • $\begingroup$ @ThomasBenjamin Not that I can think of. $\endgroup$
    – Noah Schweber
    Commented Apr 26, 2021 at 21:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .