递归函数（十）

为了提供一些分析层次结构的说明，记录以下内容很有用：

定义 3.19：集合 �⊆� 在 ��2 中隐式可定义，只要存在一个算术公式 �(�)，其 � 为其唯一自由集变量，没有自由数变量，并且 � 是 ��2 标准模型中满足 �(�) 的唯一集合。

真算术 (TA) 对应于 �� 标准模型中为真的一阶算术句子的哥德尔数集，即 TA={⌜�⌝:�∈�� ∧ �⊨�}。在定义解析层次结构之前，Hilbert & Bernays 已经证明了以下内容：

定理 3.14（Hilbert & Bernays 1939：§5.2e）：TA 在��2 中隐式可定义。

因此，不难证明以下内容：

命题 3.10（Spector 1955）：如果 � 是隐式可定义的，则 � 在 ��2 中 Δ11 可定义。

因此，TA 是 Δ11 可定义的。另一方面，根据塔斯基关于真不可定义定理，TA 不是算术可定义的，即对于任何 �∈�，TA∉Σ�0∪Π�0。这反过来表明解析集适当地扩展了算术集。

�的Δ11可定义子集类也与克莱尼最初对超算术集类的研究有关，通常表示为HYP。 HYP 的定义取决于克莱恩于 1938 年引入的构造性序数符号系统，即�=⟨�,＜�⟩。（这也是在定义�的背景下，他证明了递归定理 3.5——见 Rogers 1987：第 11.7 章和 Y. Moschovakis 2010。）HYP 可以非正式地描述为自然数集类�，使得�≤�∅(�)，其中�是接受符号�∈�的序数，即�∈HYP，以防它可以通过图灵跳跃的超限迭代计算到第一个非递归序数�1��。[32] 克莱恩的原始结果如下：[33]

定理 3.15（Kleene 1955b）：集合 �⊆� 当且仅当 �∈HYP 时才是 Δ11 可定义的。

分析层次的下一步涉及 Π11 可定义集的表征。Kleene (1955a) 最初使用二阶算术语言的变体建立了 ��2 公式的范式定理，该语言包含函数量词 �,�,ℎ,…，其范围是 �→�，而不是集合量词，其范围是 �(�)（Rogers 1987：第 16.2 章）。在这种情况下，可以证明以下内容：

命题 3.11：当且仅当存在可计算（即可 Δ10 定义）关系 �(�,�) 时，�∈Π11，使得

当且仅当 ∀�∃��(�,�―(�)) 时，�∈�

其中 �―(�) 表示 ⟨�(0),…,�(�−1)⟩。

对于每个这样的关系，我们还可以定义一个可计算树 Tr�，它由有限序列 �∈�＜� 组成，使得对于所有适当的初始子序列 �⊂�, ¬�(�,�) 成立。因此，这棵树中的叶节点对应于 � 成立的第一个位置。因此，Tr� 中的无限路径对应于一个函数�，使得 ∀�¬�(�,�―(�))，而该函数又是�∉�的见证。因此，当且仅当 Tr� 是良基的，�∈�。由于有效地枚举可计算树很简单，因此证明以下内容也不难：

命题 3.12：对于 Π11 可定义集，良基可计算树的索引集�是 m 完全的，即�∈Π11，并且对于所有�∈Π11，�≤��。

回想一下�表示自然数集，它们是 Kleene 的�中序数的符号，相关结果如下：

命题 3.13：�是 Π11 完全的。

然后可以使用层次定理 3.13 证明 � 和 � 都不是 Σ11 可定义的。这些结果为根据构造序数对 Δ11 和 Π11 可定义集的结构进行归纳分析提供了基础，该分析建立在定理 3.15 的基础上（参见 Rogers 1987：第 16.4 章）。

上述结果均涉及使用 ��2 公式描述自然数集。将分析层次结构与经典描述集理论联系起来的初始步骤是通过考虑定义子类 �⊆�(�) 的公式 �(�) 来实现的。在这种情况下，�∈� 可以等同于其特征函数 ��(�) 的图形——即，一个无限序列，如果 �∈�，则其 �第 � 个元素为 1，如果 �∉�，则其 0。这样，具有单个自由集变量的公式 �(�) 可以理解为定义康托空间 �=2� 的一个子集，该子集由所有无限 0-1 序列组成，而公式 �(�→) 具有 �1,…,�� 自由，可以理解为定义 2�×…×2� 的一个子类。

在描述集理论中，在定义 Borel 集和射影集的背景下，给出了 � 子类的拓扑定义的并行序列。首先回想一下，在 � 上定义拓扑的一种方法是将所有函数集 �:�→{0,1} 设为基本开集，使得 �―(�)=�，其中 �∈2＜� 和 �∈�。现在，通过定义�10 为�的所有开集的集合，��0（对于�≥1）为集合�∈�10 的所有补集�―的集合，以及��+10 为所有可数并集⋃�∈���的集合，其中��∈��0。（因此，�10 表示闭集集合，�20 表示所谓的��集合，�20 表示��集合，等等）这些类的并集对应于粗体波雷尔集�，其也可以表征为包含�的开集的最小集合类，其在可数并集和补集下是封闭的。所谓的解析集被定义为 Borel 集的连续像，用 �11 表示，而共解析集被定义为解析集的补集，用 �11 表示。最后，�11 用于表示解析集和共解析集的交集。

Addison 观察到（1958、1959），这些经典定义可以通过在 ��0 集的定义中限制为可计算并集来实现。这导致了所谓的 Borel 层次结构的轻面版本——通常使用与算术层次结构级别相同的符号 Σ�0 和 Π�0 来表示——以及 Σ11（即轻面解析）、Π11（即轻面共解析）和 Δ11 集的相应定义。具体而言，这一系列定义表明定理 3.15 与 Suslin 的以下经典结果之间存在类比：

定理 3.16（Suslin 1917）：�11 集合类等于 Borel 集合�类。

定理 3.16 的有效形式将�的 Δ11 子集与可计算代码表示的光面 Borel 集联系起来，可以从 Kleene 对定理 3.15 的原始证明中获得（例如，参见 Y. Moschovakis 2009：第 7B 章）。 Addison 还表明，同样可以得到 Lusin 定理 (1927) 的有效版本——即“任何两个不相交的解析集都可以被 Borel 集分开”——以及 Kondô 定理 (1939) 的有效版本——即“每个 �11 关系都可以被 �11 关系统一化”。参见 Y. Moschovakis (2009: ch. 2E,4E) 以及 Simpson (2009: ch. V.3,VI.2)

4. 进一步阅读

Sieg (2009)、Adams (2011) 和 Soare (2016: part V) 提供了递归函数和可计算性理论早期发展的历史概述。第 1 节中讨论的许多原始资料都收录在 Davis (1965)、van Heijenoort (1967) 和 Ewald (1996) 的文集中。介绍初级和中级可计算性理论的教科书包括 Hopcroft & Ulman (1979)、Cutland (1980)、Davis、Sigal & Weyuker (1994) 和 Murawski (1999)。第 2 节和第 3 节中提出的材料（直到 Post 问题的提出）的原始教科书阐述包括 Kleene (1952)、Shoenfield (1967) 和 Rogers (1987；第一版 1967)。多一结构和图灵度在更高级的教科书中有所介绍，例如 Sacks (1963a)、Shoenfield (1971)、Hinman (1978)、Soare (1987)、Cooper (2004) 和 Soare (2016)。除了 Shoenfield (1967: ch. 7) 和 Rogers (1987: ch. 16) 之外，超算术和分析层次结构的经典处理是 Sacks (1990)。经典和有效的描述集理论由 Y. Moschovakis (2009, 第一版 1980) 和 Kechris (1995) 发展。Simpson (2009) 发展了可计算性理论和逆向数学之间的联系。 （这对应于用语言��2表述的完整二阶算术子理论的公理研究。这样的理论形成一个层次结构RCA0⊂WKL0⊂ACA0⊂ATR0⊂Π11-CA0，其中可以发展许多古典数学，并且其模型可以用可计算性理论方法来表征——例如，递归集形成RCA0的最小� 模型，算术集形成ACA0的最小� 模型，等等。参见“逆向数学”条目。）Péter (1967)、Rose (1984)、Clote & Kranakis (2002：第 6-7 章) 和 Schwichtenberg & Wainer (2011) 提供了子递归层次结构的处理以及与证明理论和理论计算机科学的联系。本条目调查的许多历史和数学主题也在 Odifreddi 的两卷《古典递归理论》（1989、1999a）中得到了更详细的介绍，其中包含许多额外的历史参考。