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
@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. –  user49557 Jan 5 '13 at 2:20
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 5 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 –  user49557 Jan 5 '13 at 3:03
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


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