2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm confused by the 1-1 terminology. Do you want an injective or a bijective map? $\endgroup$ – Christian Sievers Jun 7 '16 at 16:09
  • $\begingroup$ 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... $\endgroup$ – Christian Sievers Jun 7 '16 at 16:19
3
$\begingroup$

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.

Put another way, an order-preserving bijection between the two sets would be an isomorphism between their ordinal structures, but their ordinal structures aren't isomorphic.

$\endgroup$
1
  • $\begingroup$ So we don't need the details I asked for, great! $\endgroup$ – Christian Sievers Jun 7 '16 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.