# Thread: Prove the 2^N has the same cardinality as the reals

1. ## Prove the 2^N has the same cardinality as the reals

I was studying Cantor's contributions to set theory, and I came upon two results:

#1: It can be shown that the power set of the naturals $2^{\mathbb{N}}$ has a higher cardinality than the naturals $\mathbb{N}$ by attempting to enumerate all the subsets of $\mathbb{N}$ and being able to create a new subset previously not listed, thus contradicting the fact that there was originally a bjiection between $2^{\mathbb{N}}$ and $\mathbb{N}$.

#2: It can also been shown that the reals $\mathbb{R}$ are "more numerous" than the naturals $\mathbb{N}$ by using Cantor's Diagonalization argument.

Thus, it is known that both $2^{\mathbb{N}}$ and $\mathbb{R}$ have a higher cardinality than the naturals $\mathbb{N}$.

But how can we show that $2^{\mathbb{N}}$ and $\mathbb{R}$ have the same cardinality as each other, though? I tried constructing a bijection (because I know that one must exist); I tried to use Cantor's style; nothing really worked.

I am so stuck on this proof that I do not even know where to start. Someone give me a hint or a starting point, please?

2. ## Problem

Well I may well be wrong, but I think this result is equivalent to the continuum hypothesis. So I think it can be proved; however, only by using the Axiom of Choice.

3. Hello,

Here are the steps in which it is organized in my lecture notes. (I don't have time to copy it, nor to find it on the internet ><)

$\mathcal{P}$ denotes the power set

1. $\{0,1\}^{\mathbb{N}}$ and $\mathcal{P}(\mathbb{N})$ are equipotent

2. Any part of $\mathbb{R}$ (something in $\mathcal{P}(\mathbb{R})$) containing an open interval is equipotent to $\mathbb{R}$
(Cantor-Bernstein theorem)

3. $\text{Card}(\{0,1\}^{\mathbb{N}}) \leq \text{Card}([0,1/2])$, which is $=\text{Card}(\mathbb{R})$, thanks to 2.
prove that $\phi ~:~ \{0,1\}^{\mathbb{N}} \to [0,1/2]$
$x:=(x_n)_{n \in \mathbb{N}} \mapsto \sum_{n=0}^\infty \frac{x_n}{3^{n+1}}$
is an injection

4. $\text{Card}(\{0,1\}^{\mathbb{N}}) \geq \text{Card}([0,1[)$, which is $=\text{Card}(\mathbb{R})$, thanks to 2.
uses the proper diadic development of x (don't know the name in English )
prove that $\psi ~:~ [0,1[ \to \{0,1\}^{\mathbb{N}}$
$x \mapsto x_n$
is an injection

where
$x_0=\lfloor 2x\rfloor$
$x_n=\lfloor 2^{n+1} \left(x-\sum_{k=0}^{n-1} \frac{x_k}{2^{k+1}}\right) \rfloor$