Kaufman decimals

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.

Introduction

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.

Finite repetitions

If we replace the infinite repetition by repeating the sequence K times, it’s easy to analyze the resulting sequences. For example, if K = 3,

\displaystyle \overline{\overline{\strut 9}\,1}\,2 = 9991999199912.

So now we can define concatenation in the following way:

\displaystyle \mathcal{C}(a_{i<n}, b_{j<m})_{k<n+m} = \begin{cases}a_k & \text{if }k < n \\ b_{k-n} & \text{otherwise}\end{cases}.

Repetition is also quite easy:

\displaystyle \mathcal{R}_K(a_{i<n})_{j < n \cdot K} = a_{k \bmod n}.

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:

9991999199912
Infinite repetitions

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:

  • Concatenation: \mathcal{C}(a_{\alpha < \delta}, b_{\beta < \zeta})_{\gamma < \delta + \zeta} = \begin{cases}a_\gamma & \text{if }\gamma < \delta \\ b_{\gamma - \delta} & \text{otherwise}\end{cases}
  • Repetition: \mathcal{R}(a_{\alpha < \gamma})_{\beta < \gamma \cdot \omega} = a_{\beta \bmod \gamma}.

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”,

\displaystyle K_0 = \{"0", "1", ..., "9"\} (where “0” is the length 1 sequence having the single digit 0),

and defining the next step based on the previous one,

\displaystyle K_{n+1} = K_n \cup \{\mathcal{C}(a_{\alpha < \delta}, b_{\beta < \zeta}) | a_{\alpha < \delta}, b_{\beta < \zeta} \in K_n\} \cup \{\mathcal{R}(a_{\alpha < \delta}) | a_{\alpha < \delta} \in K_n\}.

As we have defined K_n for all integer n, now we can define K_\omega, the set of Kaufman sequences, as

\displaystyle K_\omega = \bigcup_{n < \omega} K_n.

Total order

It’s easy to see that this sequences can be totally ordered. Let’s define the extension operation for the Kaufman digit sequences:

\displaystyle \mathcal{E}(a_{\alpha < \gamma})_{\beta \in \mathrm{On}} = \begin{cases}a_\beta & \text{if }\beta < \gamma \\ 0 & \text{otherwise}\end{cases}

Then we define two sequences are equal if their extensions match:

\displaystyle a_{\alpha < \delta} = b_{\beta < \zeta} \Leftrightarrow \forall \gamma \in \mathrm{On} : \mathcal{E}(a_{\alpha < \delta})_\gamma = \mathcal{E}(b_{\beta < \zeta})_\gamma.

If they don't match, they must differ in some digit and we can order them based on that digit:

\displaystyle a_{\alpha < \delta} < b_{\beta < \zeta} \Leftrightarrow \exists \gamma \in \mathrm{On} : \left(\mathcal{E}(a_{\alpha < \delta})_\gamma < \mathcal{E}(b_{\beta < \zeta})_\gamma \right)\wedge \left(\forall \lambda < \gamma : \mathcal{E}(a_{\alpha < \delta})_\lambda < \mathcal{E}(b_{\beta < \zeta})_\lambda\right).

Conclusions

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.

Advertisements

2 thoughts on “Kaufman decimals

  1. Petr Simecek says:

    I tried to implement the comparison for infinite repetitions, see https://github.com/rakosnicek/decimals

  2. […] indexed by a general ordinal alpha. One of them is a variant of "Kaufman decimals" (see https://mchouza.wordpress.com/2013/08/25/kaufman-decimals/ and http://www.jefftk.com/p/decimal-inconsistency) in which the digit-set {0,…,9} is replaced by […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s