0
$\begingroup$

Find the cardinality of all the infinite binary sequences that don't contain 010

I think it's $\aleph_0$. I marked the set all infinite binary sequences that don't contain 010 in A, and the set of All the infinite binary sequences that don't contain 01 in B. $B\subseteq A$, and $|B|=\aleph_0$, therefore $\aleph_o\le|A|$. But I don't know how to show that $|A|\le\aleph_o$ . Thanks

$\endgroup$
  • 1
    $\begingroup$ Consider the set C all sequences made up of 11 and 00. Such sequences cannot contain 010. What do you think its cardinality is? $\endgroup$ – almagest Jun 24 '16 at 14:36
0
$\begingroup$

This is not $\aleph_0$, but rather $2^{\aleph_0}$, as it contains all 0-1 sequences of the form \begin{equation} x_1x_1x_2x_2x_3x_3x_4x_4\ldots \end{equation} where $x_i\in\{0,1\}$.

$\endgroup$
  • 1
    $\begingroup$ I don't know of any standard meaning for $\aleph$. What does it mean here? $\endgroup$ – TonyK Jun 24 '16 at 14:41
  • $\begingroup$ I apologize, I have meant the cardinality of the continuum: $2^{\aleph_0}$. $\endgroup$ – Bach Jun 24 '16 at 14:42
0
$\begingroup$

There is a bijection from the set of all binary sequences to the set of all sequences not containing 010: just replace all occurrences of 01 with 011. And the cardinality of the set of all binary sequences is...?

$\endgroup$

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.