Easiest way to prove that $2^{\aleph_0} = c$

Question

$\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$?

Answer 1

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

Answer 2

$\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 Schroeder-Bernstein theorem, $\mathfrak{c} = 2^{\aleph_0}$.

Answer 3

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