0
$\begingroup$

What is the cardinal all the finite & infinite binary sequences that don't contain '10'?

I know I can make a function $f(z, o)$ where $z, o \in \mathbb{N}$ that builds a sequence that starts with $z$ zeros and ends with $o$ ones. But that only gives me the cardinal of the finite sequences. How should I continue?

$\endgroup$
1
  • $\begingroup$ Why can't you have a function f(n) (where n is a positive integer) that builds a sequence starting with zeroes and then from the nth term onward is all ones? $\endgroup$ – browngreen Apr 10 '16 at 15:24
1
$\begingroup$

You have the right idea. Such a sequence is determined by:

  • The length of the sequence, which takes values in $\mathbb{N} \cup \{ \infty \}$;
  • The position (counting from $1$) at which the sequence switches from $0$ to $1$, which takes values in $\mathbb{N} \cup \{ \infty \}$, where a value of $0$ corresponds to a sequence which is constantly zero, and a value of $\infty$ (or a value greater than the length of a finite sequence) corresponds to a sequence which is constantly one.

So you can surject $(\mathbb{N} \cup \{ \infty \}) \times (\mathbb{N} \cup \{ \infty \})$ onto your set, by mapping $(\ell, p)$ to the sequence with length $\ell$, which has $0$ in all positions up to and including position $p$ and $1$ in all positions afterwards.

(P.S. This post uses the convention that $0 \in \mathbb{N}$.)

$\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.