Cardinality of the set of all natural sequences is $2^{\aleph_0}$ I was wondering how can you prove that $\mathbb{N}^\mathbb{N} \sim  2^\mathbb{N}$ (where $\mathbb{N}^\mathbb{N}$ is the set of all functon $f:\mathbb{N}\rightarrow \mathbb{N}$).
I think I can show that $2^\mathbb{N} \sim n^\mathbb{N}$ for some $n\in\mathbb{N}$ with a tedious bijection, but I'm not sure what to do with $\mathbb{N}^\mathbb{N}$.
I apologize if the question lacks details/notation, I have only studied elementary set theory and we haven't mentioned $\mathbb{N}^\mathbb{N}$'s cardinality at all (I usually ended up finding injections/bijections to/from $2^\mathbb{N}$, but now I'm curious as to why the above correct).
Thanks in advance.
 A: For every number $n\in\Bbb N$ let $\sigma_n$ be the binary sequence of $1$'s of length $n$ and then a $0$, this is - if you want to think of it that way - a representation of $n$ in base $1$. With a zero afterwards.
Now given a sequence $a=\langle a_n\mid n\in\Bbb N\rangle$ where $a_n$ is a natural number, we define the following binary sequence by induction.


*

*$b_0$ is the empty sequence.

*If $b_n$ was defined, $b_{n+1}$ is the concatenation of $b_n$ with $\sigma_{a_n}$. That is we write $b_n$, and then $\sigma_{a_n}$.


$b$ is the sequence we have at the end of the induction process. Then $b\in 2^{\Bbb N}$, which is easy to see, as it is an infinite sequence of $0$-$1$ digits.
And I claim that the map sending $a$ to $b$ (where $a$ is a sequence of natural numbers, and $b$ is a sequence defined as above from $a$) is a bijection.
For this we just observe that the function decoding sequences of $1$'s between $0$'s is an inverse function. It's a bit harder to write down formally, but I'll try.
Let $b=\langle b_n\mid n\in\Bbb N\rangle$ be an infinite binary sequence. We define a sequence of integers.


*

*$a_0=\min\{k\mid b_n=0\}$.

*If $a_0,\ldots,a_n$ were defined, let $t$ be the least $k$ such that $b_k=0$ and $k\geq\sum (a_i+1)$ then $a_n=t-\sum (a_i+1)$.


I might be off with the indices in that second part, but that's the general idea. We find out how to decompose $b$ into pieces looking like $\sigma_k$, then we take the $k$ from each piece.
