# Uncountability of the Cantor Set

Let $x=\left(0.a_1a_2...\right)_3 \in \mathcal{C}$, where $\mathcal{C}$ denotes the Cantor set and the $a_i$'s are either $0$ or $2$. Let $f:\mathcal{C}\rightarrow \left[0,1\right]$ such that $f(x)=\left(0.(a_1/2)(a_2/2)...\right)_2$.

I ultimately want to show that $\mathcal{C}$ is uncountable. But before I must show that $f$ is continuous and surjective.

This is my attempt for the surjective part:

Let $y\in [0,1]$. Then $y$ has a binary expansion, say, $y=(0.y_1y_2...)$ let $y_i=a_i/2$. Then $f(x)=(0.y_1y_2...)=y$. So $f$ is onto.

Afterwards can I conclude that since $[0,1]$ is uncountable and $f$ is a surjection, $\mathcal{C}$ is uncountable?

My Questions:
1. Is my attempt for the surjective part okay? Also, is my conclusion about the uncountablity of $\mathcal{C}$ okay, or I will have to do more?
2. How do I show that $f$ is continuous?

Thanks.

-
When representing real numbers in base notation, you should also consider the case of an infinite trailing string of 1s (or 2s in in the ternary case), although there are only a countable number of such cases and it won't affect the result. Why do you need to show that f is continuous? I think your argument is pretty convincing already. – Dan Brumleve Sep 14 '11 at 2:56
Maybe this related thread is helpful. – t.b. Sep 14 '11 at 3:10
@Dan: Thanks for your response. Well, I am to show first that $f$ is continuous and surjective and then conclude that $\mathcal{C}$ is uncountable. – Kuku Sep 14 '11 at 3:13
Kuku, it seems to me that showing f is a surjection is enough to establish that the Cantor set is uncountable. – Dan Brumleve Sep 14 '11 at 3:19
"Afterwards can I conclude" has the word order for a question, but the sentence doesn't end in a question mark. Do you mean "Afterwards I can conclude" as a statement, or is the question mark missing? Please clarify this by an edit. (You might also want to tidy up the "My Questions" part while you're at it, though that doesn't lead to ambiguity -- the questions under "1." are both missing question marks, and "I will have" has the word order for a statement.) – joriki Sep 14 '11 at 6:35

You don’t have to show that $f$ is continuous in order to conclude that $\mathcal{C}$ is uncountable: that follows from the fact that $f$ is surjective, assuming that you know that $[0,1]$ is uncountable. Your argument for surjectivity is correct, though it could be stated a bit better, but for clarity you ought to deal with a point raised by Dan Brumleve. Here’s your argument, slightly restated:

Let $y\in [0,1]$ be arbitrary, and let $(0.y_1y_2\dots)$ be a binary representation of $y$. For each positive integer $i$ let $a_i=2y_i$, and let $x$ be the number whose ternary representation is $(0.a_1a_2\dots)$; then $y=f(x)$, so $f$ is surjective.

Since this looks at first sight as if you were actually constructing a function from $[0,1]$ to $\mathcal{C}$, it would help the reader if you were to point out that this isn’t the case. For example, $y=1/2$ has two binary representations, $0.1\bar{0}$ and $0.0\bar{1}$, where the bar indicates a repeating digit, so it’s both $f(0.2_{\text{three}})=$ $f(\frac23)$ and $f(0.\bar{2})=f(\frac13)$.

As I said, continuity of $f$ isn’t needed if all you want is to prove the uncountability of $\mathcal{C}$, but if for some other reason you have to prove the continuity of $f$, here’s one approach. For $x\in\mathbb{R}$ and $r>0$ let $B(x,r)=\{y\in\mathbb{R}:\vert y-x\vert\le r\}$. Suppose that $0.x_1x_2\dots$ is the $1$-less ternary expansion of some $x\in\mathcal{C}$. For $n\in\mathbb{Z}^+$ let $T_n(x)=$ $\{(0.a_1a_2\dots)\in\mathcal{C}:\forall i\le n [a_i=x_i]\}$. Show that $$B(x,3^{-(n+1)})\cap\mathcal{C}\subseteq T_n(x)\subseteq B(x,3^{-n})\cap\mathcal{C}.$$ Then show that for each $r>0$ there is an $n(r)\in\mathbb{Z}^+$ such that $T_{n(r)}(x)\subseteq B(f(x),r)$.

Another approach is to show that $f$ preserves convergent sequences, i.e., that if $\langle x_n:n\in\mathbb{N}\rangle$ is a sequence in $\mathcal{C}$ that converges to $x\in\mathcal{C}$, then $\langle f(x_n):n\in\mathbb{N}\rangle \to f(x)$ in $[0,1]$. A good first step would be to show that if $\langle x_n:n\in\mathbb{N}\rangle$ is a sequence in $\mathcal{C}$ that converges to $x\in\mathcal{C}$, then for each $m\in\mathbb{Z}^+$ there is an $n(m)\in\mathbb{N}$ such that $x_n\in T_m(x)$ whenever $n\ge n(m)$: that is, every term of the sequence from $x_{n(m)}$ on agrees with $x$ to at least $m$ ternary places. Then each term of $\langle f(x_n):n\in\mathbb{N}\rangle$ from $f(x_{n(m)})$ on agrees with $f(x)$ to at least $m$ binary places. From this it’s not hard to conclude that $\langle f(x_n):n\in\mathbb{N}\rangle \to f(x)$.

-
Your first assumption is fine, since for any function $f$, $|dom(f)|\geq|im(f)|$. A simple $\epsilon-\delta$ proof should do for continuity.
Suppose $\mathcal{C}$ is countable, and make a (possibly countably infinite) list of its elements. Then create a new $(0.a_1a_2...)_3$ representation of a number by making $a_i$ anything other than the $i^{th}$ digit of the $i^{th}$ number in your list.
Your constructed number will differ by at least one digit from every number you have listed in your supposedly exhaustive enumeration of the elements of $\mathcal{C}$, yielding a contradiction.
Thus $\mathcal{C}$ is uncountable. For more on the diagonalization argument, see the corresponding Wikipedia page.