# Ordinals as strings of ∅, commas and braces

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 $\backslash empty$:

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

and so forth until

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

You can notice that $1$ has only one element $\varnothing $ and for any $n\; \backslash 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:

## 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\; =\; \{\backslash 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:

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

$$\{L\_\{i+1\}\; -\; L\_\{i\}\}\; =\; \{2^\{i-1\}\; \backslash left(\; L\_2\; -\; L\_1\; \backslash right)\}$$

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

$$L\_n\; -\; L\_1\; =\; \{\backslash sum\_\{i=1\}^\{n-1\}\; L\_\{i+1\}\; -\; L\_\{i\}\}\; =\; \{\backslash left(\; L\_2\; -\; L\_1\; \backslash right)\; \backslash left(\backslash sum\_\{i=0\}^\{n-2\}\; 2^i\; \backslash right)\}=\; \{\; \{\backslash left(\; L\_2\; -\; L\_1\; \backslash right)\}\; \{\backslash left(2^\{n-1\}-1\backslash right)\}\; \}$$

Finally, given that $L\_1\; =\; 1$ and $L\_2\; =\; 2L\_1\; +\; 3\; =\; 5$, one can write for all $n\; \backslash 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.

## Order-type of infinite strings

It is possible to generalize this problem to infinite ordinal numbers. The string $S\_\{\backslash alpha\}$ and its length $L\_\backslash alpha$ are defined by induction for any ordinal $\backslash alpha$. $S\_0$ is the empty string $L\_0\; =\; 0$. $S\_1$ is the string with one character `"∅"`

and $L\_1\; =\; 1$. For $\backslash alpha\; \backslash geq\; 1$, $S\_\{\backslash alpha+1\}$ is the string obtained by concatenating the string $S\_\backslash alpha$, a comma character `","`

, an opening brace character `"{"`

, the string $S\_\backslash alpha$ and finally a closing brace character `"}"`

. It is of length $L\_\{\backslash alpha+1\}\; =\; L\_\backslash alpha\; +\; 2\; +\; L\_\backslash alpha\; +\; 1$. Beware that ordinal operations are not commutative so this cannot be simplified a priori!

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

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

Let’s consider some examples. In the case $\backslash omega\; =\; \backslash mathbb\; N$, the string $S\_\backslash omega$ can be more easily seen as the $\backslash 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\_\{\backslash omega\}\; =\; \backslash omega$ and this aligns with the definition for limit ordinal.

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

$$L\_\{\backslash omega+1\}\; =\; L\_\backslash omega\; +\; 2\; +\; L\_\backslash omega\; +\; 1\; =\; \backslash omega\; +\; 2\; +\; \backslash omega\; +\; 1\; =\; \backslash omega2\; +\; 1$$

Continuing for other successor ordinals, one can write

$$L\_\{\backslash omega+2\}\; =\; L\_\{\backslash omega+1\}\; +\; 2\; +\; L\_\{\backslash omega+1\}\; +\; 1\; =\; \backslash omega2\; +\; 1\; +\; 2\; +\; \backslash omega2\; +\; 1\; +\; 1\; =\; \backslash omega4\; +\; 2$$ $$L\_\{\backslash omega+3\}\; =\; L\_\{\backslash omega+2\}\; +\; 2\; +\; L\_\{\backslash omega+2\}\; +\; 1\; =\; \backslash omega4\; +\; 1\; +\; 2\; +\; \backslash omega4\; +\; 2\; +\; 1\; =\; \backslash omega8\; +\; 3$$

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

$$L\_\{\backslash omega+n\}\; =\; \backslash omega\{2^n\}\; +\; n$$

To calculate $S\_\{\backslash omega2\}$, one takes the union for $n\; <\; \backslash omega$ of the $L\_\{\backslash omega+n\}$-sequence of characters describing $\backslash omega+n$. Its length is

$$L\_\{\backslash omega2\}\; =\; \{\backslash sup\_\{n\; <\; \backslash omega\}\; \backslash left(\backslash omega\{2^n\}\; +\; n\backslash right)\}\; =\; \backslash omega^2$$

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

$$L\_\{\backslash omega2+n\}\; =\; \backslash omega^2\{2^n\}\; +\; n$$

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

$$L\_\{\backslash alpha\}\; =\; L\_\{\backslash omega\; \backslash beta\; +\; n\}\; =\; \backslash omega^\backslash beta\; 2^n\; +\; n$$

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

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

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

$$L\_\{\backslash omega\; \{(\backslash beta\; +\; 1)\}\}\; =\; L\_\{\backslash omega\backslash beta\; +\; \backslash omega\}\; =\; \{\backslash sup\_\{n\; <\; \backslash omega\}\; L\_\{\backslash omega\; \backslash beta\; +\; n\}\}\; =\; \{\backslash sup\_\{n\; <\; \backslash omega\}\; \{(\backslash omega^\backslash beta\; 2^n\; +\; n)\}\; \}\; =\; \backslash omega^\{\backslash beta+1\}$$

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

$$L\_\{\backslash omega\; \backslash lambda\}\; =\; \{\backslash sup\_\{\backslash beta\; <\; \backslash lambda\}\; L\_\{\backslash omega\; \backslash beta\}\}\; =\; \{\backslash sup\_\{\backslash beta\; <\; \backslash lambda\}\; \backslash omega^\{\backslash beta\}\}\; =\; \backslash omega^\{\backslash lambda\}$$

Q.E.D.