CKO

CKO（Church-Kleene Ordinal），是可数序数的上确界。

定义

Church-Kleene 序数，记作 ${\omega }_1^{\mathrm{C}\mathrm{K}}$，是可计算序数（computable ordinals）的上确界。具体来说，它是在可计算良序（computable well-orderings）的序型（order types）集合中的最小不可数上界。

形式化定义

设 $\mathrm{O}$ 是所有可计算良序的序型构成的集合。即，若 $\prec$ 是一个可计算关系（存在一个图灵机可以判定对于任意的 $x,y$，是否有 $x\prec y$），且 $(A,\prec )$ 是一个良序集（well-ordered set），其中 $A\subseteq \mathrm{N}$，则该良序的序型 $\mathrm{otype}(A,\prec )\in \mathrm{O}$。那么，

${\omega }_1^{\mathrm{C}\mathrm{K}}=\sup \{\mathrm{otype}(A,\prec ):(A,\prec )\text{ 是可计算良序}\}$

性质

不可递归枚举性：不存在一个图灵机可以枚举出所有小于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的可计算序数。换句话说，集合 $\{\alpha <{\omega }_1^{\mathrm{C}\mathrm{K}}:\alpha \text{ 是可计算序数}\}$ 不是递归可枚举的。这是因为如果存在这样的图灵机，我们可以利用它构造出一个更大的可计算序数，从而与 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是可计算序数的上确界这一性质矛盾。

不可超递归性：${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 本身不是可计算序数。因为如果 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是可计算的，那么我们可以构造出一个可计算良序，其序型大于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​（通过在已有的可计算良序基础上进行适当的扩展），这与 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的定义矛盾。

在可计算分析中，${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是超穷归纳原理（transfinite induction）在可计算结构上能够有效应用的最大序数。对于任何小于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的序数 $\alpha$，我们可以在可计算的意义下对序型为 $\alpha$ 的良序进行归纳。但对于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$ 本身，不存在这样的可计算归纳过程。

${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 与算术层次（arithmetic hierarchy）有着密切的联系。可计算序数可以看作是在算术可定义性框架内能够构造和研究的序数。${\omega }_1^{\mathrm{C}\mathrm{K}}$的存在表明，在算术可定义性的范围内，序数的研究有一个自然的界限。具体来说，${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是 ${\mathrm{\Delta }}_1^1$​ 完备的，这意味着它是所有 ${\mathrm{\Delta }}_1^1$​ 集合中序型最大的元素（在序数的序关系下），并且任何 ${\mathrm{\Delta }}_1^1$​ 集合的序型都小于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​。

历史背景

Church-Kleene 序数得名于数学家 Alonzo Church 和 Stephen Cole Kleene。他们在 20 世纪 30 年代和 40 年代对递归函数理论和可计算性进行了深入研究，提出了许多重要的概念和结果，其中包括可计算序数和 Kleene 的 O 记号系统。${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的概念为递归理论和可计算分析提供了一个重要的界限和基准，使得研究人员能够更清晰地划分可计算和不可计算的对象在序数结构中的位置。