Q:

$|\mathbb N^{\mathbb N}| = |2^\mathbb N|$

I was trying to find a direct proof that $|\mathbb N^{\mathbb N}| = |2^\mathbb N|$, by finding a bijection between the two sets. The idea that came to mind was to start with the sequence of natural numbers. Each natural number would be 'translated' in a sequence of zeroes of the length given by the natural number. A  1 would be added to the sequence obtained, and all the 01 sequences thus obtained would be concatenated in the order dictated by the original sequence of naturals. However, this would run into problems, since all complete 01 sequences thus obtained would end on 1, so that the function from $\mathbb N^{\mathbb N}$ to $2^\mathbb N$ would not be surjective.
I turned to Stack Exchange for advice and found out that the post Cardinality of the set of all natural sequences is $2^{\aleph_0}$ contained the same solution, except that ones were switched for zeroes and vice versa. Of course, this could not work either: all 01 sequences obtained end on 0.
As a workaround to the problem, I would propose the function as described above, except that the last natural number in the original series would now be translated in its binary form, and no 0 or 1 added. I think that would result in a bijection. Could that be right? Would there be other possibilities?
Edit: I am now convinced that the approach I proposed cannot work either. The function is not injective. At first I thought that the last part of the 01 sequence corresponding to the last natural number of the original sequence would be identifiable by its starting with 11 (one 1 stemming from the previous number, the other from the binary form of the last natural in the sequence - except when that would be 0). I now realize that 11 may occur within the binary form itself.
Therefore, still at a loss...

A:

There is clearly an injection $2^{\mathbb{N}} \to \mathbb{N}^{\mathbb{N}}$, and the graph of a function provides an injection $\mathbb{N}^{\mathbb{N}} \to 2^{\mathbb{N} \times \mathbb{N}}$. Composing this with some injection (or even bijection) $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ yields an injection $\mathbb{N}^{\mathbb{N}} \to 2^{\mathbb{N}}$. Now recall that the proof of the Cantor-Schröder-Bernstein theorem is constructive. It explicitly produces a bijection $\mathbb{N}^{\mathbb{N}} \cong 2^{\mathbb{N}}$ from our two injections. It is a good exercise to write it down.
Edit: Here are some details. Given injections $f : A \hookrightarrow B$, $g : B \hookrightarrow A$, one recursively  defines sets by $C_0 = A \setminus g(B)$, $C_{n+1}:=g(f(C_n))$, and takes their union $C=\cup_{n \geq 0} C_n$. Then, the map
$$h : A \to B,~a \mapsto \left\{\begin{array}{cc} f(a) & a \in C \\ g^{-1}(a) & a \notin C \end{array}\right.$$
is a bijection: this is the content of the Cantor-Schröder-Bernstein theorem. In our case, $f : \mathbb{N}^{\mathbb{N}} \hookrightarrow 2^{\mathbb{N}}$ is defined by $a \mapsto \{(2n+1) \cdot 2^{a(n)} : n \in \mathbb{N}\}$; here I have chosen the bijection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$, $(x,y) \mapsto (2x+1) 2^y$; and I identify $2^{\mathbb{N}}$ with the power set of $\mathbb{N}$. On the other hand, $g : 2^{\mathbb{N}} \hookrightarrow \mathbb{N}^{\mathbb{N}}$ simply maps $T\subseteq\mathbb{N}$ to the characteristic function $\chi_T$. If $a \notin C_0$, i.e. $a \in g(B)$, then $g^{-1}(a) = a^{-1}(\{1\})$. So we only have to describe $C \subseteq \mathbb{N}^{\mathbb{N}}$ in order to make the bijection $h : \mathbb{N}^{\mathbb{N}} \to 2^{\mathbb{N}}$ explicit.

