Surreal Number

Pentiment · 2025-04-29 16:12:21 · 算法·理论

下文用 SN 代指 Surreal Number（超现实数）。

非常好递归，使我大脑旋转。

SN 的构造

SN 的构造基于 ZF 公理体系和以下定义：

定义 x=\{x_L\mid x_R\} 是 SN，其中 x_L,x_R 是之前已定义过的 SN（即定义不会出现环，避免类似罗素悖论的情况），并满足 \forall l\in x_L,r\in x_R,r\not\le l。

定义 SN x\le y，如果 \forall l\in x_L,y\not\le l，且 \forall r\in y_R,r\not\le x。这是一个全序关系（在后面会证明）。

定义 x\ge y，如果 y\le x。

定义 x=y，如果 x\le y 且 x\ge y，这是一个等价关系。

定义 x<y，如果 x\le y 且 y\not\le x。同样可以定义 y>x。这一点看似多余，但实际上在未确定 \le 是否是全序的情况下，这样定义很有必要。

定义 0=\{\mid\}。由此可以定义：

然而 \{0\mid0\} 并不满足 SN 的定义（由于 0\le 0）。因此我们得到了两个新的数：\{0\mid\} 和 \{\mid0\}，满足 \{\mid0\}<0<\{0\mid\}，不妨定义 -1:=\{\mid0\},1:=\{0\mid\}。

进一步地，我们可以得到以下合法的 SN：

其中有很多等价表示，例如 \{\mid1\} 和 0，有 0\le\{\mid1\} 且 \{\mid1\}\le0，故 \{\mid1\}=0。按照等价类划分：

可以发现负数和正数的等价类恰好是对称的：交换 x_L,x_R 并将每个元素取负。

证明 \le 是偏序

记 \text{rank}(x) 表示从 0 构造出 x 需要多少步，例如 \text{rank}(0)=0，\text{rank}\left(\dfrac12\right)=2。所有 SN 都是通过递归定义的，故 \max\limits_{l\in x_L}\{\text{rank}(l)\},\max\limits_{r\in x_R}\{\text{rank}(r)\} 均小于 \text{rank}(x)，且 \text{rank}(x) 具有下界 0，启示我们使用无限递降法反证。

偏序 \le 需要满足以下三个条件：

1. 自反性：x\le x；
2. 反对称性：x\le y\land y\le x\Rightarrow x=y；
3. 传递性：x\le y\land y\le z\Rightarrow x\le z。

先证明传递性。

假设有 x\le y,y\le z,x\not\le z。根据 \le 的定义，有 \exists l\in x_L,z\le l 或 \exists r\in z_R,r\le x。同时有 y\not\le l 且 r\not\le y。

那么有 y\le z,z\le l,y\not\le l 或者 r\le x,x\le y,r\not\le y，即得到了 \text{rank} 之和更小的不满足传递性的三元组。这个过程可以一直进行下去直到 0，但 0 是满足传递性的，因此这是不可能的。\square

再证明自反性。

假设 x\not\le x，有 \exists l\in x_L,x\le l 或 \exists r\in x_R,r\le x。

对于第一种情况，有 \forall x'\in x_L,l\not\le x'，当然 l 也涵盖在内，故 l\not\le l，且 \text{rank}(l)<\text{rank}(x)，由无限递降法可得矛盾。第二种情况同理。\square

容易证明 = 是等价关系，从而反对称性也成立。

x 与 x_L 和 x_R 的关系

定理：\forall l\in x_L,l\le x；\forall r\in x_R,x\le r。

若 \exists l\in x_L,l\not\le x，则 \exists l'\in l_L,l'\ge x 或 \exists r\in x_R,r\le l，而后者违背了定义。对于前者，有 \forall x'\in x_L,l'\not\le x'，当然 l 也涵盖在内，故 l'\not\le l，由无限递降法可得矛盾。r 的情况同理。\square

因此可以将 x 看作是一个“夹在”x_L 和 x_R 之间的数。

证明 \le 是全序

即要证明 x\not\le y\Rightarrow y\le x。

根据定义，有 \exists l\in x_L,y\le l 或 \exists r\in y_R,r\le x。若 y\le l，由于 l\le x，有 y\le x；若 r\le x，由于 y\le r，有 y\le x。\square

证明了 \le 是全序，那就可以直接把 x\not\le y 记作 x>y 了。

因此，我们可以得到 x<y\vee x=y\vee x>y。

SN 的运算

首先定义加法。

定义 x+y 为 \{(x_L+y)\cup(y_L+x),(x_R+y)\cup(y_R+x)\}，其中 SN 的集合 S 和 SN x 的加法为 S+x:=\{s+x\mid s\in S\}。可以验证其满足封闭性、交换律和结合律，0 为加法单位元。

这样定义的 + 是保序的，即 x\le y\Leftrightarrow x+z\le y+z。证明的话，把定义拆开来逐个反证即可。

定义负数 -x=\{-x_R\mid-x_L\}，其中集合取负 -S=\{-s\mid s\in S\}。记 x-y=x+(-y)，可以验证 x-x=0。

再来定义乘法。

定义 x\cdot y=\{(x_L\cdot y+x\cdot y_L-x_L\cdot y_L)\cup(x_R\cdot y+x\cdot y_R-x_R\cdot y_R)\mid(x_L\cdot y+x\cdot y_R-x_L\cdot y_R)\cup(x_R\cdot y+x\cdot y_L-x_R\cdot y_L)\}。可以验证其满足封闭性、交换律、结合律和对加法的分配律，1 为乘法单位元。

定义乘法逆元 \dfrac 1x 满足 x\cdot\dfrac 1x=1，记 \dfrac xy=x\cdot\dfrac 1y。因此超现实数构成了一个域，记作 \text{No}。

\text{No} 和 \mathbb R

首先容易构造出 \mathbb Z：有 a+1=\{a\mid\}，使用皮亚诺公理即可。

可以定义 \{0\mid1\}=\dfrac12，\left\{\left.\dfrac12\right|1\right\}=\dfrac34 等等，故可以构造出所有形如 \dfrac{x}{2^k} 的数。

然后可以使用二进制展开的方法定义出所有实数，例如 \pi=\left\{\left.3,\dfrac{25}{8},\dfrac{201}{64},\dots\right|4,\dfrac72,\dfrac{13}{4},\dfrac{51}{16},\dots\right\}。

还能验证如上的定义是保序保运算的，因此 \mathbb R 可以完全嵌入 \text{No} 中。

直到无穷

在 \text{No} 中还能定义出不属于 \mathbb R 的元素。在迭代无限次后，我们会得到这样一个数：\omega=\{1,2,3,\dots\mid\}，左边是全体自然数。它确实满足 SN 的定义，但它又比 \omega_L 中的任意元素，即任意自然数大，它不存在于 \mathbb R 中。

但它并不是 \text{No} 中最大的数，1+\omega=\{\omega,2,3,\dots\mid\} 就比它大。注意 SN 的运算和序数的运算并不完全相同，SN 的加法、乘法满足交换律，而序数的运算不满足。

以此类推，我们还会有 2+\omega,3+\omega,\dots，直到 \omega+\omega，甚至 \omega\cdot\omega 和 \omega^\omega 这样的东西都会出现。

事实上，\text{No} 是最大的有序域，任意一个有序域都是 \text{No} 的子域。

后面再咕咕咕这个和非平等博弈的关系吧。