User blog:Rgetar/Ordinal Explorer update (periods; levels; indentation modes)

Today I updated Ordinal Explorer web page program.

I found errors in its previous (March 2021) version, for example, infinite descending chain, incorrect converting into syntax sugar. In the new version I fixed these issues and many other bugs and made other improvements.

Periods

In previous version fundamental sequences looked ugly, for example, fundamental sequence of ω² were

ω

ω + 1

ω2

ω2 + 1

ω3

ω3 + 1

ω4

ω4 + 1

...

I noticed that fundamental sequences look better after removing some elements, for example,

ω

ω2

ω3

ω4

...

Then I noticed that fundamental sequence of any string can be represented as

primer + ending₀

primer + period + ending₁

primer + period + period + ending₂

primer + period + period + period + ending₃

primer + period + period + period + period + ending₄

primer + period + period + period + period + period + ending₅

...

Generally, n-th element of fundamental sequence of string α:

fs(α, n) = primer + n periods + ending_n

Moreover, I noticed that primer and period always can be extracted from α.

ending_n can be found from known primer, period and n.

So, to find fs(α, n) it is enough to find primer and period of α.

Levels

Then I noticed that the system can be generalized onto levels so that lesser level system is special case of larger level system. I set level using nlevels parameter. Initially I worked with nlevels = 2, but now the program works with any natural nlevels: 0, 1, 2, 3, ... In different levels strings, corresponding to the same ordinal, are different, but their fundamental sequences are identical.

For example, let we start with nlevels = 1, and initial string is the largest string in nlevels = 1. Then we do some expansions and create some list of strings. Then we start with nlevels = 2, and set initial string such as corresponding ordinal is the same as for largest string in nlevels = 1. Then we do same expansions. The resulting list will be identical with previous list (the same corresponding ordinals, the same number of strings), although all strings are different. But this time initial string is not the largest in nlevels = 2. (Then we can increase initial string and go beyond the largest string in nlevels = 1).

Corresponding largest ordinals in levels:

nlevels = 0: ε₁

nlevels = 1: Bachmann-Howard ordinal

nlevels = 2: I do not know, in my designations it is limit of {ε₀, [I], [[c²]] = [I(1, 0, 0)], [[c^c]], [[c^cc]], ...} ([M]? Rathjen's ordinal?)

...

Alphabet

Alphabet consists of 3 symbols:

]

[

c

(Note: in the program I use "!" instead of "]", because "]" goes after "[" in Unicode).

Strings

Strings:

empty string

c

β[X], where β, X are strings

Definitions of base and booster:

base(β[X]) = β

booster(β[X]) = X

(Note: base and booster work also with invalid β strings, for example, with β = [[).

There is also special string "Some large ordinal" (SLO).

Comparison

Strings are compared lexicographically, where ] < [ < c.

SLO is larger than any other string.

Periodical comparison

To do "periodical comparison" of 2 strings compare their length. If the lengths are equal, then compare strings lexicographically. Else repeat shorter string several times to make it longer (or at least not shorter), then compare strings lexicographically.

Fundamental sequences

Parameter nlevels is a natural number.

"+" means concatenation of strings.

let repeat(string, N) = string repeated N times

To find fs(α, n) (n-th element of fundamental sequence of string α) we need to find primer, period and ending_n of α:

fs(α, n) = primer + repeat(period, n) + ending_n

There are 5 rules to find primer and period:

If α = empty string then

Zero rule

fundamental sequence is empty

else if α = SLO then

SLO rule

primer = repeat([, nlevels) + c

period = [c

else if α = β[] then

Successor rule

fundamental sequence contains only one element fs(α, 0) = β

that is

primer = β

else if last non-] symbol of α = [ then

Plain rule

remove all trailing ] of α

replace last symbol of α with ]

primer = base(α)

period = [ + booster(α) + ]

else

Main rule

create cb array:

cb[0] = α

cb[1] = booster(α)

cb[2] = booster(booster(α))

cb[3] = booster(booster(booster(α)))

cb[4] = booster(booster(booster(booster(α))))

...

cb[N] = c

if nlevels < 2 then

let leastr = SLO

else

let leastr = repeat([, nlevels - 2) + c + repeat(], nlevels - 2)

let lr = last element of cb < leastr

let p = last element of cb < lr

remove all trailing ] of elements of cb

replace last symbol of each element of cb with [

primer = cb[0]

remove all trailing [ of primer

remove all cb elements preceding p

remove all leading [ of elements of cb

period = periodically largest element of cb (if there are periodically equal largest elements, take last of them)

move all trailing [ of period to beginning

Finding ending_n

ending_n consists of "]" symbols so that fs(α, n) contains same number of "[" and "]" symbols.

For example, let primer + repeat(period, n) contains 8 "[" and 5 "]". Then ending_n = ]]].

Standard forms

SLO is standard form.

If α is standard form, then fs(α, n) is standard form.

Other strings are non-standard forms.

Note: some non-standard forms (for example, c) may be described as uncountable ordinals, but such strings appear only as parts of "countable" strings.

Switching nlevels and initial strings

By default nlevels = 2.

N key: decrease nlevels by 1

M key: increase nlevels by 1

Initial string also may be switched:

V key: decrease initial string

B key: increase initial string

Initial string is always largest string of some level. For example, possible initial strings at nlevels = 0:

largest string of level 0

possible initial strings at nlevels = 1:

largest string of level 0

largest string of level 1

possible initial strings at nlevels = 2:

largest string of level 0

largest string of level 1

largest string of level 2

possible initial strings at nlevels = 3:

largest string of level 0

largest string of level 1

largest string of level 2

largest string of level 3

...

By default initial string is largest string of level 2.

To check that larger levels are special cases of lesser levels try to set same initial strings at different levels. For example, multiple expansions of largest string of level 0 as initial string results in identical lists of ordinals at any level:

3 strings after single expansion

6 strings after double expansion

14 strings after triple expansion

40 strings after quadruple expansion

135 strings after quintuple expansion

524 strings after sextuple expansion

2310 strings after septuple expansion

11568 strings after octuple expansion

66379 strings after ninefold expansion

multiple expansions of largest string of level 1 as initial string at any level results in

3 strings after single expansion

10 strings after double expansion

53 strings after triple expansion

415 strings after quadruple expansion

4694 strings after quintuple expansion

79419 strings after sextuple expansion

multiple expansions of largest string of level 2 as initial string at any level results in

3 strings after single expansion

15 strings after double expansion

150 strings after triple expansion

2479 strings after quadruple expansion

69567 strings after quintuple expansion

etc.

(Multiple expansions can be performed using C key several times (expansions of highlighted string); or using 2 - 9 keys, then mouse click on a string).

Note: syntax sugar works incorrectly for nlevels ≠ 2. For example, ε₀ is displayed as

c at nlevels = 0

Ω at nlevels = 1

ε₀ at nlevels = 2 (correclty)

[ε₀] at nlevels = 3

[[ε₀]] at nlevels = 4

[[[ε₀]]] at nlevels = 5

...

Note: switching nlevels or initial string also resets list.

Indentation modes

In older versions of Ordinal Explorer fundamental sequences displayed like this:

1

2

3

4

5

6

7

ω

ω + 1

ω2

ω²

ω^ω

ε₀

I thought: what if do alignment of indentation by fundamental sequences instead of expansions? That is like this:

1

2

3

4

5

6

7

ω

ω + 1

ω2

ω²

ω^ω

ε₀

Now there are 3 indentation modes:

no indentation

alignment by fundamental sequences (default mode)

alignment by expansions (old mode)

How to switch them:

J key: remove indentation

K key: toggle alignment by fundamental sequences

L key: toggle alignment by expansions

Сontrol of the list from the keyboard

Arrow up key: move highlight up

Arrow down key: move highlight down

Space key: add to the list one element of fundamental sequence of highlighted string

Enter key: do single expansion of highlighted string

Backspace key: remove largest element of fundamental sequence of highlighted string and all strings between them

C key: do continued expansions of highlighted string (single, double, triple, ...)

R key: reset list

Some changes

The new rules led to some changes, and I like them.

For example, I noticed that "Ω_{n + 1}" correspond to ε numbers of "Ω_n" (that is ε_{Ωn + 1}, ε_{Ωn + 2}, ε_{Ωn + 3}, ...)

Non-standard form for Bachmann-Howard ordinal [Ω₂] is [ε_{Ω + 1}], etc.

But in older versions this pattern did not always work, for example, [Ω₂][Ω₂] was supremum of

[Ω₂][Ω]

[Ω₂][Ω2]

[Ω₂][Ω²]

[Ω₂][Ω^Ω]

[Ω₂][Ω^ΩΩ]

...

Now [Ω₂][Ω₂] is supremum of

[Ω₂][ε_{Ω + 1}]

[Ω₂][ε_{Ω + 1}2]

[Ω₂][ε_{Ω + 1}²]

[Ω₂][ε_{Ω + 1}^{ε_{Ω + 1}}]

[Ω₂][ε_{Ω + 1}^{ε_{Ω + 1}ε_{Ω + 1}}]

...

that is [Ω₂][Ω₂] = [ε_{Ω + 2}], and so on.

Non-trivial cases of non-minimal standard forms

Sometimes standard form is not the shortest form. For example, at nlevels = 2

[[c]][[[c]][[[c]]]] is standard form of ε₀²

but

[[[c]][[[c]]]] is shorter non-standard form of ε₀²

Or

[[c]][[[c]][[[c]][[[c]]]]] is standard form of ε₀^ε₀

but

[[[[c]][[[c]]]]] is shorter non-standard form of ε₀^ε₀

The point is that this is to keep lexicographical order. Because with shortest forms we get

[[c]] > [[[c]][[[c]]]] > [[[[c]][[[c]]]]]

Bu we need

ε₀ < ε₀² < ε₀^ε₀

With non-minimal standard forms we get correct order:

[[c]] < [[c]][[[c]][[[c]]]] < [[c]][[[c]][[[c]][[[c]]]]]

---

Using new rules I found non-trivial cases of non-minimal standard forms, for example,

[[c[c]]][[c[[c[c]]]][c[[c[[c[[c[c]]]]]]]]] = [I][Ω_{Φ(1, 0) + ΩΦ(1, 0)}]

But

Ω_{Φ(1, 0)} = Φ(1, 0)

and I asked myself: why not

[[c[c]]][[c[[c[c]]]][c[[c[[c[c]]]]]]] = [I][Ω_{Φ(1, 0)2}]

Then I realized that this is not an error, because there is larger string

[[c[c]]][[c[[c[c]]]][c[[c[[c[[c[c]]]]][]]]]] = [I][Ω_{Φ(1, 0) + ΩΦ(1, 0)ω}]

But lexicographically

[[c[c]]][[c[[c[c]]]][c[[c[[c[c]]]]]]] > [[c[c]]][[c[[c[c]]]][c[[c[[c[[c[c]]]]][]]]]]

However, non-minimal standard form keeps lexicographical order:

[[c[c]]][[c[[c[c]]]][c[[c[[c[[c[c]]]]]]]]] < [[c[c]]][[c[[c[c]]]][c[[c[[c[[c[c]]]]][]]]]]

---

Unfortunately, currently syntax sugar converter can not work with such cases, and such strings are displayed incorrectly. For example,

[[c[c]]][[c[[c[c]]]][c[[c[[c[[c[c]]]]]]]]]

is displayed as

[I][Ω_{Φ(1, 0) + ΩΦ(1, 0)}]

but supposed

[I][Ω_{Φ(1, 0)2}]

Or, different strings may be displayed identically. For example, fundamental sequence of

[[c[c]]][[c[[c[c]]]][c[[c[[c[[c[c]]]]][]]]]] (displayed as [I][Ω_{Φ(1, 0) + ΩΦ(1, 0)ω}], but correct form is [I][Ω_{ΩΦ(1, 0)ω}])

is displayed as

[I][Ω_{Φ(1, 0) + ω}]

[I][Ω_{Φ(1, 0) + ΩΦ(1, 0)}]

[I][Ω_{Φ(1, 0) + ΩΦ(1, 0)}]

[I][Ω_{Φ(1, 0) + ΩΦ(1, 0)}]

[I][Ω_{Φ(1, 0) + ΩΦ(1, 0)}]

[I][Ω_{Φ(1, 0) + ΩΦ(1, 0)}]

...

but supposed

[I][Ω_{Φ(1, 0) + ω}]

[I][Ω_{Φ(1, 0)2}]

[I][Ω_{ΩΦ(1, 0)2}]

[I][Ω_{ΩΦ(1, 0)3}]

[I][Ω_{ΩΦ(1, 0)4}]

[I][Ω_{ΩΦ(1, 0)5}]

...

Other issues

Also there were some other issues with syntax sugar converter and other small bugs, and I fixed them.

P.S.: Example of infinite descending chain in previous version:

[I2]

[I + Φ(1, 0)]

[I + Ω_{Φ(1, 0)}]

[I + Ω_{ΩΦ(1, 0)}]

[I + Ω_{ΩΩΦ(1, 0)}]

...

(The cause of this problem was incorrect work of function checking is input string a standard form. In the new version this function is not used).

Example of incorrect converting into syntax sugar in previous version:

[[c[[c][[c][[c]]]]]] → [Ω_Ω^Ω]

and its fundamental sequence:

[Ω_ω^ωωω]

[Ω_ω^ωωωω]

[Ω_ε0^ε0]

[Ω_{[Ωω]^[Ωω]}]

[Ω_{[Ωω^ω]^[Ωωω]}]

Supposed:

[[c[[c][[c][[c]]]]]] → [Ω_Ω^ΩΩ]

and its fundamental sequence:

[Ω_Ω^Ωωω]

[Ω_Ω^Ωωωω]

[Ω_Ω^Ωε0]

[Ω_Ω^Ω[Ωω]]

[Ω_{Ω^Ω[Ωωω]}]

(The cause of this problem was passing an array as a parameter to a function, but sometimes original array changed, because arrays are of pointer type. The problem was solved by passing copy of the array).