Editing Nimber (section)

== Addition ==
Nimber addition (also known as '''nim-addition''') can be used to calculate the size of a single nim heap equivalent to a collection of nim heaps.  It is defined recursively by
<math display=block>\alpha \oplus \beta = \operatorname{mex} \! \bigl( \{ \alpha' \oplus \beta : \alpha' < \alpha \} \cup \{\alpha \oplus \beta' : \beta' < \beta \} \bigr),</math>
where the [[minimum excludant]] {{math|mex(''S'')}} of a set {{mvar|S}} of ordinals is defined to be the smallest ordinal that is ''not'' an element of {{mvar|S}}.

For finite ordinals, the '''nim-sum''' is easily evaluated on a computer by taking the [[Bitwise operation|bitwise]] [[exclusive or]] (XOR, denoted by {{math|⊕}}) of the corresponding numbers. For example, the nim-sum of 7 and 14 can be found by writing 7 as 111 and 14 as 1110; the ones place adds to 1; the twos place adds to 2, which we replace with 0; the fours place adds to 2, which we replace with 0; the eights place adds to 1. So the nim-sum is written in binary as 1001, or in decimal as 9.

This property of addition follows from the fact that both {{math|mex}} and XOR yield a winning strategy for Nim and there can be only one such strategy; or it can be shown directly by induction: Let {{mvar|α}} and {{mvar|β}} be two finite ordinals, and assume that the nim-sum of all pairs with one of them reduced is already defined. The only number whose XOR with {{mvar|α}} is {{math|''α'' ⊕ ''β''}} is {{mvar|β}}, and vice versa; thus {{math|''α'' ⊕ ''β''}} is excluded. 
<math display=block>\zeta := \alpha \oplus \beta \oplus \gamma</math> 
On the other hand, for any ordinal {{math|''γ'' < ''α'' ⊕ ''β''}}, XORing {{mvar|ζ}} with all of {{mvar|α}}, {{mvar|β}} and {{mvar|γ}} must lead to a reduction for one of them (since the leading 1 in {{mvar|ζ}} must be present in at least one of the three); since 
<math display=block>\zeta \oplus \gamma = \alpha \oplus \beta > \gamma,</math> 
we must have either
<math display=block>\begin{align}
\alpha > \zeta \oplus \alpha &= \beta \oplus \gamma, \quad\text{or}\\[4pt]
\beta > \zeta \oplus \beta &= \alpha \oplus \gamma.
\end{align}</math>
Thus {{mvar|γ}} is included as either
<math display=block>\begin{align}
(\beta \oplus \gamma) \oplus \beta, \quad\text{or}\\[4pt]
\alpha \oplus (\alpha \oplus \gamma);
\end{align}</math>
and hence {{math|''α'' ⊕ ''β''}} is the minimum excluded ordinal.

Nimber addition is [[associative]] and [[commutative]], with {{math|0}} as the additive [[identity element]]. Moreover, a nimber is its own [[additive inverse]].<ref name=Unity2021>{{cite book |title=The Unity of Combinatorics |first=Ezra |last=Brown |authorlink=Ezra Brown |first2=Richard K. |last2=Guy |author-link2=Richard K. Guy |section=2.5 Nim arithmetic and Nim algebra|page=35 |publisher=[[American Mathematical Society]] |year=2021 |isbn=978-1-4704-6509-4 |volume=36 of The Carus Mathematical Monographs |edition=reprint}}</ref> It follows that {{math|1=''α'' ⊕ ''β'' = 0}} [[if and only if]] {{math|1=''α'' = ''β''}}.