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.

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

I am aware of the bijection between binary sequences and the Cantor set $C$ which is used to prove that it is an uncountable set. In fact, there is a website that the binary sequences can be given an order topology based on "lexicographic order." My question is how do you actually verify that the map from the sequences into $C$ respects order? Once this can be verified, it follows that $2^{\omega}$ and $C$ are in fact homeomorphic. Wouldn't this necessarily make our map increasing? Math Reference

share|cite|improve this question
I'm sorry to ask, but where exactly is the problem? Can you write down the map explicitly? – t.b. Aug 10 '11 at 17:15
No problem, just need to check that the map is increasing and respects order. Not sure how to write it down explicitly. – Libertron Aug 10 '11 at 17:33
How about $\displaystyle\sum_{n=0}^{\infty} \phantom{|} \frac{2\varepsilon_n}{3^{n+1}}$ where $(\varepsilon_n)$ is a binary sequence? – t.b. Aug 10 '11 at 17:40
Wait a minute, that leads to a ternary expansion and if I'm not mistaken, that is not one-to-one! Then again, I might be wrong. – Libertron Aug 10 '11 at 17:48
The sequences are on $\{0,1\}$ which is a set with two elements. Not $[0,1]$ which is a set with continuum many elements. Since both $\{0,1\}^\omega$ and $[0,1]^\omega$ have the same cardinality you can have a bijection; however $[0,1]$ in the order topology is the standard topology. You cannot have an order preserving map into the Cantor set, since $[0,1]$ is connected and $\mathcal C$ is totally disconnected. – Asaf Karagila Aug 10 '11 at 17:56
up vote 9 down vote accepted

The usual bijection between the set of binary sequences and the Cantor set is the following: given a binary sequence $(a_n)$ ($n\geq 1$), we map $$a_n \longmapsto \sum_{n=1}^{\infty}\frac{2a_n}{3^n}.$$ Call this map $\Psi$.

Now, suppose that $(a_n)\lt (b_n)$, and let $k$ be the smallest positive integer such that $a_k\lt b_k$. Then $a_k=0$, $b_k=1$. Thus $$\begin{align*} \Psi(b_n) - \Psi(a_n) &= \sum_{n=1}^{\infty}\frac{2b_n-2a_n}{3^n}\\ &= \sum_{n=k}^{\infty}\frac{2b_n - 2a_n}{3^n}\\ &= \frac{2}{3^k} + \sum_{n=k+1}^{\infty}\frac{2b_n-2a_n}{3^n}\\ &\geq \frac{2}{3^k} - \sum_{n=k+1}^{\infty}\frac{2}{3^n}\\ &= \frac{2}{3^k} - 2\sum_{n=k+1}^{\infty}\frac{1}{3^n}. \end{align*}$$

Since $$\begin{align*} \sum_{n=k+1}^{\infty}\frac{1}{3^n} &= \sum_{m=0}^{\infty}\frac{1}{3^{k+1}}\left(\frac{1}{3}\right)^n \\ &= \frac{1}{3^{k+1}}\left(\frac{3}{2}\right) = \frac{1}{2(3^k)}, \end{align*}$$ it follows that $$\Psi(b_n) - \Psi(a_n) \geq \frac{2}{3^k} - \frac{2}{2(3^k)} = \frac{1}{3^k}\gt 0;$$ therefore, $\Psi$ respects the lexicographic order on the set of binary sequences.

share|cite|improve this answer
Let $(a_n)$ be $(0, 1, 1, 1, 1, \dots)$ and $(b_n)$ be $(1, 0, 0, 0, 0, \dots)$. Then your map has $\Psi(a_n)$ to $\sum_{n=2}^{\infty}\frac{2}{3^n} = \frac23$, and $\Psi(b_n) = \frac23$ also. So it's not a bijection — isn't this issue what the OP was asking about in the comments? – ShreevatsaR Aug 10 '11 at 18:23
@ShreevatsaR: $\sum_{n=2}^{\infty}\frac{2}{3^n} = \frac{2}{9}\sum_{n=0}^{\infty}\frac{1}{3^n} = \frac{2}{9}\left(\frac{3}{2}\right) = \frac{1}{3}\neq \frac{2}{3}$. Or, viewed another way, the number whose ternary expansion is $0.022222\ldots$ is equal to the number whose ternary expansion is $0.100\ldots$, not to $0.200\ldots$. – Arturo Magidin Aug 10 '11 at 18:31
Oops, you're right, sorry. Nice bijection. – ShreevatsaR Aug 10 '11 at 18:44

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.