Results 1 to 5 of 5

Thread: 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
    5
    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 $\displaystyle X^w$ is the set of all infinite sequences of elements drawn
    from $\displaystyle \{0,1\}$ and $\displaystyle w^w$ is the set of all sequences of elements
    drawn from $\displaystyle \{0,1,2, \dots\}=\mathbb{N}$.

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

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

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

    Hence:

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

    so with the earlier result:

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

    RonL
    Last edited by CaptainBlack; Mar 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
    10
    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 $\displaystyle X^w$ and $\displaystyle w^w$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    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 $\displaystyle X^w$ and $\displaystyle 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: Dec 7th 2010, 07:43 PM
  2. Countable and Uncountable sets
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: Oct 21st 2010, 11:58 AM
  3. Which of the following sets is uncountable?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Apr 17th 2010, 07:15 PM
  4. countable and uncountable sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 7th 2009, 12:40 PM
  5. Countables and Uncountable sets.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Sep 8th 2008, 10:40 PM

Search Tags


/mathhelpforum @mathhelpforum