【硬核】集合论 - 序数 - 第八章 - PrSS&BMS

· · 算法·理论

这是这一系列的第八章，第七章在这。

由于不可抗力因素，我们需要先讲 PrSS，不讲这个理解 BMS 是困难的。

PrSS 形如 (a_1,a_2,\dots,a_n,\dots)。

一个序列作为一个合法的 PrSS，必要条件就是：

注意这仅仅是必要条件，有很多满足这个条件的可能不是那么合法。

首先我们定义好部、坏部和坏根：

  1. 最后一个比最后一个数小的数称作坏根；
  2. 坏根之后（含）的数是坏部（不含最后一个数）；
  3. 不是坏部且不是最后一个数的就是好部。

然后就是 PrSS 的展开规则：

  2. 若 a_n=1，则把 a_n 删去计算序数，再把计算完的结果 +1；
  3. 如果 a_n\not=1，则把好部保留，把最后一个数删去，把坏部无限重复，例如 (1,2) 展开成 (1,1,1,1,\dots)，(1,2,3) 展开成 (1,2,2,2,2,\dots)。

那么，开始扽西！

最简单的就是 (1,1,1,1,\dots)，有几个 1 就是几。

然后 (1,2) 是 \omega 个 1，所以是 \omega。

$(1,2,2,1)=\omega^2+1,(1,2,2,1,2)=\omega^2+\omega,(1,2,2,1,2,2)=\omega^22,(1,2,2,2)=(1,2,2,1,2,2,1,2,2,1,2,2,\dots)=\omega^3,(1,2,2,2,2)=\omega^4,(1,2,3)=(1,2,2,2,2,\dots)=\omega^\omega$。 $(1,2,3,1)=\omega^\omega+1,(1,2,3,1,2)=(1,2,3,1,1,1,1,\dots)=\omega^\omega+\omega,(1,2,3,1,2,3)=(1,2,3,1,2,2,2,2,\dots)=\omega^\omega2,(1,2,3,2)=(1,2,3,1,2,3,1,2,3,1,2,3,\dots)=\omega^{\omega+1}$。 $(1,2,3,2,2)=\omega^{\omega+2},(1,2,3,3)=(1,2,3,2,3,2,3,2,3\dots)=\omega^{\omega^2},(1,2,3,4)=(1,2,3,3,3,3,\dots)=\omega^{\omega^\omega}$。 $(1,2,3,4,5)=\omega\uparrow\uparrow5,\dots,(1,2,3,4,5,6,\dots)=\omega\uparrow\uparrow\omega=\varepsilon_0$。 这是 PrSS 的极限。 PrSS 很弱，但是他是之后我要讲的所有记号（除 FFFZ）的基础。 把 $a_{k+1}\le a_k+1$ 去掉，定义 $(1,3)=(1,2,3,4,5,6,\dots),(1,4)=(1,3,5,7,\dots)$ 可以得到 lPrSS。 引入阶差的概念可以得到 hPrSS。 多层求阶差可以得到 0-Y。 将序数改成多行，就是接下来要讲的 BMS。 （其实本来想讲一讲 Hydra，后来发现其实没啥必要。） --- 接下来要说一说 BMS 了。 BMS 是一个矩阵，但是它一般写作若干个数列的形式，一个列一个列的记（如 $(0,0)(1,1)$）。 一个合法的 BMS 要满足对于每一列，前面的行总是大于后面的行，且首列必须全为 $0$。 先说在 BMS 中的定义。 对于第一行，父项是和它在同一行的在它前面的比他小的最后一个数（这句话有点绕，本质上就是 PrSS 中的坏根）（由于 PrSS 父项和坏根定义相同，所以 PrSS 中只有坏根）。 祖先项指的是父项、父项的父项等的集合。 对于非第一行，在第一行父项的条件下，还要满足父项的上一行是现在元素的上一行的祖先项。 坏根指的是最后一行最后一个非 $0$ 数的父项所在列。 好部指的是坏根（不含）前面的列。 坏部指的是坏根（含）后面的列（不含最后一行）。 阶差数列指的是最后一列按位减去坏根的值，注意如果最后一列有一项为 $0$，那么阶差数列对应的上一项也要置为 $0$。 然后就可以说展开规则了。 1. 如果最后一列全是 $0$，把最后一列去掉并将算出的序数 $+1$； 2. 否则将好根保留，将坏根无限重复，第 $i$ 次重复加上 $i-1$ 倍阶差； 3. 为了防止不会停机的问题，如果一个元素的祖先项不包含坏根元素，那么复制的时候这个元素保持不变。 另外，在没有歧义的情况下，我们可以把最末尾的 $0$ 删去。 然后，开始扽西！ 双行 BMS 的扽西点就很构式，大家忍着点。 显然一行 BMS 就是 PrSS 每个元素减 $1$。 $(0)(1,1)=(0)(1)(2)(3)\dots=\varepsilon_0,(0)(1,1)(0)=\varepsilon_0+1,(0)(1,1)(0)(1,1)=\varepsilon_02,(0)(1,1)(0)(1,1)(0)(1,1)=\varepsilon_03,(0)(1,1)(1)=(0)(1,1)(0)(1,1)(0)(1,1)(0)(1,1)=\varepsilon_0\omega,(0)(1,1)(1)(2,1)=\varepsilon_0^2,(0)(1,1)(1)(2,1)(2)(3,1)=\varepsilon_0^{\varepsilon_0},(0)(1,1)(1,1)=(0)(1,1)(1)(2,1)(2)(3,1)(3)(4,1)=\varepsilon_1$。 $(0)(1,1)(1,1)(1,1)=\varepsilon_2,(0)(1,1)(2)=\varepsilon_\omega,(0)(1,1)(2)(1,1)=\varepsilon_{\omega+1},(0)(1,1)(2)(1,1)(2)=\varepsilon_{\omega2},(0)(1,1)(2)(3)=\varepsilon_{\omega^\omega},(0)(1,1)(2)(3,1)=\varepsilon_{\varepsilon_0},(0)(1,1)(2,1)=\zeta_0$。 $(0)(1,1)(2,1)(2,1)=\eta_0,(0)(1,1)(2,1)(2,1)(2,1)=\varphi(4,0),(0)(1,1)(2,1)(3)=\varphi(\omega,0),(0)(1,1)(2,1)(3)(2,1)=\varphi(\omega+1,0),(0)(1,1)(2,1)(3)(4,1)=\varphi(\varphi(1,0),0),(0)(1,1)(2,1)(3,1)=\varphi(1,0,0),(0)(1,1)(2,1)(3,1)(3,1)=\varphi(1,0,0,0),(0)(1,1)(2,1)(3,1)(4)=\varphi(1@\omega),(0)(1,1)(2,1)(3,1)(4)(5,1)=\varphi(1@\varepsilon_0),(0)(1,1)(2,1)(3,1)(4)(5,1)(6,1)(7,1)(8)=\varphi(1@\varphi(1@\omega)),(0)(1,1)(2,1)(3,1)(4,1)=LVO=\varphi(1@(1,0))=\psi(\Omega^{\Omega^\Omega})$。 现在开始换 OCF 来分析。 $(0)(1,1)(2,2)=\psi(\varepsilon_{\Omega+1})=\psi(\psi_1(0)),(0)(1,1)(2,2)(2,2)=\psi(\psi_1(1)),(0)(1,1)(2,2)(3,1)=\psi(\psi_1(\Omega)),(0)(1,1)(2,2)(3,2)=\psi(\Omega_2),(0)(1,1)(2,2)(3,3)=\psi(\psi_2(0)),(0)(1,1)(2,2)(3,3)(4,4)=\psi(\psi_3(0)),(0)(1,1,1)=(0)(1,1)(2,2)(3,3)(4,4)\dots=\psi(\Omega_\omega)$，这是双行 BMS 的极限。 --- 然后就是三行 BMS 了。 二行 BMS 还是“和蔼可亲”，三行就是和癌可氢了！ 三行的极限比你想象的要大，三行 BMS 的极限是 $\psi(\omega-\operatorname{Projection})$。 说完这些文字就开始扽西了。 $(0)(1,1,1)(2,1)=\psi(\Omega_\omega\Omega),(0)(1,1,1)(2,1)(1,1,1)=\psi(\Omega_\omega^2),(0)(1,1,1)(2,1)(3,2)=\psi(\Omega_{\omega+1}),(0)(1,1,1)(2,1,1)=\psi(\Omega_{\omega^2}),(0)(1,1,1)(2,1,1)(3,1)=\psi(\Omega_\Omega)$。 然后就是反射序数了。 $(0)(1,1,1)(2,1,1)(3,1)(2)=\psi(I),(0)(1,1,1)(2,1,1)(3,1,1)=\psi(I_\omega),(0)(1,1,1)(2,1,1)(3,1,1)(2,1,1)(3,1)(2)=\psi(\psi_{I(1,0)}(0)),(0)(1,1,1)(2,1,1)(3,1,1)(3)=\psi(I(\omega,0)),(0)(1,1,1)(2,1,1)(3,1,1)(3,1,1)=M_\omega,(0)(1,1,1)(2,1,1)(3,1,1)(4,1,1)=K_\omega,(0)(1,1,1)(2,2)=\psi(\Pi_\omega)$。 然后开始稳定序数。 $(0)(1,1,1)(2,2)(3,1,1)(4,2)=\psi(\lambda\alpha.\alpha+2-\Pi_0),(0)(1,1,1)(2,2)(3,2)=\psi(\lambda\alpha.\alpha+\omega-\Pi_0),(0)(1,1,1)(2,2)(3,2)(4,1)(2)=\psi(\lambda\alpha.\alpha2-\Pi_0),(0)(1,1,1)(2,2)(3,2)(4,1)(3,2)(4,1)(2)=\psi(\lambda\alpha.\alpha^2-\Pi_0),(0)(1,1,1)(2,2,1)(3)=\psi(\lambda\alpha.\Omega_{\alpha+\omega}-\Pi_0),(0)(1,1,1)(2,2,2)=\psi(\omega-\pi-\Pi_0)$。 然后是稳定。 这一部分在稳定分析过了，注意稳定里面需要左边来个 $\psi()$，右边最前面来个 $(0)$。 最后就做完了。 然后就到了 $TSSO$。 然后是四行极限 $QSSO$。 据称有一种可以将投影扩展到 $QSSO$ 的方法，但我不会。 最后是有限行 BMS 的极限 $(0)(1,1,1,1,1,\dots)=SHO$。 BMS 完。