0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ comment deleted $\endgroup$ – George Tomlinson Oct 18 '13 at 14:53
3
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ AHA! So I have to consider removing the finite set from the infinite set. Correct? $\endgroup$ – Don Larynx Oct 18 '13 at 15:11
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Oct 18 '13 at 15:16
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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.

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

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.