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
Map from binary sequences on $\{0,1\}$ into the Cantor set $C$ respects order
-
1The 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. – 2011-08-10
1 Answers
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.
-
0Oops, you're right, sorry. Nice bijection. – 2011-08-10