Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
1  
@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
1  
@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

3 Answers 3

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

share|improve this answer

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.

share|improve this answer
    
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. –  Fernando Martin 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.