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
    19,131
    Thanks
    1853
    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
    10
    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