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!
[Math] Understanding the proof for $ 2^{\aleph_0} > \aleph_0$
cardinalselementary-set-theory
Best Answer
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...