Results 1 to 3 of 3

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

  1. #1
    Member Last_Singularity's Avatar
    Joined
    Dec 2008
    Posts
    157

    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 $\displaystyle 2^{\mathbb{N}}$ has a higher cardinality than the naturals $\displaystyle \mathbb{N}$ by attempting to enumerate all the subsets of $\displaystyle \mathbb{N}$ and being able to create a new subset previously not listed, thus contradicting the fact that there was originally a bjiection between $\displaystyle 2^{\mathbb{N}}$ and $\displaystyle \mathbb{N}$.

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

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

    But how can we show that $\displaystyle 2^{\mathbb{N}}$ and $\displaystyle \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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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 ><)

    $\displaystyle \mathcal{P}$ denotes the power set

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

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

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

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

    where
    $\displaystyle x_0=\lfloor 2x\rfloor$
    $\displaystyle x_n=\lfloor 2^{n+1} \left(x-\sum_{k=0}^{n-1} \frac{x_k}{2^{k+1}}\right) \rfloor$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Prove 2 bases have the same cardinality
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 5th 2011, 07:27 PM
  2. Replies: 1
    Last Post: Aug 23rd 2010, 08:23 AM
  3. Replies: 1
    Last Post: May 14th 2010, 01:53 AM
  4. Prove that two sets have the same cardinality
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: Mar 17th 2010, 03:04 AM
  5. Prove Cardinality of the sets
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: Feb 25th 2010, 09:46 PM

Search Tags


/mathhelpforum @mathhelpforum