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
-
0I'm sorry to ask, but where exactly is the problem? Can you write down the map explicitly? – 2011-08-10
-
0No problem, just need to check that the map is increasing and respects order. Not sure how to write it down explicitly. – 2011-08-10
-
0How about $\displaystyle\sum_{n=0}^{\infty} \phantom{|} \frac{2\varepsilon_n}{3^{n+1}}$ where $(\varepsilon_n)$ is a binary sequence? – 2011-08-10
-
0Wait 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. – 2011-08-10
-
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.
-
0Let $(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? – 2011-08-10
-
3@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$. – 2011-08-10
-
0Oops, you're right, sorry. Nice bijection. – 2011-08-10