序数坍缩函数

序数塌缩函数(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将与它们分道扬镳。