# Decimal representations of the reals both 1-1 and order-preserving?

The conventional representation of the non-negative reals as infinite decimals is 1-1 for numbers which are not multiples of $10^{-n}$ for some $n$, and 2-1 for numbers which are (for example, $0.2999...=0.3000...$). However, it does preserve order: the lexicographic ordering on infinite decimals exactly matches the conventional ordering of the reals. (Let's talk about $\le$ as the ordering relation in order to get rid of the "2-1 mapping" blemish).

This representation leads to ugly consequences when we want to deploy Cantor's proof that the reals in $[0,1)$ are not countable. Having listed all the infinite decimals, we construct a new one by making its $n$th digit unequal to the $n$th digit of the $n$th decimal in the list, but we have to resort to undignified tricks to ensure that we don't end up with a $...999...$ version of a real number which already exists in its $...000...$ form (or vice versa). For instance, Aigner and Ziegler in their claimed "Book Proof" disallow $...000...$ forms altogether and also, although it's overkill, restrict the digits in the constructed infinite decimal to just 1 and 2 - not only ugly, but also not usable in base 2. Definitely not Book!

To switch to binary, as being more elegant, it is possible to devise a 1-1 mapping between $\{0,1\}^\omega$ and $\mathbb{R}$ (ie. between infinite sequences of binary digits and the reals). But that mapping is not order-preserving: the lexicographical ordering of $\{0,1\}^\omega$ does not match the numerical ordering of $\mathbb{R}$.

My question is therefore: is it the case that you can have either a 1-1 mapping or an order-preserving mapping between infinite decimals and the reals, but not both?

Existence of 1-1 mapping

This is a consequence of the Cantor-Bernstein theorem, for which Aigner & Ziegler give a Book Proof by König: If each of two sets M and N can be mapped invectively into the other, then there is a bijection from M to N.

In this case:

• An injective mapping from $\{0,1\}^\omega$ to the reals in $[0,1)$: given $\{a_i\}$, the corresponding real number is $\sum{2^{-2a_i}}$ - or, if you prefer, "$0.abcdef...$" is mapped onto the binary decimal $0.0a0b0c0d0e0f...$ - or, if you prefer, the binary decimal is simply interpreted as a base-4 one. However you look at it, the real numbers corresponding to the infinite decimals are all distinct, so this is an injection.

• An injective mapping from the reals in $[0,1)$ to $\{0,1\}^\omega$: the ordinary decimal expansion (to base 2), choosing the "$...000...$" representation if the real number in question is a multiple of $2^{-n}$ for some $n$.

Given the injections each way, a bijection exists and can be constructed by following the steps in König's proof, but it is not order-preserving: hence my question.

• I'm confused by the 1-1 terminology. Do you want an injective or a bijective map? – Christian Sievers Jun 7 '16 at 16:09
• Oh, and while I know $\{0,1\}^\omega$, how exactly do your "infinite decimals" look like, and how are they ordered? Think about 007.3333... or -0.000... – Christian Sievers Jun 7 '16 at 16:19

Yes, this is correct. There is no infinite decimal between the infinite decimals $0.\overline9$ and $1.\overline0$; they follow each other in the lexicographic ordering of the infinite decimals; whereas between any two real numbers there are further real numbers. Thus no bijection between the infinite decimals and the reals can respect their orders.