The Universe of Discourse

The road to epsilon-zero: Shortlex order also orders sequences of numbers

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

In part 4, Infinite Nim as a coin-moving game, we saw how to reinterpret infinite Nim into an equivalent game: instead of heaps of beans and various special tokens, we interpreted it as a game about moving coins first on a track, then on a grid, and then in a rather difficult-to-visualize infinite-dimensional space.

In part 5, Coin-moving games with no coins, we stopped thinking about the coins and their locations in space, and just wrote down the coordinates of each coin. Each coin has an infinite sequence of coordinates, each of which is a non-negative number. But crucially, only a finite number of the coordinates are greater than zero, so every coin's list of coordinates can be written down as a finite sequence, with the infinite tail of zeroes left implicit.

The rule for the original game of Nim was: take as many beans as you want from any one pile.

The rule for the reinterpreted form is: reduce any one sequence of coordinates, as follows:

1. Pick any nonzero coordinate
2. Reduce it by at least 1
3. Replace any coordinates to the left of that one with any numbers at all

For example, we can move from !!⟨2, 3⟩!! to !!⟨17, 2⟩!! (the !!3!! has decreased), or to !!⟨1, 3⟩!! (the !!2!! has decreased). We can move from !!⟨9, 3, 7⟩!! to !!⟨1000, 23, 5⟩!! (the !!7!! has decreased), or to !!⟨86, 19, 0⟩!!, which we can also write as !!⟨86, 19⟩!!.

Now that we've learned about shortlex order, we can state the game rule more simply:

Replace any one sequence of coordinates with one that is earlier in shortlex order.

There's one minor wrinkle. We had defined shortlex order as:

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

None of that has changed, but we need to be a bit careful about “lexicographically”.

When we write ordinary numerals, like 239, we write the most significant part on the left. In this case it's the !!2!!, which represents !!200!!. And when we compare numerals of the same length lexicographically, we compare these most significant parts first, moving rightward only if the leftmost parts are tied.

To lexicographically compare sequences of coordinates or the same length, we still need to begin with the most significant part as before. But because of how we are writing the sequences, the most significant part is the rightmost component. A sequence like !!⟨9, 3, 2⟩!! represents a nim-heap of !!9 + ω·3 +ω^2·2!! beans, and the !!2!! is the most significant component, because !!ω^2·2!! is vastly more than !!9+ω·3!! beans.

I said at some point that !!ω^ω!! was where the ordinals start to get scary. But !!ω^ω!! is now not scary at all. It's just the family of of nim-heaps where:

1. Instead of beans, we think of a heap as a finite sequence of finite numbers
2. Instead of imagining the player removing beans from a heap, we imagine them replacing the sequence with a sequence that is earlier in shortlex order

And to play Nim with ⸢heaps⸣ of this sort, the winning rule is, as always, that the winner is the player who reduces the last ⸢heap⸣ to to zero.

We can completely forget about beans, about infinite piles, about infinite varieties of colored tokens, about coins moving around in infinite-dimensional spaces, and so on. !!ω^ω!!-Nim is just finite sequences of ordinary numbers, and you can move from one sequence to any earlier one.

I think !!ε_0!! is going to arrive in the next article.

Claude was on vacation this week, and took all the em-dashes with it, so I not only had to write the whole thing myself, I couldn't even put in any em-dashes.

[Other articles in category /math/ordinals] permanent link