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

#### Solutions Collecting From Web of "Uncountability of the Cantor Set"

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.

However, one may show the Cantor set is uncountable the same way one shows any continuum is uncountable: a diagonalization argument.

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.