序数坍缩函数
更多操作
序数塌缩函数(Ordinal Collapsing Function,OCF)是一种序数函数。它们的特点是利用足够大的序数(通常是非递归序数)来输出递归序数。事实上,OCF 有很多不同的版本。本词条着力于介绍 EBO 之前的 BOCF(Buchholz's OCF)和 MOCF(Madore's OCF)。
教学
BOCF 简介
前排提醒:对严谨数学定义不感冒或看不懂的读者可以直接跳到直观理解与操作规则。
定义
首先我们给出 BOCF 只引入第一个非递归序数 的定义:
其中的 要求是一个足够大的序数。以往的资料一般使用第一个不可数序数 (FUO)来作为它。但我们发现,第一个非递归序数 (CKO)已经可以满足我们的需求。因此,目前提到 ,默认指的是 。
这四条规则很是抽象,让我们一条一条来看。
规则 1:。对于任意的 x , 是同一个集合。
规则 2,这个规则递归定义了 ,它是 再加上 中的元素通过加法和 ψ 函数能产生的所有元素。这里要求 ψ 函数自变量小于 x,因为 是需要 来定义的。
规则3, 是对所有的 取并集得到的集合。
规则4, 就是所有小于 的序数中,不属于 的最小序数。
之前
以下是一些运算实例:
- ……
,省略号省掉了大于 的序数。
因此 是最小的小于 的不在 里的序数,即 1。
下一个例子是 ,假定首先你已经知道了 (可以自己验证),我们要开始计算 ,还是不展示大于 的序数:
- 包含了 1,2 和 ,即 ω
- 包含了
以此类推,最后能得到 中包含了全体小于 的序数和一大堆大于 的序数。因此根据定义,。
ψ 函数内是极限序数并不影响定义和计算。
你有没有觉得一步一步按定义走太过于繁琐?下面给出它的 2 个性质:
- ,m 是任意序数
- ,α 是任意非 0 极限序数
根据这个性质,我们可以轻松的得到:
- ……
到这里和康托范式,Veblen 函数的 都是一致的。然而,在 开始,OCF 将与它们分道扬镳。
与平台期
的第一个不动点,这里没有问题。问题出在 上。
注意到 , 中小于 的最大元素是 , 中小于 的最大元素是 , 中小于 的最大元素是 ……
因此, 始终无法出现在这里面。这直接导致了 中,小于 的最小的不在里面的依然是 ,相当于“卡住了”。这意味着对于所有的 ,都有 。这就像一个巨大的平台,因此称为平台期。
直到 才迎来了转机。因为 也在 里面,因此 终于可以被放进 里面了。结果是 。后面再一次向上增长,直到 的不动点。从这里到 又是一段平台期。直到 再次恢复增长。
这样的定义可以一直运行到 ,再往后走不下去了。可是它相比其他序数记号,如 Veblen 函数依然是孱弱的。为了继续前进,我们需要引入更多的非递归序数。
更多的非递归序数
下面是引入更多非递归序数的 BOCF 定义:
函数即 函数。
可以看到,根据定义,有 ,随后 是根据 中元素进行加法所得到的所有东西,注意到它们内部依然不存在 的序数。因此,。对于 ,因为它可以把 塞进 C 里,因此,最后有 。之后的内容是顺理成章的,类似 的过程,有 。我们暂时记 的不动点。可以验证,对于 函数来说,这里依然存在 的平台期。后面的一切都是顺理成章的。直到任意的 ,都是一样的。
但有一点需要注意,对于 函数来说, 并没有打破从 开始的平台期,这个平台期继续向前,直到 才结束。这一现象称为藏层。
BOCF 的 ,这一序数有一个名字是 BO(Buchholz's Ordinal ),在 googology 中是一个非常重要的序数。
tips:OCF中的 不一定非得是非递归序数,它只需要大于所有你研究的序数就可以了,比方说你想要研究 BMS,那么理论上你只需要保证它大于 BMS 极限就可以了。但是我们的研究是永无止境的,因此普遍使用非递归序数这一大于所有递归序数的东西来充当 。
直观理解与操作规则
让我们从 开始。
BOCF 有这样的性质:
,m 是任意序数。
因此,可以得到 。得到之后,你对 之前的序数已经很清楚了,于是,可以把这些序数也都放进 函数内部,于是,你最大能得到 。得到它之后,你又对它之前的序数很清楚了,于是又可以把它们也放进 函数内部,最大能得到 ……以此类推,你可以得到嵌套任意多层的 。
这个时候,我们的新朋友 出场了。我们令 ,于是我们可以继续:。现在你会发现,它内部既然可以加一,那是不是也可以加上更大的序数呢?答案是肯定的。你先前已经得到了 ,那么对它之前的序数已经清楚了。于是只需要重走一遍 1 到 的路,就可以得到 。和前面类似的,得到 后,也就可以理解 ,毕竟只是在 内重走一遍先前走过的路。上面的路又可以一直走下去,直到 。
于是, 再次登场,它让 。我们又可以按先前的思路,首先得到 ,然后重走一遍 1 到 的路,就得到 ;再重走一遍 到 的路,就得到 ,再以此类推,得到 后再把它变成 ,然后再……
说到这里,读者应该对 有一定的认识了。它的“能力”是让包着它的一层 函数连同内部的其他内容一起嵌套 n 层。如 。细心的读者可能注意到,这其实是不动点的体现。没错,OCF 中的 可以说是不动点的“化身”,只要它出现,就一定是代表了一个不动点。事实上,前文只展示了加法。 对于乘法和乘方所做的事情和加法是如出一辙的,以下是例子:
得到 ,理解加一个 起到什么作用之后,只需要重走一遍 到 的路,就能得到 ,然后再重走一遍 到 的路,就能得到 ……最后得到 。
得到 ,理解加一个 起到什么作用之后,只需要重走一遍 1 到 的路,就能从 开始得到 ,然后再重走一遍 到 的路,就能得到 ……最后得到 。
得到 和 ,只需要重走一边 1 到 的路,就能从 开始得到 ,然后再重走一遍 到 路,就能得到 ……最后得到 。
以下是 BHO(即 )之前的 BOCF 的操作规则:
这四条和康托范式的规则是一样的,主要是要找准表达式最右侧的结构。如果最右侧是外面的 1 那就是后继,最右侧是 里面的 1 那就是乘 。最右侧如果是 ,则先操作它。
但如果最右侧是 呢?很简单,只需要找到包着它的那一层 ,然后在原位嵌套即可。即:
,其中 ~ 是 + 或者 × 或者 ^。注意这里的 Z 并不一定是一个序数,它可以只是一个算式。比如说 对应的 Z 是 标红的部分。
有的时候最右侧的 被藏起来,你需要自己去挖掘出来。比方说 ,你需要把它写成 这种形式。
tips:BOCF 中实际上并不存在乘法和乘方,因此上文的大部分式子严格来说是不标准的。但是在 googology 绝大多种情况下,为了方便和清晰性,我们都会用这种“部分”引入乘法和乘方的 BOCF 不标准式。
BHO 之上,就需要引入更多的非递归序数 。对于他们来说,有 函数, 函数, 函数……分别对应, 和 函数之间的关系与 Ω 和 ψ 函数的关系是一模一样的。( 函数即 函数, 即 )
对于 函数,有如下规则:
不难发现和 函数的操作规则几乎一模一样。
比如说,有 ,,,, 等等。最后会得到 。借助 函数,我们确实突破了前面 BHO 的界限。但事情还没这么简单。
因为 OCF 存在一个“藏层”现象。即, 这样的式子是不标准的,它等价于 。相当于那个 的层被“藏起来”了,因此称为藏层。
根据前文所说, 是一定要找 函数去嵌套的。那么,面对藏层,我们要如何操作呢?
答案是,找到包着 的最近的 函数满足 ,我们视作 函数被藏在了这个 内部。随后进行嵌套,但要在嵌套过程中把内部的 改成 ,即:
举例,考虑 ,最右端是 ,它要找一个最近的 函数满足 n<2,是最外层的 ψ 函数。于是我们按照操作规则得到展开式为 。
BO 是 ,它的基本列是 。从这条基本列中的元素开始按照操作规则展开所得到的式子就是标准的,如果得不到,则是不标准的。
以上就是 BO 前的 BOCF 的直观理解与操作规则。
枚举
MOCF 简介
下面是 MOCF 的数学定义:
可以发现,MOCF 和 BOCF 不同的点在于它把加法、乘法和乘方都放进了 中,而 BOCF 只有加法。因此,MOCF 的 ,并且有 。在出现 的地方,两种 OCF 是一样的,如平台期等概念,二者也是一样的。
下面是引入更多非递归序数的 MOCF 定义:
可以看到和 BOCF 的定义大差不差,唯一的区别是乘法和乘方的引入。因而操作规则无太大差异,除了 。此处不再赘述。
MOCF 的 也是 BO。
枚举
主条目:BOCF VS MOCF
BO 之后
之后,googologist 们实际上已经不再关注其数学定义,因此这里只介绍操作规则。
BOCF 中,我们对每个后继序数 对应的 都定义出 函数满足 和 。MOCF 中则是 和 。如果 β 是个极限序数,则没有对应的 函数。
那么,对于类似 或 的东西,又要如何处理呢?答案是把下标也看做一个运算,如 被看做ΩΩ。展开过程中找最右侧的 时找的是下标的 而非整体的 。换句话说,“找最右侧的 ”本身就要求 α 一定小于 。
以下是补充的操作规则:
,α 为任意序数,~ 代表 + 或 × 或 ^ 或下标。
,如果 β 是极限序数。
这套规则可以一直运用到 ,这个序数称为 EBO。如果想要继续前进,就需要新的非递归序数了,它们会给出它们对应的折叠规则。具体则需要参见对应词条。
那么在这里,我们实际上可以说,OCF 本身是一个和增长层级类似的“壳子”,它们接受对应的非递归序数,然后输出大的递归序数。那么,为什么 OCF 没有像增长层级(如 FGH)一样占据 googology 的所有空间呢?有两方面原因。
第一方面,OCF 没有像增长层级一样具有非常明确的转化规则。googology 社区有一个“俗话”——1000 个人有 1001 种 Mahlo OCF。这种共识的缺乏是致命的。
第二方面,对于目前的 googology 爱好者来说,构造非递归序数的难度和构造其他类型序数记号,如 Worm 型记号,相比,在难度上拉不开差距。不像 FGH 加序数记号对传统数阵记号的“降维打击”。而且,googology 爱好者普遍没有很强的数理逻辑或序数分析基础,难以理解和运用学界所构造的大可数序数。
但我还是希望,伴随着 googology 爱好者水平不断提高,有一天 OCF 加大非递归序数会占据 googology 的主流,而 Worm 型记号会像曾经的数阵记号一样被边缘化。如果是这样,那对于 googology 来说,就是不亚于 2014 年的大飞跃发展了。
定义
MOCF
令 。
的递归共尾度 定义为 的递归的基本列的最小长度。
含第一个非递归序数的 MOCF
含第一个非递归序数 的 MOCF 定义为利用 ,所有的 以及序数加法、乘法、乘方运算,经过任意有限次运算所不能构建的最小序数。特别地,上述定义中的 满足 ,且是能够在有限次运算之中通过 进行加法、乘法、乘方运算,以及将这些序数放到 MOCF 之中所得到的序数。
以上的定义描述了含 的 MOCF 的行为,其集合论定义可以表述如下:
含自然数下标的 MOCF
含有 的 MOCF 标准形式定义为:
- 如果 ,且各 均为标准形式,则 也是标准形式。
- 如果 ,且 均为标准形式,则 为标准形式。
- 如果 ,则 为标准形式。
含有自然数下标的 MOCF 的基本列定义为:
- 若 ,则 且
- ,且
- ,且
- ,且
- 若 ,则 且
- 若 ,则 且
- ,且
- 若 ,则 且
- 若 ,则 且 ,其中
含有自然数下标的 MOCF 定义为利用所有小于 的序数、所有自然数下标的 ,所有自然数下标的 以及序数加法、乘法、乘方运算,经过任意有限次运算所不能构建的最小序数。特别地,上述定义中的 满足 ,且是能够在此前的运算之中得到的序数。
以上的定义描述了含自然数下标 的 MOCF 的行为,其集合论定义可以表述如下:
含序数下标的 MOCF
含有 的 MOCF 标准形式定义为:
- 如果 ,且各 均为标准形式,则 也是标准形式。
- 如果 ,且 均为标准形式,则 为标准形式。
- 如果 ,则 为标准形式。
含有序数下标的 MOCF 的基本列定义为:
- 若 ,则 且
- ,且
- ,且
- ,且
- 若 ,则 且
- 若 ,则 且
- ,且
- 若 ,则 且
- 若 ,则 且 ,其中
含有序数下标的 MOCF 定义为利用所有小于 的序数、所有自然数下标的 ,所有自然数下标的 以及序数加法、乘法、乘方运算,经过任意有限次运算所不能构建的最小序数。特别地,上述定义中的 满足 ,且是能够在此前的运算之中得到的序数。
以上的定义描述了含序数下标 的 MOCF 的行为,其集合论定义可以表述如下:
BOCF
含有 的 BOCF 标准形式定义为:
- 如果 ,且各 均为标准形式,则 也是标准形式。
- 如果 ,则 为标准形式。
- 如果 ,则 为标准形式。
含有序数下标的 BOCF 的基本列定义为:
- 若 ,则 且
- ,且
- 若 ,则 ,且
- ,且
- 若 ,则 ,且
- 若 ,则 且 ,其中
其集合论定义可以表述如下:
NOCF
主条目:NOCF
由于 NOCF 没有完整的定义,这里给出它的理念:
,;在 OCF 内遇到 的处理方式与 MOCF 一致。