Prove the 2^N has the same cardinality as the reals

**Last_Singularity** · January 3rd 2009, 11:58 AM

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?

**Gamma** · January 3rd 2009, 12:38 PM

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.

**Moo** · January 3rd 2009, 12:54 PM

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$

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

LinkBack

Thread Tools

Display

Prove the 2^N has the same cardinality as the reals

Problem

Similar Math Help Forum Discussions

[SOLVED] Prove 2 bases have the same cardinality

F, vector space of all functions Reals to Reals. Which of these subsets are subspaces

Which group modulo the additive reals is isomorphic to the multiplicative reals.

Prove that two sets have the same cardinality

Prove Cardinality of the sets

Search Tags