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
  • 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
    Commented Jun 24, 2016 at 14:36

2 Answers 2

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$
2
  • 1
    $\begingroup$ I don't know of any standard meaning for $\aleph$. What does it mean here? $\endgroup$
    – TonyK
    Commented Jun 24, 2016 at 14:41
  • $\begingroup$ I apologize, I have meant the cardinality of the continuum: $2^{\aleph_0}$. $\endgroup$
    – Bach
    Commented Jun 24, 2016 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$
0

You must log in to answer this question.

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