The Universe of Discourse

The road to epsilon-zero: Coin-moving games with no coins

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

In the previous article we saw how to interpret Nim heaps of up to !!ω^2!! beans as coins on a quarter-infinite array:

The coin here represents a heap of !!ω·3 + 2!! beans. The heap can be reduced to any smaller number of beans. In the coin version of the game, this corresponds to moving the coin to any square to the left in the same row, or to any square in any lower row.

To extend this past !!ω^2!!, though, was a little clumsy. We had to pile up an infinite stack of these grids, and that got us only to !!ω^3!!. Then to go further we had to move into the fourth dimension, and to get all the way to !!ω^ω!! we had to imagine a sort of discrete Hilbert space with an infinite number of dimensions, not easy. I personally have trouble imagining anything with more than about !!17!! dimensions, and an infinite number of dimensions is a couple more than I can handle comfortably.

We can do better. Instead of imagining a grid of squares with coins on the squares, just write the coordinates of the coin! The one above, representing a pile of !!ω·3+2!! beans, is simply $$⟨2, 3⟩.$$

A game of infinite Nim is now simply a list of these pairs, one for each coin. A legal move is to pick one of the pairs and:

• reduce the first coordinate, which corresponds to moving the coin to the left in the same row, or
• reduce the second coordinate (which moves it to a lower row) and replace the first coordinate with any number at all, even a larger one (any square in the lower row is allowed)

Moving from !!ω·3+2!! to !!ω·3+1!! uses the first rule to reduce the first coordinate from !!⟨2, 3⟩!! to !!⟨1, 3⟩!!. Moving from !!ω·3+2!! to !!ω·2+17!! uses the second rule to reduce the second coordinate from !!⟨2, 3⟩!! to !!⟨2, 2⟩!! and simultaneously replace the first coordinate with !!17!!, leaving the coin on !!⟨17, 2⟩!!.

Removing the entire pile uses the second rule to reduce the second coordinate from !!⟨2, 3⟩!! to !!⟨2, 0⟩!! and simultaneously replace the first coordinate with !!0!!, yielding !!⟨0, 0⟩!!.

To stack up multiple grids no longer requires third dimension, just a third coordinate. To make it compatible with the two-coordinate notation, we just agree to understand !!⟨a, b⟩!! as an abbreviation for !!⟨a, b, 0⟩!!. The move rule generalizes to:

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, 0⟩!! to !!⟨17, 2, 0⟩!! (the !!3!! has decreased), or from !!⟨2, 3, 9⟩!! to !!⟨1000, 0, 7⟩!! (the !!9!! has decreased).

To go into the fourth dimension and beyond is similarly easy: just allow a list of coordinates of any finite length, and use the same rule as above: reduce any single coordinate, and simultaneopusly replace any or all of the coordinates to its left.

For example, !!ω^7 + ω^3·12 + ω^2 + ω + 83!! is now represented as !!⟨83, 1, 1, 12, 0, 0, 0, 1⟩!!. We can also imagine there is a trailing sequence of zeroes, of either finite or infinite length, but they don't affect the game.

Maybe it's easier to see now why this enormous nim-heap must eventually be removed. On the first move, someone must either reduce that !!83!! or else one of the numbers to the right of it. But the players can't indefinitely put off reducing one of the other numbers; if they work only on the !!83!!, then after at most !!83!! they will have arrived at !!⟨{\bf 0}, 1, 1, 12, 0, 0, 0, 1⟩!!, and then someone must reduce one of the other numbers, since moves from !!0!! aren't allowed.

The !!83!! can be increased, but only at the cost of reducing a farther-right number. But that's true of every number except the final !!1!!. And however long the players avoid reducing that final !!1!!, by reducing numbers farther left — and it might be a very, very, very long time — eventually they will get to !!⟨0, 0, 0, 0, 0, 0, 0, 1⟩!! and won't be able to put it off any longer.

To get ordinals up to !!ω^ω!! is straightforward: they correspond directly to finite sequences of numbers, with the moving rule described above: sequence !!A!! represents an ordinal less than sequence !!B!! if one of !!A!!'s elements is less than the corresponding one of !!B!!'s, and the elements to the right are the same.

I hd said at one point that !!ω^ω!! was where the ordinals started to get scary. And perhaps it does seem scary, if you try to think of it as cells in an infinite-dimensional array. But when you think of !!ω^ω!! as just the set of finite sequences of numbers, it's not scary at all!

That was my first big step on the road to !! \epsilon_0 !!, but !! \epsilon_0 !! seems much more daunting. It's not merely !!ω^ω!!, it's actually more like

$$ω^{ω^{ω^{ω^⋰}}}$$

because it's by definition the smallest ordinal !!x!! with the property that !!x = ω^x!!. But the next couple of articles will take us the rest of the way there!

The gold dollar coin in the first illustration started out as an SVG provided by Claude, but underwent signficant transformation at my hands in Inkscape. All other slop in this article is entirely the product of my own natural intelligence.

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