叉义叉重读 On Numbers and Games

· · 学习·文化课

事情是这样的。如果你不知道的话，这篇文章其实是翻译参考了 Conway 的 On Numbers and Games。最近刷 B 站发现了一个有趣的玩意：无限象棋的 \omega 步杀，这立刻让前几天正在研究超限序数的我把超限序数和博弈联系在了一起——而这听起来有点耳熟，事实上，也正是 ONaG 讨论的的内容。

上面的描述略过了中间研究 googology 和证明论的种种碰壁

Chapter 0

定义"数"——其实我们一般称为超现实数的概念。

为了避免读者在页面间跳转来跳转去，我们抄写一遍数的定义。

一个数 x 由两个数集合 x_L,x_R 构成，记作 \{x_L|x_R\}，其中不存在 d_1\in x_L\ge d_2\in x_R。

数遵循一般称之为"超限归纳法"的性质，即如果性质 P 满足 P(x_L),P(x_R) 能推出 P(x)（归纳）和 P(0)（奠基），那么任意数都满足性质 P。

称 x\le y 当且仅当

\begin{cases} \forall d\in x_L,d\not\ge y\\ \forall d\in y_R,d\not\le x \end{cases}

我们以后会把这简写成

\begin{cases} x_L\not\ge y\\ y_R\not\le x \end{cases}

定义

-x=\{-x_R|-x_L\}

定义

x+y=\{x_L+y,x+y_L|x_R+y,x+y_R\}

定义

xy =\{x_Ly+xy_L-x_Ly_L,x_Ry+xy_R-x_Ry_R| x_Ly+xy_R-x_Ly_R,x_Ry+xy_L-x_Ry_L\}

本文就不再验证这些运算的性质了。

由此我们可以定义

0=\{|\} 1=\{0|\} -1=\{|0\} 2=\{0,1|\} \dfrac 12=\{0|1\} \omega=\{0,1,2,\ldots|\} \dfrac1\omega=\left\{0|1,\frac12,\frac14,\ldots\right\} \dfrac13=\left\{\frac14,\frac14+\frac1{16},\ldots|\frac 12,\frac 12-\frac 18,\ldots\right\}

前面都很好理解。\dfrac 13 属于是有戴德金分割那味了。

一个有趣的工作是检验 \omega\cdot\frac1{\omega}=1。（请不要把这里的加法、乘法与序数运算混淆。那位甚至没有交换律。）

\omega\cdot\frac1{\omega}=\left\{0|\dfrac{\omega}{2^n}+\dfrac{m}{\omega}-\dfrac{m}{2^n}\right\}

直观讲（毕竟我们还没定义 \frac{\omega}{2^n}，只能凭借我们的直观认为 \frac{\omega-m}{2^n}\not\le 1），这玩意的右集合显然 \not\le 1，于是 1\le \omega\cdot \dfrac 1{\omega}；而 \omega\cdot\dfrac{1}{\omega}\le 1 则是显然的。谢天谢地。

剩下的一些好玩的构造如下。

\{0,1,2,\ldots|\omega\}+1=\omega \rightarrow\{0,1,2,\ldots|\omega\}=\omega-1 \{0,1,2,\ldots|\omega,\omega-1,\omega-2,\ldots\}=\dfrac{\omega}{2} \{0,1,2,\ldots|\omega,\dfrac{\omega}2,\dfrac{\omega}{4},\ldots\}=\sqrt\omega \left\{0|\dfrac 1\omega\right\}=\dfrac{1}{2\omega} \left\{\dfrac1\omega|1,\dfrac 12,\dfrac 14,\ldots\right\}=\dfrac 2{\omega} \left\{0|\dfrac{1}{\omega},\dfrac{1}{2\omega},\ldots\right\}=\dfrac{1}{\omega^2}

Chapter 1

对诸运算的性质的证明，证明了以上的数集 \mathbf{No} 是个域。skip。

Chapter 2 & 3

上面这些数字的定义看得我们头疼。而且除了爆试四则运算之外我们根本不能判断某个形如 \{x_L|x_R\} 的玩意该用什么形式表示。是时候终结这一问题了。

定理.（简单性定理）

如果 x_L\not\ge z\not\ge x_R 且 z_L,z_R 中的任何一个元素都不满足此条件，那么 x=z。

证明.

而如果后一条件不满足，即 $x\le z_L$，那么 $x_L\not\ge x\le z_L<z\not\ge x_R$，也就是 $x_L\not\ge z_L\not\ge x_R$，矛盾。 因此必有 $x\ge z$。反之亦然，必有 $x\le z$。故 $x=z$。

因此我们立即可以得到 \{2\frac12|998244353\}=3 和 \{\frac 14|1\}=\frac 12 等等。至少对于我们熟知的实数，世界清净了。

定理.

对于任何序数 \alpha，\alpha=\{\beta<\alpha|\}。

好好好这很序数。

对于每个序数 \alpha 我们定义 M_{\alpha} 为可以通过如下方式创造的数：x=\{x_L\in M_{\beta}|x_R\in M_{\beta}\}，其中 \beta<\alpha。我们把 M_{\alpha} 称为"第 \alpha 天及之前创造的数"。而 N_{\alpha}=M_{\alpha}/\bigcup_{\beta<\alpha}M_{\beta} 自然就是"第 \alpha 天创造的数。"

根据简单性定理，我们很容易可以得知，任何第 \alpha 天创造的数总可以通过 \bigcup_{\beta<\alpha}M_{\beta} 上的"戴德金分割"唯一确定。

事实上，选定 x\in N_{\alpha} 后，对于每个 \beta<\alpha，我们都可以制造一个 x 在 M_{\beta} 级别的近似 x_{\beta}\in N_{\beta}。x_0 总是 0，而 x_{\alpha}=x。对于 \gamma>\alpha，我们也认为 x_{\gamma}=x。

至此，通过 x_{\beta} 列的增长，我们已经可以给出每个 x 的唯一表示，但这还不够。我们考虑 x 和 x_{\beta} 的大小关系，这决定了我们在生成 x 时每一步是向左走还是向右走。这样，给出一列（可能有超限长度的）+,-,= 列，我们断言这就能唯一确定一个数。（应当很好证明。）这就让我们得到了那张著名的图片：

其中虚线标定的正是每个数的"所用天数"。

例如

\begin{bmatrix}0&1&2&\ldots\\ +&=&=&\ldots\end{bmatrix}=1 \begin{bmatrix}0&1&2&3&4&5&\ldots\\ +&-&+&-&+&-&\ldots\end{bmatrix}=\frac 23 \begin{bmatrix}0&1&2&\ldots&\omega&\ldots\\ +&+&+&\ldots&=&\ldots\end{bmatrix}=\omega \begin{bmatrix}0&1&\ldots&\omega&\omega+1&\ldots&\omega\cdot 2&\ldots\\ +&+&\ldots&-&-&\ldots&=&\ldots\end{bmatrix}=\frac\omega2

事实上，通过观察我们可以得出一种把任意数直接对应到 \pm 序列的方法。

至于将任意数的标准形式 \sum\omega^x\cdot r 写出来的方法，我们留待读者探索。（逃）

End of Chapter 3

最后，我们在整个域 \mathbf{No} 上进行戴德金分割，分割出来的元素称为隙（Gaps）。

（事实上这很危险。正如有理数这一可数集上的戴德金分割（实数集）是不可数的，\mathbf{No} 这一真类（众所周知包含全体序数就没法是集合了）上的戴德金分割甚至干碎了真类的概念，以至于在大多数集合论中都是一种非法的存在。）

幸好我们只会讨论一些很少的、健康的隙，如

\mathbf{On}=(\mathbf{No},\varnothing) \frac1{\mathbf{On}}=(0,\text{positive numbers}) \infin=(\mathbb{R}^{+},\text{positive infinite numbers}) \frac 1\infin=(\text{positive infinitesimals},\mathbb{R}^{+})

Chapter 4

未完待续