Cardinals of $\mathbb{N}$ and $2^\mathbb{N}$ proof

54 Views Asked by At

Show that $\mathbb{N}^{\mathbb{N}}$ is equivalent to $2^\mathbb{N}$, where $2^\mathbb{N} = \{f:\mathbb{N} \rightarrow \{0, 1\}\}$.

My attempt:

It suffices to show that the two sets have the same cardinal. We know that $|\mathbb{N}| = \aleph_0$. So,

$2^{\aleph_0}\leq \aleph_0^{\aleph_0}\leq (2^{\aleph_0})^{\aleph_0} =2^{\aleph_0\cdot\aleph_0} = 2^{\aleph_0^2} = 2^{\aleph_0}$

What theorem does this proof follow from? Also, is there a way to do this proof by constructing a bijective function? If yes what would such a proof look like? Any insight much appreciated.