高级递归论 Higher Recursion Theory

Gerald E.SACKS著  眭跃飞 译

Cambridge University Press, 1990

原作者序

高级递归论(HRT)是我前二十年的两个主要着迷之一. 尽管如此我的兴趣没有被磨灭. 大概因为, 如Browning宣称的:

"最好的是将来的."

我是由G. Kreisel引入到这个主题来的, 一路胆怯. 冒失鬼式坚持, 在开始于1961 年的几次谈话中, 递归论的推广的存在性其中无穷长的计算收敛. 我听了几个小时, 没有懂一个字, 他关于递归论主脉的故事藏在有效描述集合论的主峰下面. 我对他的故事起先的反映是天真的. 一个可以准备推广经典递归论(CRT)的静态(或语法的)方面，比如枚举定理, 但不可能希望提升动态的结果像Friedberg-Muchnik对Post问题的解到高级定义域. 显然CRT的动态方面与某些有限集合的组合性质是不可分离的, 并且这些性质，本质上是“真有限的"，不能有结果地推广. 在1961年我企图证明递归可枚举度的稠密性, 研究有一个有点意思的味道使得所有躁动的追求令人不快的.

在1963年我开始理解Kreisel谈的是什么. 他揭示了ω-逻辑的紧致性定理其中超算术起着有限的作用. 他的结果是: 如果A是ω-逻辑的一个Π¹₁公理集合并且A的每个超算术的子集有一个模型, 则A有一个模型. (这个开眼器是Barwise的Σ₁可允许集合的紧致性定理.) Kreisel1961年的提议, 我的1963年的理解, 是: 替换自然数为超算术集合的一个Π¹₁指数集合J, 并且递归可枚举为Π¹₁的; 大部分重要的结果, 设" 有限的"表示超算术的. 探究他的初始模糊的提议越久, 它变成越清晰. 这是清楚的, 一个" 有限的"集合的" 有限"并是" 有限的". 一个集合A是" 递归的"如果A和I-A是Π¹₁的; 用Kreisel的术语A是超算术于I的. 直接得到一个" 递归的"函数限制于一个" 有限的"集合是" 有限的".

现在看起来CRT的动态结果可以提升了. 新的概念标记为元递归可枚举的, 元有限的, 以及元递归的. 为平滑超算术集合的指数集合I替换为一个递归序数的唯一标识的Π¹₁集合, 最后替换为递归序数集合. 这样一个元递归可枚举集合简单地是一个递归序数集合它的唯一标识构成一个Π¹₁集合. 元递归论的第一个测试. Kreisel 准确地宣称, 是证明Friedberg-Muchnik定理. 一个主要技术障碍出现在路中央. 这是可能的，一个元有限集合的元递归可枚举子集不是元有限的. (这个障碍对我来说是元喜悦的源泉.) 它在1963年由ω到ω₁^CK上的一个部分元递归映射, L上的Jensen的投影技术一个预试, 所克服.

在1966年我完成了元递归论的工作并且设想一个计划来写一本称为高级递归论的书. 部分A将发展超算术理论并包括力迫与紧致性的联系. 部分B将阐述元递归, 而部分C将讨论Σ₁可允许序数. 这个计划的主要缺陷是我忽视了Kleene的有限类型正规对象上的递归论. Platek在1969年Manchester的超跳跃的讲座给了我第一个小立足点于Kleene理论, 并且与Gandy和Grilliot在1970年的长期讨论带我到了主题的顶点. 这样部分D产生了. 在1970年和1980早期相当多的进展出现在可允许序数和有限类型, 因此部分C和部分D一次又一次地重新开始. 甚至超算术理论, 相当稳定了几年, 现在看起来又是新发展.

到1980年我形成了高级递归论(HRT)内容的一个确定的观点. 前进路上只有一个分叉. 自然数变成序数或集合. 如果是序数, 则递归可枚举的变成Σ₁的. 如果是集合, 则属于一个递归可枚举集合意味着存在一个收敛的计算表现为一个良定的, 可能无穷树. 序数处理由G. Takeuti提出的, 集合可计算由S. C. Kleene提出的, 两个均在1950 年代展示. 幸运地每个以不同的方式导致Friedberg-Muchnik定理的一个证明.

HRT的一个早期的希望是通过上述想法发现CRT的新定理. 现在很明显(如常, 几种情况以后)CRT对HRT的应用来说不是足够" 低". 一个HRT定理由克服缺失一些在CRT 中理所当然的组合事实来证明. 向上移动意味着将CRT的一些能力留下. 相同的损失出现当向下移动时. 这是不惊讶的，HRT成功地用在CRT" 向下". 考虑CRT的分离定理: 每个非递归的, 递归可枚举度是两个不可比较的这样度的并. T. Slaman 和H. Woodin证明了分离在Peano算术的一个截断, 称为Σ₁界定, 上是不可证明的. 他们的讨论从HRT吸引到技巧上. M. Mytilinaios证明了分离由Σ₁归纳得到. 他的结果是受R. Shore的每个Σ₁可允许序数的分离定理证明的启发; 它使用Σ₂区块. J. Shinoda和T. Slaman证明了递归集合的多项式时间度理论解释一阶算术. 他们应用Moschovakis的工作(有限类型正规对象的Kleene理论)的一个想法，将发散看着是本质上Σ₁的.

这本书, 非形式地, 是几乎自包含的. 一些讨论呈现, 以一个容易理解的方式, 材料，一个典型的读者鼓励以一个更形式的设置理解. 比如不假设有过Goedel的L的一个课程. L的基本事实是自始给出的, 但一个读者可以需要更多细节. 不需要以前熟悉力迫, 但帮助清晰这书研究的力迫的各种有效概念. 知道CRT越多, 越好, 但假设知道枚举定理, 并且至少知道一个著名的逻辑学家以准备学习在Σ₁可允许序数的设置下在运用到CRT之前的优先方法.

这书有4个部分:

A. 超算术集合

B. 元递归

C. α-递归

D. E-递归

部分A比期望的要长一些. 它徘徊, 如同生命是不短的, 在有效超限递归(ETR), 由Church和Kleene在他们研究序数的标识时发明的方法. 我的处理ETR来自于H. Rogers的, 他是第一个直观地呈现它的. 经典定理证明, 大部分是原先的方式, 定理像递归序数定义可构造序数, Kleene的O是Π¹₁完全的, Σ¹₁界定, 以及超算术的等于Δ¹₁的. 此外测度和力迫发展和运用于一个超算术的上下文中. 所有使得递归于X的序数是递归序数的实数X的集合有测度1. 带超算术可编码的完美集合的力迫产生一个极小超度. 带Σ₁¹$集合(由Gandy发明)的力迫导致Louveau的分离定理. 超算术理论(HT)常常看着, 也是正确地, 是有效描述集合论的源泉. 这本书是高级递归论的序言. 许多HRT的主要发展被笼罩在HT中. 部分B带出上述元递归的进展. 一旦熟悉将超算术的看着" 有限的"就容易懂了. 部分B特别验证Friedberg和Muchnik的优先方法可以在一个更高级的定义域上执行. Simpson的二分法运用元递归来产生新的

Π¹₁集合的类别.

部分C处理α, 一个任意Σ₁可允许序数. Post问题由组合$L$的良好结构和优先方法解决了. 这里的妙语是" Σ₁做Σ₂的事情". 优先方法, 当运用于CRT, 需要Σ₂替换. 在α-递归中借助于有效逼近Σ₁足够了, 向下投影以及Goedel-Jensen压缩. Shore的稠密性定理是一个Σ₃ (更精确地Σ_2.5)的讨论的一个例子，从CRT提升到每个Σ₁可允许的α. 一个早期结果指出这样的α的灵活性是正则集合定理. 一个α的子集是正则的如果它与每个小于α的序数的交是α-有限的(即, 属于L(α)). 一个α-递归可枚举集合可以不是正则的, 但它总是与某个正则的α-递归可枚举集合有相同的α度.

部分D指派一个意思于{e}(x)对每个集合x通过一个计算的概念跟随Normann设计的模式, 并且(因而)Moschovakis. 一个结构是E-封闭的如果它是在运用部分E-递归函数{e}对所有的E下是封闭的. E-封闭结构中的最大的主拧是反映现象的存在以及他们运用于优先和力迫方法，由于Harrington和Kechris发现的一个至关重要的联系于反映序数和Moschovakis发散证据. 在普通水平上, E-递归中进展的关键通常是一个新选取定理, 像由Gandy, Grilliot, Moschovakis和Normann证明的. 这在优先方法中是真的, 甚至在力迫方法中也是. 直观地, 一个选取定理提供一个有效方法选取从非空的" 递归可枚举的"集合中一个元素. van de Wiele的定理解释为什么一些Σ₁函数不是E-递归的. 本书结束于, 我认为合适地, Slaman的E-封闭的L(κ)的稠密性定理.

我特别感谢我的学生写了HRT的这些:

C. Bailey, G. Driscoll, S. Friedman, E. Griffor, L. Harrington, S. Homer, F. Lowenthal, M. Machtey, J. Macintyre, D. MacQueen, J. Owings, R. Shore, S. Simpson, T. Slaman, J. Sukonick and S. Thomason.

也感谢同行付出贡献于HRT: C.T. Chong, J.E. Fenstad, R. Gandy, T. Grilliot, B. Jacobs, S. C. Kleene, G. Kreisel, A. Leggett, M. Lerman,

W. Maass, J. Moldstad, Y. N. Moschovakis, D. Normann, R. Platek, J. Shinoda, C. Spector, G. Takeuti and T. Tugue.

我感谢长期提供资助的the National Science Foundation (Division of Mathematical Sciences). 几次启发性的访问Mathematics Institute at Oberwolfach通过Heidelberg Academy的慷慨和贡献于G.H. Mueller的逻辑.

这书是由M. Beucler和L. Schlesinger录入的, 他们的耐心是可佳的. 书稿由Brian O'Neill阅读过, 他提出许多数学的和语法的建议. 最后感谢J.B. Rosser (1907-1989), A.Nerode, H.Rogers和B. Dreben. 最后4位使我开始并坚持下来. 如果他们满意HRT, 那我也满意.

 Gerald E. Sacks

June 1990

Cambridge, Chicago, Pasadena and Princeton

目录

注: 如果需要全文的, 请email我: yfsui@ict.ac.cn.