Frédéric Wang Yet another non-exponentially growing weblog

About Me  Blog Archive

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

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

and so forth until

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

You can notice that 11 has only one element and for any n1n \geq 1, in order to enumerate the elements of n+1n+1 using only the four characters "∅", ",", "{" and "}", you first write the elements of nn, followed by a comma, followed by an opening brace, followed by the elements of nn 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=6n=6 already exceeds the 72-character limit. From the previous recursive construction of the string one can deduce a recursive definition of its length:

L1=1L_1 = 1 Ln+1=Ln+2+Ln+1=2Ln+3L_{n+1} = L_n + 2 + L_n + 1 = 2L_n +3

It is easy to see that Ln=Ω(2n)L_n = {\Omega{(2^n)}} so although the simple JavaScript loop above uses a time complexity of O(n){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=72n = 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 LnL_n for any n1n \geq 1. Since for all i1i \geq 1, Li+2Li+1=2(Li+1Li)L_{i+2} - L_{i+1} = 2\left(L_{i+1} - L_i\right) the sequence (Li+1Li)i1\left(L_{i+1} - L_i\right)_{i \geq 1} is a geometric sequence with common ratio 2 and for all i1i \geq 1 we can write

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

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

LnL1=i=1n1Li+1Li=(L2L1)(i=0n22i)=(L2L1)(2n11) 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 L1=1L_1 = 1 and L2=2L1+3=5L_2 = 2L_1 + 3 = 5, one can write for all n1n \geq 1:

Ln=(2n11)(51)+1=2n+13L_n = (2^{n-1}-1) (5-1) + 1 = 2^{n+1} - 3

This formula can be used to calculate LnL_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αS_{\alpha} and its length LαL_\alpha are defined by induction for any ordinal α\alpha. S0S_0 is the empty string L0=0L_0 = 0. S1S_1 is the string with one character "∅" and L1=1L_1 = 1. For α1\alpha \geq 1, Sα+1S_{\alpha+1} is the string obtained by concatenating the string SαS_\alpha, a comma character ",", an opening brace character "{", the string SαS_\alpha and finally a closing brace character "}". It is of length Lα+1=Lα+2+Lα+1L_{\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λS_\lambda is obtained by taking the union of the LαL_\alpha-sequence Sα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λS_\lambda is of length Lλ=supα<λLαL_\lambda = \sup_{\alpha < \lambda} L_\alpha.

By construction, LαL_\alpha is an increasing sequence of ordinals and so Lαα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ωS_\omega can be more easily seen as the ω\omega-concatenation of finite strings: the empty set, a comma, S1S_1 surrounded by braces, a comma, S2S_2 surrounded by braces, a comma, S3S_3 surrounded by braces, a comma, etc So clearly Lω=ωL_{\omega} = \omega and this aligns with the definition for limit ordinal.

In order to write Sω+1S_{\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 ω+ω+1\omega + \omega + 1 sequence. This aligns with the definition in the successor ordinal case, using the fact that k+ω=ωk + \omega = \omega for any k<ωk < \omega:

Lω+1=Lω+2+Lω+1=ω+2+ω+1=ω2+1L_{\omega+1} = L_\omega + 2 + L_\omega + 1 = \omega + 2 + \omega + 1 = \omega2 + 1

Continuing for other successor ordinals, one can write

Lω+2=Lω+1+2+Lω+1+1=ω2+1+2+ω2+1+1=ω4+2L_{\omega+2} = L_{\omega+1} + 2 + L_{\omega+1} + 1 = \omega2 + 1 + 2 + \omega2 + 1 + 1 = \omega4 + 2 Lω+3=Lω+2+2+Lω+2+1=ω4+1+2+ω4+2+1=ω8+3L_{\omega+3} = L_{\omega+2} + 2 + L_{\omega+2} + 1 = \omega4 + 1 + 2 + \omega4 + 2 + 1 = \omega8 + 3

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

Lω+n=ω2n+nL_{\omega+n} = \omega{2^n} + n

To calculate Sω2S_{\omega2}, one takes the union for n<ωn < \omega of the Lω+nL_{\omega+n}-sequence of characters describing ω+n\omega+n. Its length is

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

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

Lω2+n=ω22n+nL_{\omega2+n} = \omega^2{2^n} + n

Continuing this kind of calculations for larger values ω3,ω4,,ω2\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α=Lωβ+n=ωβ2n+nL_{\alpha} = L_{\omega \beta + n} = \omega^\beta 2^n + n

where β1\beta \geq 1 and n<ω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 β=1\beta = 1 in the example above. Similarly, for a given β1\beta \geq 1, it is enough to prove the case n=0n = 0, the formula for n>0n > 0 follows, using the property k<ω,k+ωβ=ωβ\forall k < \omega, k + \omega^\beta = \omega^\beta and the calculations we gave for the case β=1\beta = 1.

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

Lω(β+1)=Lωβ+ω=supn<ωLωβ+n=supn<ω(ωβ2n+n)=ωβ+1L_{\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ωλ=supβ<λLωβ=supβ<λωβ=ωλL_{\omega \lambda} = {\sup_{\beta < \lambda} L_{\omega \beta}} = {\sup_{\beta < \lambda} \omega^{\beta}} = \omega^{\lambda}


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