3
$\begingroup$

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!

  • 0
    Another proof of the relation $|(0,1)|=|\mathcal P(\mathbb N)|$ is [here](http://math.stackexchange.com/a/388998/462).2013-07-15

3 Answers 3

9

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...

1

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.

  • 0
    True, bu$t$ the bod$y$ of the question asks for the equality.2012-10-08
0

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.