How to prove $2^{\aleph_0} = \operatorname{card}(P(\mathbb N))$

Question

I have understood that for a finite set, the cardinality of the power set = $2^n$, however, how can we just generalize this if $n$ is an infinite cardinal such as $\aleph_0$ ?

Answer 1

If $X$ and $Y$ are two sets, it is common to use the symbol $Y^X$ to denote the set of all functions mapping $X$ to $Y$.

If $X$ and $Y$ are finite, then it is fairly obvious (from combinatorics) that $\operatorname{card}(Y^X)=\operatorname{card}(Y)^{\operatorname{card}(X)}$. For example, if $\operatorname{card}(X)=2, \operatorname{card}(Y)=3$, then there are $3^2=9$ such functions. To some extent, this is the justification for using the symbol $Y^X$ (rather than, say, $X^Y$) for the set of functions from $X$ to $Y$.

Now, let's extend this definition to infinite sets, and say:

• For any two sets $X$, $Y$, let $Y^X$ be the set of all functions from $X$ to $Y$.
• If $\kappa=\operatorname{card}(X), \nu=\operatorname{card}(Y)$, define $\nu^\kappa:=\operatorname{card}(Y^X)$

and that is how we define exponentiation on cardinals.

One can prove that this is a good definition, because, if, say, $X$ and $X'$ are of the same cardinality, and $Y$ and $Y'$ are of the same cardinality, then the sets of functions $Y^X$ and $Y'^{X'}$ are of the same cardinality.

---

Now, let $X$ be a set, and let $Y=\{0, 1\}$ be a two-element set. The cardinality of $Y^X$ is $\operatorname{card}(Y)^{\operatorname{card}(X)}=2^{\operatorname{card}(X)}$. However, one can see that $Y^X$ is of the same cardinality as $P(X)$. Namely, each map $f:X\to\{0,1\}$ defines a subset of $X$ (of precisely those elements of $X$ mapped to $1$) and every subset of $X$ defines a map of $X$ to $\{0, 1\}$ (map the elements from the subset to $1$ and the rest to $0$).

Or, in other words, every subset $A\subset X$ is mapped to its indicator function $i_A(x)=\begin{cases}1&x\in A\\0& x\not\in A\end{cases}$, and the mapping $A\mapsto i_A$ is a bijection of $P(X)$ to $\{0,1\}^X$.

This gives us the important theorem: $2^{\operatorname{card}(X)}=\operatorname{card}(P(X))$

Applied to $X=\mathbb N, \operatorname{card}(X)=\aleph_0$, we get:

$$2^{\aleph_0}=\operatorname{card}(P(\mathbb N))$$