ニンバー

数学において、ニンバー（ Grundy数とも呼ばれる。Grundy彩色数とは混同しないように注意が必要）は組合せゲーム理論で導入され、ゲーム「ニム」におけるヒープの値として定義される。ニンバーは順序数と同じ固有ク​​ラスであるが、順序数の加算と乗算とは異なるニンバー加算とニンバー乗算を備えている。

スプラーグ＝グランディの定理によれば、すべての公平なゲームは一定サイズのニムの山に相当するため、ニムはより広範な公平なゲームに出現する。また、ドミネアリングのような党派的なゲームにも出現する可能性がある。

数体の加算と乗算演算は結合法則と交換法則を満たします。各数体は自身の加法逆元です。特に、いくつかの順序数のペアでは、数体の和はどちらの加数よりも小さくなります。^{[ 1 ]} 最小排他演算は数体の集合に適用されます。

クラスとして、ニンバーは順序数によってインデックス付けされ、ジョン・コンウェイが組み合わせゲームの理論の一部として導入した超現実数のサブクラスを形成します。^{[ 2 ]}しかし、ニンバーは、ニン加算とニン乗算という独自の算術規則に従う点で、順序数や超現実数とは異なります。ニンバーは集合ではなく真のクラスであることに加えて、ニン加算とニン乗算の下で体を形成します。ニンバーの体はOn ₂と表記されます。

有限数は集合として、有限順序数（すなわち自然数）と1対1に対応させることができます。しかしながら、それらの算術構造は同型ではなく、数の算術は自然数に対する通常の算術演算とは根本的に異なります。

数字はしばしば星印で表されます。${\displaystyle \{*0,*1,*2,...,*\omega ,*(\omega +1),...\}}$あるいは、通常の算術として解釈される式は、慣例として角括弧で囲まれます。例えば、${\displaystyle 2^{2}=*(2)^{2}=3}$ニム乗算では、${\displaystyle [2^{2}]=*(2^{2})=4}$[ ^{3 ] [ 4 ]​}

ニム加算（ニム加算とも呼ばれる）は、ニムヒープの集合に相当する単一のニムヒープのサイズを計算するために使用できます。これは、次のように再帰的に定義されます。 $${\displaystyle \alpha \oplus \beta =\operatorname {mex} \!{\bigl (}\{\alpha '\oplus \beta$$  ここで、 順序数の集合Sの最小排他数mex( S )は、 Sの要素ではない最小の順序数として定義されます。

有限順序数の場合、対応する数のバイナリ表現のビットごとの排他的論理和（XOR、⊕で表される）を取ることで、コンピュータ上で簡単にニム和を計算できます。たとえば、7と14のニム和は、7を111、14を1110と書くことで求められます。これら2つのバイナリ数のXORはバイナリ数1001なので、ニム和は9です。

この加算の性質は、 mexと XOR の両方が Nim の勝利戦略を生み出し、そのような戦略は 1 つしか存在しないという事実から導かれます。または、帰納法によって直接示すこともできます。αとβを2 つの有限順序数とし、そのうちの 1 つを減算したすべてのペアの nim-sum が既に定義されていると仮定します。α との XOR が α ⊕ β となる唯一の数はβであり、その逆も同様です。したがって、α ⊕ βは除外されます。 $${\displaystyle \zeta$$ :=\alpha \oplus \beta \oplus \gamma } 一方、任意の順序数γ < α ⊕ βに対して、 ζをα、 β、 γのすべてとXOR すると、それらのいずれかが減少するはずです ( ζの先頭の 1 は、少なくとも 3 つのうちの 1 つに存在する必要があるため)。 $${\displaystyle \zeta \oplus \gamma =\alpha \oplus \beta >\gamma ,}$$ 我々はどちらかを持たなければならない $${\displaystyle {\begin{aligned}\alpha >\zeta \oplus \alpha &=\beta \oplus \gamma ,\quad {\text{または}}\\[4pt]\beta >\zeta \oplus \beta &=\alpha \oplus \gamma .\end{aligned}}}$$ したがって、γは以下のいずれかに含まれる。 $${\displaystyle {\begin{aligned}(\beta \oplus \gamma )\oplus \beta ,\quad {\text{または}}\\[4pt]\alpha \oplus (\alpha \oplus \gamma );\end{aligned}}}$$ したがって、α ⊕ βは最小の除外順序数である。

ニンバーの加算は結合法則と交換法則を満たし、0は加法単位元である。さらに、ニンバーは自身の加法逆元である。^{[ 7 ]}したがって、 α ⊕ β = 0はα = βの場合に 限る。

ニンバー乗算（ニム乗算）は、以下のように再帰的に定義される。

$${\displaystyle \alpha \otimes \beta =\operatorname {mex} \!{\bigl (}\{(\alpha '\otimes \beta )\oplus (\alpha \otimes \beta ')\oplus (\alpha '\otimes \beta '):\alpha '<\alpha ,\beta '<\beta \}{\bigr )}.}$$

数乗法は結合法則と交換法則を満たし、順序数1が乗法単位元となる。さらに、数乗法は数加算に対して分配法則を満たす。^{[ 7 ] [ a ]}

したがって、ニンバーが集合ではなく真クラスを形成するという事実を除けば、ニンバーのクラスは環を形成する。実際、それは標数2の代数的に閉じた体さえも決定し、非ゼロ順序数αのニンバー乗法逆元は次のように与えられる。

$${\displaystyle \alpha ^{-1}=\operatorname {mex} (S),}$$ ここで、Sは、以下の条件を満たす最小の順序数（数値）の集合である。

1. 0はSの要素である。
2. 0 < α ′ < αかつβ'がSの要素である場合、${\displaystyle (1\oplus (\alpha '\oplus \alpha )\otimes \beta ')\otimes (\alpha ')^{-1}}$はSの要素でもある。

すべての自然数nに対して、 [2 ^{2 n} ]より小さい数の集合は、位数2 ^{2 n}のガロア体GF(2 ^{2 n} )を形成します。したがって、有限数の集合は、n → ∞のときの体GF(2 ^{2 n} )の直接極限と同型です。この部分体は代数的に閉じていません。なぜなら、kが2 のべき乗でない体GF(2 ^k )は、これらの体のいずれにも含まれておらず、したがってそれらの直接極限にも含まれていないからです。たとえば、GF(2 ³ )に根を持つ多項式x ³ + x + 1は、有限数の集合に根を持ちません。 

数加算の場合と同様に、有限順序数の数積を計算する方法があります。これは次の規則によって決定されます。

1. フェルマーの2乗（[2 ^{2 n} ]の形の数）とより小さい数の数積は、それらの通常の積に等しい。
2. フェルマーの2乗[2 ^{2 n} ]の二乗は[3·2 ^{2 n −1} ]に等しい。

無限の整数への後続の拡張では、各素数次数に対する拡張が追加されます。たとえば、次の拡張セット ( ω ^ωまで) は、有限の整数上の次数3 ⁿの拡張です。 ^{[ 3 ]}

1. ω ³ = 2 ;
2. n ≥ 1 の場合、[ ω ^{3 n} ] ³ = [ ω ^{3 n −1} ]。

^{代数的に閉じた最小のニンバーの体は、最小の無限順序数}ωより小さいニンバーの集合である。したがって、ニンバーとして、ω ^{ω ω}は体上の超越元である。 ^{[ 8 ]}次の超越元は不明である。^{[ 3 ]}

以下の表は、最初の16個の数字間の加算と乗算を示しています。

この部分集合は、16 が[2 ^{2 n} ]の形であるため、両方の操作に関して閉じています。 

すべての順序数のクラス上の同様の体On _{p を}各素数特性pに対して構築することができ、そこでは加算は繰り上がりのない基数pの加算として解釈されるなどするが、定義はより複雑である。^{[ 4 ] [ 3 ]}例えば、On ₃における nim 加算は次のように再帰的に定義される。 $${\displaystyle \alpha \oplus \beta =\operatorname {mex} (\{\alpha '\oplus \beta$$ :\alpha '<\alpha \}\cup \{\alpha \oplus \beta ':\beta '<\beta \}\cup \{\alpha '\oplus \beta ':\alpha '<\alpha \wedge \beta '<\beta \wedge \alpha '+\beta =\alpha +\beta '\}).} 各On _p の構造はω ^{ω ω}以下で同様です。ωまでの 2 次拡張の系列に続き、各素数次数について各ω ^{ω n}までの拡張が行われ、 ω ^{ω ω}が最小の超越元となります。有限の数値は、すべてのnに対してGF( p ^{2 n} )の直接極限を形成し、異なる Fermat pべき乗 ( [ p ^{2 n} ]の形の数の積がそれらの通常の積となり、Fermat pべき乗の 2 乗は、原始元が存在するように定義されます。例えば、 On ₃の場合、 3 ² = 2、9 2 = 4、 n ≥ 2の場合[3 ^{2 n} ] ² = 3 ^{2 n −1}とすることができます。 ω ^{ω ω}より小さい数に対する規則を含む、 p^を法とする nim 加算と nim 乗算の一般的な定義が記述されています。 ^{[ 3 ]}

また、 On _pの帰納的定義を用いて、標数 0 のOn ₀を定義することも可能である。この場合、最小の体はω ^ωより小さい順序数であり、有理数と同型である。^{[ 3 ]}

• シュールな数字