Results 1 to 3 of 3

Math Help - 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 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?
    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 ><)

    \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
    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: November 5th 2011, 07:27 PM
  2. Replies: 1
    Last Post: August 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: March 17th 2010, 03:04 AM
  5. Prove Cardinality of the sets
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: February 25th 2010, 09:46 PM

Search Tags


/mathhelpforum @mathhelpforum