# Is the set of binary sequences with no consecutive ones countable?

A binary sequence is an infinite list of zeroes and ones, ie, $b$ is a binary sequence means that $b = b_1,b_2,b_3,...,b_i,...,$ where each $b_i \in \{0,1\}$. Let $C$ be the subset of $B$ containing only those sequences that have no consecutive ones. Decide whether or not C is countable.

My attempt:

Consider an element $c_i \in C$ and its sequence of digits in a decimal expansion, perhaps $0.1010101.$ Although there may be no consecutive ones, there may be infinitely many ones. Thus another element $c_{i+1}$ and its sequence could be $0.1010101$. The only way a certain $c_n$ couldn't belong in $C$ is if it had at least two 1's next to each other, which simply can't be the case. This makes $C$ countably infinite.

• comment deleted – George Tomlinson Oct 18 '13 at 14:53

No, you are wrong, $C$ is uncountable. And it's not that hard to define injective function $f:B\to C$. For instance you could insert $0$ between every consecutive digits in each sequence from $B$. Now knowing that $B$ is uncountable, $C$ is also uncountable by Cantor-Bernstein-Schroeder theorem.

Edit: You are not removing anything. We got injection from $B$ into $C$, so $|B|\leq|C|$, which is already sufficient to conclude that $C$ is uncountable, as $B$ is uncountable. But also $|C|\leq|B|$, as $C\subset B$, hence $|B|=|C|$. And just to be precise $f$ can by defined by: $$f(b)(n) = \begin{cases} b\left(\frac n2\right), & \text{if n is even} \\ 0, & \text{if n is odd} \\ \end{cases}$$

• AHA! So I have to consider removing the finite set from the infinite set. Correct? – Don Larynx Oct 18 '13 at 15:11
• @DonLarynx: no, you are not removing anything. He is showing how to establish a bijection between $B$ and $C$ by showing you have an injection both ways. – Ross Millikan Oct 18 '13 at 15:16

You can use a Cantor diagonal argument to show that all of the sequences with blocks 00 and 01 are uncountable. Examples of these block sequences:

0100010001....... 00000101000001.....

NO:

1000.....

These form a subset of the set you are asking about.

Let $a=\{a_n\}$ be a sequence of positive integers. Define $S(a)\in C$ by $$S(a)=(0)_{a_1}1(0)_{a_2}1(0)_{a_3}1\dots,$$ where $(0)_k$ means $k$ consecutive $0$'s. $S$ is an injection from $\mathbb{N}^\mathbb{N}$ into $C$, so that $C$ is uncountable.

• Oh, so it's simply all of the binary sequences but listed consecutively, isn't it @Julian? – Don Larynx Oct 27 '13 at 23:13
• I do not understand your comment. My construction assigns to each sequence of positive integers a unique binary sequence without consecutive ones. – Julián Aguirre Oct 28 '13 at 10:03
• But it's still infinite, meaning every binary sequence shall be included. @Julian – Don Larynx Oct 28 '13 at 12:25

A hint:

Consider the subset $C'\subset C$ consisting of the sequences beginning with $1$, having infinitely many ones and only $1$ or $2$ zeros between consecutive ones. Recode the sequences $b\in C'$ in a way that makes the anser to your problem immediately apparent.

Use Cantor's diagonal proof with adjustment:

Observe two consecutive bits as a pair, you'll find that those bits belong to the set {01, 10, 00} . Put { 01, 10 } to group A and { 00 } to group B, and then your sequence will be ABBABA....... something like that. Ready for diagonal proof!

Thanks hardmath for pointing out the mistakes. I know that there is an accepted answer, just providing another method to deal with this problem.

• oh sorry my bad... – Chih-Yang Yeh Apr 7 '16 at 19:20