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.

$\aleph_0$ is the cardinality of the set of natural numbers, $\aleph_0 = |N|$. $c$ is the cardinality of the continuum, i.e. the set of real numbers $c = |R|$.

I know that $|P(A)| = 2^{|A|}$. This means that the cardinality of the power set of a set is 2 raised to the power of the cardinality of that set.

This basically means that to prove $2^{\aleph_0} = c$, I need to prove $c = |P(N)|$. I've seen the Cantor diagonal argument, although I have no idea on how to use it to prove this.

Could anyone suggest ideas of the simplest way to prove that $2^{\aleph_0} = c$?

share|improve this question
1  
@isomorphismes I don't need to prove that c = aleph 1. That would require the Continuum hypothesis and further complicate things. Also, I am looking for the simplest way, your edit might suggest that I am looking for the original proof. –  Alex Jan 5 '13 at 2:20
1  
HINT: $2^{\aleph_0}$ may be thought of as the set of all functions from $\mathbb{N} \to \{0,1\}$. –  andybenji Jan 5 '13 at 6:06

3 Answers 3

up vote 6 down vote accepted

Hint: First convince yourself that $|\mathbb R|=|[0,1)|$; every real in $[0,1)$ can be written in base $2$ as an infinite binary string. Second, $2^{\mathbb N}$ is the set of infinite binary strings. You don't quite have a bijection here, since binary expansions of real numbers are not unique (for example, $0.0111\ldots=0.1$), but you almost do, so it shouldn't be hard to think of two injections $2^{\mathbb N}\to[0,1)$ and $[0,1)\to 2^{\mathbb N}$. Now apply the Cantor-Schröder-Bernstein theorem and you are done.

Added after an edit: Let's produce the desired injections. First of all, the binary expansions of a real number is unique unless it can be written with an infinite tail of $1$s, in which case there is exactly one other binary representation for it, ending with an infinite tail of $0$s. For every real number $x$, let $0.b_1b_2b_3\ldots$ be the unique binary expansion of $x$ without an infinite tail of $1$s. An injection from $[0,1)$ to $2^{\mathbb N}$ is given by $x\mapsto(b_1,b_2,\ldots)$.

Now we want an injection from $2^{N}$ to $[0,1)$. For a sequence $(b_1,b_2,\ldots)$, we could try to view it as the binary expansion of a number and map it to $\sum b_n/2^n$, but this would not be injective. However, we could view it as a decimal expansion instead, where the only ambiguous expansions are those ending with an infinite tail of $9$s. Thus, an injection from $2^{\mathbb N}$ to $[0,1)$ is given by $(b_1,b_2,\ldots)\mapsto \sum b_n/10^n$.

share|improve this answer
    
@Alex: I saw that you made a comment saying you can't use the Cantor-Schröder-Bernstein theorem. First, are you sure? The theorem states that if $|A|\leq |B|$ and $|B|\leq|A|$, then $|A|=|B|$, so your text may have mentioned it without naming it. However, it is possible to produce an explicit bijection. In our case, we can put the binary expansions of numbers in $[0,1)$ in bijective correspondence with all but countably many of the elements of $2^{\mathbb N}$, so what we have to do is stuff away countably many elements somehow, which can be done, but it will be ugly. –  Samuel Jan 5 '13 at 2:56
    
Your answer is good. I understand what the theorem states, I looked it up before posting this. I'll wait a while to see if anybody comes up with a simpler solution, and if that doesn't happen I'll accept the answer. Forget an explicit bijection, but could you possibly explicitly suggest examples for the desired injections? Thanks –  Alex Jan 5 '13 at 3:03
1  
Done. By the way, if you want to find an explicit bijection later, the following exercises will lead you on the right way: 1. Find a bijection $\mathbb N\to\mathbb N\setminus\{1\}$; 2. Find a bijection $[0,1)\cup\{1\}\to[0,1)$; 3. Find a bijection $[0,1)\cup\mathbb N\to[0,1)$. –  Samuel Jan 5 '13 at 3:19

$\Phi : \mathbb{R} \rightarrow \mathcal{P}(\mathbb{Q})$ defined by $r \mapsto \{q \in \mathbb{Q} : q < r\}$ is an injection. $|\mathcal{P}(\mathbb{Q})| = |2^{\aleph_0}|$.Hence $\Phi$ induces an injection from $\mathbb{R} \rightarrow 2^{\aleph_0}$. $\mathfrak{c} \leq 2^{\aleph_0}$.

$\Psi : 2^{\aleph_0} \rightarrow \mathbb{R}$ defined by $\psi(f) = \sum_{i = 1}^\infty \frac{2f(i)}{3^i}$ is an injection, where $f: \omega \rightarrow \{0,1\}$ (i.e. an $\omega$ sequence of $0$ or $1$). $\Psi$ is actually a bijection onto the usual middle third Cantor Set. Hence $2^{\aleph_0} \leq \mathfrak{c}$.

By the Schoder-Berstein theorem, $\mathfrak{c} = 2^{\aleph_0}$.

share|improve this answer

Another approach (though slightly more advanced) is as follows:

  1. Note that $| \mathbb{R} | = | ( 0 , 1 ) |$, and since $\mathbb{Q}$ is countable while $\mathbb{R}$ is uncountable, it follows that $| ( 0 , 1 ) | = | ( 0 , 1 ) \setminus \mathbb{Q} |$.
  2. Note that every $x \in ( 0 , 1 ) \setminus \mathbb{Q}$ has a unique infinite continued fraction representation as $[0; a_1 , a_2 , \ldots ]$ where each $a_i \in \mathbb{N} = \{ 1 , 2 , \ldots \}$. (And every such infinite continued fraction represents an irrational number in $(0,1)$.) This establishes a bijection $\mathbb{N}^{\mathbb{N}} \to (0,1) \setminus \mathbb{Q}$.
  3. It is quite easy to show that $| \mathbb{N}^{\mathbb{N}} | = 2^{\aleph_0}$.
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.