The Universe of Discourse : The road to epsilon-zero: ordinals as nim-heaps

We're going to get to !!{\epsilon_0}!! in a long and roundabout way. First I want to talk about the game of Nim.

Nim

Nim is a very simple game for two players. There are some piles of beans, which are called nim-heaps. When it's your turn, you are allowed to remove as many beans as you like, as long as they are all in the same pile. Whoever takes the last bean wins.

Nim with only one pile of beans is trivial, because whoever goes first can simply take all the beans from the one pile and win. And with two piles it's very simple. But with three or more piles it starts to be a little interesting. Consider the case where there are three nim-heaps, with 1, 2, and 3 beans respectively. The first player can't prevent the second player from taking the last bean.

For a slightly less simple example, consider a game that starts with nim-heaps of size 1, 3, 4, and 8 beans. Here the first player can win, if they might the right opening move. But there's only one winning move! If the first player does anything else, the second player can win.

(Hover for spoiler: The unique winning move is to take two beans from the pile of 8, leaving 6.)

Nim lies at the heart of an important part of the theory of mathematical games. In many games, the two players have different legal moves. For example, in chess the White player is only allowed to move the white pieces, and the Black player is only allowed to move the black pieces. If someone shows you a chessboard and asks you to make a legal move, you can't do it until they tell you whether you're allowed to move the white or the black pieces.

Nim isn't like this. When it's one player's turn, they have exactly the same legal moves as the other player would if it were their turn: take as many beans as they like from one pile.

It transpires that any game where the two players always have exactly the same legal moves can be understood as a disguised version of Nim. We don't have time to explore this surprising fact though, we're hunting !!{\epsilon_0}!!.

Ordinals are nim-heaps

Ordinals can be understood as nim-heaps, and vice versa. Instead of several piles of beans on a table, we have a list of ordinal numbers, one number for each pile. The finite ordinals are simple: !!0!! is an empty heap, which we can ignore. !!1!! is a heap with only one bean, and !!53!! is a heap of !!53!! beans.

Whe a Nim situation is understood as a list of ordinal numbers, the rule that says you can remove beans from any single heap now says you can reduce any single ordinal to a smaller ordinal. Reducing the ordinal !!53!! to !!21!! is analogous to taking enough beans from a pile of !!53!! to leave !!21!!. You're allowed to take all the beans in a single pile. In ordinal number language that says you can reduce any single ordinal to the smaller ordinal !!0!!.

With this understanding, we can interpret infinite ordinals as nim-heaps also. If !!ω!! one of the ordinals, you can reduce it to a smaller ordinal, which must be a finite number because !!ω!! is the smallest infinite ordinal. But it could be any finite number because every finite number is smaller than !!ω!!.

Don't imagine !!ω!! as an infinite heap of beans. That's not right, because if you take 17 beans from an infinite heap, the heap is still infinite, and !!ω!! doesn't work that way. The ordinals less than !!ω!! are all finite, so to reduce the !!ω!! heap, you have to replace it with a finite pile of beans. Picture !!ω!! as a special green token on the table, which can be replaced with a single pile of any number of beans.

Nim still makes sense with green tokens

The game still makes sense even with these crazy green tokens! Imagine playing the game with five heaps, say of sizes !!1, 3, 4, 8,!! and !!ω!!. It turns out that, like before, there is exactly one good move that will allow the first player to win, and if they make any other move, the second player can force the win instead.

The first player should replace the !!ω!! with exactly 14 beans.
If the first player replaces it with more than 14, the second player can win easily by reducing the number to 14, leaving the situation the way the first player should have.
If they replace it with fewer, or if they remove beans from any of the finite piles, the second player can still win, but it's not so simple.

If you find this sort of thing fun, analyzing a few games of Nim-with-tokens will be fun. There are all sorts of interesting patterns. For example: If there are any number of piles of beans, and a single !!ω!! token in a separate pile, the first player can always win, and their winning move will always be to replace the !!ω!! token with the correct number of beans, as in the example. But if there is more than one !!ω!! token, the first player might not have a winning move, and if they do, it might not involve the !!ω!! token. For example, consider the position !!\{1, ω, ω\}!!. Here the first player can win by removing the lone bean from its pile. Do you see why?

Bigger ordinals

Now we have a way to imagine !!ω·2!!: it's just a heap with two green tokens. To make a legal move in this heap, one can replace one of the tokens with any number !!n!! of beans, reducing the ordinal !!ω·2!! to the smaller ordinal !!ω+n!!. Or one can remove a token entirely (that is, replace it with zero beans), reducing the ordinal !!ω·2!! to the smaller ordinal !!ω!!. Or one can remove both tokens, replacing them with any number of beans, even zero, reducing the ordinal to a finite one.

When it's your turn, if you want to move in this heap, you may remove up to three green tokens and up to five beans — any or all. And also, if you remove any green tokens, you may replace them with as many beans as you like, none or five or five billion.

Green tokens and beans are enough to take us almost to !!ω^2!!, but not quite. For !!ω^2!! we need something new. It's a different kind of token, say a square token. When there is a square token in a heap, a player may remove it and replace it with any number of green tokens and beans.

Then we could imagine a cubical token for !!\omega^3!!, which can be removed and replaced with any number of square tokens, green tokens, and beans, and so on, and that gets us almost to !!ω^ω!!.

But there's a simpler way to think about !!ω^ω!!, which I hope to reach in the coming days.