Ben Orlin posted an interesting extension of the normal repeating decimals called “Kaufman decimals” (because they were developed jointly with Jeff Kaufman). In this post I will try to define them more precisely and show they can be totally ordered.
The Kaufman digit sequences (the decimals without the initial “0.” prefix) are formed by starting from single digit sequences (“0”, “1”, …, “9”) and applying the following operations a finite number of times:
- Concatenation: taking two digit sequences and putting one after the other.
- Repetition: taking a digit sequence and repeating it an infinite number of times.
As it’s difficult to start directly with the infinite case, let’s start by defining formally a more simple case.
If we replace the infinite repetition by repeating the sequence times, it’s easy to analyze the resulting sequences. For example, if ,
So now we can define concatenation in the following way:
Repetition is also quite easy:
We can check the definition with the following Python code:
def l(a): from itertools import count for i in count(): if a(i) is None: return i def r(k, a): l_a = l(a) return lambda i: a(i % l_a) if i < l_a * k else None def c(a, b): l_a, l_b = l(a), l(b) return lambda i: a(i) if i < l_a else b(i - l_a) if i < l_a + l_b else None def s(c): assert len(c) == 1 return lambda i: c if i == 0 else None def p(a): print ''.join(a(i) for i in range(l(a))) if __name__ == '__main__': p(c(r(3,c(r(3,s('9')),s('1'))),s('2')))
that gives us the expected output:
For the real Kaufman digit sequences we can promote the ordinary digit sequences to transfinite ones (we use a slightly non-standard definition, allowing sequences of any length), using ordinal indices. Then the concatenation and repetition operations can be defined in essentially the same way:
- Repetition: .
Ordinal modulus is easily defined by using the division theorem for ordinals.
We can construct the set containing all the Kaufman sequences by starting with the one digit “sequences”,
(where “0” is the length 1 sequence having the single digit 0),
and defining the next step based on the previous one,
As we have defined for all integer , now we can define , the set of Kaufman sequences, as
It’s easy to see that this sequences can be totally ordered. Let’s define the extension operation for the Kaufman digit sequences:
Then we define two sequences are equal if their extensions match:
If they don't match, they must differ in some digit and we can order them based on that digit:
The Kaufman decimals can be formally defined and totally ordered by using transfinite sequences. It wouldn’t be too hard to adapt the previous Python code to accept ordinal indices in Cantor normal form, but I’m still not sure if there is an efficient procedure to order Kaufman decimals.