Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let us define the set $$C=\bigg\{ \sum_{n=1}^\infty a_n 3^{-n}: a_n=0,2 \bigg\}$$ This is the Cantor set, could anyone help me prove it is uncountable? I've been trying a couple of approaches, for instance assume it is countable, list the elements of $C$ as decimal expansions, then create a number not in the list, I am having trouble justifying this though.

Secondly i've been trying to create a function $f$ such that $f(C)=[0,1]$.

Many thanks

share|improve this question
1  
It suffices to find a surjective map from $C$ onto $[0, 1]$. Then use the $3$-ary expansion of numbers in $[0, 1]$. –  Jonas Teuwen Jan 21 '12 at 19:29
    
your diagonalization method should work: write down a countable list of $\{0,2\}$-sequences and create one not on the list. –  yoyo Jan 21 '12 at 19:31
    
Thanks guys, this makes much more sense now –  Freeman Jan 21 '12 at 19:46
    
The Cantor set is a perfect set. The perfect sets are uncountables. –  leo Jan 21 '12 at 22:44
add comment

3 Answers 3

up vote 3 down vote accepted

There is a bijection between elements of $C$ and infinite sequences of $0$’s and $2$’s: $$\sum_{n=1}^\infty a_n3^{-n}\mapsto\langle a_1,a_2,\dots\rangle\;.$$ Can you show that the set of such sequences is uncountable? If you already know that $\mathbb{Z}^+$ has uncountably many subsets, one way it to match up these sequences with subsets of $\mathbb{Z}^+$. HINT: Think of characteristic (indicator) functions. It’s also possible to use the usual diagonal argument directly. And of course you can also infer it from the next part (see below), assuming that you know that $[0,1]$ is uncountable.

To get your map from $C$ onto $[0,1]$, just convert every $2$ to a $1$ and interpret the sequence as a binary expansion instead of a ternary expansion; I’ll leave the details to you.

share|improve this answer
    
I like your idea of mapping each element to a infinite series of zero's and 2's. at this point we could assume countability and create using the diagonal argument an element not in the list, if I am correct? –  Freeman Jan 21 '12 at 19:43
    
@LHS: Yes, exactly right. –  Brian M. Scott Jan 21 '12 at 19:55
add comment

Note the "obvious" bijection between $C$ and $P(\mathbb N)$ defined as:

$$f(A)= 2\sum_{n=1}^\infty\frac{\chi_A(n)}{3^n}$$

Where $\chi_A$ is the characteristics function of $A$ ($1$ for $n\in A$, $0$ otherwise).

Suppose that $A\neq B$ and $x=\min (A\Delta B)$, wlog $x\in A$ then $f(A)-f(B)\ge\dfrac2{3^x}>0$.

In the other direction, if $x\in C$ then we can write $A=\{n\in\mathbb N\mid a_n=2\}$ and it is quite clear why $f(A)=x$.

Now we use the fact that $P(\mathbb N)$ is uncountable (direct result of Cantor's theorem) and we are done.

share|improve this answer
    
Thank you for this! it's good to see a different way compared to the other answers. –  Freeman Jan 21 '12 at 19:46
    
@LHS: It's not really different, it is just a different presentation of the same idea and pretty much the same way. –  Asaf Karagila Jan 21 '12 at 19:47
add comment

Why list the numbers as their decimal expansion? Given a countable list $((a_n^m)_n)_m$ of sequences with values $0$ and $2$, construct another sequence $(b_n)_n$ that does not appear in the list. You can do that just as in Cantor's proof that the unit interval is uncountable.

For the surjection from $C$ onto $[0,1]$, notice that every element of $C$ uniquely determines the sequence $a_n$ it comes from. Now map every sequence $(a_n)_n$ to the sequence $(b_n)_n$ where $b_n=0$ if $a_n=0$ and $b_n=1$ if $a_n=2$. Now consider $\sum_{n=1}^\infty b_n2^{-n}$.

share|improve this answer
    
Ah yes, as in Brian M. Scott's post, this is a great idea! –  Freeman Jan 21 '12 at 19:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.