On bar recursive interpretations of analysis
On bar recursive interpretations of analysis
复制标题
On bar 分析的递归解释
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Thomas Powell
中科院分区：
文献类型：
--
作者：
Thomas Powell
本文通过证明解释来关注分析的计算解释，并考察了用于解释选择公理的酒吧递归的变体。它由应用和理论组成。应用部分包含了一系列的案例研究，解决了理解的意义和行为的酒吧递归程序提取证明分析的问题。以最近的工作为出发点埃斯卡多和奥利瓦的产品选择功能，解决哥德尔的功能解释的几个著名的数学定理，并语义提取的程序描述。特别是，新的博弈论的计算解释发现弱柯尼希引理的101-树和最小坏序列参数。在理论方面，建立了几个新的可定义性结果，涉及各种模式的酒吧递归。首先，定义了系统T的基于有限条递归的片段的层次结构，并证明了这些片段与通常的基于本原递归的片段是一一对应的.其次，它表明，所谓的“特殊”的变种斯佩克特的酒吧递归实际上定义了一般的。最后，证明了在连续泛函模型下，修正的bar递归（以选择函数的隐控制积的形式）、开递归、更新递归和可数选择的Berardi-BezemCoquand实现子都是本原递归等价的.
This dissertation concerns the computational interpretation of analysis via proof interpretations, and examines the variants of bar recursion that have been used to interpret the axiom of choice. It consists of an applied and a theoretical component. The applied part contains a series of case studies which address the issue of understanding the meaning and behaviour of bar recursive programs extracted from proofs in analysis. Taking as a starting point recent work of Escardó and Oliva on the product of selection functions, solutions to Gödel’s functional interpretation of several well known theorems of mathematics are given, and the semantics of the extracted programs described. In particular, new game-theoretic computational interpretations are found for weak König’s lemma for Σ1-trees and for the minimal-bad-sequence argument. On the theoretical side several new definability results which relate various modes of bar recursion are established. First, a hierarchy of fragments of system T based on finite bar recursion are defined, and it is shown that these fragments are in one-to-one correspondence with the usual fragments based on primitive recursion. Secondly, it is shown that the so called ‘special’ variant of Spector’s bar recursion actually defines the general one. Finally, it is proved that modified bar recursion (in the form of the implicitly controlled product of selection functions), open recursion, update recursion and the Berardi-BezemCoquand realizer for countable choice are all primitive recursively equivalent in the model of continuous functionals.
DOI：
10.1016/j.apal.2011.12.009
发表时间：
2012
期刊：
Ann. Pure Appl. Log.
影响因子：
--
作者：
Kohlenbach
通讯作者：
Kohlenbach
DOI：
10.2178/jsl/1344862165
发表时间：
2012
期刊：
The Journal of Symbolic Logic
影响因子：
--
作者：
Kreuzer;Kohlenbach
通讯作者：
Kohlenbach
序贯弱紧性的统一定量形式及Baillon非线性遍历定理
影响因子：
1.6
作者：
Kohlenbach
通讯作者：
Kohlenbach