Results 1 to 5 of 5

Math Help - Uncountable sets

  1. #1
    Newbie
    Joined
    Mar 2006
    Posts
    2

    Uncountable sets

    I have a cardinality question. If anyone can give me some guidance on this, I would greatly appreciate it. Here it goes:

    If X={0,1} and w={0,1,2,...}, then show X^w and w^w have the same cardinality.

    Showing that both these sets are uncountable isn't too bad, but I need them to be the same uncountable size. I'm just not seeing how to set up a bijection between these two sets. I was also thinking that I might be able to show that both sets inject into the reals, then using the continuum hypothesis. Can anyone help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by kennyb
    I have a cardinality question. If anyone can give me some guidance on this, I would greatly appreciate it. Here it goes:

    If X={0,1} and w={0,1,2,...}, then show X^w and w^w have the same cardinality.

    Showing that both these sets are uncountable isn't too bad, but I need them to be the same uncountable size. I'm just not seeing how to set up a bijection between these two sets. I was also thinking that I might be able to show that both sets inject into the reals, then using the continuum hypothesis. Can anyone help?
    This will be a bit informal.

    First X^w is the set of all infinite sequences of elements drawn
    from \{0,1\} and w^w is the set of all sequences of elements
    drawn from \{0,1,2, \dots\}=\mathbb{N}.

    Clearly \mathcal{C}(X^w) \le \mathcal{C}(w^w)

    Now let x \in w^w then x=x_1,x_2, \dots. Now we may write each of the
    x_is in unary, that is n is represented by n\ 1s, but we will write them in unary+ as
    n+1\ 1s.

    Now map x \in w^w to y \in X^w such that y consists of the unary+
    repersentations of the x_is seperated by a single 0s. This map takes
    w^w one-one onto a subset of X^w (in fact the sub-set where there are no
    two consecutive 0s.

    Hence:

    \mathcal{C}(X^w) \ge \mathcal{C}(w^w)

    so with the earlier result:

    \mathcal{C}(X^w) = \mathcal{C}(w^w)

    RonL
    Last edited by CaptainBlack; March 14th 2006 at 10:54 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by kennyb
    I have a cardinality question. If anyone can give me some guidance on this, I would greatly appreciate it. Here it goes:

    If X={0,1} and w={0,1,2,...}, then show X^w and w^w have the same cardinality.

    Showing that both these sets are uncountable isn't too bad, but I need them to be the same uncountable size. I'm just not seeing how to set up a bijection between these two sets. I was also thinking that I might be able to show that both sets inject into the reals, then using the continuum hypothesis. Can anyone help?
    I have an idea but maybe it is useless here. Axiom of Choice, thus, conclude that there exists a surjetive map between X^w and w^w.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    I have an idea but maybe it is useless here. Axiom of Choice, thus, conclude that there exists a surjetive map between X^w and w^w.
    If a result can be proven without AC it should be, and here we can

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2006
    Posts
    2
    Thanks for your help Captain Black. Your explanation makes perfect sense.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. countable & uncountable sets
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 7th 2010, 07:43 PM
  2. Countable and Uncountable sets
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: October 21st 2010, 11:58 AM
  3. Which of the following sets is uncountable?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 17th 2010, 07:15 PM
  4. countable and uncountable sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 12:40 PM
  5. Countables and Uncountable sets.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 8th 2008, 10:40 PM

Search Tags


/mathhelpforum @mathhelpforum