Fri, 21 Aug 2026
The road to epsilon-zero: Shortlex order also orders sequences of numbers
Previously:
- Ordinal numbers and basic set theory
- Ordinals as nim-heaps
- Nim always ends, even with infinite ordinals
- Infinite Nim as a coin-moving game
- Coin-moving games with no coins
- 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:
- Pick any nonzero coordinate
- Reduce it by at least 1
- 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:
- If the sequences are different lengths, the shorter one comes first.
- 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:
- Instead of beans, we think of a heap as a finite sequence of finite numbers
- 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.
[Other articles in category /math/ordinals] permanent link
Thu, 13 Aug 2026
The road to epsilon-zero: Productive programs and well-founded orders
Previously:
- Ordinal numbers and basic set theory
- Ordinals as nim-heaps
- Nim always ends, even with infinite ordinals
- Infinite Nim as a coin-moving game
- Coin-moving games without the coins
Previously we saw how to interpret the difficult-seeming ordinal !!ω^ω!! as a particular ordering of the set of finite sequences of numbers, revealing what seemed like a scary monster as gentle and straightforward.
Now we're going to take a sidetrack into one of my favorite topics, computation with infinite lists. I wrote about this for The Perl Journal in 1997 and then it turned into chapter 6 of Higher-Order Perl and here we are again. Gosh! it just keeps coming back. Like John the Baptist.
Infinite lists
Suppose you have an infinite set of strings — we'll call this set !!S!! for the rest of the article — and you want a program to print them all out. Of course the program can't exactly print them all out, because it will only run for a finite amount of time. But there are more and less useful ways for the program to try.
For each string that the program is supposed to print, we should at least be able to guarantee that the the program will print it, eventually, if we just wait long enough. If this is true then we'll say that the program is “productive”.
Here's a productive program to print the base-10 numerals for all the positive integers:
# Python
i = 1
while True:
print(i)
i += 1
What would a non-productive program look like? Here's an example of a non-productive program to print the base-10 numerals for all the positive integers:
# Python, silly
i = 1
while True: # print all the odd numbers
print(i)
i += 2
i = 2
while True: # then print all the even numbers
print(i)
i += 2
This one tries to print all the odd numbers first, and then all the even numbers. Obviously that doesn't work because it never finishes with the odd numbers. If you were to sit around waiting for the number !!14!!, you'd wait forever. Whereas with the first program, whatever number you are waiting for, even if it is very very big, it will come out eventually.
That's what I meant when I said there are more and less useful ways for a program to try to print an infinite set. The first one never finishes, true, but the way in which it never finishes is much more useful than the way in which the second one never finishes.
Okay, that was a silly example. But there are less silly examples.
Printing strings in sorted order
A productive program is always semidecidable: if a user wants to know if some particular string !!s!! is in !!S!!, and they wait long enough, !!s!! will come out and they have the answer. But if !!s!! isn't in !!S!!, they never find that out! They just wait and wait, wondering if it will come out, and never getting a definitive answer.
If we can get a productive program to produce its strings in sorted order, we can make a better guarantee. The program will be decidable: the user will eventually get an answer, one way or the other. If !!s\in S!! the productive program will eventually produce !!s!!, and the user can stop watching. But if !!s\notin S!!, the program must eventually produce a string that comes after !!s!! in sorted order, and they can quit then. And the program must eventually produce some string that comes after !!s!!, because, being productive, it eventually produces every string in !!S!!.
(What if there is no string in !!S!! that comes after !!s!! in sorted order? Then the productive program will first produce all the strings that precede !!s!!, then it will produce !!s!!, and then it will halt. When it does that user has their answer, whatever it is.)
Not every program is productive
The non-productive program I showed above is silly, but productivity isn't something you can always guarantee, if you want the data in sorted order. Some orders work, and some don't.
The conventional order for strings, implemented by Python's
< operator or C's strcmp, is called lexicographic, which means
“dictionary-style”. There are some sets of strings for which
no productive program can print all the strings in lexicographic order.
For example, consider the set of all strings that are made up of
either all as or all bs:
a
b
aa
bb
aaa
bbb
aaaa
bbbb
…
Notice that this list is not in lexicographic order, because in
lexicographic order, the string aa should come out before b.
There is no productive program to print this set in lexicographic order. Why not? Because in lexicographic order the list begins like this:
a
aa
aaa
aaaa
aaaaa
…
and the program never gets around to printing any of the strings with
bs. This is analogous to how the non-productive example earlier waited to
print even numbers until after it was finished with the odd numbers.
To print these strings in lexicographic order would meansto print the
strings beginning with b after printing the strings
beginning with a. But the program never does finish with the strings
beginning with a. The program is supposed to produce bbb, but it
never does, no matter how the user waits. And it's supposed to reach
a point where the user can be sure that banana will not come out,
but it never does that either, it keeps printing as and never prints
a string like bbb that comes after banana in lexicographic order.
The problems with lexicographic order are even worse than this example shows. Consider this set of strings:
b
ab
aab
aaab
aaaab
aaaaab
…
Notice again: not lexicographic order, because b should come out last, not first.
But what should come first? A program to print these strings in lexicographic order
can't even get started, because in lexicographic order, this list of strings doesn't have
a first element! The program can't print out b first because all
the a strings were supposed to come out before that. And it can't
print out ab first because aab was supposed to come out before
that. And it can't print out aaaaaaaaab because aaaaaaaaaaaaaaab
was supposed to come out before that. Whatever string the program
tries to print out first, it will have made a mistake!
If you're trying to print out an ordered, infinite list of strings, lexicographic order just won't do.
Lexicographic order isn't well-founded
In an earlier article in this series we talked about “well-founded” orders. In a well-founded order, every set of items has a first item, if it has any at all. Writing a productive program for a well-founded order is easy:
- Repeat forever:
Question: Are there any items left to print?
No: Halt
Yes:- Let !!P!! be the set of unprinted items
- Let !!s!! be the first item in !!P!!
(There must be one, because we're printing the items in a well-founded order) - Print !!s!!
As we saw, the conventional lexicographic order is not well-founded for strings. Some sets simply don't have a lexicographically first element.
So in circumstances where we might be handling infinite data streams, we often prefer a different string ordering, almost as simple and considerably better-behaved.
Shortlex order
You already know this one, although perhaps not by that name. It's
nothing more than the order we use for regular numerals like 723.
It's not lexicographic, because as you've probably noticed, in
lexicographic order, 10 comes before 2. Here's the track listing
of my copy of Quadrophenia, as listed by the Unix ls program:
1 I am the sea.mp3
10 I've had enough.mp3
11 515.mp3
12 Sea And Sand.mp3
13 Drowned.mp3
14 Bell Boy.mp3
15 Doctor Jimmy.mp3
16 The Rock.mp3
17 Love Reign O'er Me.mp3
2 The real me.mp3
3 Quadrophenia.mp3
4 Cut my hair.mp3
5 The punk and the godfather.mp3
6 I'm one.mp3
7 The dirty jobs.mp3
8 Helpless dancer.mp3
9 Is it in my head.mp3
Hey, wait, why did ls put track 17 ahead of track 2? Because ls
lists files in lexicographic order, and in lexicographic order, 17 comes
ahead of 2 for the same reason that agony and the other ag-
words come before bony and the other b- words in the dictionary:
1 comes before 2 just as a comes before b.
If you name your files after numbers, then when the computer lists them in lexicographic order, they won't be in numeric order. Numeric order isn't lexicographic. But numerals, in shortlex order are in numeric order, and of course it's trivial to print all possible numerals in numeric order.
The rule to compare two strings in shortlex order is:
- If the strings are different lengths, the shorter one comes first.
- If they're the same length, compare them lexicographically.
Compare the shortness first, and use lexicographic comparison as a tiebreaker. Hence “short” + “lex”.
Consider what this means for numerals. Here's a list of binary numerals from !!0!! to !!15!!:
0
1
10
100
1000
1001
101
1010
1011
11
110
1100
1101
111
1110
1111
It looks strange because it's in lexicographic order — all the numerals that begin with 10
appear before all those beginning with 11, which means that 1000
comes before 11, even though (checking my notes) !!3 \lt 8!!.
If we want to print all binary numerals in lexicographic order, we're out of luck. The list starts like this:
0
1
10
100
1000
…
and we never get to printing any of the numerals starting with 11,
including 11 itself.
In shortlex order, it's what we expect. We get the numeral for every number, and in numeric order:
0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
…
Unlike lexicographic order, the shortlex order is well-founded. Remember that “well-founded” means that every set of strings has a first element. But in lexicographic order, this set of binary numerals has no first element:
11
101
1001
10001
100001
…
In shortlex order there's no problem. There can't be, because shortlex order is numeric order, and if numeric order wasn't well-founded there wouldn't be a productive program to print all the numerals in order, which of course there is.
The infinite lists that we couldn't put into lexicographic order before give us no trouble in shortlex order. In fact, I listed both in shortlex order already:
a b
b ab
aa aab
bb aaab
aaa aaaab
bbb aaaaab
… …
For strings, shortlex order is well-founded, which means that every set of strings contains a first element. Here's why: Consider some set !!S!! and some string !!s\in S!!. The string !!s!! has a length !!\ell!!. Consider the set !!E!! of strings that come before !!s!!. The set !!E!! must be finite because every string that comes before !!s!! in shortlex order has length less than or equal to !!\ell!!, and there are only a finite number of such strings.
If !!E!! is empty, then !!s!! itself is the first string in !!S!!. If !!E!! is not empty, then, being finite, it must have a first element. (Just sort !!E!!.) This first element is the first string in !!S!!. Done.
Wait, why are there are only a finite number of strings with length less than or equal to !!\ell!!? Well, there are only a finite number of strings of length !!0!!. (There's only one.) And there are only a finite number of strings of length !!1!!: If the character set contains !!n!! symbols, there are only !!n!! with length !!1!!. Similarly there are only !!n^2!! strings of length !!2!!, and so on. Since there are only a finite number with each length up to !!\ell!!, we just add up this finite list of finite numbers and the sum is finite. And since every string in !!E!! has length no more than !!\ell!!, the number of strings in !!E!! is at most this finite number.
Coming next: Shortlex order also orders sequences of numbers.
[Other articles in category /math/ordinals] permanent link
Wed, 05 Aug 2026
The road to epsilon-zero: Coin-moving games with no coins
Previously:
- Ordinal numbers and basic set theory
- Ordinals as nim-heaps
- Nim always ends, even with infinite ordinals
- 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:
- Pick any nonzero coordinate
- Reduce it by at least 1
- 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!
Coming next:
- You can write a program to print an infinite list of strings, but you can't always write one to print them in alphabetic order: Productive programs and well-founded orders
- Shortlex order also orders sequences of numbers
[Other articles in category /math/ordinals] permanent link
Wed, 29 Jul 2026
The road to epsilon-zero: Infinite Nim as a coin-moving game
Previously:
- Ordinal numbers and basic set theory
- Ordinals as nim-heaps
- 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.
Coming next:
And then:
[Other articles in category /math/ordinals] permanent link
Sun, 19 Jul 2026
The road to epsilon-zero: Nim always ends, even with infinite ordinals
Previously:
[Yesterday][prev-2] 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.
At first it might seem that Nim with !!ω!!-tokens could go on forever. Not so!
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.
He said “I don't know, I have to think about it.”
His boss, being a reasonable woman, asked him when he would be able to tell her.
Again he said “I don't know, I have to think about it.”
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.
“Not more than two days,” he said at once.
“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?”
“That's right.”
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.
Coming next:
And then:
- Coin-moving games without the coins
- Productive programs and well-founded orders
- Shortlex order also orders sequences of numbers
[Other articles in category /math/ordinals] permanent link
Sat, 18 Jul 2026
The road to epsilon-zero: ordinals as nim-heaps
Previously:
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.
Spoiler:
- 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.
!!ω·3+5!! is a heap with three green tokens and five beans:
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.
Coming next: Every game of Nim, even with the wildest craziest infinite tokens, must end after a finite number of moves!
And after that:
- Infinite Nim as a coin-moving game
- Coin-moving games without the coins
- Productive programs and well-founded orders
- Shortlex order also orders sequences of numbers
[Other articles in category /math/ordinals] permanent link