无偏数

在组合博弈论中, 无偏数 (也称 Nim 数) 是用来描述正常无偏博弈 (例如取石子游戏) 的数. 大致来说, 无偏数形如 $\ast n$, 其中 $n$ 是序数 (称为它的编号), 它在取石子游戏中对应于由 $n$ 个石子构成的一堆 (如 $n$ 有限). 如写成游戏局面的形式, 则可以归纳地写为 (竖线的两边表示双方行动后的所有可能状态)$$\ast n=\{\ast 0,\cdots ,\ast (n-1)\mid \ast 0,\cdots ,\ast (n-1)\},$$也就是说任意一方取石子后, 局面会变成有更少石子的一堆. $\ast 0=\{\mid \}$ 则是无人可动, 先行动者输的局面. 与此同时, 任意正常无偏博弈的局面均等价于某个无偏数 $\ast n$.

无偏数可以用类似于超现实数的方法定义加法和乘法. 无偏数的加法对应于局面的和, 且可以显式地写为它对应编号的异或和. 无偏数的乘法不太直观, 且伴有一些奇特的现象 (例如可以证明 $(\ast \omega {)}^3=\ast 2$). 由此, 全体无偏数构成特征为 $2$ 的域, 记作 ${\mathbf{On}}_2$, 且编号小于某些序数的数会构成它的子域. 例如对每个自然数 $n$, 编号小于 $2^{2^n}$ 的无偏数构成有限域, 每一个都是前一个的二次扩张; 编号小于 $\omega$ 的无偏数构成对二次扩张封闭的域; 编号小于 ${\omega }^{{\omega }^{\omega }}$ 的无偏数构成 ${\mathbb{F}}_2$ 的代数闭包.

1定义

显式定义

我们首先给出无偏数和它的加法、乘法的显式定义.

定义 1.1 (无偏数). 无偏数指的是形如 $\ast n$ 的数, 其中 $n$ 是序数, 称为它的编号.

为定义加法与乘法, 我们引入以下记号.

定义 1.2 (最小排除). 对由无偏数构成的类 $X$, 记 $\mathrm{mex}(X)$ 为编号最小的无偏数 $\ast k$, 使得 $\ast k\notin X$. 特别地, $\mathrm{mex}(\varnothing )=0$.

定义 1.3 (加法). 使用超限归纳法. 定义

•	$\ast m+\ast n=\mathrm{mex}(\{\ast m^{\prime }+\ast n,\ast m+\ast n^{\prime }\mid m^{\prime }<m,n^{\prime }<n\})$.

定义 1.4 (乘法). 使用超限归纳法, 定义

•	$\ast m\cdot \ast n=\mathrm{mex}(\{\ast m^{\prime }\cdot \ast n+\ast m\cdot \ast n^{\prime }-\ast m^{\prime }\cdot \ast n^{\prime }\mid m^{\prime }<m,n^{\prime }<n\})$.

使用局面

显式定义虽然简洁却不太直观, 以下给出使用局面的定义, 可以由此看出与超现实数的相似性.

定义 1.5 (无偏数). 无偏数是通过以下归纳构造可构造出的数.

•	如集合 $X$ 中的所有元素都是无偏数, 则局面 $\{X\mid X\}$ 是无偏数.
•	如果两个无偏数对应的局面等价, 则它们视为相等的.

一类特殊的局面记为 $\ast n$.

定义 1.6 ($\ast n$). 对序数 $n>0$, 归纳定义局面 $\ast n$ 为$$\{\{\ast n^{\prime }\mid n^{\prime }<n\}\mid \{\ast n^{\prime }\mid n^{\prime }<n\}\}.$$

以下的 “最小排除原理” 保证了所有无偏数必与某 $\ast n$ 相等.

定理 1.7 (最小排除原理). 如集合 $X$ 中只含有形如 $\ast n$ 的无偏数, 则 $\{X\mid X\}=\mathrm{mex}(X)$.

无偏数的加法与乘法即是局面的加法与乘法.

定义 1.8 (加法与乘法). 记 $x=\{X\mid X\}$, $y=\{Y\mid Y\}$, 则

•	$x+y:=\{\{x^{\prime }+y,x+y^{\prime }\}\mid \{x^{\prime }+y,x+y^{\prime }\}\}$.
•	$x\cdot y:=\{\{x^{\prime }y+x{y}^{\prime }-x^{\prime }{y}^{\prime }\}\mid \{x^{\prime }y+x{y}^{\prime }-x^{\prime }{y}^{\prime }\}\}$. 其中 $x^{\prime }$ 取遍 $X$, $y^{\prime }$ 取遍 $Y$.

由以上的最小排除原理可以看出, 两种定义的加法与乘法是相同的.

2性质

域论性质

命题 2.1 (加法的描述). 任何序数均可以唯一地写成 $2^{{\alpha }_1}+2^{{\alpha }_2}+\cdots +2^{{\alpha }_n}$ 的形式, 其中 ${\alpha }_1>\cdots >{\alpha }_n$, $n$ 有限. 以此建立序数与序数的有限子集的联络. 我们断言: $\ast \alpha +\ast \beta$ 的编号为 $\alpha ,\beta$ 所对应的集合的对称差所对应的序数.

命题 2.2 (${\mathbf{On}}_2$ 是域). ${\mathbf{On}}_2$ 是一个域.

证明.

证明. 可以直接验证除了逆元存在以外的其它性质, 这里着重说明逆元的存在性.

固定无偏数 $\ast \alpha$. 定义 $T$ 为满足如下性质的最小集合:

•	$\ast 0\in T$;
•	若 $\ast \beta \in T,\gamma <\alpha$, 则 $\ast {\gamma }^{-1}\cdot (\ast 1+(\ast \alpha +\ast \gamma )\ast \beta )\in T$.

此时, 我们断言 $\ast {\alpha }^{-1}=\mathrm{mex}(T)$. 断言的证明可以通过直接验证乘法定义中构建的集合包含 $0$ 而不含 $1$ 来实现.

$\square$

命题 2.3 (${\mathbf{On}}_2$ 中的平方根). 每一个无偏数都有其平方根.

证明.

证明. 固定无偏数 $\ast \alpha$. 定义 $T$ 为满足如下性质的最小集合:

•	对于 $\beta <\alpha$, $\sqrt{\ast \beta }\in T$;
•	对于 $\ast {\gamma }_1\ne \ast {\gamma }_2\in T$, $\frac{\ast {\gamma }_1\ast {\gamma }_2+\ast \alpha }{\ast {\gamma }_1+\ast {\gamma }_2}\in T$.

此时, 我们断言 $\sqrt{\ast \alpha }=\mathrm{mex}(T)$, 其证明可以类似地验证.

$\square$

命题 2.4 (${\mathbf{On}}_2$ 的代数闭性). ${\mathbf{On}}_2$ 是代数闭域.

命题 2.5 (${\mathbf{On}}_2$ 的万有性). 任意集合层面的 $2$ 特征域均同构于 ${\mathbf{On}}_2$ 的子域.

扩张性质

(...)

${\omega }^{{\omega }^{\omega }}$ 以内的序数与 ${\alpha }_p$ 的性质

(...)

定理 2.6. 在 ${\mathbf{On}}_2$ 中, 编号最小的, 与编号小于之的无偏数代数无关的无偏数是 ${\omega }^{{\omega }^{\omega }}$.

${\omega }^{{\omega }^{\omega }}$ 以外的性质

(...)

猜想 2.7. 在 ${\mathbf{On}}_2$ 中, 编号次小的, 与编号小于之的无偏数代数无关的无偏数是 $\phi (\omega ,0)$. 其中 $\phi$ 是 Veblen $\phi$ 记号.

3相关概念

术语翻译

无偏数 • 英文 impartial number, nimber