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

Previously: Ordinal numbers and basic set theory Ordinals as nim-heaps Nim always ends, even with infinite ordinals Infinite Nim as a coin-moving game Coin-moving games with no coins Productive programs and well-founded orders 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: If the strings are different lengths, the shorter one comes first. 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…