The Universe of Discourse : The road to epsilon-zero: ordinals as nim-heaps
The Universe of Discourse
Mark Dominus (陶敏修)
mjd@pobox.com
About me
RSS<br>Atom
12 recent entries
The road to epsilon-zero: Nim always ends, even with infinite ordinals<br>The road to epsilon-zero: ordinals as nim-heaps<br>Starting to understand epsilon-zero<br>It's our language now!<br>I owe my life to a 1913 road rage incident<br>Deciphering basmala<br>My 1992 view of the problems of computer programming in 1992<br>Egyptian fraction multiplication<br>Update: Here I am at the Sagrada Família<br>Egyptian fractions for 2/105<br>Did Ahmes find the best expansions for 2/n?<br>Programmers will document for Claude, but not for each other
Archive:
2026:<br>JFMAMJ<br>2025:<br>JFMAMJ<br>JASOND<br>2024:<br>JFMAMJ<br>JASOND<br>2023:<br>JFMAMJ<br>JASOND<br>2022:<br>JFMAMJ<br>JASOND<br>2021:<br>JFMAMJ<br>JASOND<br>2020:<br>JFMAMJ<br>JASOND<br>2019:<br>JFMAMJ<br>JASOND<br>2018:<br>JFMAMJ<br>JASOND<br>2017:<br>JFMAMJ<br>JASOND<br>2016:<br>JFMAMJ<br>JASOND<br>2015:<br>JFMAMJ JASOND<br>2014:<br>JFMAMJ JASOND<br>2013:<br>JFMAMJ JASOND<br>2012:<br>JFMAMJ<br>JASOND<br>2011:<br>JFMAMJ<br>JASOND<br>2010:<br>JFMAMJ<br>JASOND<br>2009:<br>JFMAMJ<br>JASOND<br>2008:<br>JFMAMJ<br>JASOND<br>2007:<br>JFMAMJ<br>JASOND<br>2006:<br>JFMAMJ<br>JASOND<br>2005: OND
Subtopics:
Mathematics251<br>Programming102<br>Language97<br>Miscellaneous75<br>Book50<br>Tech49<br>Etymology36<br>Haskell33<br>Oops30<br>Unix27<br>Cosmic Call25<br>Math SE25<br>Law23<br>Physics21<br>Perl17<br>Biology16<br>Brain15<br>Calendar15<br>Food15
-->
-->
Technorati Profile<br>-->
Comments disabled
Sat, 18 Jul 2026
The road to epsilon-zero: ordinals as nim-heaps
Previously:
Ordinal numbers and basic set theory
We're going to get to !!{\epsilon_0}!! in a long and roundabout way. First I<br>want to talk about the game of Nim.
Nim
Nim is a very simple game for two players. There are some<br>piles of beans, which are called nim-heaps . When it's your turn,<br>you are allowed to remove as many beans as you like, as long as they<br>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<br>can simply take all the beans from the one pile and win. And with two<br>piles it's very simple. But with three or more piles it starts to be<br>a little interesting. Consider the case where there are three nim-heaps, with<br>1, 2, and 3 beans respectively. The first player can't prevent the<br>second player from taking the last bean.
For a slightly less simple example, consider a game that starts with<br>nim-heaps of size 1, 3, 4, and 8 beans. Here the first player can<br>win, if they might the right opening move. But there's only one<br>winning move! If the first player does anything else, the second<br>player can win.
(Hover for spoiler: The unique winning move is<br>to take two beans from the pile of 8, leaving 6.)
Nim lies at the heart of an important part of the theory of<br>mathematical games. In many games, the two players have different<br>legal moves. For example, in chess the White player is only allowed<br>to move the white pieces, and the Black player is only allowed to move<br>the black pieces. If someone shows you a chessboard and asks you to<br>make a legal move, you can't do it until they tell you whether you're<br>allowed to move the white or the black pieces.
Nim isn't like this. When it's one player's turn, they have exactly<br>the same legal moves as the other player would if it were their turn:<br>take as many beans as they like from one pile.
It transpires that any game where the two players always have<br>exactly the same legal moves can be understood as a disguised version<br>of Nim. We don't have time to explore this surprising fact though,<br>we're hunting !!{\epsilon_0}!!.
Ordinals are nim-heaps
Ordinals can be understood as nim-heaps, and vice versa. Instead of<br>several piles of beans on a table, we have a list of ordinal numbers,<br>one number for each pile. The finite ordinals are simple: !!0!! is an<br>empty heap, which we can ignore. !!1!! is a heap with only one bean,<br>and !!53!! is a heap of !!53!! beans.
Whe a Nim situation is understood as a list of ordinal numbers, the<br>rule that says you can remove beans from any single heap now says you<br>can reduce any single ordinal to a smaller ordinal. Reducing the<br>ordinal !!53!! to !!21!! is analogous to taking enough beans from a pile of<br>!!53!! to leave !!21!!. You're allowed to take all the beans in a<br>single pile. In ordinal number language that says you can reduce any<br>single ordinal to the smaller ordinal !!0!!.
With this understanding, we can interpret infinite ordinals as<br>nim-heaps also. If !!ω!! one of the ordinals, you can reduce it to a<br>smaller ordinal, which must be a finite number because !!ω!! is the<br>smallest infinite ordinal. But it could be any finite number<br>because every finite number is smaller than !!ω!!.
Don't imagine !!ω!! as an infinite heap of beans. That's not right,<br>because if you take 17 beans from an infinite heap, the heap is still<br>infinite, and !!ω!! doesn't work that way. The ordinals less than<br>!!ω!! are all finite, so to reduce the !!ω!! heap, you have to<br>replace it with a finite pile of beans. Picture !!ω!! as a special green<br>token on the table, which can...