# 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 25, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9734671711921692, "perplexity_flag": "head"}