The road to epsilon-zero: Nim always ends, even with infinite ordinals

Summary

The road to epsilon-zero: Nim always ends, even with infinite ordinals Previously: Ordinal numbers and basic set theory Ordinals as nim-heaps 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. 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 ...