# finding an injective function to prove cardinality equality

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.

• 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$. – Pedro M. May 11 '15 at 16:48
• 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. – Henning Makholm May 11 '15 at 16:50
• 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$. – dorsh605 May 11 '15 at 16:51
• @PedroM.: Some authors use $\aleph$ with no subscript to denote the cardinality $2^{\aleph_0}$ of the continuum. This meaning makes good sense here. – Henning Makholm May 11 '15 at 16:51
• @Henning Makholm: thank you! – dorsh605 May 11 '15 at 17:08