序数坍缩函数

序数塌缩函数(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 }}^{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\cdots }})}})}})$.

以下是BHO（即$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\cdots }}})$）之前的BOCF的操作规则：

$\psi ({\alpha }_1)+\psi ({\alpha }_2)+\cdots +\psi ({\alpha }_{n-1})+\psi (0)=\psi ({\alpha }_1)+\psi ({\alpha }_2)+\cdots +\psi ({\alpha }_{n-1})+1$

$(\psi ({\alpha }_1)+\psi ({\alpha }_2)+\cdots +\psi ({\alpha }_{n-1})+\psi ({\alpha }_n))[m]=\psi ({\alpha }_1)+\psi ({\alpha }_2)+\cdots +\psi ({\alpha }_{n-1})+\psi ({\alpha }_m)[m]$

$\psi (X+1)[m]=\psi (X)\times m$

$\psi (X+\psi (Y))[m]=\psi (X+\psi (Y)[m])$

这四条和康托范式的规则是一样的，主要是要找准表达式最右侧的结构。如果最右侧是外面的1那就是后继，最右侧是$\psi$里面的1那就是乘$\omega$。最右侧如果是$\psi (X)$,则先操作它。

但如果最右侧是$\mathrm{\Omega }$呢？很简单，只需要找到包着它的那一层$\psi$，然后在原位嵌套即可。即：

$\psi (Z\sim \mathrm{\Omega })=\psi (Z\sim \psi (Z\sim \psi (Z\sim \cdots )))$,其中~是+或者×或者^。注意这里的Z并不一定是一个序数，它可以只是一个算式。比如说$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\mathrm{\Omega }}})$对应的Z是$\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^{\mathrm{\Omega }}})$标红的部分。

有的时候最右侧的$\mathrm{\Omega }$被藏起来，你需要自己去挖掘出来。比方说$\psi ({\mathrm{\Omega }}^3\times 2)$,你需要把它写成$\psi ({\mathrm{\Omega }}^3+{\mathrm{\Omega }}^2\times \mathrm{\Omega })$这种形式。

tips：BOCF中实际上并不存在乘法和乘方，因此上文的大部分式子严格来说是不标准的。但是在googology绝大多种情况下，为了方便和清晰性，我们都会用这种“部分”引入乘法和乘方的BOCF不标准式。

BHO之上，就需要引入更多的非递归序数${\mathrm{\Omega }}_2,{\mathrm{\Omega }}_3,{\mathrm{\Omega }}_4,\cdots$.对于他们来说，有${\psi }_1$函数，${\psi }_2$函数，${\psi }_3$函数……分别对应，${\mathrm{\Omega }}_{m+1}$和${\psi }_m$函数之间的关系与Ω和ψ函数的关系是一模一样的。($\psi$函数即${\psi }_0$函数，$\mathrm{\Omega }$即${\mathrm{\Omega }}_1$)

对于${\psi }_m$函数，有如下规则：

${\psi }_m(0)={\mathrm{\Omega }}_m$

${\psi }_m(X+1)={\psi }_m(X)\times \omega$

${\psi }_m(Y\sim {\mathrm{\Omega }}_{m+1})={\psi }_m(Y\sim {\psi }_m(Y\sim {\psi }_m(Y\sim \cdots )))$

不难发现和$\psi$函数的操作规则几乎一模一样

比如说，有${\psi }_1(0)=\mathrm{\Omega }$，${\psi }_1(1)=\mathrm{\Omega }\times \omega$,${\psi }_1({\psi }_1(0))={\mathrm{\Omega }}^2$,${\psi }_1({\psi }_1(0)\times 2)={\mathrm{\Omega }}^3$,${\psi }_1({\psi }_1({\psi }_1(0)))={\mathrm{\Omega }}^{\mathrm{\Omega }}$等等。最后会得到${\psi }_1({\mathrm{\Omega }}_2)={\psi }_1({\psi }_1({\psi }_1(\cdots )))={\mathrm{\Omega }}^{{\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\cdots }}}$.借助${\psi }_1$函数，我们确实突破了前面BHO 的界限。但事情还没这么简单。

因为OCF存在一个“藏层”现象。即，$\psi ({\psi }_1({\mathrm{\Omega }}_2))$这样的式子是不标准的，它等价于$\psi ({\mathrm{\Omega }}_2)$.相当于那个${\psi }_1$的层被“藏起来”了，因此称为藏层。

根据前文所说，${\mathrm{\Omega }}_n$是一定要找${\psi }_{n-1}$函数去嵌套的。那么，面对藏层，我们要如何操作呢？

答案是，找到包着${\mathrm{\Omega }}_n$的最近的${\psi }_m$函数满足$m<n$，我们视作${\psi }_{n-1}$函数被藏在了这个${\psi }_m$内部。随后进行嵌套，但要在嵌套过程中把内部的${\psi }_m$改成${\psi }_{n-1}$,即：

${\psi }_m(Y\sim {\mathrm{\Omega }}_n)={\psi }_m(Y\sim {\psi }_{n-1}(Y\sim {\psi }_{n-1}(Y\sim \cdots )))$

举例，考虑$\psi ({\mathrm{\Omega }}_3+{\psi }_2({\mathrm{\Omega }}_3+{\mathrm{\Omega }}_2))$,最右端是${\mathrm{\Omega }}_2$,它要找一个最近的${\psi }_n$函数满足n＜2，是最外层的ψ函数。于是我们按照操作规则得到展开式为$\psi ({\mathrm{\Omega }}_3+{\psi }_2({\mathrm{\Omega }}_3+{\psi }_1({\mathrm{\Omega }}_3+{\psi }_2({\mathrm{\Omega }}_3+{\psi }_1({\mathrm{\Omega }}_3+{\psi }_2({\mathrm{\Omega }}_3+\cdots ))))))$.

以上就是BO前的BOCF的直观理解与操作规则。