更改

证明需要同时构造'''两个互相缠绕的函数'''（互相引用对方编号），由双递归定理（见 §5.2 的 [[雷蒙德·斯穆里安|Smullyan]] 版本）合法化——这是有效超限递归技术的高峰之一。Kleene 对这个学生的工作推崇备至，他常讲自己如何"行为不端"地接受它作为博士论文、又作为期刊编辑指定自己为审稿人并立即录用——"非常不合规矩，但我认为最终有利于逻辑！"<ref name="moschovakis2010" />。

证明需要同时构造'''两个互相缠绕的函数'''（互相引用对方编号），由双递归定理（见 §5.2 的 [[雷蒙德·斯穆里安|Smullyan]] 版本）合法化——这是有效超限递归技术的高峰之一。Kleene 对这个学生的工作推崇备至，他常讲自己如何"行为不端"地接受它作为博士论文、又作为期刊编辑指定自己为审稿人并立即录用——"非常不合规矩，但我认为最终有利于逻辑！"<ref name="moschovakis2010" />。

=== 沿序数逐层构造之四：HYP = \Delta^1_1 与有效描述集合论 ===

=== <math>HYP = \Delta^1_1</math> 与有效描述集合论 ===

'''背景'''：在自然数的集合（数学分析的对象）上，可以用"二阶量化"分层：<math>\Sigma^1_1</math> 集是"存在一个实数使得某个可计算性质成立"的集合（存在投影），<math>\Pi^1_1</math> 是其对偶（全称），<math>\Delta^1_1 = \Sigma^1_1 \cap \Pi^1_1</math> 是"两面都可定义"的集合——可类比为分析学中"既可开逼近又可闭逼近"的集合。

'''背景'''：在自然数的集合（数学分析的对象）上，可以用"二阶量化"分层：<math>\Sigma^1_1</math> 集是"存在一个实数使得某个可计算性质成立"的集合（存在投影），<math>\Pi^1_1</math> 是其对偶（全称），<math>\Delta^1_1 = \Sigma^1_1 \cap \Pi^1_1</math> 是"两面都可定义"的集合——可类比为分析学中"既可开逼近又可闭逼近"的集合。

> '''Kleene 定理（1955）'''：自然数的集合 A 是 <math>\Delta^1_1</math> 的，当且仅当 A 是超算术的（HYP）。<ref name="kleene1955" /><ref name="moschovakis2010" />

* '''Kleene 定理（1955）'''：自然数的集合 A 是 <math>\Delta^1_1</math> 的，当且仅当 A 是[[超算术]]的（HYP）<ref name="kleene1955" /><ref name="moschovakis2010" />。

这把可计算性理论（HYP，由机器和序数定义）与描述集合论（<math>\Delta^1_1</math>，由投影/量化定义）两大传统焊接在一起，是 Kleene 获 1983 年 AMS Steele 奖的核心成果之一。证明的两个引理（[[Kleene's O]] 是 <math>\Pi^1_1</math> 集、且是 <math>\Pi^1_1</math> 中"最复杂"的完备集）都靠 SRT 沿良基树作有效超限递归建立。<ref name="moschovakis2010" />

这把可计算性理论（HYP，由机器和序数定义）与[[描述集合论]]（<math>\Delta^1_1</math>，由投影/量化定义）两大传统焊接在一起，是 Kleene 获 1983 年 AMS Steele 奖的核心成果之一。证明的两个引理（[[Kleene's O]] 是 <math>\Pi^1_1</math> 集、且是 <math>\Pi^1_1</math> 中"最复杂"的完备集）都靠 SRT 沿良基树作[[有效超限递归]]建立<ref name="moschovakis2010" />.

在此基础上，SRT 向实数空间（[[贝尔空间|Baire 空间]]，即自然数无穷序列的空间）推广后，成为'''有效描述集合论'''的引擎，三个代表性结果：

在此基础上，SRT 向实数空间（[[贝尔空间|Baire 空间]]，即自然数无穷序列的空间）推广后，成为'''[[有效描述集合论]]'''的引擎，三个代表性结果：

1. '''Suslin–Kleene 定理'''：[[博雷尔集|Borel 集]]（从开集出发经可数次并、交、补生成的集合）与 <math>\Delta^1_1</math> 集之间可以可计算地互译。它同时蕴含经典 [[米哈伊尔·苏斯林|Suslin]] 定理（<math>\Delta^1_1 = Borel</math>）和上述 Kleene 定理，是两大传统的汇合点<ref name="moschovakis2010" />；

1. '''[[Suslin–Kleene定理]]'''：[[博雷尔集|Borel 集]]（从开集出发经可数次并、交、补生成的集合）与 <math>\Delta^1_1</math> 集之间可以可计算地互译。它同时蕴含经典 [[米哈伊尔·苏斯林|Suslin]] 定理（<math>\Delta^1_1 = Borel</math>）和上述 Kleene 定理，是两大传统的汇合点<ref name="moschovakis2010" />；

2. '''赋范归纳定理'''（Moschovakis 1974）：对带有良好"秩函数"结构的归纳定义，其最小/最大不动点保持在相应的可定义层级内。它的证明使用"关系版 SRT"（不动点代码 <math>\varepsilon</math>* 使自己的每个后继元组都由自己的前段定义）。这可视为对 Kleene 1944 年错误（见 3.3）的"正确打开方式"：SRT 只给某个不动点，要拿到'''最小'''不动点需要额外的秩结构<ref name="moschovakis2010" />；

2. '''[[赋范归纳定理]]'''（Moschovakis 1974）：对带有良好"秩函数"结构的归纳定义，其最小/最大不动点保持在相应的可定义层级内。它的证明使用"关系版 SRT"（不动点代码 <math>\varepsilon</math>* 使自己的每个后继元组都由自己的前段定义）。这可视为对 Kleene 1944 年错误（见 3.3）的"正确打开方式"：SRT 只给某个不动点，要拿到'''最小'''不动点需要额外的秩结构<ref name="moschovakis2010" />；

3. '''编码引理'''（Moschovakis 1970）：在 ZF+DC+'''AD'''（确定性公理，一个与大[[基数]]理论相关的集合论假设）下，若[[连续统]]可满射到基数 <math>\kappa</math>，则可满射到 <math>\kappa</math> 的幂集。证明通过'''带参数的 SRT'''作有效超限递归——SRT 由此进入基数算术这一纯集合论领域；它还是 '''Jackson 定理'''（1989：在 AD 下，三型存在量词的 Kleene 序数恰好等于'''最小的弱不可达基数'''）的基本工具——这是连接高类型递归论与大基数理论的最惊人结果之一<ref name="moschovakis2010" />。

3. '''[[编码引理]]'''（Moschovakis 1970）：在 ZF+DC+AD（确定性公理，一个与大[[基数]]理论相关的集合论假设）下，若[[连续统]]可满射到基数 <math>\kappa</math>，则可满射到 <math>\kappa</math> 的幂集。证明通过'''带参数的 SRT'''作有效超限递归——SRT 由此进入基数算术这一纯集合论领域；它还是 '''[[Jackson 定理]]'''（1989：在 AD 下，三型存在量词的 Kleene 序数恰好等于'''最小的弱不可达基数'''）的基本工具——这是连接高类型递归论与大基数理论的最惊人结果之一<ref name="moschovakis2010" />。

此外，Kleene 1940 年代为直觉主义数学（拒绝排中律的构造性数学）构造的'''可实现性（realizability）'''&#x89E3;释中，bar 递归定义、bar 归纳与连续性原理的验证也本质地使用 SRT 的各种形式<ref name="moschovakis2010" />。

此外，Kleene 1940 年代为直觉主义数学（拒绝排中律的构造性数学）构造的'''可实现性（realizability）'''中，[[bar递归定义]]、[[bar归纳]]与[[连续性原理]]的验证也本质地使用 SRT 的各种形式<ref name="moschovakis2010" />。

=== r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill ===

=== r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill ===