subset of binary space countable?

Question

I know that the set of all binary sequences is uncountable. Now consider the subset of this set, that whenever a digit is $1$, its next digit must be $0$. Is this set countable?

I think it is not because it is like "half" of the set of binary sequences. By that I mean if I just delete the sequences with a $1$ followed by a $1$, then I'm left with the required sequence. But I'm not sure how to show this clearly. Can someone think of a bijection that would prove this? Or am I wrong? Please help.

Thanks

Answer 1

If you insist to have a bijection, here is one. Your set $S$ is the set of all binary infinite words containing no factor $11$. Any such word can be uniquely written as an infinite word on the alphabet $\{0, 10\}$, that is, $S = \{0, 10\}^\omega$. For instance, $$0100100010010(100)^\omega = \color{blue}{0}\color{red}{10}\color{blue}{0}\color{red}{10}\color{blue}{0}\color{blue}{0}\color{red}{10}0\color{red}{10}(\color{red}{10}\color{blue}{0})^\omega$$

It follows that the map from $\{0,1\}^\omega \to S$ consisting to replace every $1$ by $\color{red}{10}$ is a bijection. No need of the Cantor-Bernstein-Schroeder theorem.

Answer 2

You can explicitly write an injective function from the set of all binary sequences to the set you are considering: just map every sequence to one with $0$ inserted in every other position.

So no, this is definitely not countable.

Answer 3

Your set has an uncountable subset: consider the infinite sequences of $a$ and $b$ where $a=10$ and $b=00$, the set of these sequences has the same cardinality of the set of sequences of $0$ and $1$ (just map $a \mapsto 0$ and $b \mapsto 1$), and it is is clearly a subset of your set.

Answer 4

Here's another (possibly) interesting way of proving uncountability, since you tagged this as a topology question. You can inject your set into $[0,1]$ under the evaluation map

$$ (x_i) \mapsto \sum_{i = 1}^\infty \frac{x_i}{2^i} $$

This is injective on your set (but not the set of all binary sequences, since $0.0111\dots = 0.100\dots$). We shall show the image of this map is a perfect set, and hence uncountable (see Rudin, or some other source on metric spaces). Surely no point in the set is isolated, because if we have an expansion $x = 0.a_0 a_1 \dots a_2$, and if this expansion does not eventually end in all zeroes, we may truncate the expansion to find another number in the image which is as close to this number as possible. If the number does end in all zeroes, you may add a one to an arbitrary position to get another number as closed as possible. Now suppose $\lim x_i = x$, where each $x_i$ is in the image of the evaluation. We must have $0 < x < 1$, for if $x = 1$, the $x_i$ must eventually be of the form $0.11\dots$, which is impossible. Write $x = 0.a_0 a_1 \dots$. Suppose $a_k = 1$. If we force $|x_i - x| < 1/2^{k+2}$, then the first $k+2$ digits of $x_i$ must be the same as the first $k+1$ digits of $x$, hence $a_{k+1} = 0$. Thus the image is perfect, and the set is uncountable.

Intuition tells me this set is probably fractal, similar to the Cantor set, but I can't visualize it very well.

Answer 5

You can inject the set of all sequences of integers into this your set (call it $A$): $$ (n_i)_{i<\omega} \mapsto (1 + 0^{n_0+1} + 1 + 0^{n_1+1} + \dotsc)\colon \omega^\omega\to A. $$ where the value is meant as an infinite regular expression. That is, the $i$-th $1$ is followed by $n_i+1$ many $0$s. (The "$+ 1$" guarantees that the value under this function is a member of A.)

Thus, $A$ has cardinality $\lvert A\rvert \ge |\omega^\omega| = \lvert\Bbb R\rvert$. But $A\subseteq 2^\omega$, so $\lvert A\rvert \le \lvert 2^\omega\rvert = \lvert\Bbb R\rvert$. By the Cantor-Schroeder-Bernstein Theorem, $\lvert A\rvert = \lvert\Bbb R\rvert$.

Answer 6

Notation: $\chi_A (x)=1$ if $x\in A$, and $\chi_A (x)=0$ if $x\not \in A.$

Let $E=\{2 n:n\in N\}.$ For $S\subset E \;$ let $S^*=\{n :2 n\in S\}$ and let $f(S)=(\chi_{S^*} (n))_{n\in N}.$

Then $f$ is a bijection from the power-set $P(E)$ to the set $B$ of all binary sequences.

For $S\subset E$ let $g(S)=(\chi_S (n))_{n\in N}.$ Then $g$ is an injection from $ P(E)$ into the set $G$ of binary sequences $(b_n)_{n\in N}$ that satisfy $\forall n\in N\;(b_n=1\implies b_{n+1}=0)\}.$

Thus $g f^{-1}$ is an injection from $B$ into $G.$ So $G$ is uncountable because it has the uncountable subset $\{g f^{-1}(x): x\in B\}.$

The Cantor-Schroeder-Bernstein Theorem implies that for any $B,G$ with $G\subset B,$ there is a bijection $h:B\to G$ if there is an injection $i:B\to G.$