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

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.

share|cite|improve this question
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? god. Thanks. – Bombyx mori Sep 11 '12 at 5:12

For the sake of completeness I will add my own proof.

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

share|cite|improve this answer

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.