3,094
个编辑
更改
跳到导航
跳到搜索
第623行：
第623行： − + − {{Anchor|6.4}} − +
→超算术级与有效描述集合论
证明需要同时构造'''两个互相缠绕的函数'''（互相引用对方编号），由双递归定理（见 [[#推论：SRT 衍生出的若干重要结果|§5.2]] 的 [[雷蒙德·斯穆里安|Smullyan]] 版本）合法化——这是有效超限递归技术的高峰之一。Kleene 对这个学生的工作推崇备至，他常讲自己如何"行为不端"地接受它作为博士论文、又作为期刊编辑指定自己为审稿人并立即录用——"非常不合规矩，但我认为最终有利于逻辑！"<ref name="moschovakis2010" />。
证明需要同时构造'''两个互相缠绕的函数'''（互相引用对方编号），由双递归定理（见 [[#推论：SRT 衍生出的若干重要结果|§5.2]] 的 [[雷蒙德·斯穆里安|Smullyan]] 版本）合法化——这是有效超限递归技术的高峰之一。Kleene 对这个学生的工作推崇备至，他常讲自己如何"行为不端"地接受它作为博士论文、又作为期刊编辑指定自己为审稿人并立即录用——"非常不合规矩，但我认为最终有利于逻辑！"<ref name="moschovakis2010" />。
==== 超算术级与有效描述集合论 ====
==== 超算术集与有效描述集合论 ====
'''背景'''：在自然数的集合（数学分析的对象）上，可以用"[[二阶量词]]"分层：<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">Kleene, S. C. (1955). On the forms of the predicates in the theory of constructive ordinals (second paper). ''American Journal of Mathematics'', 77, 405–428.【<math>\Delta^1_1</math> = 超算术集合（HYP）的原始定理出处（§[[超算术级与有效描述集合论|5.8.4]]）】</ref><ref name="moschovakis2010" />。
* '''Kleene 定理（1955）'''：自然数的集合 A 是 <math>\Delta^1_1</math> 的，当且仅当 A 是[[超算术]]的（HYP）<ref name="kleene1955">Kleene, S. C. (1955). On the forms of the predicates in the theory of constructive ordinals (second paper). ''American Journal of Mathematics'', 77, 405–428.【<math>\Delta^1_1</math> = 超算术集合（HYP）的原始定理出处（§[[超算术集与有效描述集合论|5.8.4]]）】</ref><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" />.