What identifies two subsets

At least five hundred and seventy-one turned the census of self-negative values into a construction. For any set $S$ of values, the position $\{S \mid -S\}$ is its own negative — mirror the options and the game is unchanged — and every self-negative value born by day three arises that way from a subset of day two. That gave a floor on day four, and it closed on the map’s fibres:

The rung above is the fibres of the mirror map. Every subset $S$ of a day gives a self-negative value, and enormously many subsets give the same one — 1,793 subsets of day two give 30 values … What identifies two subsets is the question, and it is a question about canonical forms rather than about negation.

It is, and it happens twice.

The first stage is a theorem #

Nineteen twentieths of the collapse needs no computation at all.

An option of $\{S \mid -S\}$ is dominated when another option is at least as good, and Left’s options are exactly the elements of $S$. So an element $a$ with some $b \in S$ satisfying $b \ge a$ is deleted — and on the Right side, $-a$ is deleted because $-b \le -a$ says the same thing mirrored. The two deletions happen together, which is what makes the mirror construction well behaved: the form stays self-negative through every step of its own reduction.

What survives is the antichain of maximal elements of $S$. So $\{S \mid -S\}$ depends on $S$ only through that antichain, and two subsets with the same maximal elements give the same value by construction.

Among the 1,793 subsets of size at most three there are 96 distinct antichains, so this stage alone takes the fibres from 1,793 to 96 — and the reason the factor is so large is that most subsets are triples, and a triple of day-two values usually has one element beating another. Twenty-two singletons give 22 antichains, 231 pairs give 52 more, and all 1,540 triples between them add only 22.

And the second is not #

Ninety-six antichains give 30 values, and the collapse is not spread evenly over them. Forty-eight of the 96 give nought. Fourteen more give star. Three give $\ast 2$, four values are reached by two antichains apiece, and the remaining 23 values are reached by exactly one.

So outside two fibres the mirror map is very nearly injective on antichains, and the whole of the second stage is two large classes and a tail. That is a much more specific answer than reversibility does the rest, and it means the question splits: describe the two fibres, and the rest is a bijection.

The largest fibre, exactly #

$\{S \mid -S\}$ is nought exactly when no element of $S$ is greater than or equal to nought. Five hundred and seventy-five subsets satisfy it and 1,218 do not, and the rule is exact both ways.

The argument is one line of outcome arithmetic. Left moving first in $\{S \mid -S\}$ moves to some $a \in S$ and wins from there precisely when $a \ge 0$, since winning as the second player in $a$ is what $a \ge 0$ says. So Left moving first wins the whole position exactly when some element is at least nought, and by mirror symmetry the same is true of Right. A position both players lose moving first is a second-player win — and a self-negative second-player win can only be nought, because $G = -G$ and $G = 0$ is the only value equal to its own negative with that outcome.

The outcome table says the same thing counted differently, and it is worth having because it makes the zero fibre countable without evaluating anything. Exactly half of the 96 antichains give a second-player win. All 48 of them are nought, and none of the other 48 is — so how many subsets give nought is answerable by checking each element against nought, which is 22 comparisons done once and then a lookup.

The other fibre has no rule #

Fourteen antichains give $\ast$ and nothing on this page describes them. $\{0\}$ gives $\ast$, which is the definition of star. $\{\uparrow\}$ gives $\ast$, which is the standard identity $\{\uparrow \mid \downarrow\} = \ast$. $\{\,\{1 \mid \ast\}\,\}$ gives $\ast$, and $\{0, \ast 2\}$ gives $\ast$, and there is no property this page has found that the fourteen share and the other 82 antichains lack.

That is the honest state of the second stage: one clause described exactly and one left open. The open one is small — fourteen antichains out of 96, all of them in hand with their elements — and it is the obvious thing for the rung above to look at.

Why the two stages are worth separating #

There is a temptation to describe the whole collapse as the canonical form does it, and the two stages behave so differently that the description would hide the interesting half.

The first stage is structural: it depends on the partial order of day two and on nothing about the mirror construction beyond the fact that it puts $S$ on one side and $-S$ on the other. It would be the same for any construction that took a set to a position with that set as one side’s options, and it can be computed from the order alone, without evaluating a single position.

The second stage is semantic: it identifies antichains that are genuinely different sets and whose mirrors happen to be the same game. Nothing about the order predicts it, and half of it is a single value — nought — arriving because a position with nothing good in it for either player is a second-player win.

Keeping them apart is what makes the counting tractable. The rung below’s floor on day four came from counting constructions; a count rather than a floor needs the fibres, and the fibres are now one exact rule, one open class of fourteen, and a bijection on the rest.

What a fibre this shape says about the construction #

It is worth reading the numbers as a statement about the mirror map rather than about day two.

A construction that produced a new value for every input would be a bijection and would make counting trivial. A construction that collapsed everything would be useless. This one does neither: it is injective on 23 of its 30 outputs and it sends half of its inputs to a single value, and both halves of that sentence are informative.

The half that collapses is collapsing for a reason with nothing to do with negation. A subset with no element at least nought is a subset offering Left nothing worth moving to, and mirroring it offers Right nothing either — so the construction has been handed two hands of bad cards and produces the empty game. That is a degenerate input, not a collision, and the right way to read 48 of 96 is that half the antichains of day two are entirely below or beside nought.

The half that does not collapse is where the construction earns its place. Forty-eight antichains give 29 distinct non-zero values, so on the useful half of its domain the mirror map is losing almost nothing — which is exactly what a construction used to put a floor under a count needs to be. At least five hundred and seventy-one was counting constructions and hoping they were mostly distinct, and on the half that matters they are.

Where the day-two order does the work #

The first stage is arithmetic on a partial order and it is worth seeing the order that produces it, because the numbers are unintuitive.

Day two has 22 values and its order is not a chain: most pairs are confused rather than comparable, since the infinitesimals and the switches are incomparable with almost everything. A partial order with many incomparable pairs has many antichains — in the extreme, a completely unordered set of 22 elements would have every subset as an antichain, and the first stage would collapse nothing at all.

So the factor of nineteen is a measurement of how ordered day two is. Twenty-two singletons are all antichains, of course. Of the 231 pairs, 52 are antichains — so 179 of the 231 pairs are comparable, which is far more order than the reputation of the day-two lattice suggests. And of the 1,540 triples, only 22 are antichains, which is what happens when comparability is that common: a triple avoids a comparison three ways over and almost never manages it.

That is a fact about day two rather than about mirrors, and it is why the first stage carries most of the collapse. On a day whose values were mostly incomparable the antichain count would be near the subset count and the whole burden would fall on the second stage, which is the stage without a rule.

What this does not say #

Subsets of size at most three. The rung below established that every self-negative value born by day three is $\{S \mid -S\}$ for such a subset, so nothing is missed among day-three values — but the map from all subsets of day two is not what has been swept, and a four-element antichain of day two would add antichains this page does not count.

Day two only. The whole analysis is of subsets of the 22 values born by day two. Day three has 1,474 values and its antichains are a much larger object; whether the two-stage picture holds there, and whether nought still takes half, is the same computation at a scale that would need care.

The zero rule is about elements, not about the antichain. It is stated and checked over subsets, and it happens to be inherited by antichains because deleting a dominated element cannot introduce an element that is at least nought. That inheritance is used and not separately verified.

The 96 are antichains of a bounded size. Because the subsets stop at three elements, so do the antichains, and an antichain of four incomparable day-two values would be a 97th. Day two has enough incomparable pairs to make such antichains exist, so the 96 is the count within the sweep rather than the count of antichains of day two.

And the star fibre is described as undescribed. Fourteen antichains with no common property that this page has looked for is a weaker statement than no common property. What has been tried is containing nought, containing an infinitesimal, and the size of the antichain; none separates the fourteen from the rest.

Two collapses, and only one of them is a theorem #

The reduction from 1,793 to 30 happens in two stages, and the stages are not two applications of one idea. Keeping them apart is what makes the second one tractable.

Domination is a theorem and it is cheap. A subset and the antichain of its maximal elements give the same mirror, because the elements below a maximal one are dominated in the resulting form and the reduction deletes them. That is an argument, it applies to every subset of every day, and it takes 1,793 to 96 with nothing to measure.

The rest is not a theorem and it is where the interest is. Ninety-six antichains give thirty values, so two thirds of the antichains are identified with something else — and that identification is not domination, since an antichain has no dominated elements left to remove. It is reversibility, or the simplicity of the value, or something with no name yet, and it is what a description has to describe.

The measurement that makes the second stage tractable is where it concentrates. If the 66 identifications were spread evenly over the thirty values there would be thirty little problems; they are not, they land almost entirely on two values, so there are two fibres to describe and twenty-eight that are nearly singletons.

That is the shape a hard problem takes when it is about to become an easy one. A general map with no description becomes two specific sets with descriptions, and the rung above supplies both — with one rule, which turns out to be a mex.

What it would take to count day four #

The rung below produced a floor of 571 self-negative values on day four and said plainly that a floor is what it was. It is worth setting out what this page changes about the prospect of a count.

A count needs three things. The domain: every subset of day three, which is $2^{1474}$ and is not going to be enumerated — so the count has to run over antichains from the start, and the first stage above is what licenses that. The fibres: for each antichain, whether some other antichain gives the same value. And a completeness argument: that every self-negative value born by day four is the mirror of some subset of day three, which the rung below checked one day lower and did not prove.

This page settles the first and half of the second, at day two. Antichains rather than subsets is now known to lose nothing; and among antichains the map is injective outside two classes, one of which is described exactly. What it does not settle is whether the same shape holds a day up, and there is a specific reason to doubt it: the collapse to nought is driven by how much of the day sits at or below zero, and day three’s population is differently distributed.

So the honest position is that the route to a count is now visible and each of its three steps is a day-three computation nobody has run. The antichains of day three are the expensive one — how rare it is to be bigger measures how often two day-three values are comparable, which is the number that decides whether antichains are a manageable object there at all.

The convention, named #

Normal play throughout, and every value computed by the recursion and reduced to canonical form.

The mirror of a set $S$ is the position $\{S \mid -S\}$, whose Left options are the elements of $S$ and whose Right options are their negatives. It is self-negative for every $S$: negating a game swaps the two sides and negates every option, which returns the same position.

An element of $S$ is maximal when no other element of $S$ is at least as good in the game order; the antichain of $S$ is the set of its maximal elements, and two elements confused with each other are both maximal.

The fibre of a value is the set of subsets whose mirror is that value. Fibres are counted in two currencies here — subsets and antichains — and the tables say which.

Nought means the value 0, not the outcome. Second-player win is the outcome in which whoever moves first loses. For self-negative values the two coincide, which is the point of the outcome table.

Where the ladder goes next #

The negation anchor has seven rungs to here, and this one has reduced the mirror map’s fibres to two — nought’s, which has an exact description, and star’s, which does not.

The rung above supplies the missing one and does it by finding that there was never more than one rule. A mex with no impartial game in it describes star’s fibre as some element is at least nought, and none is at least star — and then observes that this and the description of nought’s fibre are the same rule read at two indices. The mirror value of a set is the least nimber no element of the set reaches.

That is a mex, and it arrives in a construction built entirely out of partizan values with no impartial game anywhere near it. Which is less of a coincidence than it looks: a mex is the answer to what is the smallest object of a standard family that this set does not reach, and the mirror has to be a value the set’s own elements do not already supply — the same question the Grundy value answers, asked of a different construction.

So the two-stage collapse this page measures has a single explanation for its second stage. Domination takes 1,793 subsets to 96 antichains and is a theorem about orders; the rest takes 96 to 30 and is a mex over nimbers, which is why it concentrates on nought and star and barely touches the other twenty-eight. Those two values are the two smallest nimbers, and a mex lands on small ones.