Gentzen-style monadic translation extends Gödel's System T with new tools
The Gentzen-style monadic translation of Gödel's System T revisited
Logic in Computer Science
Summary
Gödel’s System T is a foundational system in mathematical logic used to represent computations. This paper revisits a way to translate System T terms using a structure called a nucleus that acts like a monad but doesn’t have to follow all monad rules. By picking different nuclei, the authors show how to represent various mathematical concepts such as measures of function size, continuity, and recursion inside System T. They also improve and expand the translation for more data types and provide comparisons with another translation style. This work helps understand and manipulate computational properties within a unified logical framework.
What this means in practice
- •For functional programming developers: Use the refined translation to represent and verify continuity and recursion properties within functional programs.
- •For proof assistants engineers: Incorporate extended monadic translations to enhance correctness proofs involving sums, lists, and recursion in formal verifications.
Authors
Chuangjie Xu
Abstract
We revisit the Gentzen-style monadic translation of Gödel's System T. The translation is parametrized by a nucleus, a monad-like structure that need not satisfy the monad laws. A fundamental theorem of logical relations provides a uniform correctness argument for its instances. By choosing suitable nuclei, we obtain majorants, moduli of pointwise and uniform continuity, internal dialogue trees, and functionals of general bar recursion, all represented by terms of T. The internal dialogue-tree application gives a simpler construction, with correctness established directly using Church-encoded terms. We also extend the translation and its fundamental theorem to sums and finite lists. Finally, we develop the Kuroda-style translation and its continuity instance, comparing the moduli obtained with those of the Gentzen-style translation.