Continuous well-orders

continuous.mkd

Let [ ] : Ord -> Relation Nat be a function that realizes an ordinal into a well-ordering of the naturals with that order type.

Given a relation R on the naturals, we define the restricted relation R(<n) to be R but just acting on the first n naturals.

Defn: [ ] is continuous iff for every series of ordinals a_i whose limit is l, for every natural n, there exists an i such that for all j > i, [a_i](<n) = [l](<n).

Intuitively, if you are only looking at a finite prefix of the naturals, you can get to a limit ordinal by going finitely high up its limit sequence.

Defn: The interpolator between two well-orderings R and R' on N, denoted by <R|R'>(n), is defined by: x <R|R'>(n) y iff one of these conditions holds:

• x < n, y < n, and x R' y
• x >= n, y >= n, and x R y
• x >= n and y < n

The order type of <[a] | R>(n) is a + n. The limit as n goes to infinity is R.

An interpolator between

w = 0 1 2 3 4 5 6 7 8 9 ...

and

w*2 = 0 2 4 6 8 ... 1 3 5 7 9 ...

Proceeds as follows:

<w|w*2>(0) = 0 1 2 3 4 5 6 7 8 9 ...
       (1) = 1 2 3 4 5 6 7 8 9 ... 0
       (2) = 2 3 4 5 6 7 8 9 ... 0 1
       (3) = 3 4 5 6 7 8 9 ... 0 2 1
       (4) = 4 5 6 7 8 9 ... 0 2 1 3
       (5) = 5 6 7 8 9 ... 0 2 4 1 3
       (6) = 6 7 8 9 ... 0 2 4 1 3 5
       (7) = 7 8 9 ... 0 2 4 6 1 3 5
       (8) = 8 9 ... 0 2 4 6 1 3 5 7
       (9) = 9 ... 0 2 4 6 8 1 3 5 7
       (10) = 10 11 ... 0 2 4 6 8 1 3 5 7 9

Notice how <w|w*2>(10)(<10) (just cut off all numbers >= 10 and remove the dots in line (10)) looks the same as [w*2](<10).

It's not the most interesting thing to look at; the old ordering just slides off left as the new ordering is sorted in. It would be nice to have something a little more "stable". But this is what I've got, let's see where it goes.

To get to eg. w*w, we need to interpolate in a more sophisticated way. We need a restricted sequence to look like, for example:

w
w + 1
w + 2
w + 3 = w + w = w*2
w * 2 + 1
w * 2 + 2
w * 2 + 3 = w * 2 + w = w * 3
w * 3 + 1
w * 3 + 2 = w * 3 + w = w * 4 = w * w

Note the last line. We need it so that, for a high enough n, [w * n](<b) = [w * w](<b). We need an interpolator from w to w*w which has sequences of type w*n instead of w+n. We can use the normal interpolator between w*n and w*(n+1).

Let's rename the normal interpolator to the successor interpolator. Now we will define a general concept which interpolates limit ordinals.

Defn: A limit interpolator on a sequence of relations R_i whose order types limit to the relation L, denoted <R_i>(n), is defined by x <R_i>(n) y iff one of these conditions hold:

• x < n, y < n, and x L y.
• x >= n, y >= n, and x R_n y.
• x < n, y >= n.

That is, it plucks elements more-or-less at random (in increasing order of their representation) from the ordering and puts them in the ordering of L at the beginning (in contrast to the successor interpolator, which puts them at the end). Since the prefix is always finite, the ith element will always have the same order type as R_i, as long R_i is infinite.

However, the R_i are not restricted to only being infinite. In fact, if R_i is any successor ordinal, then we may accidentally pluck one of finite top elements and repurpose it at the beginning, thus changing the order type from S a to a. So for this interpolator to work, all the R_i order types must be limit ordinals. Fortunately we already have the successor interpolator.

These two interpolators give us the ability take any set of concrete orderings for the limit ordinals and modify them to be continuous.

Each continuous well ordering chain has as many degrees of freedom as there are limit ordinals. I was hoping to make a nice visualization of a sequence getting more and more tangled up as its order type increases. But w*2 can be represented to make any (particular) finite prefix look however you want it to; including the signature of the great most-tangled-up ordinal.

Can we restrict our requirements further in order to preserve a more natural tangling?