Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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
up vote 5 down vote accepted

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)$.

share|cite|improve this answer
Thanks for your answer. – Kuku Sep 14 '11 at 13:10

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.

share|cite|improve this answer
Thanks for your response. – Kuku Sep 14 '11 at 13:10

Your Answer


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.