The road to epsilon-zero: “Shortlex” isn't actually a single order

Previously:

1. Ordinal numbers and basic set theory
2. Ordinals as nim-heaps
3. Nim always ends, even with infinite ordinals
4. Infinite Nim as a coin-moving game
5. Coin-moving games with no coins
6. Productive programs and well-founded orders
7. Shortlex order also orders sequences of numbers

Something tricky happened a couple of articles ago that I wish now I'd explained more carefully. The recent articles talk about “shortlex order”. But “shortlex order” isn't really just one order. It's actually a method for turning one order into another, fancier one.

The definition I gave said:

The rule to compare two strings in shortlex order is:

1. If the strings are different lengths, the shorter one comes first.
2. If they're the same length, compare them lexicographically.

But there's something hiding in that “lexicographically”. To compare strings lexicographically, you have to compare them character-by-character, and that means you already have to have some idea of the order of the characters themselves. If we don't notice that “sort these into lexicographic order” is ambigous, it's only because a particular standard ordering of the characters is implicit.

But lexicographic and shortlex orderings aren't restricted to strings of characters. They can be used to extend an ordering on any kind of thing to an ordering on sequences of that-kind-of-thing. If the things are characters, they extend the ordering of the characters to an ordering on strings, which are sequences of characters. But the things don't have to be characters.

In the previous article we took the ordinary ordering on finite numbers (note, not characters) and used the shortlex constructin to produce an ordering on sequences of finite numbers:

Replace any one sequence of [finite number] coordinates with one that is earlier in shortlex order.

The phrase “in shortlex order” there is implicitly assuming the usual ordering of finite numbers. If we had decided to start with a different ordering of finite numbers, the shortlex extension to sequences would be different.

A of couple of episodes ago we saw an ordering of the positive numbers that put all the odd numbers before all the even numbers. Since that basic ordering puts before , the shortlex extension of it would put before . And because the basic ordering also put before the shortlex extension would put before .

Digression

For wacky fun, put the list of words in the dictionary into a lexicographic order that is extended from a different alphabetical order than the usual one!

For example, suppose the alphabet was in the order QWERTY UIOP ASDF GHJKL ZXCV BNM. The dictionary would start with “queer”, then all the other QU words up through “quandaries”, finish out the Q section with a few non-Qu words like “Qantas”, and then continue with the W words. The last word in the dictionary wouldn't be “zyzzyva”, it would be “mnemonics”.

Is your kid having trouble learning to alphabetize? Try alphabetizing this random list into QWERTY order to help yourself feel sympathetic:

criteria dapple duskiest flapjack gnawing immerses irk puppet surveyor sweetens

Remember, ‘c’ is no longer the third letter of the alphabet, it's now 22nd.

Here they are in QWERTY order instead:

irk immerses puppet sweetens surveyor duskiest dapple flapjack gnawing criteria

Shortlex isn't an order, it's a method for elaborating a simpler order

Say we have some set of things, and an order relation on , which we'll call .

We use the symbol “” rather than “” to emphasize that this is not necessarily the usual ordering. We still write to mean that comes before in whatever order represents, and analogously we can write means the same: comes after .

The notation means the set of all finite sequences of elements of . For example, when is a character set, is the set of strings over that character set. Elements of are not at all the same kind of things as elements of . Elements of are something-or-others, maybe melons or something — let's say melons, melons are fun — and if melon is rounder than melon . Elements of are sequences of melons.

If and are two sequences, you can't sensibly ask whether or , since it doesn't make to say that one sequence is rounder than another. is meaningful for comparing melons, not sequences.

We can't use to order elements of . But we can lexicographicize to make a new ordering that makes sense for . To lexicographically compare two elements of , that's two finite sequences of elements of , whatever they are, do this:

1. Compare the corresponding elements of each sequence, using , starting with the first elements
2. If two sequence elements are different at some posision, the sequence with the -earlier element comes earlier
3. If the two elements are the same, move on to the next corresponding elements and continue similarly.
4. If one sequence ends before the other, then that one comes earlier.
   If both end at the same time, the two sequences were exactly the same, so neither comes earlier.

This turns into a lexicographic elaboration of that makes it work on sequences. This is the same transformation that turns an ordering on characters into the derived ordering for strings.

We can turn into an ordering for sequences in another way, the shortlex way, producing an order I'll write as :

1. If the sequences are different lengths, the shorter one comes first.
2. If they're the same length, compare them lexicographically as above.

This is the same transformation that turns the regular ordering on digits () into the derived ordering for ordinary base-10 numerals.

I thought we'd get to today, but it seems not. Here's a preview of the next article, though: We're not going to stop with , we're going to go on to and .

Claude wanted to help with this article, but I wouldn't let it.