BMS的良序性

我们给出 BMS 良序性的证明过程。^[1]^[2]

定义在 BMS 中给出如下定义和约定：

(1) 列和行均从 0 开始数起。例如 $(000) (111)$ 的 $(000)$ 是第 0 列。

(2) $A$ ：一般指一个 BMS。

(3) $A [n]$ ：一般指 $A$ 的基本列第 $n$ 项。

(4) $G$ ：一般指“好部”。

(5) $B_{x}$ ：一般指“坏部”，其中 $B_{0}$ 一般指最前面的“坏部”。

(6) $C$ ：一般指 $A$ 的最后一列。

(7) $A_{1} + A_{2}$ ：指把 $A_{2}$ 连接在 $A_{1}$ 的后面，例如 $(000) (111) + (222) (333) = (000) (111) (222) (333)$ 。

(8) $m$ 父项：列 $i$ 是列 $j$ 的 $m$ 父项当且仅当 $i < j$ ，列的第 $m$ 个元素小于列 $j$ 的第 $m$ 个元素，当 $m > 0$ 时还需列 $i$ 是列 $j$ 的 $m - 1$ 祖先，同时是满足此定义中的最大者。若不存在这样的列 $i$ ，则列 $j$ 没有 $m$ 父项。

(9) $m$ 祖先：列 $i$ 是列 $j$ 的 $m$ 祖先当且仅当列 $i$ 是列 $j$ 的 $m$ 父项或列 $i$ 是列 $j$ 的 $m$ 父项的 $m$ 祖先。（即列 $j$ 的 $m$ 父项，列 $j$ 的 $m$ 父项的 $m$ 父项，列 $j$ 的 $m$ 父项的 $m$ 父项的 $m$ 父项……）例如：在 $(000) (111) (220) (331)$ 中， $(220)$ 是 $(331)$ 的 0 父项、1 父项、2 父项，因此也是 $(331)$ 的 0 祖先、1 祖先、2 祖先。 $(111)$ 是 $(220)$ 的 0 父项、1 父项，但不是 $(220)$ 的 2 父项。因此， $(111)$ 是 $(331)$ 的 0 祖先、1 祖先，但不是 2 祖先。

(10) 一个非空的 BMS 可以写成这样的形式： $A = G + B_{0} + C$ ，其基本列第 $n$ 项可以写为 $A [n] = G + B_{0} + \dots + B_{n}$ 。其中， $B_{0}$ 的第 0 列是 $C$ 的 $m_{0}$ 父项，若 $m_{0}$ 无定义，则 $B_{0}$ 为空。

(11) 提升：设 $D$ 为 $B_{0}$ 中的一列，若 $D$ 为 $B_{0}$ 的第 0 列或 $B_{0}$ 的第 0 列是 $D$ 的 $m$ 祖先，则 $D$ 的第 $m$ 个元素称为提升的（这一定义与原文不同，为行文方便做了修改）。 $B_{i}$ 是 $B_{0}$ 的一个复制，但是每个满足行标 $m < m_{0}$ 的提升的元素都要增加 $i \times (C$ 的第 $m$ 个元素 $- B_{0}$ 首列的第 $m$ 个元素 $)$ 。

引理 1 BMS 在字典序下是全序的。

这定理说的是，任何两个 BMS 都可以比大小。关于这一定理的详细证明从略。

进一步有 BMS 的如下性质：

引理 2 设 $A = G + B_{0} + C$ 是一个非空的 BMS， $n$ 是一个自然数， $l_{0}, l_{1}$ 分别为 $G, B_{0}$ 的长度。则有以下五点成立：

(1) 任取 $i < l_{0}, j < l_{1}, k \in ℕ$ ， $G$ 的第 $i$ 列是 $B_{0}$ 的第 $j$ 列的 $k$ 祖先当且仅当 $G$ 的第 $i$ 列是 $B_{n}$ 的第 $j$ 列的 $k$ 祖先。

(2) 任取 $i, j < l_{1}, k \in ℕ$ ， $B_{0}$ 的第 $i$ 列是 $B_{0}$ 的第 $j$ 列的 $k$ 祖先当且仅当 $B_{n}$ 的第 $i$ 列是 $B_{n}$ 的第 $j$ 列的 $k$ 祖先。

(3) 设 $n > 0, i < l_{1}, k < m_{0}$ ， $B_{0}$ 的第 $i$ 列是 $C$ 的 $k$ 祖先当且仅当 $B_{n - 1}$ 的第 $i$ 列是 $B_{n}$ 第 $0$ 列的 $k$ 祖先。

(4) 设 $0 < i < l_{1}$ ， $B_{n}$ 的第 $i$ 列的 $k$ 父项只会在 $G$ 或 $B_{n}$ 中。

(5) 任取 $i, j < l_{1}, k \in ℕ, n_{0} < n_{1} < n$ ， $B_{n_{0}}$ 的第 $i$ 列是 $B_{n_{1}}$ 的第 $j$ 列的 $k$ 祖先当且仅当 $B_{n_{0}}$ 的第 $i$ 列是 $B_{n_{1} + 1}$ 的第 $j$ 列的 $k$ 祖先。

（注意，以上的列是从第 0 列开始数的）

证明：用数学归纳法，先证明 $k = 0$ 时定理 2 成立，再假设对所有 $k^{'} < k$ ，定理 2 成立（五条全部成立），尝试说明此时定理 2 对 $k$ 成立。

先考虑 $k = 0$ 的情况：

首先证明 (2)： $j = 0$ 时 $B_{0}$ 的第 $j$ 列在 $B_{0}$ 当中不会有祖先（因为它自己就是 $B_{0}$ 最左的一列），因此结论平凡成立。 $j > 0$ 时，若 $m_{0} = 0$ ，则 $B_{0} = B_{n}$ ；若 $m_{0} > 0$ ，不难看出 $B_{0}$ 中每一列的第 0 个元素都是提升的，因此 $B_{0}$ 和 $B_{n}$ 当中的 0 祖先关系保持一致，此时 (2) 成立。

(3)：与 (2) 类似，因为假设了 $m_{0} > 0$ ，因此 $B_{n}$ 的第 0 个元素不会比 $C$ 的第 0 个元素小。

(4)： $B_{0}$ 的第 0 列一定是 $B_{0}$ 的第 $i$ 列的 0 祖先，因此，用 $k = 0$ 时的 (2)，可得 $B_{n}$ 的第 0 列也是 $B_{n}$ 的第 $i$ 列的 0 祖先。因此， $B_{n}$ 第 $i$ 列的 0 父项自然也会在 $B_{n}$ 中。

(1)：显然，只需注意到若 $G$ 中第 $i$ 列是 $B_{0}$ 中某列的 0 祖先，则任何 $B_{x}$ 中都不会有比其第 0 个元素小的列。

(5)：与 (1) 类似，显然。

接下来，假设定理 2 对 $k^{'} < k$ 成立，考虑 $k$ 的情况：

(2)： $j = 0$ 时显然。 $j > 0$ 时设 $I$ 为 $B_{0}$ 第 $j$ 列的 $k - 1$ 祖先的列号组成的集合（例如若 $B_{0}$ 是 $(00) (11) (22)$ ， $k = 1$ ，则此时的 $I = {0, 1}$ ），则显然有 $i \in I$ ，此时有两种情况。

情况一： $B_{0}$ 的首列是 $B_{0}$ 第 $j$ 列的 $k$ 祖先，则此时第 $j$ 列的第 $k$ 个元素就是提升的，同时，第 $i$ 列的第 $k$ 个元素也是提升的，因为要么 $i = 0$ ，要么首列也是第 $i$ 列的一个 $k$ 祖先。不难看出，此时所有 $I$ 中的列，第 $k$ 个元素都是提升的。因此在 $B_{n}$ 当中，若第 $j$ 列的第 $k$ 个元素有增加，则 $I$ 中其他列的第 $k$ 个元素也得到了同样的增加，又由于归纳假设， $B_{n}$ 中第 $j$ 列的 $k - 1$ 祖先也都是序号在 $I$ 中的那些列，因此 $B_{n}$ 中的祖先关系与 $B_{0}$ 中保持一致。

情况二： $B_{0}$ 的首列不是 $B_{0}$ 第 $j$ 列的 $k$ 祖先，则第 $j$ 列的第 $k$ 个元素是不提升的，且任何 $k$ 祖先所在列的第 $k$ 个元素也是不提升的。又由归纳假设，在 $B_{n}$ 当中祖先关系与 $B_{0}$ 中保持一致。（反过来， $B_{n}$ 推出 $B_{0}$ 也是类似的，第 $k$ 个元素要提升则整个 $I$ 一起提升，若不提升则所有第 $j$ 列的 $k$ 祖先对应的第 $k$ 个元素都不提升。）

(3)：与 (2) 类似， $k < m_{0}$ 保证了 $B_{1}$ 的第 0 个元素不会比 $C$ 的小。

(4)：若存在 $k^{'} < k$ ，使得 $B_{n}$ 第 $i$ 列的 $k^{'}$ 父项在 $G$ 中，则 $B_{n}$ 第 $i$ 列的 $k$ 父项也必然在 $G$ 中。配合归纳假设，设对所有 $k^{'} < k$ ， $B_{n}$ 第 $i$ 列的 $k^{'}$ 父项都在 $B_{n}$ 中。若存在某个 $k^{'}$ 使得 $B_{n}$ 的首列不是第 $i$ 列的 $k^{'}$ 祖先，则使用归纳假设，可知第 $i$ 列所有的 $k^{'}$ 祖先均在 $G$ 或 $B_{n}$ 中，因此它的 $k$ 父项也必然在其中。若对任意的 $k^{'} < k$ ，都有 $B_{n}$ 的首列是第 $i$ 列的 $k^{'}$ 祖先，假设 $B_{n}$ 的第 $i$ 列的 $k$ 父项不在 $B_{n}$ 中，我们证明它一定在 $G$ 中。若 $B_{n}$ 的第 $i$ 列的 $k$ 父项不在 $B_{n}$ 中，则 $B_{n}$ 的首列不是第 $i$ 列的 $k$ 祖先。因此，第 $i$ 列的第 $k$ 个元素一定是不提升的，它与 $B_{0}$ 的第 $i$ 列第 $k$ 个元素相等。由 (ii) 可知， $B_{0}$ 中也不存在某列是第 $i$ 列的 $k$ 父项，因此它的 $k$ 父项一定在 $G$ 中。同时，对于 $B_{0}$ 中所有第 $i$ 列的 $k - 1$ 祖先，它们的第 $k$ 个元素一定会大于等于第 $i$ 列的第 $k$ 个元素，因此也大于等于 $B_{n}$ 第 $i$ 列的第 $k$ 个元素。因此，若 $B_{n}$ 第 $i$ 列的 $k$ 父项不在 $B_{n}$ 中，那么它也会是 $B_{n}$ 首列的一个 $k$ 祖先。当 $k \geq m_{0}$ 时， $B_{n}$ 首列的 $m_{0}$ 父项就已经在 $G$ 中了，与我们的假设矛盾。当 $k < m_{0}$ 时，由于 $B_{0}$ 的首列是 $C$ 的 $m_{0}$ 父项，因此也是 $C$ 的 $k$ 祖先，反复使用 (iii) 可得对每个 $m > 0$ ， $B_{m - 1}$ 的首列都是 $B_{m}$ 首列的 $k$ 祖先。设存在 $n^{'} < n$ 使得 $B_{n}$ 第 $i$ 列的 $k$ 父项在 $B_{n^{'}}$ 中，则由于此列和 $B_{n^{'}}$ 的首列均为 $B_{n}$ 首列的 $k$ 祖先，因此 $B_{n^{'}}$ 的首列也会是此列的 $k$ 祖先，而这是不可能的（ $B_{n^{'}}$ 的首列的第 $k$ 个元素严格大于此列的第 $k$ 个元素）。

(1)：若 $B_{0}$ 的首列是第 $j$ 列的 $k$ 祖先，则也是 $B_{n}$ 第 $j$ 列的 $k$ 祖先，此时 (i) 成立。若 $B_{0}$ 的首列不是第 $j$ 列的 $k$ 祖先，由 (iv) 可知 $B_{n}$ 第 $j$ 列的 $k$ 祖先只在 $B_{n}$ 和 $G$ 中，由于此时 $B_{0}$ 第 $j$ 列第 $k$ 个元素不提升，因此 $G$ 中最右边的祖先列也会是 $B_{0}$ 第 $j$ 列的 $k$ 祖先，此时 (i) 成立。

(5)：若 $B_{n_{0}}$ 的第 $i$ 列是 $B_{n_{1}}$ 的第 $j$ 列的 $k$ 祖先，则由 (iv)， $B_{n_{1}}$ 的首列也是 $B_{n_{1}}$ 的第 $j$ 列的 $k$ 祖先，因此 $B_{n_{0}}$ 的第 $i$ 列是 $B_{n_{1}}$ 的首列的 $k$ 祖先。若 $k \geq m_{0}$ ，则与 $B_{n_{1}}$ 的首列的 $k$ 父项在 $G$ 中矛盾。若 $k < m_{0}$ ，则可以使用 (iii)，得到 $B_{n_{0}}$ 的第 $i$ 列是 $B_{n_{1} + 1}$ 的首列的 $k$ 祖先，再由 (ii) 可得结论，反过来的方向也类似。

利用数学归纳法，在每一层都是 2、3 推出 4，2、3、4 推出 1、5，因此我们就证明了全部的结论。

然后是关于稳定序数的定理。记 $⟨ L_{α}, \in ⟩$ 是第 $α$ 个可构造宇宙层级， $M ⪯_{Σ_{n}} N$ 代表 $M$ 是 $N$ 的 $Σ_{n}$ 初等子结构。记 $α \leq_{n} β$ 代表 $⟨ L_{α}, \in ⟩ ⪯_{Σ_{n + 1}} ⟨ L_{β}, \in ⟩$ ，特别的， $α \leq_{n} O r d$ 代表 $⟨ L_{α}, \in ⟩ ⪯_{Σ_{n + 1}} ⟨ L, \in ⟩$ 。记 $σ$ 是最小的序数使得存在 $β$ ，有任取 $n \in ℕ$ ，都有 $σ \leq_{n} β$ 成立。

引理 3 任取 $α, β \in σ$ ， $n \in ℕ$ ，若 $ω < α <_{n} β$ ，任取 $X, Y$ 为有限集，满足 $γ < α \leq δ < β$ 对任意的 $γ \in X, δ \in Y$ ，存在一个序数集合 $Y^{'}$ 和一个双射 $f : Y \to Y^{'}$ 对任意 $γ \in X, δ_{0}, δ_{1} \in Y, n \in ℕ, m < n$ 有以下五条性质:

(1) $γ < f (δ_{0}) < α$ .

(2) $γ <_{k} δ_{0} \to γ <_{k} f (δ_{0})$ .

(3) $δ_{0} < δ_{1} \to f (δ_{0}) < f (δ_{1})$ .

(4) $δ_{0} <_{k} δ_{1} \to f (δ_{0}) <_{k} f (δ_{1})$ .

(5) $δ_{0} <_{m} β \to f (δ_{0}) <_{m} α$

证明这一引理的思路是构造一个合适的 $Σ_{n + 1}$ 公式，它能反应我们想要的性质，同时使得它可以在 $L_{β}$ 中验证为真 (代入 $Y$ 中的元素)，因此它在 $L_{α}$ 中也为真，能使得它为真的那组参数就组成了 $Y^{'}$ 。

证明：记 $γ_{0}, \dots, γ_{| X | - 1} \in X$ 为固定参数，记 $φ_{0} (η, ξ)$ 为 $η < ξ$ ， $φ_{1} (η, ξ, k)$ 为 $η <_{k} ξ$ ， $φ_{2} (η, k)$ 为 $η <_{k} O r d$ 。则 $φ_{0}$ 是 $Σ_{0}$ 公式， $φ_{1}$ 是 $Σ_{1}$ 公式，文章[2]的定理 1.8 证明了 $φ_{2}$ 是 $Π_{k + 1}$ 公式，因此也是 $Σ_{k + 2}$ 公式。由于 $k < n$ ，这三条公式全都是 $Σ_{n + 1}$ 公式。由于这里提到的所有序数都在 $σ$ 之下，因此任取 $η, ξ \in X \cup Y$ ，都只有有限个 $k$ 使得 $φ_{1} (η, ξ, k)$ 成立。因此，只有有限个句子 $φ_{0} (γ_{i}, ζ_{j}), φ_{1} (γ_{i}, ζ_{j}, k), φ_{0} (ζ_{i}, ζ_{j}), φ_{1} (ζ_{i}, ζ_{j}, k), φ_{2} (ζ_{i}, m)$ 在代入 $δ_{i}$ 为 $Y$ 中第 $i$ 小的元素时为真。记 $φ$ 为这些句子的合取，则 $φ$ 为 $Σ_{n + 1}$ 公式。同时令 $ψ$ 为断言所有这些 $ζ_{i}$ 为序数的句子，则 $φ \land ψ$ 为 $Σ_{n + 1}$ 公式。最后，句子 $\exists ζ_{0} \exists ζ_{1} \dots \exists ζ_{| Y | - 1} (φ \land ψ)$ 也是 $Σ_{n + 1}$ 公式。在 $L_{β}$ 中，把 $Y$ 中的元素代入，就知道这个句子是真的。又因为 $α <_{n} β$ ，可知在 $L_{α}$ 中这个句子也是真的。因此， $L_{α}$ 中使得这个句子为真的那些取值组合成 $Y^{'}$ ， $Y$ 和 $Y^{'}$ 之间自然的序同构记为 $f$ ，则引理 3 成立。(例如第一条，在 $L_{α}$ 中取 $ζ_{j}$ 为 $f (δ_{j})$ ， $φ_{0} (γ_{i}, ζ_{j})$ 就是说 $γ_{i} < f (δ_{j})$ ，也即第一条性质成立，其他四条也可以用类似的方式得到。)

综合上述两条定理，我们就可以证明 BMS 的良序性

定理 BMS 在字典序下是良序的。

证明的思路是构造一个映射 $o : B M S \to O r d$ ，只需证明该映射是保序的即可。定义BMS 的稳定表示函数：设 $A$ 为一个 $n$ 列的 BMS，一个函数 $f : n \to O r d$ 是 $A$ 的稳定表示，当且仅当对任意的 $i < j < n$ ，有 $f (i) < f (j)$ 且若 $A$ 的第 $i$ 列为第 $j$ 列的 $m$ 祖先，则 $f (i) <_{m} f (j)$ 。可以看出，同一个 BMS，对应的稳定表示函数可以有很多。例如任何满足 $α <_{0} β$ 的序数 $α$ 和 $β$ ， $f (0) = α, f (1) = β$ 都可以作为 (0)(1) 的稳定表示函数。

定义 $o (A)$ 为最小的序数 $α$ 使得存在一个 $A$ 的稳定表示函数 $f$ ，满足 $f (n - 1) \leq α$ 。为方便起见，记 $B M S [n] = (0 \dots 0) (1 \dots 1)$ 共 $n$ 个 0 和 $n$ 个 1 ， $X_{n} = {B M S [i_{0}] [i_{1}] \dots [i_{n}]}$ .为方便起见，记 $B M S [n] = (0 \dots 0) (1 \dots 1)$ ，共 $n$ 个 0 和 $n$ 个 1， $X_{n} = {B M S [i_{0}] [i_{1}] \dots [i_{n}]}$ .

证明：(对展开次数做归纳) 首先证明 $o$ 在 $X_{0}$ 上是保序的，随后证明若 $o$ 在 $X_{n}$ 是保序的，则 $o$ 在 $X_{n + 1}$ 上是保序的。这样就证明了 $o$ 是保序的。

对 $X_{0}$ ，不难看出若 $α_{n}$ 是最小的满足存在 $β_{n}$ ，使得 $α_{n} <_{n - 1} β_{n}$ ，则 $o ((0 \dots 0) (1 \dots 1)) = β_{n}$ （共 $n$ 个 0， $n$ 个 1 ）。因此，显然有 $o$ 在 $X_{0}$ 上保序。

设 $o$ 在 $X_{n}$ 上保序，想证明 $o$ 在 $X_{n + 1}$ 上保序。任取非空的 BMS $A \in X_{n}$ ，设 $A$ 的长度为 $l$ 记 $f$ 是 $A$ 的稳定表示，使得 $o (A) \geq f (l - 1)$ 。记 $l_{n}$ 为 $A [n]$ 的长度，则 $f$ 限制在 $l_{0}$ 上就是 $A [0]$ 的一个稳定表示，记为 $f_{0}$ 。接下来，我们将递归构造 $A [n]$ 的稳定表示 $f_{n}$ 。

设 $f_{k}$ 为 $A [k]$ 的稳定表示，且将 $B_{k}$ 对应的列号映射到 $B_{0}$ 对应的列号在 $f$ 下的像。设 $α$ 为 $B_{0}$ 的首列的列号在 $f$ 下的像， $β$ 为 $A$ 的最后一列的列号在 $f$ 下的像。设 $Y$ 为 $B_{k}$ 对应的列号在 $f_{k}$ 下的像集， $X$ 为 $B_{k}$ 之前的列号在 $f_{k}$ 下的像集 (因此， $X$ 可能为空，但 $Y$ 一定非空) 。由于前述引理，存在那样的 $Y^{'}$ ，我们把 $B_{k}$ 对应的列号映射到 $Y^{'}$ 的对应元素， $B_{k + 1}$ 对应的列号映射到 $Y$ 的对应元素，其他列号的像不变，就得到了 $f_{k + 1}$ 。由于引理 2， $f_{k + 1}$ 是 $A [k + 1]$ 的一个稳定表示，同时它将 $B_{k + 1}$ 对应的列号映射到 $B_{0}$ 对应的列号在 $f$ 下的像。这样，我们就得到了所有的 $f_{n}$ ，同时，由于任取 $m < n$ $f_{n}$ 在 $l_{m}$ 处截断都能得到一个 $A [m]$ 的稳定表示，因此有 $m < n \to o (A [m]) < o (A [n]) < o (A)$ 。因此， $o$ 在 $X_{n + 1}$ 保序。

这样我们就得到了 $o$ 是保序的（因为任何 BMS 都可以由 BMS 极限取有限次基本列得到），因此 BMS 是良序的，证明完毕。

↑ VARGOVCIK S. Well-orderedness of the bashicu matrix system[A]. 2023.
↑ 小清新. 对 BMS 良序性证明的个人理解[EB/OL]. 2023. https://zhuanlan.zhihu.com/p/653719928.

[1] VARGOVCIK S. Well-orderedness of the bashicu matrix system[A]. 2023.

[2] 小清新. 对 BMS 良序性证明的个人理解[EB/OL]. 2023. https://zhuanlan.zhihu.com/p/653719928.

[1]

[2]