# Cantor function must be nondecreasing?

From wikipedia, the cantor function is defined as follows:

Express x in base 3.
If x contains a 1, replace every digit after the first 1 by 0.
Replace all 2s with 1s.
Interpret the result as a binary number. The result is c(x).


However if I use $x=0.111, y=0.102$ in base 3. Then $x>y$. But the first two steps would give $\phi(x)=0.100$ and $\phi(y)=0.101$ under base 2. Then $\phi(x)<\phi(y)$. How to explain this? I have not examined wikipedia's definition is really compatible with the other definition provided.

-
Are you supposed to replace all digits after the first $1$ by $0$ before you replace all $2$s with $1$s? I think you should get $\phi(x) = \phi(y) = 0.100$. – Tunococ Sep 11 '12 at 5:12
Every digit? ....my god. Thanks. – Bombyx mori Sep 11 '12 at 5:12

To prove it is nondecreasing we need to show the combination of middle two steps are non-decreasing, because obviously the first and the last step are order-preserving. So suppose we have $$x=\sum a_{i}3^{-i},y=\sum c_{i}3^{-i}, a_{i},c_{i}\in \{0,1,2\}$$ Now if $x> y$, we find the least $j\in \mathbb{N}$ such that we have $a_{j}> b_{j}$(for otherwise $x=y$). $a_{i}=b_{i},i\le j$'s placement does not influence because for their images under the middle two steps are equal. However if one of $a_{i}=b_{i}$'s contain 1, then we must conclude $\phi(x)=\phi(y)$ immediately since the rest of the digits will not matter. This only imply if $x>y,a_{j}=b_{j}=1, a_{i}=b_{i}\not=1, \forall i\le j\rightarrow \phi(x)=\phi(y)$, hence in this case $\phi$ is still nondecreasing.
Now $a_{j}>b_{j}$ could only happen if either $a_{j}=2,b_{j}=0$, or $a_{j}=2,b_{j}=1$, or $a_{j}=1,b_{j}=0$. In the first case after two steps we have $a_{j}=1,b_{j}=0$; in the second case we have $a_{j}=1,b_{j}=0$; in the third case if we have $1$ before, we have $a_{j}=0,b_{j}=0$. Or else we have $a_{j}=1,b_{j}=0$ as before. So the only situation $\phi(x)$ could possibly be less than $\phi(y)$ is when $a_{j}=1,b_{j}=0$ and some $a_{i}=b_{i},i\le j$ is 1. But this is exact the exceptional situation we discussed earlier; and in this case $\phi(x)=\phi(y)$. So we concluded $\phi$ must be nondecreasing in $[0,1]$.