3
$\begingroup$

Let $A=\{f\in\{0,1\}^{\mathbb{N}}\,|\, f(0)=0,f(1)=0\}$, i.e. all the infinite binary vectors, that start from $0,0$. Need to proof that $A\sim\mathbb{N}^{\mathbb{N}}$. Any ideas or hint?

  • 2
    What knowledge do you have to attack this problem? What have you tried?2012-12-03

2 Answers 2

2

The condition $f(0)=f(1)=0$ does not change the cardinality of the set, hence $\#A=\# \{0,1\}^\mathbb N$. We will show that $\#(\mathbb N^\mathbb N)\leq\#\bigl(\{0,1\}^\mathbb N\bigr)$. To each infinite sequence $n_0, n_1, \dotsc \in\mathbb N$ we assign a word $0^{n_0}10^{n_1}10^{n_2}1\dotsm\in\{0,1\}^\mathbb N$. Where $0^n$ means "zero repeated $n$ times". Example: $0,1,2,3,4,5,\dotsc$ maps to $101001000100001000001\dotsm$ This map is not a bijection, because the image always contains infinitely many $1$'s. But clearly it is an injection (e.g. to two sequences of integers two different strings are assigned).

Since $\{0,1\}^\mathbb N\subseteq \mathbb N^\mathbb N$, the inequality $\#(\mathbb N^\mathbb N)\geq\#\bigl(\{0,1\}^\mathbb N\bigr)$ is obvious. Cantor-Bernstein Theorem gives that the sets have the same cardinality.

  • 0
    Yes, the same you wrote on chat :-) the way you did it with prefix code is perfect ) thanks!2012-12-03
4

Hint:

Show that $\mathbb{2^N\sim N^N}$ first, then show that $A\sim 2^\mathbb N$.

The first part is the more difficult part, but recall that $\mathbb{N^N}\subseteq\mathcal P(\mathbb{N\times N})$ and that $\mathbb{N\times N\sim N}$.

  • 0
    Thanks, I missed that point.2012-12-04