【硬核】集合论 - 序数 - 第四章 - 稳定序数

· · 算法·理论

这是这一系列的第四章，第三章在这。

看这一章的时候，你需要确保你完全了解了前一章。

并没有理解最优子结构，但是疑似在这块不太需要，所以就不讲了。

首先我们需要一个 \lambda\alpha.\alpha，他的意思是将 \alpha 稳定到 \alpha。

人话：\lambda\alpha.\alpha-\Pi_x=\Pi_{1+x}。

请注意这里是 1+x 而非 x+1。

末尾的 \Pi 相当于一个计数器，逢 \omega 进 1。也就是 \lambda\alpha.(\alpha+1)-\Pi_0=\lambda\alpha.\alpha-\Pi_\omega=\Pi_\omega。

这样的话 \lambda\alpha.(\alpha+x)-\Pi_0 的 x 可以不断增大：\lambda\alpha.(\alpha+2)-\Pi_0=\Pi_{\omega2},\lambda\alpha.(\alpha+\omega)-\Pi_0=\Pi_{\omega^2},\lambda\alpha.(\alpha+\Omega)-\Pi_0=\Omega\dots，内部还可以继续嵌套，\lambda\alpha.(\alpha+\lambda\alpha.(\alpha+1)-\Pi_0)-\Pi_0\dots，最后得到的是 x\to\lambda\alpha.(\alpha+x)-\Pi_0 的不动点，它是 \lambda\alpha.\alpha2-\Pi_0。如果用类 \varphi 模式，\lambda\alpha.\alpha2-\Pi_0=\Pi(1,0)。

然后，\lambda\alpha.\alpha2-\Pi_1 折叠 (\lambda\alpha.\alpha2-\Pi_0-)^n，\lambda\alpha.\alpha2-\Pi_2 折叠 (\lambda\alpha.\alpha2-\Pi_1-)^n，\lambda\alpha.(\alpha2+1)-\Pi_0=\lambda\alpha.\alpha2-\Pi_\omega,\lambda\alpha.(\alpha2+\omega)-\Pi_0,\lambda\alpha.\alpha3-\Pi_0,\lambda\alpha.\alpha\omega-\Pi_0,\lambda\alpha.\alpha^2-\Pi_0,\lambda\alpha.\alpha^3-\Pi_0,\lambda\alpha.\alpha^\omega-\Pi_0,\lambda\alpha.\alpha^\alpha-\Pi_0,\lambda\alpha.\alpha^{\alpha^\alpha}-\Pi_0,\dots,\lambda\alpha.\varepsilon_{\alpha+1}-\Pi_0。

最后我们来到了这种迭代运算永远达不到的点，\lambda\alpha.\Omega_{\alpha+1}-\Pi_1。

请注意，这里结尾是 \Pi_1 而不是 \Pi_0。

更一般的，设这个稳定序数是 \lambda\alpha.f(\alpha)，若 f(\alpha) 是 \Pi_n 集合中的，那么第一个尾数就是 \Pi_{n-1}。

然后 \lambda\alpha.(\Omega_{\alpha+1}+1)-\Pi_0，这里由于 \Omega_{\alpha+1}+1 不再在 \Pi_2 中了，所以尾数可以是 \Pi_0 了。

继续变大，\lambda\alpha.(\Omega_{\alpha+1}+\omega)-\Pi_0,\lambda\alpha.(\Omega_{\alpha+1}+\alpha)-\Pi_0,\lambda\alpha.(\Omega_{\alpha+1}+\varepsilon_{\alpha+1})-\Pi_0,\lambda\alpha.\Omega_{\alpha+1}2-\Pi_0,\lambda\alpha.\Omega_{\alpha+1}^2-\Pi_0,\lambda\alpha.\Omega_{\alpha+1}^{\Omega_{\alpha+1}}-\Pi_0,\dots,\lambda\alpha.\Omega_{\alpha+2}-\Pi_1。

注意 $\Omega_{\alpha+\omega}$ 不在 $\Pi_2$ 中。 然后 $\lambda\alpha.I_{\alpha+1}-\Pi_1,\lambda\alpha.M_{\alpha+1}-\Pi_1,\lambda\alpha.N_{\alpha+1}-\Pi_1,\lambda\alpha.K_{\alpha+1}-\Pi_2,\lambda\alpha.\kappa_{\alpha+1}-\Pi_3,\dots,\lambda\alpha.\omega\operatorname{aft}\alpha-\Pi_\omega$。 我们注意到一个很奇怪的现象，这里最小的尾数就是 $\Pi_\omega$ 了，但是稳定序数的计数器逢 $\omega$ 进 $1$，也就是说，在这里稳定序数达到了极限，这已经大大扩张了反射序数。 --- 既然 $\alpha$ 能稳定到某个东西，那么我们可以让 $\alpha$ 稳定到某个 $\beta$，再让 $\beta$ 稳定到 $\beta+1$。 两段稳定链的开端是 $\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_0)-\Pi_0$，它的值是一段稳定链的极限。 这里外层的尾部 $\Pi$ 不小于内层的尾部 $\Pi$。 然后将外层的 $\Pi$ 扩大到 $\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_0)-\Pi_\omega$，然后这样就将内层 $+1$。 然后是 $\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_0+1)-\Pi_0,\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_0+\omega)-\Pi_0,\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_02)-\Pi_0,\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_0^2)-\Pi_0,\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_0)-\Pi_0^{\lambda\beta.(\beta+1)-\Pi_0}-\Pi_0,\dots$。 然后是 $\lambda\alpha.\Omega_{\lambda\beta.(\beta+1)-\Pi_0+1}-\Pi_0,\lambda\alpha.K_{\lambda\beta.(\beta+1)-\Pi_0+1}-\Pi_0,\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_0\operatorname{aft}\lambda\beta.(\beta+1)-\Pi_0)-\Pi_0=\lambda\alpha.(2\operatorname{nd}\lambda\beta.(\beta+1)-\Pi_0)$，然后就进行 $1-,2\ 1-,\omega\ 1-,2-,\omega-$ 折叠，最后到了 $\lambda\alpha.((\lambda\beta.(\beta+1)-)^{\beta})-\Pi_0$，折叠这一切的是 $\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_1)-\Pi_1$。 然后 $\lambda\alpha.(\lambda\beta.(\beta+1)-\Pi_2)-\Pi_2,\dots,\lambda\alpha.(\lambda\beta.\omega\operatorname{aft}\beta-\Pi_\omega)-\Pi_\omega$。 这步跳的有点大，大到和上一节整节一样大。 然后二段稳定就结束了。 --- 接着，我们还会有三段稳定链、四段稳定链、……、$n$ 段稳定链。 我们记 $n-\pi-f-\Pi_x$ 表示所有稳定链的尾数都是 $\Pi_x$，稳定链底端是 $f(\theta)$（这里 $\theta$ 代指最后一个稳定序数）。 所以我们来到了 $\omega-\pi-\Pi_0$。$f$ 不重要，到 $\omega$ 这个等级的什么 $f$ 都一样。 然后我们为了节省字数，多跳几步，直接跳到 $x\to x-\pi-\Pi_0$ 的不动点，这是 $\Sigma_1$ 稳定的弱极限。我们将其记为 $\alpha(\alpha(0))$，也可以记作 $\lambda\alpha.(\alpha-\pi-\Pi_0)-\Pi_0$。 --- 啥？OCF？ 这玩意不是上面的东西套个 $\psi$ 就行的？ 该讲的第 $3$ 章最后一节都讲了，列举几个有名字的序数吧。 1. $LSO=\psi(\lambda\alpha.\alpha2-\Pi_0)$； 2. $BGO=\psi(1-\lambda\alpha.\Omega_{\alpha+2}-\Pi_1)$； 3. $SDO=\psi(\lambda\alpha.\Omega_{\alpha+\omega}-\Pi_0)$； 4. $LDO=\psi(\lambda\alpha.\psi_I(\alpha+1)-\Pi_0)$； 5. $LRO=\psi(\omega-\pi-\Pi_0)$: 6. $FSLSO=\psi(\alpha(\alpha(0)))$。