1. ## 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?

2. 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

3. 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$.

4. 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

5. Thanks for your help Captain Black. Your explanation makes perfect sense.