The Universe of Discourse

The road to epsilon-zero: Infinite Nim as a coin-moving game

Previously:

1. Ordinal numbers and basic set theory
2. Ordinals as nim-heaps
3. Nim always ends, even with infinite ordinals

In the previous articles I talked about the game of Nim, a very simple game for two players:

• There are some piles of beans
• Players alternate turns
• A legal move is to take any number of beans from one pile
• Whoever takes the last bean wins

I wrote about how Nim could be extended to include certain types of “infinite” piles while still remaining a sensible game. This involved introducing green tokens that could be replaced with any number of beans, then square tokens that could be replaced with any number of green tokens and beans, and so on.

Rather than think about an infinite family of different kinds of tokens, there's a simple way to make them all the same sort of thing.

Imagine a game where the board is a track of squares, extending to the right (and to the right only) as far as needed. Let's number the squares: the leftmost one is !!0!!, then !!1, 2, 3, \dots!! and so on.

On some of the squares are coins. In this game, a player's legal moves are to take one coin and move it some number of squares to the left. Coins don't interfere with one another; any number of coins may occupy a single space. As in Nim, the player who is able to make the last legal move wins. In Nim that means taking the last bean; in this game it means moving the last coin to the !!0!! square.

This game is nothing but Nim, in a different form. A Nim game with piles of !!2, 2, 3, 5, !! and !!6!! beans is exactly equivalent to the strip game, with coins on squares !!2, 2, 3, 5, !! and !!6!!.

Removing four beans from a pile is isomorphic to moving a coin four squares leftward.

A coin on square zero behaves like an empty pile of beans — no further moves are possible for that coin / pile, and it has no further effect on the game.

In Nim, we represented !!ω!! with a green token that could be replaced with any number of beans:

In the strip game, we don't need special tokens. We represent !!ω!! by adding a second strip, atop the first:

and the rule that a coin in the upper strip can be moved to the left or to any space in the lower strip:

The picture above shows how to take all but six beans from a pile of !!ω+3!!.

Adding more strips gets us easily almost to !!ω²!!:

The coin here represents a pile of !!ω·3 + 2!! beans.

If we were to stack a second grid on top of this one, and then add the rule that a coin in the upper grid can be moved to any square in the lower grid, then the lower-leftmost square in the upper grid would be equivalent to a pile of !!ω^2!! beans, and the other squares in the upper grid would be variouls ordinals of the form !!ω^2 + ω·b + c!!. Adding a third grid would get us up to !!ω^2·2 + ω·b + c!!, and a whole infinite stack of grids would get us an infinite cube that would almost take us to !!ω^3!!.

We could then build an infinite four-dimensional stack of cubes to get to !!ω^3!! and beyond, and so on to infinite dimensions, and that's the construction I had in mind when I said !!ω^ω!! was where the ordinals start to get scary. But there's an easier way to proceed, which we'll see in the next article.

Claude generated the green poker chip image. I used Inkscape to transform its original chip illustration into the two kinds of coins. Everything else in this article, including the em-dash, was entirely human-generated. These disclosures are ridiculous

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