序数坍缩函数

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

BOCF

定义

首先我们给出BOCF只引入 $Ω$ 的定义：

$C_{0} (x) = {0, Ω}$
$C_{n + 1} (x) = C_{n} (x) \cup {α + β, ψ (γ) | α, β, γ \in C_{n} (x), γ < x}$
$C (x) = ⋃_{n < ω} C_{n} (x)$
$ψ (x) = m i n {α < Ω | α \in̸ C (x)}$

其中的 $Ω$ 要求是一个足够大的序数。以往的资料一般使用第一个不可数序数 $ω_{1}$ 来作为它。但我们发现，第一个非递归序数 $ω_{1}^{C K}$ 已经可以满足我们的需求。因此，目前提到 $Ω$ ,默认指的是 $ω_{1}^{C K}$ 。

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

规则1： $C_{0} (x) = {0, Ω}$ 。对于任意的x ， $C_{0} (x)$ 是同一个集合。

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

规则3， $C (x)$ 是对所有的 $C_{n} (x)$ 取并集得到的集合。

规则4， $ψ (x)$ 就是所有小于 $Ω$ 的序数中，不属于 $C (x)$ 的最小序数。

$ε_{0}$ 之前

以下是一些运算实例：

$C_{0} (0) = {0, Ω}$

$C_{1} (0) = {0, Ω, Ω \times 2}$

$C_{2} (0) = {0, Ω, Ω \times 2, Ω \times 3, Ω \times 4}$

……

$C (0) = {0, Ω, \dots}$ ,省略号省掉了大于 $Ω$ 的序数

因此 $ψ (0)$ 是最小的小于 $Ω$ 的不在 $C (0)$ 里的序数，即1.

下一个例子是 $ψ (2)$ .首先你已经知道了 $ψ (1) = ω$ ，我们要开始计算 $ψ (2)$ ，还是不展示大于 $Ω$ 的序数

$C_{0} (2) = {0, Ω}$

$C_{1} (2) = {0, ψ (0) = 1, Ω, \dots}$

$C_{2} (2)$ 包含了1，2和 $ψ (1)$ ,即ω。

$C_{3} (2)$ 包含了 $1, 2, 3, 4, ω, ω + 1, ω + 2, ω \times 2$

以此类推，最后能得到 $C (2)$ 中包含了全体小于 $ω^{2}$ 的序数和一大堆大于 $Ω$ 的序数。因此根据定义, $ψ (2) = ω^{2}$

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

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

$ψ (m + 1) = ψ (m) \times ω$ ,m是任意序数
$ψ (λ) = s u p {ψ (κ) | κ < λ}$ ,α是任意非0极限序数

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

$ψ (ω) = ω^{ω} = ψ (ψ (1))$

$ψ (ω + 1) = ω^{ω + 1} = ψ (ψ (1) + 1)$

$ψ (ω \times 2) = ω^{ω \times 2} = ψ (ψ (1) \times 2)$

$ψ (ω^{2}) = ω^{ω^{2}} = ψ (ψ (2))$

$ψ (ω^{ω}) = ω^{ω^{ω}} = ψ (ψ (ψ (1)))$

$ψ (ω^{ω^{ω}}) = ω^{ω^{ω^{ω}}} = ψ (ψ (ψ (ψ (1))))$

……

到这里和康托范式，veblen函数的 $φ (x)$ 都是一致的。然而，在 $ε_{0}$ 开始，OCF将与它们分道扬镳。

MOCF

BOCF

定义

ε0之前

MOCF

$ε_{0}$ 之前