【硬核】集合论 - 序数 - 第二章 - OCF

· · 算法·理论

这是这一系列的第二章，第一章在这。

我查到的 OCF 都是直接上定义，这对新手十分的不友好，所以我会把这个玩意讲清楚。

首先我们有三个数 0,1,\omega，和三种序数运算加法、乘法和乘方。

通过这些能达到最大的数是 \omega\uparrow\uparrow\omega=\varepsilon_0，那么我们令 \psi(0)=\varepsilon_0。

然后我们现在已经有了 0,1,\omega,\psi(0)=\varepsilon_0，那么我们再做一遍，就可以得到 \varepsilon_0\uparrow\uparrow\omega=\varepsilon_1。

一直往后做，得到 \psi(x)=\varepsilon_x，x 可以是任何序数小于 \zeta_0 的序数。

这里，我们对 \psi(x) 下一个具体的定义：

注意第三条规则中的 n 不能是 \omega，这个不起眼的地方决定了现在的 OCF 在 x=\zeta_0 的时候早早取到极限。

由于 \varepsilon_{\zeta_0}=\zeta_0，所以 \psi(\zeta_0)=\zeta_0，而 \psi(\zeta_0+1) 并不是 \varepsilon_{\zeta_0+1}，因为 \max C^n(x) 仅仅是 \varepsilon^{(n)}_x，只有 \max C^{\omega}(x) 才能真正达到 \zeta_0，所以很可惜，\psi(\zeta_0+1)=\zeta_0。

那么 \forall x\ge\zeta_0,\psi(x)=\zeta_0，这不免让我们失望。

但是我们会有更加强大的方式的！

我们设 \Omega 为第一个非递归序数，也就是 \omega_1^{CK}（待查证），这里你不需要理解 \Omega 是什么，你只需要知道它很大，比我们知道的任何序数还要大且无法通过任何运算达到就行了。我们将 0,1,\omega 的初始值变成 0,1,\omega,\Omega，每次选取的为不包含 \Omega 的最大的非递归序数。

显然对于所有的 \zeta_0\le x\le\Omega，事情并不会发生任何变化。

当 x=\Omega+1 时，事情开始有了一丝转机，由于 \Omega<\Omega+1，\psi(\Omega)=\zeta_0 就可以作为元素放进 C^1(x)，于是 \psi(\Omega+1)=\varepsilon_{\zeta+1}，更一般的，对于所有的 1\le x\le \zeta_0,\psi(\Omega+x)=\varepsilon_{\zeta_0+x}。

事实上这个上界不仅是 \zeta_0 了！

我们还有 \psi(\Omega+\psi(\Omega+\zeta_0))，这些嵌套可以一直嵌套到映射 x\to\psi(\Omega+x) 的不动点，\zeta_1。

和刚才的情况类似，\forall \zeta_1\le x\le\Omega,\psi(\Omega+x)=\zeta_1。

然而考虑 \psi(\Omega2+1)，和刚才 \psi(\Omega+1) 的分析类似，\psi(\Omega2+1)=\varepsilon_{\zeta_1+1}。

然后推下去有 \psi(\Omega x)=\zeta_{x-1}。

那么我们有 \psi(\Omega\omega)=\zeta_{\omega}。

接着，\psi(\Omega\psi(\Omega))=\zeta_{\zeta_0},\psi(\Omega\psi(\Omega\psi(\Omega)))=\zeta_{\zeta_{\zeta_0}}...，最后达到了 x\to\psi(\Omega x) 的不动点，\eta_0。

然后对于 \psi(\Omega\eta_0) 到 \psi(\Omega^2) 的情况都是一样的，\eta_0。

直到 \psi(\Omega^2+\Omega) 获得进一步的增长。

一直下去，会有 \psi(\Omega^3)=\vartheta_0，一直到 \psi(\Omega^x)=\varphi(x+1,0) 便是极限。

接着再玩一层不动点，x\to\psi(\Omega^x) 的不动点就是 \Gamma_0，也就是 \varphi(1,0,0)，直到 \psi(\Omega^{\Omega}) 一直如此。

然后再将自变量进一步增大，\psi(\Omega^{\Omega}2)=\varphi(1,0,1),\psi(\Omega^{\Omega+1})=\varphi(1,1,0),\psi(\Omega^{\Omega^2})=\varphi(1@3),\psi(\Omega^{\Omega^x})=\varphi(1@(x+1))，最终得到了序元 Veblen 的极限 \psi(\Omega^{\Omega^{\Omega}})=\varphi(1@(1,0))。

然后再往上叠 \Omega 的指数塔，最后叠到 \psi(\Omega\uparrow\uparrow\omega)=\psi(\varepsilon_{\Omega+1})，也即超序元 Veblen 的极限 BHO。

直到这里 OCF 和 Veblen 能表示的东西还是一样的。

我们创造性的定义一个新的非递归序数 \Omega_2=\omega_2^{CK}，再定义一个 OCF \psi_1(x)，输出一个 \Omega 至 \Omega_2 间的序数。

我们再定义一个 C_1，除了初始集合和 C 不一样意外其余都一样，初始集合 C_1^0(x)=\Omega\cup\{\Omega\}=\{x|x\le\Omega\}。

有了更为厉害的 \psi_1 后，我们要把 \psi 改造成和他原先定义彼此彼此的 C^0(x)=\{0,1,\omega,\Omega,\Omega_2\}。

这样看来，\psi(\psi_1(0)) 就是 BHO，然后接着迭代一系列的序数，最后得到了 \psi(\zeta_{\Omega+1})，这个序数很大，大到现有的记号已经没有它的第二种表示形式了。

但是我们还可以做到更好：在第一内层中引入 \Omega_2，然后类似没有 \Omega_2 时，最后会达到 \psi(\varepsilon_{\Omega_2+1})。

接着我们已经做了示范，可以照葫芦画瓢引出 \Omega_3,\dots,\Omega_{\omega}。然后我们得到了 \psi(\Omega_{\omega})=BO。

然后接着扩展，\psi(\Omega_{\omega+1})=TFBO,\psi(\Omega_{\Omega})=BIO，然后最后得到 x\to\psi(\Omega_x) 的不动点 EBO，可以用反射序数表示为 \psi(\psi_I(0))。