The case that was supposed to be hard

A mex with no impartial game in it found that the mirror construction’s nimber values obey a mex: $\{S \mid -S\}$ is $\ast k$, where $k$ is the least number with no element of $S$ at least $\ast k$. It fires on 66 of the 96 antichains, is right on every one, and the page closed by naming what would turn it into a theorem and what would make that hard:

The rung above is the induction … The step that needs care is the partial order — no element at least $\ast k$ leaves incomparable elements in play, and an incomparable element is exactly the case a total order would not have to handle.

There is no induction. The argument is four lines, and the case flagged as the difficulty is the case that makes it work.

What has to be shown #

Write $G = \{M \mid -M\}$ for the mirror of an antichain $M$, and $k$ for the least number with no element of $M$ at least $\ast k$. The claim is $G = \ast k$, and since $\ast k$ is its own negative that is the claim that

$$G + \ast k = 0$$

— that the sum is a second-player win.

Two facts about $M$ are available and both come from the definition of the mex. No element is at least $\ast k$ — that is what makes $k$ a bound. And some element is at least $\ast j$ for every $j$ below $k$ — that is what makes it the least such, and it is the half that does the work in the first branch.

Both are checked on all 66 antichains, along with the conclusion itself, computed by the ordinary canonical-form machinery rather than deduced from the argument it is meant to confirm.

One preliminary is worth stating because it is what lets the argument talk about $M$ rather than about $S$. What identifies two subsets established that an option of $\{S \mid -S\}$ is dominated exactly when another element of $S$ is at least as good, so the form reduces to the antichain of maximal elements and the Right side reduces with it. That is why every statement here is about an antichain: the construction on any subset gives the same value as the construction on its maximal elements, and there is no loss in assuming the elements are pairwise incomparable to begin with.

The first branch: a move in the nimber #

Suppose the first player moves in $\ast k$, taking it to $\ast j$ for some $j < k$. The position is $G + \ast j$ and the responder is to move.

By the second fact there is an element $a$ of $M$ with $a \geq \ast j$. If the responder is Right, they move in $G$ to $-a$, leaving

$$-a + \ast j \ \leq\ -\ast j + \ast j \ = \ 0$$

so the position is at most nought and Right wins it. If the responder is Left, the mirror argument applies to $a$ itself.

That branch is used 23 times across the census — once for each $j$ below each antichain’s $k$ — and the sign of the reply is checked in all 23.

The second branch: a move in $G$ #

Suppose instead the first player moves in $G$, to some element $a$ of $M$. The position is $a + \ast k$ and the responder is to move.

Here the mex gives only a negative: $a$ is not at least $\ast k$. In a total order that would say $a < \ast k$ and the argument would be over. In this order it leaves two cases.

$a$ is below $\ast k$. Then $a + \ast k < 0$, the position is a win for Right whoever moves, and if the responder is Right they win it. Thirty-nine of the elements in the census are of this kind.

$a$ is incomparable with $\ast k$. Then $a + \ast k$ is fuzzy with nought — neither at least nought nor at most it — which is a first-player win. And after a move in $G$ the first player is the responder. So they win it.

That is the whole of the flagged difficulty. Incomparability does not block the argument; it is answered by one of the four outcome classes doing exactly what it is for. Confused is not the same as unknown is where the fourth relation is set out, and this is as clean a use of it as the site has: a relation that a total order does not have, doing a job a total order would need a case analysis for.

$a$ is at least $\ast k$. Excluded by the mex. Nought cases, which is the one row of the table that is a tautology.

Two details of that branch deserve a sentence each, because both are places the argument could have failed and does not.

The reply is available on both sides. $G$’s Left options are the elements of $M$ and its Right options are their negatives, so whichever player is responding has a move to the witness in the appropriate orientation. That is the mirror construction’s whole point and it is why a self-negative value is easier to reason about than an arbitrary one.

And the reply is to an element, not to a smaller antichain. The responder moves in $G$ and $G$’s options are elements of $M$ — full games, not mirrors of anything — so the position after the reply is $\pm a + \ast j$, a sum of two ordinary games whose sign is a comparison rather than another instance of the problem. That is the second reason there is no induction: the recursion bottoms out after one move.

And it is the majority case #

Across the 66 firing antichains there are 127 elements for the second branch to handle. Thirty-nine are below $\ast k$ and 88 are incomparable with it.

So more than two elements in three are the case the rung below expected to be the obstacle. An argument that covered only the comparable ones — the ones a proof written for a total order would reach — would have covered under a third of the ground, and would have looked like a proof.

That is worth stating as a general warning rather than as a fact about this construction. In a partial order, not greater than or equal is a much weaker statement than less than, and the difference is not a technicality at the edges: here it is two thirds of the population.

Why there is no induction #

The rung below proposed an induction on $k$ — assume the rule at $k - 1$ and derive it at $k$ — and the argument above uses no such assumption anywhere.

The reason is that the mex’s two facts are both statements about $M$ directly, not about a smaller antichain. Some element is at least $\ast j$ is available for every $j$ below $k$ at once, so the first branch has all the witnesses it needs without descending. And the second branch is about $\ast k$ alone. Nothing in the argument mentions the rule at any other value.

That is a slightly deflationary finding and it is the right one. An induction is what a proof needs when the object at $k$ is built from the object at $k - 1$; here the object is a set and $k$ is a property of it, so there is nothing to descend through. The rung below reached for induction because a mex looks like an inductive object — and the mex here is a description of a value rather than a recursion producing it.

The distribution shows why the induction would have had little to do anyway. Of the 66 antichains, 48 have $k = 0$, 14 have $k = 1$, three have $k = 2$ and one has $k = 3$. An induction on $k$ would have had three non-trivial steps in the entire census.

The picture a proof does not have #

This page is the first on the anchor whose product is an argument rather than a measurement, and it is worth saying what that costs in figures.

A measurement has a natural picture: the population, the quantity, and the distribution. An argument has a natural picture only when it is geometric, and this one is not — it is four sentences about signs and turns. So every figure here is a census of the argument’s cases rather than a drawing of the argument: how many antichains, how many elements of each kind, how many replies checked. The figures answer is the argument’s coverage complete and not why is it true.

The one figure that comes closest to the reasoning is the incomparable table, where the element, the sum it leaves and the verdict fuzzy with nought sit in one row. A reader who follows that row has the second branch. What no figure carries is the sentence that makes it work — that the responder is the player to move — because that is a fact about a game tree’s turn order and there is nothing to draw of it.

Confused is not the same as unknown does draw the four outcome classes, and it is the page whose picture this argument is using.

Argued and checked #

Every claim above has a computation beside it, and the computations do not use the argument.

That the reply after a nimber move lands at most at nought is checked by taking the sign of $-a + \ast j$ from the canonical forms, 23 times. That an element below $\ast k$ leaves a negative sum is checked 39 times, and that an incomparable one leaves a fuzzy sum 88 times. And the conclusion — $\{M \mid -M\} + \ast k = 0$ — is computed directly on all 66, so a flaw in the reasoning would show up as a disagreement rather than as a silence.

The distinction matters on a site whose usual product is a measurement. What is being claimed here is a proof, and a proof of a statement that is already known to be true on the population is worth exactly its argument. What the checks buy is that the argument’s own intermediate claims are true, which is what a reader cannot verify by re-running the census.

What the argument is an argument about #

It is worth being explicit about the object, because a mex with no impartial game in it is a strange sentence and this page is the place it becomes precise.

The mirror construction takes any set of short games and returns a value that is its own negative. Nothing about it is impartial: the elements of $M$ are partizan games, $G$’s Left and Right options are different sets, and the construction never asks whether a position looks the same to both players. What it does produce is a position in which whose turn it is stops mattering — that is what $G = -G$ means — and the mex appears exactly there.

So the mex is not a fact about impartial play. It is a fact about self-negation, and the argument above shows why: the whole of it turns on $\ast k$ being its own negative, so that $G + \ast k$ can be attacked from either side with the same reasoning, and on $M$’s elements being incomparable with $\ast k$ rather than below it. Neither step uses impartiality anywhere.

That is the transferable statement. Wherever a construction produces self-negative values, the outcome of adding a nimber to one of them is decided by one comparison per option, and a mex is what a family of such comparisons produces.

What this does not settle #

The population is one day. The antichains are antichains of day-two values, which is where the construction was built and measured. The argument mentions the day nowhere and ought to hold for antichains of any set of short games; that it does is a claim this page makes and does not test, because the day-three census is a different order of computation.

The mex is bounded by the nimbers available. The rule fires when some $\ast k$ has no element above it, and on 30 of the 96 antichains no such $k$ exists within the nimbers the census carries. Those 30 are the antichains whose value is not a nimber, and nothing here is about them — the rung below established that the firing set and the nimber-valued set are the same, and this page inherits that.

And the argument is not a construction. It shows the sum is nought without saying what the second player’s strategy looks like as a whole, because the incomparable branch’s win comes from an outcome class rather than from a named reply. A reader who wanted the strategy would have to unfold each fuzzy position, and there are 88 of them.

The census is a check and not the proof’s scope. The argument is written for any antichain and any $k$; the 66 are what the day-two construction happens to produce. A reader should take the checks as evidence that the argument’s own steps are stated correctly rather than as the extent of what it establishes — the two are different, and conflating them is how a proof gets quietly demoted to a sweep.

Normal play throughout, and every comparison is comparison in every company — equal in every company rather than in any restricted universe, which is what makes incomparable mean what it means here.

One consequence, immediately #

The rule now has an argument, and one number on this anchor changes standing because of it.

At least five hundred and seventy-one used the mirror construction to put a floor under the count of self-negative values born by day four: every subset of day three gives one, and distinct values give distinct members. The floor was a floor because the map’s fibres were not understood — two subsets might collide and the count would over-report.

With the mex rule proved, the collisions that produce a nimber are completely described: two antichains give the same nimber exactly when they have the same mex, and the mex is a one-line computation on the antichain. That does not close the count, because the non-nimber values remain undescribed. It does mean the floor’s error is confined to them, and they are the part of the census where the map is nearly one-to-one.

So the floor is no worse than it was and is now known to be no worse in a specific place. That is a small gain and it is the sort a proof buys: not a new number, but a boundary drawn round where the old number could be wrong.

Where the ladder goes next #

The negation anchor has nine rungs: every game has a negative, the values that are their own negatives, what a self-negative value costs, the thirty that cancel themselves, what can be struck out, at least five hundred and seventy-one, what identifies two subsets, the rule that identifies them, and now why the rule holds.

The rung above is the non-nimber values. The mex rule and its argument account for 66 of the 96 antichains, and the other 30 have values that are not nimbers and no description at all — what identifies two subsets found 34 antichains giving 28 distinct values, so the map is nearly one-to-one out there and there is no fibre structure to find. What there might be is a formula: the argument above works because $\ast k$ is its own negative and the sum’s outcome is decidable from one comparison, and any self-negative value has the first property. Whether some other self-negative value plays the role $\ast k$ plays here, for an antichain the mex is silent on, is the question the argument makes askable.

Two neighbours are worth the trip. Sprague–Grundy is where the mex belongs and where it is an induction, and reading it beside this page is the clearest statement of the difference between a mex that generates values and a mex that describes them. And at least five hundred and seventy-one is where the construction became a counting tool, and the rule proved here is what would turn its floor into a count.