I know how to prove whether countably infinite, or countable sets are equinumerous, and know that a diagonalization method can be used to prove a set is uncountably infinite, but I cant seem to find any material online detailing how to prove that larger sets are equinumerous.
For example, how would one prove that the power set of the natural numbers is equinumerous to the set of all functions on the natural numbers?
Best Answer
In general, the question "are these two sets equinumerous" can be very difficult, and depends on the sets you're looking at. That being said, one of (if not the) most important results that helps answer that question is:
This is proven in any Set Theory text (or Wikipedia)
For your particular example:
First, the power set of the naturals has the same size as $2^\mathbb{N}$, i.e. the set of all infinite sequences of $0$ and $1$s. To see this, map each set $A\subset\mathbb{N}$ to its characteristic function $\chi_A$ defined by $\chi_A(n)=1$ if $n\in A$ and $\chi_A(n)=0$ if $n\not\in A$. The map $$ \mathcal{P}(\mathbb{N})\to 2^\mathbb{N} $$ $$ A\mapsto \chi_A $$ is a bijection. You can prove this by hand, or by noting that the function $2^\mathbb{N}\to \mathcal{P}(\mathbb{N})$ defined by $f\mapsto f^{-1}(\{1\})$ is the inverse of the map mentioned above.
Back to the problem at hand. It suffices to see that $2^\mathbb{N}$ and $\mathbb{N}^\mathbb{N}$ have the same size.
As $2^\mathbb{N}\subset \mathbb{N}^\mathbb{N}$ (any sequence of $0$ and $1$s is also a sequence of naturals), we have one injection, namely the inclusion (identity) mapping.
Producing an injection $F:\mathbb{N}^\mathbb{N}\to 2^\mathbb{N}$ is more challenging. Here's one. Given a sequence of naturals $(x_n)_{n\in\mathbb{N}}$, let $$ F((x_n)_{n\in\mathbb{N}})=(\underbrace{0,\dots, 0}_{x_0 \text{ many}},1, \underbrace{0,\dots, 0}_{x_1 \text{ many}},1,\underbrace{0,\dots, 0}_{x_2 \text{ many}},1,\dots)\in 2^\mathbb{N} $$ Then $F$ is injective (I leave checking this, together with writing a precise definition of $F$, to you).
Here's another way of solving the problem, using some cardinal arithmetic, which is another useful tool. The CBS Theorem I mentioned above is also present, since it makes the argument work, but in a less explicit function.
The powerset of $\mathbb{N}$ has cardinal $2^{\aleph_0}$. So, we show that $\mathbb{N}^\mathbb{N}$ has cardinal $2^{\aleph_0}$. To see this, note that, by definition, $\mathbb{N}^\mathbb{N}$ has cardinal ${\aleph_0}^{\aleph_0}$. So, it all boils down to showing: $$ 2^{\aleph_0}={\aleph_0}^{\aleph_0} $$ Note: $$ 2^{\aleph_0}\le {\aleph_0}^{\aleph_0}\le (2^{\aleph_0})^{\aleph_0}=2^{{\aleph_0}{\aleph_0}}=2^{\aleph_0} $$ as desired (the fact that $2^{\aleph_0}\le {\aleph_0}^{\aleph_0}\le 2^{\aleph_0}$ is equivalent to $2^{\aleph_0}={\aleph_0}^{\aleph_0}$ is where we're using the CBS theorem).
I'd like to clarify that the topic of cardinal arithmetic leads to extremely difficult problems in mathematics. I'm typing this out of guilt from calling cardinal arithmetic a "tool". It is a very rich, deep and beautiful area of mathematics.