# Uncountable sets

• Mar 14th 2006, 08:42 AM
kennyb
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?
• Mar 14th 2006, 09:50 AM
CaptainBlack
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_i$s in unary, that is $n$ is represented by $n\ 1$s, but we will write them in unary+ as
$n+1\ 1$s.

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

Hence:

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

so with the earlier result:

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

RonL
• Mar 14th 2006, 10:06 AM
ThePerfectHacker
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$.
• Mar 14th 2006, 10:08 AM
CaptainBlack
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
• Mar 14th 2006, 10:10 AM
kennyb