# Proof $A\sim\mathbb{N}^{\mathbb{N}}$

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?

-
What knowledge do you have to attack this problem? What have you tried? – arjafi Dec 3 '12 at 15:13

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.

-
You mean $b(n)=n\, mod\:2$ ? – Denis Turov Dec 3 '12 at 15:35
Don't mind the question, I get it. But this way can't I immediately prove that $\mathbb{N}^{\mathbb{N}}\sim2^{\mathbb{N}}$ ? – Denis Turov Dec 3 '12 at 15:44
Well, the truth is that you can ;) I'll edit the answer. – yo' Dec 3 '12 at 15:45
I think that the vector $0,0,0,0,0,...$ maps into the empty word? may be to stay with the previous version of binary representation of each number? – Denis Turov Dec 3 '12 at 15:56
Oh, sorry, the "1"s still remain. But still is there a problem with a binary representation? – Denis Turov Dec 3 '12 at 15:58

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

-
Thanks Asaf, to show that $2^{\mathbb{N}}\sim\mathbb{N^{\mathbb{N}}}$ I used the way that tohecz proposed. But in the proof that you mentioned: why $$\mathbb{N}^{\mathbb{N}}\subseteq\mathcal{P}(\mathbb{N}\times\mathbb{N})$$ $\mathbb{N}^{\mathbb{N}}$ is the set of all functions from $\mathbb{N}$ to $\mathbb{N}$ , and $\mathcal{P}\left(\mathbb{N}\times\mathbb{N}\right)$ is set of all subsets of pairs $\left(n_{1},n_{2}\right)$ ? – Denis Turov Dec 3 '12 at 19:13
@DenisTurov Because for $f:\mathbb N\to\mathbb N$ we have $\{(n,f(n)):n\in\mathbb N\}\subset N\times N$. – yo' Dec 3 '12 at 22:27
@Denis: I apologize, I missed your comment in my inbox until tohecz wrote his. As tohecz wrote, every $f\in\mathbb{N^N}$ is a set of ordered pairs from $\mathbb{N\times N}$. Therefore $f\colon\mathbb{N\to N}$ implies that $f\in\mathcal P(\mathbb{N\times N})$. – Asaf Karagila Dec 3 '12 at 22:30
Thanks, I missed that point. – Denis Turov Dec 4 '12 at 16:41