Editing Sprague–Grundy theorem (section)

==First Lemma==
As an intermediate step to proving the main theorem, we show that for every position <math>G</math> and every <math>\mathcal{P}</math>-position <math>A</math>, the equivalence <math>G\approx A+G</math> holds.  By the above definition of equivalence, this amounts to showing that <math>G+H</math> and <math>A+G+H</math> share an outcome class for all <math>H</math>.

Suppose that <math>G+H</math> is a <math>\mathcal{P}</math>-position.  Then the previous player has a winning strategy for <math>A+G+H</math>: respond to moves in <math>A</math> according to their winning strategy for <math>A</math> (which exists by virtue of <math>A</math> being a <math>\mathcal{P}</math>-position), and respond to moves in <math>G+H</math> according to their winning strategy for <math>G+H</math> (which exists for the analogous reason).  So <math>A+G+H</math> must also be a <math>\mathcal{P}</math>-position.

On the other hand, if <math>G+H</math> is an <math>\mathcal{N}</math>-position, then <math>A+G+H</math> is also an <math>\mathcal{N}</math>-position, because the next player has a winning strategy: choose a <math>\mathcal{P}</math>-position from among the <math>G+H</math> options, and we conclude from the previous paragraph that adding <math>A</math> to that position is still a <math>\mathcal{P}</math>-position.  Thus, in this case, <math>A+G+H</math> must be a <math>\mathcal{N}</math>-position, just like <math>G+H</math>.

As these are the only two cases, the lemma holds.