Cardinality: $\left|\Bbb N^{\Bbb N}\right| = \left|\{0,1\}^{\Bbb N}\right|$ Let $F$ be the set of functions from $\Bbb N$ to $\Bbb N$ and $G$ be the set of functions from $\Bbb N$ to $\{0,1\}$. Prove that $|F| = |G|$.
What I tried doing is saying that every number in $\mathbb{N}$ maps to a bitstring, but I don't know how to construct from there?
 A: Every sequence of integers $(a_k)_{k\in\mathbb{N}}$ can be represented as an infinite long string with the decimal representations of $a_k$ joined togather using "comma" as a separator.
For example, the Fibonacci sequence can be represented as a "string" beginning with characters "1,1,2,3,5,8,13,21,". 
If one view the resulting string as a sequence of bytes (e.g. encode the characters using ASCII encoding) and then view each byte as a sequence of $8$-bits, this representation will establish an injection from $\mathbb{N}^{\mathbb{N}}$ into $\{ 0,1 \}^{\mathbb{N}}$.
One the other hand,$\{ 0, 1 \}^{\mathbb{N}}$ can be viewed as a subset of
$\mathbb{N}^{\mathbb{N}}$. The natural embedding of $\{ 0, 1 \}^{\mathbb{N}}$
into $\mathbb{N}^{\mathbb{N}}$ is an injection in opposite direction.
By Cantor–Bernstein–Schroeder theorem, there is a bijection
between $\mathbb{N}^{\mathbb{N}}$ and $\{ 0, 1 \}^{\mathbb{N}}$
and hence $\displaystyle |\mathbb{N}^{\mathbb{N}}| = \left| \{ 0, 1 \}^{\mathbb{N}} \right|$.
A: \begin{align}
|\{0,1\}^{\mathbb{N}}|
&=2^{\aleph_0}\\
&\le\aleph_0^{\aleph_0}=|\mathbb{N}^{\mathbb{N}}|\\
&\le (2^{\aleph_0})^{\aleph_0}\\
&=2^{\aleph_0\aleph_0}\\
&=2^{\aleph_0}=|\{0,1\}^{\mathbb{N}}|
\end{align}
A: Here's an explicit bijection $f: \{0,1\}^{\mathbb{N}}\to \mathbb{N}^{\mathbb{N}}$.  First let $s:\mathbb{N}\to\{0,1\}^{\mathbb{N}}$ be an enumeration of sequences that contain only a finite amount of $0$'s (i.e. those that are eventually constant $1$).  Then $f(\sigma)$ is given by


*

*If $\sigma = s(k)$ then $f(\sigma) = (2k + 1, 0, 0, 0, \ldots)$

*If $\sigma = (\underbrace{1, 1, \ldots, 1}_k, 0, 0, 0, \ldots)$ for some $k \geq 0$ then $f(\sigma) = (2k, 0, 0, 0, \ldots)$.

*Otherwise $f(\sigma)$ is the sequence counting the number of $1$'s before the first $0$ in $\sigma$, then the number of $1$'s between the first and second $0$ and so on. In other words, each $0$ in $\sigma$ is interpreted as a separator between strings of $1$'s and the lengths of these strings are the entries of $f(\sigma)$.  For example $$f: (0,1,1,0,1,0,0,1,1,1,0, \ldots) \mapsto (0, 2, 1, 0, 3,\ldots).$$


Case 3. alone would almost do the job, but it cannot handle sequences with only a finite amount of $0$'s in them.  These are handled through a standard trick by cases $1.$ and $2.$ (make room for the countable number of remaining sequences).
