Ordinals as strings of ∅, commas and braces

05 Mar 2020

This week, my colleagues at Igalia were talking about cutting text at a 72-characters limit for word-wrapping emails. One might say that the real question is whether 72 is a cut or a limit. Or wonder how one has decided to set that particular value?

The latter link explains the recursive definition of 72 as a finite set, which can be written with only braces, commas and the empty set $\empty$:

$$0 = {\{\}} = \empty$$ $$1 = 0 \union {\{0\}} = {\{0\}} = {\{\empty\}}$$ $$2 = 1 \union {\{1\}} = {\{0,1\}} = {\{ \empty, {\{\empty\}} \}}$$ $$3 = 2 \union {\{2\}} = {\{0,1,2\}} = {\{ \empty, {\{\empty\}}, {\{ \empty, {\{\empty\}} \}} \}}$$

and so forth until

$$72 = 71 \union {\{71\}} = {\{0,1,2,\dots,71\}} = \dots$$

You can notice that $1$ has only one element $∅$ and for any $n \geq 1$, in order to enumerate the elements of $n+1$ using only the four characters "∅", ",", "{" and "}", you first write the elements of $n$, followed by a comma, followed by an opening brace, followed by the elements of $n$ and finally followed by a closing brace. One can write a simple JavaScript loop that initializes a variable string = "∅" and performs the concatenation string += `,{${string}}` at each step:

The elements of are

Length of the string

You notice that the length of the string obtained for $n=6$ already exceeds the 72-character limit. From the previous recursive construction of the string one can deduce a recursive definition of its length:

$$L_1 = 1$$ $$L_{n+1} = L_n + 2 + L_n + 1 = 2L_n +3$$

It is easy to see that $L_n = {\Omega{(2^n)}}$ so although the simple JavaScript loop above uses a time complexity of ${O{(n)}}$ string concatenations, the space complexity is at least exponential. That’s why in the definition of 72 above I used dots instead of showing the whole string!

One can however easily modify the previous JavaScript loop to calculate the length of such a string. At Igalia, we have been working on a new native type called BigInt which is particularly useful to accurately calculate large integers. The case $n = 72$ demonstrates why it is more appropriate than JavaScript Number:

The length of the strings enumerating the elements of has the following length (first field uses Number, second field uses BigInt):

One can do better and try to calculate an explicit formula for $L_n$ for any $n \geq 1$. Since for all $i \geq 1$, $L_{i+2} - L_{i+1} = 2\left(L_{i+1} - L_i\right)$ the sequence $\left(L_{i+1} - L_i\right)_{i \geq 1}$ is a geometric sequence with common ratio 2 and for all $i \geq 1$ we can write

$${L_{i+1} - L_{i}} = {2^{i-1} \left( L_2 - L_1 \right)}$$

Summing this up for $1 \leq i \leq n - 1$:

$$L_n - L_1 = {\sum_{i=1}^{n-1} L_{i+1} - L_{i}} = {\left( L_2 - L_1 \right) \left(\sum_{i=0}^{n-2} 2^i \right)}= { {\left( L_2 - L_1 \right)} {\left(2^{n-1}-1\right)} }$$

Finally, given that $L_1 = 1$ and $L_2 = 2L_1 + 3 = 5$, one can write for all $n \geq 1$:

$$L_n = (2^{n-1}-1) (5-1) + 1 = 2^{n+1} - 3$$

This formula can be used to calculate $L_n$ using built-in JavaScript exponentation instead of a loop, as done below.

The length of the strings enumerating the elements of has the following length (first field uses Number, second field uses BigInt):

Order-type of infinite strings

It is possible to generalize this problem to infinite ordinal numbers. The string $S_{\alpha}$ and its length $L_\alpha$ are defined by induction for any ordinal $\alpha$. $S_0$ is the empty string $L_0 = 0$. $S_1$ is the string with one character "∅" and $L_1 = 1$. For $\alpha \geq 1$, $S_{\alpha+1}$ is the string obtained by concatenating the string $S_\alpha$, a comma character ",", an opening brace character "{", the string $S_\alpha$ and finally a closing brace character "}". It is of length $L_{\alpha+1} = L_\alpha + 2 + L_\alpha + 1$. Beware that ordinal operations are not commutative so this cannot be simplified a priori!

For any limit ordinal $\lambda$, the string $S_\lambda$ is obtained by taking the union of the $L_\alpha$-sequence $S_\alpha$ for $\alpha < \lambda$. This is still a well-defined sequence since these strings always agree on the character at a given index. $S_\lambda$ is of length $L_\lambda = \sup_{\alpha < \lambda} L_\alpha$.

By construction, $L_\alpha$ is an increasing sequence of ordinals and so $L_\alpha \geq \alpha$. Can we calculate it more explicitly?

Warning: The rest of the blog post gives the solution to this puzzle, so you might want to have fun solving it yourself first and then go back checking my proposed solution later 😉...

Let’s consider some examples. In the case $\omega = \mathbb N$, the string $S_\omega$ can be more easily seen as the $\omega$-concatenation of finite strings: the empty set, a comma, $S_1$ surrounded by braces, a comma, $S_2$ surrounded by braces, a comma, $S_3$ surrounded by braces, a comma, etc So clearly $L_{\omega} = \omega$ and this aligns with the definition for limit ordinal.

In order to write $S_{\omega+1}$, you first write the elements of $\omega$, followed by a comma, followed by an opening brace, followed by the elements of $\omega$ and finally followed by a closing brace. So really this is an $\omega + \omega + 1$ sequence. This aligns with the definition in the successor ordinal case, using the fact that $k + \omega = \omega$ for any $k < \omega$:

$$L_{\omega+1} = L_\omega + 2 + L_\omega + 1 = \omega + 2 + \omega + 1 = \omega2 + 1$$

Continuing for other successor ordinals, one can write

$$L_{\omega+2} = L_{\omega+1} + 2 + L_{\omega+1} + 1 = \omega2 + 1 + 2 + \omega2 + 1 + 1 = \omega4 + 2$$ $$L_{\omega+3} = L_{\omega+2} + 2 + L_{\omega+2} + 1 = \omega4 + 1 + 2 + \omega4 + 2 + 1 = \omega8 + 3$$

and more generally for all $n < \omega$:

$$L_{\omega+n} = \omega{2^n} + n$$

To calculate $S_{\omega2}$, one takes the union for $n < \omega$ of the $L_{\omega+n}$-sequence of characters describing $\omega+n$. Its length is

$$L_{\omega2} = {\sup_{n < \omega} \left(\omega{2^n} + n\right)} = \omega^2$$

Then the exact same calculation as above leads for all $n < \omega$ to

$$L_{\omega2+n} = \omega^2{2^n} + n$$

Continuing this kind of calculations for larger values $\omega3, \omega4, \dots, \omega^2$ suggests the following conjecture: For every infinite ordinal $\alpha$, the order-type of the sequence describing its element is:

$$L_{\alpha} = L_{\omega \beta + n} = \omega^\beta 2^n + n$$

where $\beta \geq 1$ and $n < \omega$ are the quotient and remainder of the euclidean division of $\alpha$ by $\omega$.

Let’s sketch the proof by induction on $\beta$. We already explained the case $\beta = 1$ in the example above. Similarly, for a given $\beta \geq 1$, it is enough to prove the case $n = 0$, the formula for $n > 0$ follows, using the property $\forall k < \omega, k + \omega^\beta = \omega^\beta$ and the calculations we gave for the case $\beta = 1$.

If the formula holds for some $\beta \geq 1$ then because $\omega{(\beta + 1)}$ is limit and the lengths are increasing, the formula holds for $\beta + 1$:

$$L_{\omega {(\beta + 1)}} = L_{\omega\beta + \omega} = {\sup_{n < \omega} L_{\omega \beta + n}} = {\sup_{n < \omega} {(\omega^\beta 2^n + n)} } = \omega^{\beta+1}$$

Finally, if the formula holds for all $\beta$ below a limit ordinal $\lambda$ then because the lengths are increasing the formula holds for $\lambda$ too:

$$L_{\omega \lambda} = {\sup_{\beta < \lambda} L_{\omega \beta}} = {\sup_{\beta < \lambda} \omega^{\beta}} = \omega^{\lambda}$$

Q.E.D.

Sorry, no JavaScript program to calculate these infinite strings 😇...