Sums and comparison

Confused is not the same as unknown

Two positions can be neither greater, nor smaller, nor equal. That is a fourth relation with its own symbol, it is a fact about the pair rather than a limit of the method, and it is what makes a game worth playing — a position is a first-player win exactly when it is confused with zero.

Assumes: Comparing positions · Comparing two positions means playing a third

Numbers are totally ordered. Given two of them, one is bigger, or they are equal, and there is no fourth possibility — which is such a deep habit that it takes an effort to notice it is being used.

Games are not. Given two positions, the comparison can come back confused: neither is at least the other, and they are not equal either. The subject writes it G ‖ H, and it is not a shrug.

Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.
Fig. 1 Four comparisons, each decided by building the difference and asking who wins it. Two come back with an ordering and two come back confused — and the confused ones are as fully settled as the ordered ones, by the same computation.

What the symbol is asserting

The definition of the order is one line: G ≥ H when Left, moving second, wins G − H. That is the only definition there is, and it is a claim about a game rather than an inspection of two objects.

Run it both ways and there are four outcomes:

  • Left wins G − H moving second and Right wins H − G moving second: G = H.
  • Left wins moving second and Right does not: G > H.
  • The mirror: G < H.
  • Neither wins moving second: G ‖ H, confused.

The fourth case is not a failure to decide. It is the decided answer that G − H is a first-player win — whoever moves in the difference wins it — and that is as definite a verdict as the other three.

What that costs is the same whichever answer comes back, and the rung below prices it: the difference is built, the recursion walks its position graph, and the verdict is read off the outcome. A confused row and an ordered row are the same computation with different answers at the end of it, so nothing about the fourth relation is cheaper, later, or less certain than the other three.

Confused with zero is what a game is

The single most useful instance is the comparison against zero, because it recovers the outcome classes exactly.

A position greater than 0 is a win for Left whoever moves. Less than 0 is a win for Right. Equal to 0 is a second-player win. And confused with 0 is a first-player win: whoever moves, wins.

Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.
Fig. 2 Five positions compared with nought, four of which come back confused. When the second side is nought the difference is the first side, so each verdict is that position’s own outcome class read as an order relation — and the four confused rows are exactly the four first-player wins. The fifth row is the control: up is genuinely above nought, so an infinitesimal is not automatically confused with it.

Over the small pool this essay sweeps — sixteen values from 0 and ±1 through the switches and the infinitesimals — the positions confused with zero are ∗, ∗2, ↑∗, {2 | 0} and {1 | −1}. Those are exactly the pool’s first-player wins, and that is not a coincidence but a restatement: who moves last is the essay that derives the correspondence.

So the fourth relation is not an exotic corner. It is the class of positions worth playing. A game where every position were comparable with zero would be a game whose winner never depended on whose turn it was.

How much of the order is confusion

The pool is small enough to sweep exhaustively, and the proportions are worth having.

Sixteen values give 256 ordered pairs. Of those, 91 come back greater, 91 smaller, 16 equal — the diagonal — and 58 come back confused: 22.7% of all comparisons, more than one in five.

That is a lot of a partial order to be missing. And the confusion is not spread evenly: it is concentrated on the pairs where one side is an infinitesimal or a switch, which is to say on the positions where the outcome depends on the move.

Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.
Fig. 3 Three switches against numbers, inside and outside. A switch spans an interval rather than sitting at a point, so it is confused with every number strictly inside — with nought, with a half, with three halves — and comparable in the ordinary way with every number outside, as the last two rows show. The confusion is a fact about an interval and a point, and the two boundary cases are where it stops.

The other concentration is at the opposite end of the scale, and it has the opposite geometry. A switch is confused with numbers because its interval is wide; an infinitesimal is confused with nothing on the number line at all, because its interval has collapsed to a point and the confusion it has is with nought alone.

Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.
Fig. 4 And the other source, caught between two numbers. Up, star and two ups are each strictly below a sixty-fourth and strictly above minus a sixty-fourth, and the same is true for every pair of numbers straddling nought however close together — which is what being infinitesimal means. Every row here is ordered, and none of it settles the comparison with nought, which is a separate search and comes back confused for star and not for up.

Where the word comes from

The vocabulary is worth a paragraph, because three words are in circulation for one relation and they are not quite synonyms.

Confused is the word for the relation between two positions: G ‖ H says the difference is a first-player win. Fuzzy is the same word applied to a single position against zero — a fuzzy game is one confused with 0 — and it carries the picture the name suggests: the game is not at a point on the number line, it is smeared across a neighbourhood of one.

Incomparable is the order-theoretic word and it is the least useful of the three here, because it invites the reading this essay exists to refuse: that the comparison has not been made. It has been made. The answer is the third thing.

That is why the subject kept its own symbol rather than writing G ≰ H ∧ G ≱ H. A negation of two relations reads as an absence, and what is being reported is a presence — a game whose solution is that whoever moves wins it.

The distinction matters most when reading a table. A cell containing is not an empty cell; it is a cell containing an answer that took a search to produce, and a table that left it blank would be claiming something quite different.

The relation that is not transitive

Here is the property that makes ‖ a genuinely different kind of thing, and it is easy to state and easy to get wrong.

Being confused is not transitive. Over the same pool there are 252 triples with a ‖ b and b ‖ c and a not confused with c. The smallest is immediate: 0 ‖ ∗ and ∗ ‖ ↑, and 0 < ↑.

Meanwhile the order itself behaves perfectly. Over all 4,096 triples in the pool there is not one failure of transitivity for ≥: whenever a ≥ b and b ≥ c, it is checked and true that a ≥ c.

So the structure is exactly a partial order — reflexive, antisymmetric, transitive — and confusion is what fills the gaps in it. A reader who treats ‖ as a weak form of equality will conclude that ∗ is “about the same as” both 0 and ↑, and therefore that 0 and ↑ are about the same as each other, which is false.

Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.
Fig. 5 The same failure with a switch in the middle rather than a star, to show it is not a peculiarity of the nimbers. Minus one is confused with the switch and the switch is confused with one — both differences are the same game, {0 | −2} — and minus one is nevertheless a whole two moves below one. Chaining the first two relations would order nothing correctly; the third row is what the computation says.
Three partizan positions against every nimber, and not one match. Sprague and Grundy give every impartial position a single number that is complete: two positions with the same value are interchangeable everywhere. The three positions here are partizan — the two players have different moves — and each is compared against every nimber up to eight. Nothing is equal to anything. The magenta cells are worse than inequality: a position confused with a nimber is not above it or below it either, so no ordering could rescue the substitution.
Fig. 6 Confusion in bulk. Each row is a partizan position compared against every nimber in range, and the interesting cell is ‖ rather than ≠. A position merely unequal to every nimber might still be squeezed between two of them; a position confused with all of them is not on that line at all, and no single nimber can stand in for it in any sum.

Why a partial order and not a total one

The reason is structural and it is worth naming, because it explains why no amount of cleverness will produce a total order.

Games form a partially ordered abelian group: they add, every game has a negative, addition respects the order, and the order is not total. That last clause is forced by the first three plus one fact — that ∗ + ∗ = 0.

If the order were total, ∗ would be positive, negative or zero. It is not zero, since ∗ is a first-player win rather than a second-player one. If it were positive then ∗ + ∗ would be positive too, and it is zero. If negative, likewise. So ∗ is none of the three, and the order has a gap in it that no refinement can close.

The fact that forces it is one identity: +=0\ast + \ast = 0. A position confused with nought can be its own negative, and a totally ordered group has no element of order two — so the gap is put there by the addition rather than left there by the comparison, and the way outcome classes fail to compose is the same observation approached from the other end.

One fact explains both failures

Two things have now been said to go wrong: the order is not total, and confusion is not transitive. They look like separate defects, one about pairs and one about triples. They are the same fact, and it is +=0\ast + \ast = 0.

Start from the definition. Every relation here is decided by a difference, so being confused is not really a relation between two positions at all — it is membership of a set. Write FF for the fuzzy games, the ones confused with zero. Then

GHGHF,G \parallel H \quad\Longleftrightarrow\quad G - H \in F,

and the whole apparatus of comparison is the question of where a difference falls relative to that one set.

Now ask what transitivity of \parallel would require. If GHG \parallel H and HKH \parallel K, then GHG - H and HKH - K are both in FF, and GKG - K is their sum. So confusion is transitive exactly when FF is closed under addition — and it is not, because \ast is in FF and +\ast + \ast is zero, which is not.

That is the essay’s own smallest counterexample, one level down. 00 \parallel \ast because 0=0 - \ast = \ast is fuzzy; \ast \parallel \uparrow because \ast - \uparrow is  ⁣\downarrow\!\ast, which is fuzzy; and the sum of those two differences is \downarrow, which is strictly below zero and not fuzzy at all. Two fuzzy differences adding to an ordered one is all that ever goes wrong, and it goes wrong because FF has a pair of elements that cancel.

The section on why the order cannot be total runs the same argument on one element instead of two: \ast cannot be positive, since then +\ast + \ast would be positive and it is zero; cannot be negative for the mirror reason; and is not zero. Both failures are the observation that FF contains something of order two. A totally ordered group has no such element, and a group whose fuzzy set is closed under addition has none either.

What that says about the structure

Read the other way round, this says what kind of object FF actually is, and it is worth writing down because “the set of first-player wins” is a phrase the site uses constantly without saying what shape it has.

FF is symmetric: GG is confused with zero exactly when G-G is, since negating a difference exchanges the two players and a first-player win stays one. It does not contain zero, by definition. And it is not closed under addition — which, given the first two, is the interesting clause, because a symmetric set avoiding zero could easily have been closed and this one is emphatically not: it contains \ast and \ast, whose sum is the one game it excludes.

So FF is not a subgroup, not a cone, and not the complement of one. It is the set the order is built around and it has almost no algebraic structure of its own, which is precisely why confusion cannot be reasoned about by chaining and has to be recomputed for each pair.

And that is the practical warning restated with a reason behind it. The earlier section says a reader who treats \parallel as a weak equality will conclude that 00 and \uparrow are about the same because both are confused with \ast. The reason the conclusion fails is not that the relation is loose or approximate — it is that the argument silently assumes FF is closed under addition, and the one identity every reader of this site already knows is a counterexample to it.

That makes the non-transitivity considerably less surprising than the essay’s flat statement of it suggests. It would be surprising if confusion were transitive, because that would require the fuzzy games to be closed under a sum, and the very first fuzzy game anybody meets cancels against itself.

Sizing what cannot be ordered

Confusion says two positions are incomparable, and it says nothing about how far apart they are. Two tools recover part of that, and both work by changing the yardstick.

How many ups, bracketed. Every position here is all-small, so no number says anything about it and the yardstick has to be ↑ instead. Each bar spans the multiples of ↑ the position lies between: the largest it is at least, and the smallest it is at most. Four of the seven are pinned to a single multiple of ↑; the rest keep a band that comparison cannot narrow, the widest being ∗ at four ups of slack.
Fig. 7 Comparison against multiples of ↑ rather than against numbers. Every position here is confused with every number, and against the ups they bracket cleanly: the bar spans the largest multiple the position is at least and the smallest it is at most, established by comparison tests rather than by any calculus.

That is the atomic weight as evidence rather than as a formula, and it is the standard move: when the natural yardstick fails, find one that does not.

The same trick works one level further down. The tiny values are all smaller than every positive number and are strictly ordered among themselves, with the larger subscript giving the smaller value — so “smaller than everything positive” is a scale rather than a size. Against the ups they are indistinguishable: every one of them brackets between nought and a single up, so that yardstick has run out of resolution while the values it is measuring are still strictly ordered. Finding a scale is not the same as finding one fine enough.

The general lesson is that incomparability is relative to a yardstick. Two positions confused with each other may be perfectly ordered against a third scale, and finding the scale on which a class of positions is ordered is most of what the infinitesimal theory does.

What a player does with it

The practical content is short and it is the reason the relation earns its symbol.

A component confused with zero is one to move in. It is a first-player win, so whoever takes it gets it, and leaving it alone hands it over.

Two components confused with each other cannot be ranked by value. A player choosing between them needs a different criterion, and the usual one is temperature — a number attached to each, which is available precisely because it is a summary rather than a comparison.

That is worth restating as a general habit. When the order gives no answer, the answer is not “either will do”: it is that the ordering was the wrong question, and some other computed quantity has to break the tie.

Confusion intervals, and the honest picture

If a fuzzy game is smeared across a neighbourhood, the natural question is how wide the smear is, and the answer is a genuine quantity.

A position is confused with every number strictly between its two stops, and comparable with every number outside them. So {2 | 0} is confused with every number between 0 and 2 and is genuinely less than 3 and greater than −1; the interval is the confusion interval, and its width is twice the temperature for a plain switch.

That gives the picture the word fuzzy was reaching for, and it also shows what is wrong with it. The interval is not a blur caused by imprecision. It is the exact set of numbers whose comparison with the position comes back first-player-wins, and its endpoints are computed.

For an infinitesimal the interval collapses to a point: ↑ and ∗ both have stops 0 and 0, so neither is confused with any non-zero number at all. And yet ∗ is confused with 0 and ↑ is not — a distinction the interval cannot make, which is why the order and the interval are two different objects rather than one.

So the geometric picture handles switches perfectly and the infinitesimals not at all, which is the same division of labour every summary on this site runs into: numbers where there are points, and comparison where there are not.

Where the model stops

Sixteen values is a pool, not a census. The 22.7% figure is a property of this pool, and a pool weighted towards numbers would report far less confusion while a pool of infinitesimals would report much more. What the sweep establishes is that confusion is common among the values this site actually draws, not that any particular fraction is intrinsic.

Confusion is not a distance. Nothing here provides a measure of how badly two positions fail to be ordered. The bracket figures give one for all-small positions and it is not a general answer — for a switch confused with a number, the natural quantity is the temperature, and it lives in a different apparatus.

And the order is on values, not on positions. Two positions with the same canonical form are equal, so everything above is a statement about values rather than about how the positions look, and a reader comparing two boards is comparing what they reduce to.

What survives of arithmetic

Losing totality sounds like losing everything, and the accounting is worth doing, because most of arithmetic survives intact.

Addition works. Values add across a disjunctive sum, addition is commutative and associative, and zero is the identity.

Negatives work. Every game has one, by mirroring, and G + (−G) is worth exactly zero — which is what makes subtraction available and comparison a subtraction.

The order respects addition. If G ≥ H then G + X ≥ H + X for every X. That is the property that makes comparison useful rather than merely definable: a component may be replaced by a smaller one anywhere and the whole board cannot get better.

Multiplication does not exist, and nobody misses it. There is no product of two games in the general theory; the nimber multiplication is an operation on impartial values only, and it is an algebraist’s structure rather than a game one.

So the object is a partially ordered abelian group, and the single missing axiom is totality. Every technique on this site — cancellation, substitution, dominated options, canonical forms — uses the group structure and the order, and not one of them uses totality. The thing that felt indispensable turns out to have been the thing nothing needed.

What the picture cannot show

The relation symbols are drawn as characters in a column, and every figure here draws the same size and weight as > — which is honest about their status and misleading about their content.

The two symbols are not two answers to one question. > reports a game the second player wins from one side; reports a game the first player wins from both. The figures print the searches that settled them, which is the only cue on the page that the second answer is as computed as the first.

The other invisible thing is the triple. Failure of transitivity is a statement about three positions at once, and no row of a table shows it: the three examples above are assembled from three separate comparisons, and the reader has to hold them together. A figure of 252 offending triples would be a wall of symbols, and the mechanism is clearer in one sentence than in any drawing of it.

The convention, named

Normal play throughout, and one convention about what the comparison is for.

Equality here means interchangeability in every sum. G = H is not “these two positions look alike” or “these two are worth the same to a player”; it is that no game placed beside them can tell them apart. That is why the definition quantifies over a difference rather than over a board, and it is why the relation is worth computing.

Under misère play none of this survives. The difference G − H is built from a negative, misère play has no negatives, and there is no misère analogue of the comparison test at all — which is exactly why the misère theory works with quotients over a fixed universe rather than with an order on games.

Part 3 of 6

One argument about Comparison. The parts either side of it:

What links here

Essays that reach for this one mid-argument — the half of a link its own author cannot write down, the 8 sharing most with it of 28.

What this makes readable

Essays that declare this one a prerequisite.

The objects named here

The third axis, after the field and the series: the games, values and theorems themselves, and every essay that touches each one.

ComparisonConfusionDifferenceDisjunctive sumEqualityFuzzyGroupInfinitesimalOutcome classPartial orderStar (∗)Switch