Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2020.25
URN: urn:nbn:de:0030-drops-123472
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12347/
Xu, Chuangjie
A Gentzen-Style Monadic Translation of Gödel’s System T
| pdf-format: |
|
Abstract
We introduce a syntactic translation of Gödel’s System 𝖳 parametrized by a weak notion of a monad, and prove a corresponding fundamental theorem of logical relation. Our translation structurally corresponds to Gentzen’s negative translation of classical logic. By instantiating the monad and the logical relation, we reveal the well-known properties and structures of 𝖳-definable functionals including majorizability, continuity and bar recursion. Our development has been formalized in the Agda proof assistant.
BibTeX - Entry
@InProceedings{xu:LIPIcs:2020:12347,
author = {Chuangjie Xu},
title = {{A Gentzen-Style Monadic Translation of G{\"o}del’s System T}},
booktitle = {5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
pages = {25:1--25:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-155-9},
ISSN = {1868-8969},
year = {2020},
volume = {167},
editor = {Zena M. Ariola},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12347},
URN = {urn:nbn:de:0030-drops-123472},
doi = {10.4230/LIPIcs.FSCD.2020.25},
annote = {Keywords: monadic translation, G{\"o}del’s System T, logical relation, negative translation, majorizability, continuity, bar recursion, Agda}
}
| Keywords: | monadic translation, Gödel’s System T, logical relation, negative translation, majorizability, continuity, bar recursion, Agda | |
| Seminar: | 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 28.06.2020 | |
| Supplementary Material: | Agda development: https://github.com/cj-xu/GentzenTrans |
