Let $\mathbb{R}^\mathbb{R}$ be the set of all functions $f: \mathbb{R} \to \mathbb{R}$ and $P(\mathbb{R})$ be the power set of $\mathbb{R}$. How to show that they have the same cardinality?
cardinality problem
3 Answers
Note that $\mathbb R$ has the same cardinality as $\mathbb R\times\mathbb R$. Therefore their power sets have the same size.
In particular $f\colon\mathbb R\to\mathbb R$ is an element in $\mathcal P(\mathbb{R\times R})$, and therefore $\mathbb{R^R}$ has cardinality of at most $2^{|\mathbb R|}$, and the other direction is trivial, because: $2<|\mathbb R|\implies |2^\mathbb R|\leq|\mathbb{R^R}|\leq|2^\mathbb R|$
Thus equality holds.
We know that $|\mathbb R|=\mathfrak c=2^{\aleph_0}$
$|\mathcal P(\mathbb R)|=2^{\mathfrak c}$
$|\mathbb R^{\mathbb R}|=\mathfrak c^{\mathfrak c}$
So we only need to show that $2^{\mathfrak c}=\mathfrak c^{\mathfrak c}$.
We have $\mathfrak c^{\mathfrak c} = (2^{\aleph_0})^{\mathfrak c} = 2^{\aleph_0\mathfrak c}=2^\mathfrak c,$ since $\aleph_0\mathfrak c=\mathfrak c$.
We get the last equality from $\mathfrak c \le \aleph_0 \mathfrak c \le \mathfrak c \mathfrak c = 2^{\aleph_0} 2^{\aleph_0} = 2^{\aleph_0+\aleph_0} = 2^{\aleph_0} = \mathfrak c$ and from Cantor-Benstein theorem.
-
0In case some steps are still unclear, [this overview](http://math.stackexchange.com/questions/131212/overview-of-basic-results-on-cardinal-arithmetic) might be useful. – 2012-11-02
Denote $A=\{0,1\}$. You can use the fact that $\mathbb{R} \simeq A^{\mathbb{N}}$, where $\simeq$ means "have the same cardinality". So we have $ \mathbb{R}^{\mathbb{R}} \simeq \left(A^{\mathbb{N}}\right)^{\mathbb{R}} \simeq A^{\mathbb{N} \times \mathbb{R}}. $ Now we use the fact that $\mathbb{N}\times\mathbb{R} \simeq \mathbb{R}$, so $ \mathbb{R}^{\mathbb{R}} \simeq A^{\mathbb{R}} \simeq P(\mathbb{R}), $ QED.