Papers for

proof assistants engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

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

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.

Sun 4 OctLogic in Computer Science
The gist
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.
Open → 2610.05187v1