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

'''序数塌缩函数(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>\varepsilon_0=\alpha\rightarrow\psi(\alpha)</math>的第一个不动点，这里没有问题。问题出在<math>\psi(\varepsilon_0+1)</math>上。

注意到<math>C_0(\varepsilon_0+1)=\{0,\Omega\}</math>,<math>C_1(\varepsilon_0+1)</math>中小于<math>\Omega</math>的最大元素是<math>\psi(0)</math>,<math>C_2(\varepsilon_0+1)</math>中小于<math>\Omega</math>的最大元素是<math>\psi(\psi(0))</math>,<math>C_2(\varepsilon_0+1)</math>中小于<math>\Omega</math>的最大元素是<math>\psi(\psi(\psi(0)))</math>……

因此，<math>\psi(\varepsilon_0)</math>始终无法出现在这里面。这直接导致了<math>C(\varepsilon_0+1)</math>中，小于<math>\Omega</math>的最小的不在里面的依然是<math>\psi(\varepsilon_0)</math>。相当于“卡住了”。这意味着对于所有的<math>\varepsilon_0\leq\alpha\leq\Omega</math>，都有<math>\psi(\alpha)=\psi(\varepsilon_0)</math>.这就像一个巨大的平台，因此称为'''平台期'''。

直到<math>\psi(\Omega+1)</math>才迎来了转机。因为<math>\Omega</math>也在<math>C_0(x)</math>里面，因此<math>\psi(\Omega)</math>终于可以被放进<math>C_1(\Omega+1)</math>里面了。结果是<math>\psi(\Omega+1)=\psi(\Omega)\times\omega</math>.后面再一次向上增长，直到<math>\alpha\rightarrow\psi(\Omega+\alpha)</math>的不动点。从这里到<math>\psi(\Omega+\Omega)</math>又是一段平台期。直到<math>\psi(\Omega+\Omega+1)</math>再次恢复增长。

这样的定义可以一直运行到<math>\psi(\Omega\times\omega)</math>,再往后走不下去了。可是它相比其他[[序数记号]]，如[[veblen函数]]依然是孱弱的。为了继续前进，我们需要引入更多的非递归序数。

=== 更多的非递归序数 ===
下面是引入更多非递归序数的BOCF定义：

# <math>C_0^v(x)=\{\alpha|\alpha<\Omega_v\}\cup\{\Omega_{\beta}|v<\beta<\omega\}</math>
# <math>C_{n+1}^v(x)=\{\alpha+\beta,\psi_{\delta}(\gamma)|\alpha,\beta,\gamma\in C_n^v(x),\gamma<x,\delta<\omega\}</math>
# <math>C^v(x)=\bigcup_{n<\omega}C_n^v(x)</math>
# <math>\psi_v(x)=min\{\alpha<\Omega_{v+1}|\alpha\notin C^v(x)\}</math>

<math>\psi</math>函数即<math>\psi_0</math>函数。

可以看到，根据定义，有<math>C_0^1(0)=\{\alpha,\Omega_2|\alpha<\Omega\}</math>,随后<math>C_n^1(0)</math>是根据<math>C_0^1(0)=\{\alpha,\Omega_2|\alpha<\Omega\}</math>中元素进行加法所得到的所有东西，注意到它们内部依然不存在<math>\Omega\sim\Omega_2</math>的序数。因此，<math>\psi_1(0)=\Omega</math>.对于<math>\psi_1(1)</math>，因为它可以把<math>\psi_1(0)</math>塞进C里，因此，最后有<math>\psi_1(1)=\Omega\times\omega</math>.之后的内容是顺理成章的，类似<math>\psi(0)\sim\psi(\psi(\psi(\cdots)))</math>的过程，有<math>\psi_1(\psi_1(\psi_1(\cdots)))=\Omega^{\Omega^{\Omega^{\cdots}}}</math>.我们暂时记<math>\psi_1(1,0)=\alpha\rightarrow\psi_1(\alpha)</math>的不动点。可以验证，对于<math>\psi_1</math>函数来说，这里依然存在<math>\psi_1(1,0)<\alpha<\Omega_2</math>的平台期。后面的一切都是顺理成章的。直到任意的<math>\psi_n</math>，都是一样的。

但有一点需要注意，对于<math>\psi</math>函数来说，<math>\psi(\psi_1(\Omega_2))</math>并没有打破从<math>\psi(\psi_1(1,0))</math>开始的平台期，这个平台期继续向前，直到<math>\psi(\Omega_2)</math>才结束。这一现象称为'''藏层'''。

BOCF的<math>\psi(\Omega_{\omega})=sup\{\psi(\Omega),\psi(\Omega_2),\psi(\Omega_3,\cdots\}</math>,这一序数有一个名字是[[BO]]（Buchholz's Ordinal ）,在[[googology]]中是一个非常重要的序数。

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

让我们从<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^{\psi(\Omega^{\Omega^{\Omega}+\Omega^{\cdots}})}})}})</math>.

以下是[[BHO]]（即<math>\psi(\Omega^{\Omega^{\Omega^{\cdots}}})</math>）之前的BOCF的操作规则：

<math>\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</math>

<math>(\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]</math>

<math>\psi(X+1)[m]=\psi(X)\times m</math>

<math>\psi(X+\psi(Y))[m]=\psi(X+\psi(Y)[m])</math>

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

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

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

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

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

BHO之上，就需要引入更多的非递归序数<math>\Omega_2,\Omega_3,\Omega_4,\cdots</math>.对于他们来说，有<math>\psi_1</math>函数，<math>\psi_2</math>函数，<math>\psi_3</math>函数……分别对应，<math>\Omega_{m+1}</math>和<math>\psi_m</math>函数之间的关系与Ω和ψ函数的关系是一模一样的。(<math>\psi</math>函数即<math>\psi_0</math>函数，<math>\Omega</math>即<math>\Omega_1</math>)

对于<math>\psi_m</math>函数，有如下规则：

<math>\psi_m(0)=\Omega_m</math>

<math>\psi_m(X+1)=\psi_m(X)\times\omega</math>

<math>\psi_m(Y\sim\Omega_{m+1})=\psi_m(Y\sim\psi_m(Y\sim\psi_m(Y\sim\cdots)))</math>

不难发现和<math>\psi</math>函数的操作规则几乎一模一样

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

因为OCF存在一个“藏层”现象。即，<math>\psi(\psi_1(\Omega_2))</math>这样的式子是不标准的，它等价于<math>\psi(\Omega_2)</math>.相当于那个<math>\psi_1</math>的层被“藏起来”了，因此称为藏层。

根据前文所说，<math>\Omega_n</math>是一定要找<math>\psi_{n-1}</math>函数去嵌套的。那么，面对藏层，我们要如何操作呢？

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

<math>\psi_m(Y\sim\Omega_n)=\psi_m(Y\sim\psi_{n-1}(Y\sim\psi_{n-1}(Y\sim\cdots)))</math>

举例，考虑<math>\psi(\Omega_3+\psi_2(\Omega_3+\Omega_2))</math>,最右端是<math>\Omega_2</math>,它要找一个最近的<math>\psi_n</math>函数满足n＜2，是最外层的ψ函数。于是我们按照操作规则得到展开式为<math>\psi(\Omega_3+\psi_2(\Omega_3+\psi_1(\Omega_3+\psi_2(\Omega_3+\psi_1(\Omega_3+\psi_2(\Omega_3+\cdots))))))</math>.

BO是<math>\psi(\Omega_{\omega})</math>,它的[[基本列]]是<math>\{\psi(0),\psi(\Omega),\psi(\Omega_2),\psi(\Omega_3),\psi(\Omega_4),\cdots\}</math>.从这条基本列中的元素开始按照操作规则展开所得到的式子就是标准的，如果得不到，则是不标准的。

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

=== 枚举 ===
参见词条[[BOCF VS veblen函数]]

== MOCF ==
下面是MOCF的数学定义：

# <math>C_0(x)=\{0,1,\omega,\Omega\}</math>
# <math>C_{n+1}(x)=\{\alpha+\beta,\alpha\times\beta,\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\notin C(x)\}</math>

可以发现，MOCF和BOCF不同的点在于它把加法、乘法和乘方都放进了<math>C(x)</math>中，而BOCF只有加法。因此，MOCF的<math>\psi(0)=\varepsilon_0</math>,并且有<math>\psi(X+1)=\psi(X)^{\psi(X)^{\psi(X)^{\cdots}}}</math>。在出现<math>\Omega</math>的地方，两种OCF是一样的，如平台期等概念，二者也是一样的。

下面是引入更多非递归序数的MOCF定义：

# <math>C_0^v(x)=\{\alpha|\alpha<\Omega_v\}\cup\{\Omega_{\beta}|\beta<\omega\}</math>
# <math>C_{n+1}^v(x)=\{\alpha+\beta,\alpha\times\beta,\alpha^\beta,\psi_{\delta}(\gamma)|\alpha,\beta,\gamma\in C_n^v(x),\gamma<x,\delta<\omega\}</math>
# <math>C^v(x)=\bigcup_{n<\omega}C_n^v(x)</math>
# <math>\psi_v(x)=min\{\alpha<\Omega_{v+1}|\alpha\notin C^v(x)\}</math>

可以看到和BOCF的定义大差不差，唯一的区别是乘法和乘方的引入。因而操作规则无太大差异，除了<math>\psi_v(X+1)=\psi_v(X)^{\psi_v(X)^{\psi_v(X)^{\cdots}}}</math>.此处不再赘述。

MOCF的<math>\psi(\Omega_\omega)</math>也是BO。

=== 枚举 ===
参见词条[[BOCF VS MOCF]]

== BO之后 ==
[[分类:记号]]