查看“︁序数坍缩函数”︁的源代码

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

== BOCF ==

=== 定义 ===
首先我们给出BOCF只引入<math>\Omega</math>的定义：

# <math>C_0(x)=\{0,\Omega\}</math>
# <math>C_{n+1}(x)=C_n(x)\cup\{\alpha+\beta,\psi(\gamma)|\alpha,\beta,\gamma\in C_n(x),\gamma <x\}</math>
# <math>C(x)=\bigcup_{n<\omega}C_n(x)</math>
# <math>\psi(x)=min\{\alpha<\Omega|\alpha\not\in C(x)\}</math>

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

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

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

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

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

规则4，<math>\psi(x)</math>就是所有小于<math>\Omega</math>的序数中，不属于<math>C(x)</math>的最小序数。

=== <math>\varepsilon_0</math>之前 ===
以下是一些运算实例：

<math>C_0(0)=\{0,\Omega\}</math>

<math>C_1(0)=\{0,\Omega,\Omega\times2\}</math>

<math>C_2(0)=\{0,\Omega,\Omega\times2,\Omega\times3,\Omega\times4\}</math>

……

<math>C(0)=\{0,\Omega,\cdots\}</math>,省略号省掉了大于<math>\Omega</math>的序数

因此<math>\psi(0)</math>是最小的小于<math>\Omega</math>的不在<math>C(0)</math>里的序数，即1.

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

<math>C_0(2)=\{0,\Omega\}</math>

<math>C_1(2)=\{0,\psi(0)=1,\Omega,\cdots\}</math>

<math>C_2(2)</math>包含了1，2和<math>\psi(1)</math>,即ω。

<math>C_3(2)</math>包含了<math>1,2,3,4,\omega,\omega+1,\omega+2,\omega\times2</math>

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

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

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

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

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

<math>\psi(\omega)=\omega^{\omega}=\psi(\psi(1))</math>

<math>\psi(\omega+1)=\omega^{\omega+1}=\psi(\psi(1)+1)</math>

<math>\psi(\omega\times2)=\omega^{\omega\times2}=\psi(\psi(1)\times2)</math>

<math>\psi(\omega^2)=\omega^{\omega^2}=\psi(\psi(2))</math>

<math>\psi(\omega^{\omega})=\omega^{\omega^{\omega}}=\psi(\psi(\psi(1)))</math>

<math>\psi(\omega^{\omega^{\omega}})=\omega^{\omega^{\omega^{\omega}}}=\psi(\psi(\psi(\psi(1))))</math>

……

到这里和[[康托范式]]，[[veblen函数]]的<math>\varphi(x)</math>都是一致的。然而，在<math>\varepsilon_0</math>开始，OCF将与它们分道扬镳。


== MOCF ==
[[分类:记号]]