Uncountable sets

Printable View

March 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?
March 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
March 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$ .
March 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
March 14th 2006, 10:10 AM
kennyb

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