Results 1 to 4 of 4

Math Help - Help in cardinal numbers of sets question...

  1. #1
    Member
    Joined
    May 2008
    Posts
    86

    Help in cardinal numbers of sets question...

    hello there, thanks for reading!

    I need to prove that the cardinal number of {0,1}^N is the cardinality of the continuum, c.
    {0,1)^N is that set {f(x) | f:{0,1} --> N}, i.e., all the functions from the set {0,1} to Natural numbers.

    The thing is, I have never learned of sets and cardinal numbers, and the lecturer mentioned briefly what a cardinal number is - so I have no idea how to approach this kind of problem.

    Help? Please? Pretty please?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    The set \left\{ {0,1} \right\}^\mathbb{N} can be thought of as the set of infinite bit-strings.
    Use the Cantor Diagonal argument to show that the set is not countable.
    But can be mapped injectively into [0,1].
    If you are allowed to accept the Continuum Hypothesis then you are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    86
    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    You do not need to use the Continuum Hypothesis. In fact we should stay away from it.
    (By construction) \mathbb{R} is equal to P(\mathbb{N}) in cardinality.

    To show that |P(\mathbb{N})| = |2^x| where 2=\{0,1\} we are required to construct a bijection.

    Define, \mu_{X}:\mathbb{N}\mapsto 2 as \mu_{X}(a) = \left\{ \begin{array}{cc}1\mbox{ if }a\in X\\0\mbox{ if }a\not \in X \end{array} \right. for every X\subset \mathbb{N}.

    Now define \phi: P(\mathbb{N})\mapsto 2 as \phi (X) = \mu_X.
    This is a bijection.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. cardinal numbers
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 6th 2010, 08:45 PM
  2. Cardinal numbers proof (identities) & Classes/Sets
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 8th 2010, 12:33 AM
  3. Cardinal numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 16th 2010, 01:25 PM
  4. infinite cardinal numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 25th 2010, 05:34 AM
  5. Cardinal Numbers
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 24th 2009, 05:39 AM

Search Tags


/mathhelpforum @mathhelpforum