Every play ends and no round settles

Three rungs below, finite appears in the statement of the theorem and reads like a technicality. Two rungs below, it turns out to be the whole load-bearing member, and the way that is shown is by adding a cycle: a position play can return to, a recursion with nowhere to bottom out, and a set of positions the labelling never reaches.

That is one way to break finiteness and it is not the interesting one, because it breaks something else at the same time. A game with a cycle has plays that never end, and once plays can fail to end there are drawn positions and a fourth possibility and a whole separate theory. The cycle is doing two jobs and the two are easy to confuse.

Here is a game with no cycle, every play of which ends, nothing drawn anywhere — and the labelling still does not settle.

The game #

One move, and it is a choice of how long the game will be.

Black’s first move picks a run of any odd length. A run is a forced sequence: one move available at each step, nothing to decide, and after the last of them the mover has nothing and loses.

That is the whole rule set. There are infinitely many opening moves, because there are infinitely many odd numbers, and every one of them leads to a game that is over in a stated number of moves.

Nothing about it is exotic. It is finite in every sense a player would recognise: every game ends, every game ends quickly, and a spectator watching one would never suspect anything. The only thing wrong with it is that the list of openings has no end, and a list with no end is what finite was quantifying over.

Why the opening is a loss, and why that matters #

The opening’s verdict is easy: a run of odd length is a win for whoever is at its head, since it lasts an odd number of moves and the last one belongs to the mover. So every opening Black may play hands White a won position, and the opening is a loss for Black.

That is the load-bearing half. Recall the two rules of the labelling:

A win settles as soon as one option comes back a loss. One is enough.

A loss settles only when the last of its options is known. Every one of them must be in hand.

The opening is a loss, so it settles by the second rule, so it settles only when every run has been settled — and there are infinitely many runs.

Had the opening been a win, none of this would arise. A win needs one witness; a single losing option settles it; and an infinite menu with one good item on it is answered by pointing at the item. The trouble is not infinitely many options. It is infinitely many options every one of which has to be checked.

The rounds, and what they do #

Cut the menu off at some size and the game becomes finite and ordinary. The longest run on offer is some odd number, that run settles in as many rounds as it has moves, and the opening settles one round after the last of them.

Cut at one and the opening settles in round two. At three, round four. At five, round six; at seven, round eight; at eleven, round twelve; at fifteen, round sixteen. The positions go three, six, eleven, eighteen, thirty-eight, sixty-six, and the round goes with them.

No entry in that column is the answer for the uncut game, because for every entry there is a longer run whose settling comes after it. The sequence has no last term and the round has no value, and the labelling that produced the sequence has no way to say so.

Each cut is drawn as its own complete labelling with nothing left over: no drawn positions, no unreached pairs, no residue of any kind. The thing that fails is not the labelling’s coverage. It is that there is no round number to be the answer, and a procedure that counts rounds has nothing to hand back.

What the two computations agree about #

The identity the rung two below establishes — that the round a position settles in is the number of moves the game lasts from it — is checked again on every cut here, and it is checked because it is what makes the growing column mean something.

If the rounds were bookkeeping, a column of rounds growing with the cut would be a statement about the algorithm and could be answered by a better algorithm. Because the round is the length of the play, the column is a statement about the game: the opening’s number is one more than the longest run on offer, and the longest run on offer is what the cut is choosing.

So a reader can read the third column two ways and get the same warning. As rounds, it says the procedure takes longer at every cut. As lengths, it says the longest game gets longer at every cut, which is obviously true and obviously has no limit — and the two readings being the same number is why the first has no limit either.

What the induction needs instead #

The repair is not a cleverer procedure. It is a different kind of counter.

Round numbers are natural numbers, and the sequence above is a sequence of natural numbers with no upper bound. What the opening needs is a rank that comes after all of them — one more step past every finite stage — and the first such object is the ordinal ω.

That is the whole of what a transfinite induction buys. Instead of settle everything at round zero, then round one, then round two until the rounds run out, an ordinal-indexed induction says: settle everything of rank less than α before settling anything of rank α, for every ordinal α, including the ones with no predecessor. The opening has rank ω, its options have finite ranks, and the induction reaches it because ω is allowed to come after them all.

Zermelo’s own later work is about exactly that machinery, which is a fact the rung three below records in passing and is worth reading as more than biography. The 1913 paper needs the game finite; the well-ordering it would take to do without finiteness is a considerably heavier assumption; and the same person is responsible for both. It is also why the correction to the 1913 paper took two decades and two mathematicians: the tools that make the infinite case work were being built at the same time as the objection to it.

What it does not need, and this is the part that is easy to get wrong #

A reader who has met the loopy field will expect the infinite case to bring draws with it, and it does not.

Every play of this game ends. Pick a run, walk it, and the game is over in a stated number of moves. There is no line of play that goes on for ever, no position anybody can return to, and no cycle in the graph at any cut. The figures report zero drawn positions at every size and the count is asserted rather than observed.

So the fourth outcome class has nothing to do with the difficulty here, and the two ways of breaking finiteness are genuinely separate:

A cycle gives plays that never end, drawn positions, and a labelling with a residue — which written as an equation is a second solution rather than an algorithmic shortfall. Every play is finite here and there is no residue.

Infinitely many positions gives plays that all end and a rank with no finite bound. The graph is a tree, the tree is well-founded, and the counter is what runs out rather than the game.

That distinction is the same one the termination field draws between two ways to end with no bound: a game may be guaranteed to end without there being any number of moves it is guaranteed to end within, and that is a different condition from being able to go on for ever. The condition the recursion rests on is well-foundedness rather than boundedness, and this game satisfies the first and not the second — which is precisely the gap between what a value needs and what a procedure needs.

Why the site’s own machinery hides this #

Every impartial game this site computes has an unbounded version and every figure quietly draws the bounded one, which is worth admitting rather than leaving as an implementation detail.

A Grundy sequence is computed to a stated heap; a subtraction game’s table runs to a stated size; a census enumerates positions up to a stated length. In each case the game as stated by its rules has infinitely many positions, and what is evaluated is a cut of it.

That is almost always harmless, and the reason is the one this page is about: those games’ openings are wins far more often than losses, and where they are losses the option set is finite. A Nim heap of n has n options, not infinitely many; a subtraction game’s heap has as many options as the subtraction set. The infinite branching is at the top of the tree and nowhere else, and the top of the tree is where nobody starts.

The exception is exactly the shape drawn here: a position whose options are all the positions of a family. That is what a general statement about a family looks like when it is turned into a move, and it is why an essay can compute the whole of a game and still be computing a cut.

The bound question, one rung down, was this #

The rung two below is about Zermelo’s actual question — how many moves does a forced win take — and about the bound he needed and the argument that was wrong.

This is where the bound question has no answer at all, and it is worth setting the two side by side.

On a finite graph, the bound exists and Zermelo’s argument for it is loose: the number of positions works and is astronomically larger than the truth. On this game, the bound does not exist. Every position has a finite win, no single number covers them all, and the statement there is a number of moves within which the winner can always collect is false.

That is the quantifier the rung below flags as a trap, failing in the wild. For each position, some bound is true here. Some bound, for every position is false. That is the same swap the complexity field measures difficulty by when it counts how many times two quantifiers exchange places, and it costs the same thing here that it costs there. On a finite graph the two coincide because a finite set has a maximum, and taking that maximum is the step Zermelo’s paper does not properly make.

And it is why König’s lemma is the right tool. The lemma says an infinite tree with finite branching has an infinite path — so a tree whose plays are all finite and whose branching is finite must itself be finite, and the bound follows. The game here has infinite branching at exactly one node, which is the smallest possible violation of the lemma’s hypothesis, and it is enough.

Where such games actually occur #

A game whose first move picks a number looks contrived and is not.

A Nim heap of unbounded size is one: the position some heap, size unspecified has a move to every finite heap, and the same argument applies with the runs replaced by heaps. This site’s own machinery computes Grundy sequences for heaps up to some limit and quietly assumes the limit; the game with no limit is a game with a position of rank ω.

Any game with an unbounded opening choice is another — pick a board size, pick a number of counters, pick how many rounds to play — and rule sets of that shape are written all the time, usually without anybody noticing that the resulting object is not the kind of thing the theorems cover. Sylver Coinage is the one on this site: its first move names an integer, any integer, and the game is guaranteed to end by a theorem of Sylvester’s from 1884 rather than by anything a bound could say.

And the surreal numbers themselves are built from games with infinitely many options: ω is the game whose Left options are all the finite numbers, which is the same construction as the opening here with the outcome question replaced by a value question. The recursion this site cannot run is where that construction is met from the other side, and the obstacle there is the same one: a definition that quantifies over an infinite set of previously built objects.

So the boundary is not exotic. It is one clause away from the games in front of everybody, and the clause is how many moves does the first player choose between.

What the picture cannot show #

The uncut game is not drawn, because it cannot be. Every figure here is a cut, and the cuts are what a page can hold. What they establish is the growth, and the growth is what says no finite answer exists — but a reader wanting to see the game itself is asking for a picture with infinitely many nodes in it.

Nor does anything here construct the ordinal. ω is named and not built; what is built is a sequence of finite ranks with no upper bound, which is the evidence that something past them is needed. The construction of the ordinals is set theory and is one of the two subjects this page sits between.

And the game is chosen to be as simple as possible. One node with infinite branching, and everything below it a forced march with no decisions in it. A game with infinite branching in several places, or infinite branching below infinite branching, needs ranks past ω and the ordinals go on for a long time; nothing here goes further than the first step.

The convention, named #

Normal play, and it is doing something specific: the run’s last position is a position with no move, which is the base case, which is what makes every run settle at all.

Under misère play the base case inverts and every run of odd length becomes a loss for whoever is at its head — so every opening hands White a lost position, so the opening becomes a win for Black, and a win settles as soon as one option is known.

The opening’s rank is then one rather than ω, and the whole difficulty evaporates.

That is worth more than a footnote, because it says the difficulty is not a property of the game. It is a property of the game and the convention together: the same graph, the same infinite branching, and a rank of ω under one reading and one under the other. What produces the rank is the interaction between an infinite menu and a rule that requires every item on it to be checked, and which rule does that depends on which convention is in force.

The surprise: nothing is wrong with the game #

The expected shape of a counterexample to a finiteness theorem is a game that misbehaves — one that goes on for ever, or has a position nobody can evaluate, or produces an answer that is not one of the four outcome classes.

This game does none of that. Every play ends. Every play is short. Every position is decided. Nothing is drawn. There is no cycle, no residue, no fourth possibility, no ambiguity about who wins anything. A player could sit down and play it, and would never notice.

What is unavailable is the procedure, and only the procedure. The answer exists at every position; the round-by-round method for finding it does not terminate; and the difference between those two sentences is the entire content of the finiteness hypothesis.

That is worth carrying as a general warning about hypotheses of this kind. Finite in a theorem is almost never a claim that the object is well-behaved — the object here is impeccably behaved — it is a claim that a method applies. And the way to find out what such a hypothesis is protecting is not to look for an object that misbehaves, but to look for one that behaves perfectly and defeats the method anyway.

Where the ladder goes next #

determinacy has four rungs now: the theorem, the length it was scaffolding for, where a draw comes from, and what happens when the positions do not run out.

The rung above is the one this page stops at the edge of. Every game here is open in the topological sense — a win is decided at a finite stage, by somebody being stuck — and Gale and Stewart’s 1953 theorem says every such game is determined however infinite it is. The theorem needs a genuinely infinite play to be interesting, and past its hypothesis the answer changes character entirely: with the axiom of choice in hand, a game exists that neither player can force and that no procedure could ever label. That is a rung about what determinacy costs once the plays themselves are infinite, and its answer is a set-theoretic one.