# Understanding the proof for $2^{\aleph_0} > \aleph_0$

I'm trying to understand how $2^{\aleph_0} > \aleph_0$. I was reading through this sketch of the proof, but don't quite understand how they show that $\mathrm{card}((0,1)) = \mathrm{card}(\mathcal{P}(\mathbb{N}))$. Is there a different way of explaining this? Or maybe a different way of explaining the whole proof? I'm just trying to wrap my head around this, so any help is appreciated!

-
Huh? I don't see any sketch here, only a reference to Cantor's proof. Also, I'm not aware of any proofs of the inequality using equinumerosity of the interval and the power set... –  tomasz Oct 8 '12 at 0:10
@tomasz It is easy to prove that $P(N)$ and $(0,1)$ have the same cardinality, and then Cantor diagonalization shows that $P(N)$ is uncountable.... –  N. S. Oct 8 '12 at 0:12
@N.S.: How so? Cantor's diagonalization, as I know it, shows that $2^{\bf N}$ is uncountable, without $(0,1)$ in-between. –  tomasz Oct 8 '12 at 0:13
@tomasz Usually Cantor diagonalization is used to prove that $R$ or $(0,1)$ is uncountable, without needing $2^N$. –  N. S. Oct 8 '12 at 0:18
@N.S.: Really? Care to explain? The only way to do that that I can think of is by binary expansion, which is really a faux bijection of the interval and $2^\bf N$, or something of the sort. –  tomasz Oct 8 '12 at 0:24

In general, if $m$ is any cardinal number we have $2^m > m$. I think this is a Theorem by Cantor.

The proof is very simple:

If $f: A \to {\mathcal P}(A)$ is any function then the set $B= \{x\in A \mid x \notin f(x) \}$ cannot be in the image of $f$ (the argument is exactly the liar paradox)...

This means that no function from $A$ to ${\mathcal P}(A)$ can be surjective.

Added You can also prove that $2^{\aleph_0} > \aleph_0$ by showing that $2^{\aleph_0}$ is the cardinality of $[0,1)$.

To do this, all you have to do is to write all numbers in $[0,1)$ in binary, and then $f: [0,1) \to P(N)$ can be defined as $f(x)=$ the set of positions of $1's$ in the binary representation of $x$. This function is injective (and almost surjective), thus $P(N)$ has at least as many elements as $[0,1)$.

Cantor diagonalization argument shows that $[0,1)$ is uncountable, thus $P(N)$ is also uncountable...

-

You can represent any real number via its binary expansion, this gives you a mapping from $(0,1)$ to $\mathcal{P}(\mathbb{N})$ (just send the number $x$ to the sequence given by its binary expansion). We have to be careful for this map to be well defined though, since $0.0111\ldots = 0.1000\ldots$. This can be solved sticking to one type of representation. This gives you an injection from $(0,1)$ into $\mathcal{P}(\mathbb{N})$. It shouldn't be hard to find an injection the other way around.

-
You typed faster. Since you only need to show that $P(N)$ is larger than $N$, an injection from $(0,1)$ to $P(N$ suffices. –  N. S. Oct 8 '12 at 0:17
True, but the body of the question asks for the equality. –  F M Oct 8 '12 at 0:23

The idea is to map each real in $(0,1)$ to it's binary representation. Those binary representations all have the form $0.b_0b_1b_2\ldots$ where all the $b_i$ are from ${0,1}$. Each real in $(0,1)$ thus corresponds to a series $(b_i)_{i\geq0}$ of zeros and ones. The set of all such series can than be mapped to $\mathcal{P}(N)$ by interpreting a series as the characteristic function of a subset of $N$. To clarify, a certain series $(b_i)_{i\geq0}$ is mapped to the subset which contains $i$ exactly if $b_i = 1$.

Note that there's a bit of a hole in that argument - the mapping of $(0,1)$ to series of zeros and ones is not onto, i.e. there are multiple series which correspond to the same real. For example, $0.1$ and $0.01111\ldots$ both correspond to $\frac{1}{2}$. So, what they actually show is $\text{card}((0,1)) \leq \text{card}(\mathcal{P}(N))$.

Actually proving $\text{card}((0,1)) = \text{card}(\mathcal{P}(N))$ would require putting more effort into the definition of the mapping, or defining another mapping which shows $\text{card}((0,1)) \geq \text{card}(\mathcal{P}(N))$.

For the purpose of proving $\aleph_0 < 2^{\aleph_0}$, showing $\text{card}((0,1)) \leq \text{card}(\mathcal{P}(N))$ is sufficient, though.

-