论文标题
可计算性和非符号诱导性
Computability and Non-monotone induction
论文作者
论文摘要
在1960年代末和1970年代初研究了非符号诱导定义，目的是理解定义诱导步骤的复杂性与测量归纳持续时间的序数大小之间的连接。通常，任何类型2功能都将产生一个归纳过程，在本文中，我们将将非单调诱导视为3型的功能。我们研究了从Kleene方案继承的相关计算理论，我们研究了与非主持酮诱导中可计算的SETS相关代码相关的代码的性质。观察到通过非符号诱导的结构在其原始形式的经典分析中表现为自然，这是由于观察到这种功能的兴趣。 有两组结果：我们建立了最少有序的强闭合特性，而无需在非符号诱导中计算的代码，我们提供了可根据非单调诱导计算的3型功能类别的表征，这是在经过跨精力量时间内的顺序运算符方面的表征。我们还将看到，当使用此原理来构建目睹康托尔空间的紧凑性和封闭，有界间隔的功能时，需要非单调诱导的全部功能。
Non-monotone inductive definitions were studied in the late 1960's and early 1970's with the aim of understanding connections between the complexity of the formulas defining the induction steps and the size of the ordinals measuring the duration of the inductions. In general, any type 2 functional will generate an inductive process, and in this paper we will view non-monotone induction as a functional of type 3. We investigate the associated computation theory inherited from the Kleene schemes and we investigate the nature of the associated companion of sets with codes computable in non-monotone induction. The interest in this functional is motivated from observing that constructions via non-monotone induction appear as natural in classical analysis in its original form. There are two groups of results: We establish strong closure properties of the least ordinal without a code computable in non-monotone induction, and we provide a characterisation of the class of functionals of type 3 computable from non-monotone induction, a characterisation in terms of sequential operators working in transfinite time. We will also see that the full power of non-monotone induction is required when this principle is used to construct functionals witnessing the compactness of the Cantor space and of closed, bounded intervals.
