As part of a HW assignment in the course elementary set theory, I was given the following question:

Prove that the set of all binary sequences (sequences of $0$ and $1$) except for the binary sequences with two consecutive zeros has cardinality $\aleph$.

Hint: define an injective function from a set with cardinality $2^{\aleph_0}$ to the given set. then use CSB theorem.

Let us call the given set A and the set of all binary sequences B.

$A\subseteq B$ thus $\vert A\vert \leq \vert B\vert$ and i know that $B=\{0,1\}^\mathbb N$ and that $\vert\{0,1\}^\mathbb N\vert=\aleph$

Therefore I have that $\vert A\vert \leq \aleph$.

For the second inequality, I thought of using the hint by finding an injetive function from the set $B$ to the set $A$ but I can't find one.

Can anyone help me find an injective function from B to A?

I will also appreciate a different solution that uses the hint above.

  • 1
    $\begingroup$ By $\aleph$, do you mean $\aleph_1$? And unless you're using the Continuum Hypothesis, I think $\left|\{0,1\}^\mathbb{N}\right| = 2^{\aleph_0} \geq \aleph_1$. $\endgroup$ – Pedro M. May 11 '15 at 16:48
  • 1
    $\begingroup$ This is extremely close to duplicating Proving that there are as many infinite binary sequences and infinite binary sequences not containing 11 from earlier today, except for swapping 0 and 1. $\endgroup$ – Henning Makholm May 11 '15 at 16:50
  • $\begingroup$ well, actually I'm quite a beginner and i have not learned what does $\aleph_1$ means. what i meant by $\aleph$ is $\vert \mathbb R\vert$. $\endgroup$ – dorsh605 May 11 '15 at 16:51
  • 1
    $\begingroup$ @PedroM.: Some authors use $\aleph$ with no subscript to denote the cardinality $2^{\aleph_0}$ of the continuum. This meaning makes good sense here. $\endgroup$ – Henning Makholm May 11 '15 at 16:51
  • $\begingroup$ @Henning Makholm: thank you! $\endgroup$ – dorsh605 May 11 '15 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.