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?
Proof $A\sim\mathbb{N}^{\mathbb{N}}$
-
2What knowledge do you have to attack this problem? What have you tried? – 2012-12-03
2 Answers
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.
-
0You mean $b(n)=n\, mod\:2$ ? – 2012-12-03
-
0Don't mind the question, I get it. But this way can't I immediately prove that $\mathbb{N}^{\mathbb{N}}\sim2^{\mathbb{N}}$ ? – 2012-12-03
-
0Well, the truth is that you can ;) I'll edit the answer. – 2012-12-03
-
0I 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? – 2012-12-03
-
0Oh, sorry, the "1"s still remain. But still is there a problem with a binary representation? – 2012-12-03
-
0No, I got completely rid of the binary representations. Roughly speaking, the map $n\to 0^n1$ I use now is a [prefix code](http://en.wikipedia.org/wiki/Prefix_code). And yes, the sequence $0,0,0,\dotsc$ maps to the word $111\dotsm$ – 2012-12-03
-
0Sorry I didn't get you. If I still use the binary representation of number it makes some problems? – 2012-12-03
-
0This is too lengthy, please join the chat: http://chat.stackexchange.com/rooms/36/mathematics – 2012-12-03
-
0I still don't allowed to join the chat) get this: "you must have 20 reputation on The Stack Exchange Network to talk here. " – 2012-12-03
-
0But I think now the binary representation is not good, because vector 2,6,... and 5,2,... map into the same sequence 101110... – 2012-12-03
-
0Yes, the same you wrote on chat :-) the way you did it with prefix code is perfect ) thanks! – 2012-12-03
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}$.
-
0Thanks 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)$ ? – 2012-12-03
-
0@DenisTurov Because for $f:\mathbb N\to\mathbb N$ we have $\{(n,f(n)):n\in\mathbb N\}\subset N\times N$. – 2012-12-03
-
0@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})$. – 2012-12-03
-
0Thanks, I missed that point. – 2012-12-04