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

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

== BOCF ==
''前排提醒：对严谨数学定义不感冒或看不懂的读者可以直接跳到[[OCF#直观理解|直观理解]]。''

=== 定义 ===
首先我们给出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将与它们分道扬镳。

=== <math>\varepsilon_0</math>与平台期 ===

=== 更多的非递归序数 ===

=== 直观理解与操作规则 ===

让我们从<math>\psi(0)=1</math>开始。

BOCF有这样的性质：

<math>\psi(m+1)=\psi(m)\times\omega</math>,m是任意序数

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

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

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

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

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


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

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

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