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
    You mean $b(n)=n\, mod\:2$ ?2012-12-03
  • 0
    Don'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
  • 0
    Well, the truth is that you can ;) I'll edit the answer.2012-12-03
  • 0
    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?2012-12-03
  • 0
    Oh, sorry, the "1"s still remain. But still is there a problem with a binary representation?2012-12-03
  • 0
    No, 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
  • 0
    Sorry I didn't get you. If I still use the binary representation of number it makes some problems?2012-12-03
  • 0
    This is too lengthy, please join the chat: http://chat.stackexchange.com/rooms/36/mathematics2012-12-03
  • 0
    I 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
  • 0
    But 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
  • 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 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
  • 0
    Thanks, I missed that point.2012-12-04