The Universe of Discourse: category 'math/ordinals'

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:

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:

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.

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

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:

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.

Yesterday I talked about the game of Nim, which involves two players taking beans from several piles, and an extension that includes green tokens that behave a bit like infinite piles:

When there's a pile with one or more green tokens, it's legal for a player to remove any or all of them, and then to add any number of beans to the pile.

If someone gives you a Nim position where all the piles contain beans, you can say ahead of time how long the game might last. A game starting with nim-heaps of size !!\{1, 3, 4, 8\}!! simply can't last more than 16 turns, because each turn removes at least one bean from a pile, and the game ends when someone takes the last bean.

If the game starts with nim-heaps of size !!\{1, 3, 4, 8, \omega\}!!, you can't know how long it might last. If you guess it will be over in !!1,\!000!! turns, the first player might prove you wrong by replacing the !!\omega!!-token with a pile of !!10,\!000!! beans, and then the game might last up to !!10,\!016!! more turns.

If you guessed at the start that the game would last no more than !!10,\!016!! turns, one of the players might replace the token with a pile of !!1,\!000,\!000,\!000,\!000,\!000,\!000!! beans, or even more. Before the first move, there is no bound that can be placed on how long the game will take to finish.

But what you can say about !!\{1, 3, 4, 8, \omega\}!! is that after at most !!17!! moves, someone will have removed the !!ω!!-token and replaced it with some finite number of beans. And that that point you'll be able to say when the game will end.

!!ω·2!!

Similarly, suppose there is are piles !!\{1, 3, 4, 8, \omega·2\}!!. Remember that !!\omega·2!! is simply a stack of two green tokens. What's the longest this game could last?

As before, we can't say. But we can say that after at most !!17!! turns, at least one of the !!ω!! tokens will have been removed, and there will be at most one !!ω!! token and a possibly very large number of beans, say !!b_1!!. And then after at most !!b_1+1!! more moves, the last !!ω!! token will have been taken if it wasn't before, and only beans will be left, possibly a very large number of beans, say !!b_2!!.

And at that point we will be certain that the game can't last more than !!b_2!! more moves.

So with !!\{1, 3, 4, 8, \omega·2\}!! we can't say how long the game will take to finish.

And we can't say when we will be able to say how long the game will take to finish.

But we can say that in at most !!17!! moves, we will be able to say, not how long the game will take to finish, but how long it will be before we can say how long the game will take to finish.

Estimating programming tasks

This reminds me of a story I once heard from another programmer. He told me his boss had come to him to ask him if he could fix a certain bug. He had replied that he could, and the boss had asked him how long he thought it would take.

His boss, being a reasonable woman, asked him when he would be able to tell her.

The boss, having dealt with this guy before, did not lose her temper. Instead, she asked how long it would take him to figure that out.

“Okay,” she said. “Just to make sure there is no miscommunication, are you telling me that in two days you may not be able to estimate the task, but you will be able to tell me when the estimate will be ready?”

And they parted amicably, both parties satsified, at least for the time. Communication between management and engineering doesn't always turn out so well!

My friend was apaprently playing the game !!ω·2+1!!. There was only one bean, so one of the !!ω!! tokens would have to have gone by the second day. At that point there would remain !!ω + n!! for some finite number !!n!!, and although my friend wouldn't be able to say at that point how long the game would last, he would know that he would be able to deliver the estimate after at most !!n+1!! more days.

The game must end!

With !!ω·2+1!! we don't know when the game will end, or how long it will be before we know when the game will end.

But we do know that in at most two moves we will know how long it will be before we know how long it will be before the game ends, and that means that we do know that that game will end even though we're quite far away from saying when that will happen.

The argument is always the same: there are only a finite number of beans, and even if both players try to avoid the tokens, the beans will eventually run out and someone will be forced to replace a green token with more beans. Then those beans will run out and someone will be forced to take another token, and so on, until all the tokens are gone, and then when the beans run out the game is over.

Of course, both tokens and beans might go faster than that. But go they will, however slowly and even if only one at a time.

And this is true no matter how many green !!ω!! tokens there are to begin with.

And the same holds true if there are any square !!ω^2!! tokens. Even if the players avoid the square tokens, at some point all the beans and green !!ω!! tokens will be used up and someone will have to replace at least one square !!ω^2!! token with more beans and green tokens, and then those will be used up… and eventually the last square !!ω^2!! token will be gone, and then we're back to the !!ω·n+m!! case of the previous paragraph and the game must end.

But at that point we have defeated English descriptions. We have piled up an infinite sequence of “how long before we can say”s into “We can't say how long before we can say … how long before the game ends”.

Bizarre! And yet we know that even these games must end, although English isn't powerful enough to say how long it will take, or even how long before we will be able to say how long it will take.

Ordinals are well-founded

An ordinal is a set of smaller ordinals. Every move in Nim makes an ordinal smaller. If you keep making numbers smaller you eventually reach 0, and then the game is over.

This property of ordinals is called well-foundedness. We say that ordinals are well-founded.

Note that this that this is a special property of ordinals, not shared by all types of numbers. For example, the positive rational numbers do not have this property. From !!1!! you can go down to the smaller !!\frac12!!, then to the smaller !!\frac13!!, and so on, downward, always downward to smaller and smaller numbers, but never reaching zero. A game of Nim where the beans can be divided into infinitely small crumbs might never end. But a game of Nim with ordinals always ends, because the ordinals are well-founded. You can go up and up forever to crazier and crazier infinite ordinals, but no matter how far up you go, you can't go down and down forever, you must bottom out at zero after a finite time.

Well-founded orderings are the the theoretical backbone of recursive programs. When we write a recursive function, we want to be certain that it will terminate. And that means that if a function calls itself with a different argument, the new argument must smaller than it was. Maybe “smaller” mans numerically less. But it could mean many other things. If the function is processing a directory tree, “smaller” could mean “fewer levels deep”. If the function is sorting a list, “smaller” could mean “fewer items are out of order”. The essence of recursion is that the shrinking cannot continue forever. The function will eventually reach the number zero, or the directory that contains only files, or the list with no unsorted elements, and then it will be done.

In the next article we will see a way to understand infinite nim-heaps in a more uniform way than as a hodgepodge of variously shaped and colored tokens.

Claude generated the green poker chip image. Everything else in this article was written entirely by me.

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.

Claude generated the green poker chip image. Then I asked it to produce an image of a stack of three chips, plus five beans. I wasn't happy with the result, so I used Inkscape to transform its original chip illustration into a stack, and then copied over Claude's beans. Everything else in this article, including the em-dash, was entirely human-generated.