序数坍缩函数

序数塌缩函数(Ordinal Collapsing Function,OCF)是一种序数函数。它们的特点是利用足够大的序数(通常是非递归序数)来输出递归序数。事实上，OCF有很多不同的版本。本词条着力于介绍BO之前的BOCF(Buchholz's OCF)和MOCF(Madore's OCF)。

BOCF

前排提醒：对严谨数学定义不感冒或看不懂的读者可以直接跳到直观理解。

定义

首先我们给出BOCF只引入$\mathrm{\Omega }$的定义：

1. $C_0(x)=\{0,\mathrm{\Omega }\}$
2. $C_{n+1}(x)=C_n(x)\cup \{\alpha +\beta ,\psi (\gamma )|\alpha ,\beta ,\gamma \in C_n(x),\gamma <x\}$
3. $C(x)=\bigcup _{n<\omega }{C}_n(x)$
4. $\psi (x)=min\{\alpha <\mathrm{\Omega }|\alpha \in ̸C(x)\}$

其中的$\mathrm{\Omega }$要求是一个足够大的序数。以往的资料一般使用第一个不可数序数${\omega }_1$来作为它。但我们发现，第一个非递归序数${\omega }_1^{CK}$已经可以满足我们的需求。因此，目前提到$\mathrm{\Omega }$,默认指的是${\omega }_1^{CK}$。

这四条规则很是抽象，让我们一条一条来看。

规则1：$C_0(x)=\{0,\mathrm{\Omega }\}$。对于任意的x ， $C_0(x)$是同一个集合。

规则2，这个规则递归定义了$C_{n+1}(x)$,它是$C_n(x)$再加上$C_n(x)$中的元素通过加法和ψ函数能产生的所有元素。这里要求ψ函数自变量小于x，因为$\psi (x)$是需要$C(x)$来定义的。

规则3，$C(x)$是对所有的$C_n(x)$取并集得到的集合。

规则4，$\psi (x)$就是所有小于$\mathrm{\Omega }$的序数中，不属于$C(x)$的最小序数。

${\epsilon }_0$之前

以下是一些运算实例：

$C_0(0)=\{0,\mathrm{\Omega }\}$

$C_1(0)=\{0,\mathrm{\Omega },\mathrm{\Omega }\times 2\}$

$C_2(0)=\{0,\mathrm{\Omega },\mathrm{\Omega }\times 2,\mathrm{\Omega }\times 3,\mathrm{\Omega }\times 4\}$

……

$C(0)=\{0,\mathrm{\Omega },\cdots \}$,省略号省掉了大于$\mathrm{\Omega }$的序数

因此$\psi (0)$是最小的小于$\mathrm{\Omega }$的不在$C(0)$里的序数，即1.

下一个例子是$\psi (2)$.假定首先你已经知道了$\psi (1)=\omega$(可以自己验证），我们要开始计算$\psi (2)$，还是不展示大于$\mathrm{\Omega }$的序数

$C_0(2)=\{0,\mathrm{\Omega }\}$

$C_1(2)=\{0,\psi (0)=1,\mathrm{\Omega },\cdots \}$

$C_2(2)$包含了1，2和$\psi (1)$,即ω。

$C_3(2)$包含了$1,2,3,4,\omega ,\omega +1,\omega +2,\omega \times 2$

以此类推，最后能得到$C(2)$中包含了全体小于${\omega }^2$的序数和一大堆大于$\mathrm{\Omega }$的序数。因此根据定义,$\psi (2)={\omega }^2$

ψ函数内是极限序数并不影响定义和计算。

你有没有觉得一步一步按定义走太过于繁琐？下面给出它的2个性质:

1. $\psi (m+1)=\psi (m)\times \omega$,m是任意序数
2. $\psi (\lambda )=sup\{\psi (\kappa )|\kappa <\lambda \}$,α是任意非0极限序数

根据这个性质，我们可以轻松的得到：

$\psi (\omega )={\omega }^{\omega }=\psi (\psi (1))$

$\psi (\omega +1)={\omega }^{\omega +1}=\psi (\psi (1)+1)$

$\psi (\omega \times 2)={\omega }^{\omega \times 2}=\psi (\psi (1)\times 2)$

$\psi ({\omega }^2)={\omega }^{{\omega }^2}=\psi (\psi (2))$

$\psi ({\omega }^{\omega })={\omega }^{{\omega }^{\omega }}=\psi (\psi (\psi (1)))$

$\psi ({\omega }^{{\omega }^{\omega }})={\omega }^{{\omega }^{{\omega }^{\omega }}}=\psi (\psi (\psi (\psi (1))))$

……

到这里和康托范式，veblen函数的$\phi (x)$都是一致的。然而，在${\epsilon }_0$开始，OCF将与它们分道扬镳。

直观理解与操作规则

让我们从$\psi (0)=1$开始。

BOCF有这样的性质：

$\psi (m+1)=\psi (m)\times \omega$,m是任意序数

因此，可以得到$\psi (1)=\omega$。得到之后，你对$\psi (1)$之前的序数已经很清楚了，于是，可以把这些序数也都放进$\psi$函数内部，于是，你最大能得到$\psi (\psi (1))=\psi (\omega )={\omega }^{\omega }$.得到它之后，你又对它之前的序数很清楚了，于是又可以把它们也放进$\psi$函数内部，最大能得到$\psi (\psi (\psi (1)))={\omega }^{{\omega }^{\omega }}$……以此类推，你可以得到嵌套任意多层的$\psi (\psi (\psi (\cdots )))$.

这个时候，我们的新朋友$\mathrm{\Omega }$出场了。我们令$\psi (\mathrm{\Omega })=\psi (\psi (\psi (\cdots )))$，于是我们可以继续：$\psi (\mathrm{\Omega }+1)=\psi (\mathrm{\Omega })\times \omega$.现在你会发现，它内部既然可以加一，那是不是也可以加上更大的序数呢？答案是肯定的。你先前已经得到了$\psi (\mathrm{\Omega })$，那么对它之前的序数已经清楚了。于是只需要重走一遍1到$\psi (\mathrm{\Omega })$的路，就可以得到$\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega }))$.和前面类似的，得到$\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega }))$后，也就可以理解$\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega })))$，毕竟只是在$\psi$内重走一遍先前走过的路。上面的路又可以一直走下去，直到$\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega }+\cdots )))$.

于是，$\mathrm{\Omega }$再次登场，它让$\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega }+\psi (\mathrm{\Omega }+\cdots )))=\psi (\mathrm{\Omega }+\mathrm{\Omega })=\psi (\mathrm{\Omega }\times 2)$.我们又可以按先前的思路，首先得到$\psi (\mathrm{\Omega }\times 2+1)=\psi (\mathrm{\Omega }\times 2)\times \omega$，然后重走一遍1到$\psi (\mathrm{\Omega }\times 2)$的路，就得到$\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2))$;再重走一遍$\psi (\mathrm{\Omega }\times 2)$到$\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2))$的路，就得到$\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2)))$,再以此类推，得到$\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2+\cdots )))$后再把它变成$\psi (\mathrm{\Omega }\times 3)$,然后再……

说到这里，读者应该对$\mathrm{\Omega }$有一定的认识了。它的“能力”是让包着它的一层$\psi$函数连同内部的其他内容一起嵌套n层。如$\psi (\mathrm{\Omega }\times 3)=\psi (\mathrm{\Omega }\times 2+\mathrm{\Omega })=\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2+\psi (\mathrm{\Omega }\times 2+\cdots )))$.细心的读者可能注意到，这其实是不动点的体现。没错，OCF中的$\mathrm{\Omega }$可以说是不动点的“化身”，只要它出现，就一定是代表了一个不动点。事实上，前文只展示了加法。$\mathrm{\Omega }$对于乘法和乘方所做的事情和加法是如出一辙的，以下是例子：

得到$\psi (\mathrm{\Omega }\times \omega )$，理解加一个$\mathrm{\Omega }$起到什么作用之后，只需要重走一边$\omega$到$\psi (\mathrm{\Omega })$的路，就能得到$\psi (\mathrm{\Omega }\times \psi (\mathrm{\Omega }))$,然后再重走一遍$\psi (\mathrm{\Omega })$到$\psi (\mathrm{\Omega }\times \psi (\mathrm{\Omega }))$的路，就能得到$\psi (\mathrm{\Omega }\times \psi (\mathrm{\Omega }\times \psi (\mathrm{\Omega })))$……最后得到$\psi ({\mathrm{\Omega }}^2)=\psi (\mathrm{\Omega }\times \mathrm{\Omega })=\psi (\mathrm{\Omega }\times \psi (\mathrm{\Omega }\times \psi (\mathrm{\Omega }\times \cdots )))$.

得到$\psi ({\mathrm{\Omega }}^3)$，理解加一个${\mathrm{\Omega }}^2$起到什么作用之后，只需要重走一边1到$\psi ({\mathrm{\Omega }}^3)$的路，就能从$\psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times 1)$开始得到$\psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \psi ({\mathrm{\Omega }}^3))$,然后再重走一遍$\psi ({\mathrm{\Omega }}^3)$到$\psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \psi ({\mathrm{\Omega }}^3))$的路，就能得到$\psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \psi ({\mathrm{\Omega }}^3)))$……最后得到$\psi ({\mathrm{\Omega }}^3\times 2)=\psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \mathrm{\Omega })=\psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \cdots )))$.

得到$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})$和$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^1})$，只需要重走一边1到$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})$的路，就能从$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^1})$开始得到$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})}})$,然后再重走一遍$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})$到$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})}})$路，就能得到到$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})}})}})$……最后得到$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}\times 2})=\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\mathrm{\Omega }}})=\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\cdots }})}})$.