0
$\begingroup$

As the title suggests, the question is :

What is the cardinality of all binary sequnces (infinte and finite) that the sequnce 01 does not apper in them ?

I'll tell you where im stuck, let's say f is a function that recieves a natural number and creates a sequence of just ones, i.e : f(6) = (1,1,1,1,1,1), f(2) =(1.1). Uniting this countable sets togheter will generate a countable set, so lets call the orinignal set(the one we need to find his cardinality) A, so A>= 0א because this set is a subset of A.

Also, A is a subset of all binary sqeunces (infinte and finite) and all the binary sqeunces cardinaliy is א, so A <= א.

So right now i have א0 <= A <= א, which does not help me a lot because i need to find out if its א or א0.

Thanks in advance !

$\endgroup$
1
$\begingroup$

If $0$ appears in the sequence, then all the following terms must be $0$ so that $01$ does not appear in the sequence. So the sequences are: $$000\ldots\\ 10000\ldots\\ 11000\ldots\\$$

and so on. The sequence $111\ldots$ is also included. This is clearly a countable set.

$\endgroup$
  • $\begingroup$ Don't forget the finite ones. $\endgroup$ – Clive Newstead Apr 22 '15 at 18:13
  • $\begingroup$ Yes. Of course the set of all finite binary sequences is countable, hence the set of finite sequences of the given type is countable. Now the entire collection of sequences is the given type is countable. $\endgroup$ – Tim Raczkowski Apr 22 '15 at 18:16
1
$\begingroup$

If the sequence $01$ cannot appear, then any sequence in your set must be either an infinite sequence of $1$s, or be of the form $$\underbrace{11 \cdots 1}_{m\ \text{times}}\underbrace{00\cdots}_{n\ \text{times}}$$ where $0 \le m < \omega$ and $0 \le n \le \omega$.

Why? If a $0$ appears at any point in the string then $1$ can't appear at any point later in the string. Thus there is an evident bijection between your set and the set $$\{ (\omega, 0) \} \cup \{ (m, n) : 0 \le m < \omega,\ 0 \le n \le \omega \}$$ What is the cardinality of this set?

$\endgroup$
  • $\begingroup$ I undetstand why we get m times ones, but not sure why there are n times zeros, couldn't this type of sequence be infinite just like the sequnce of ones ? $\endgroup$ – NotSure Apr 22 '15 at 18:21
  • 2
    $\begingroup$ AmirH: Clive wrote that $0 \le n {\color{red}{\le}} \omega$ (not $0 \le n {\color{red}{<}} \omega$), and if $n=\omega$, the sequence is infinite. $\endgroup$ – Steve Kass Apr 22 '15 at 18:29

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.