Circular and non-wellfounded proofs have become an increasingly popular tool for metalogical treatments of systems with forms of induction and/or recursion. In this work we investigate the expressivity of a variant CT of G\"odel's system T where programs are circularly typed, rather than including an explicit recursion combinator. In particular, we examine the abstraction complexity (i.e. type level) of C, and show that the G\"odel primitive recursive functionals may be typed more succinctly with circular derivations, using types precisely one level lower than in T. In fact we give a logical correspondence between the two settings, interpreting the quantifier-free type 1 theory of level n+1 T into that of level n C and vice-versa. We also obtain some further results and perspectives on circular 'derivations', namely strong normalisation and confluence, models based on hereditary computable functionals, continuity at type 2, and a translation to terms of $\T$ computing the same functional, at all types.
翻译:圆形和无根据的证明已成为一种日益流行的工具,用于对具有诱导和(或)循环形式的系统进行元学处理。在这项工作中,我们调查了程序循环键入的G\“odel”系统T的变体CT的表达性,而不是包括一个明确的循环组合器。特别是,我们研究了C的抽象复杂性(即类型级别),并表明G\“odel原始循环功能”可以更简洁地以循环衍生方式打字,使用的类型比T低一个层次。事实上,我们给出了两种环境之间的逻辑对应,将n+1 T级的限定性1型理论解释为n C级和反转。我们还获得了关于循环“递归(即强的正常化和连带作用)”的一些进一步的结果和观点,即基于遗传可兼容功能的模型、2型的连续性和所有类型计算相同功能的翻译值为$\T$。