z-logo
open-access-imgOpen Access
Continuity of Gödelʼs System T Definable Functionals via Effectful Forcing
Author(s) -
Martı́n Hötzel Escardó
Publication year - 2013
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2013.09.010
Subject(s) - type theory , forcing (mathematics) , mathematics , dependent type , type (biology) , interpretation (philosophy) , programming language , semantics (computer science) , system f , discrete mathematics , computer science , algebra over a field , pure mathematics , lambda calculus , mathematical analysis , ecology , biology
It is well-known that the Gödelʼs system T definable functions (N→N)→N are continuous, and that their restrictions from the Baire type (N→N) to the Cantor type (N→2) are uniformly continuous. We offer a new, relatively short and self-contained proof. The main technical idea is a concrete notion of generic element that doesnʼt rely on forcing, Kripke semantics or sheaves, which seems to be related to generic effects in programming. The proof uses standard techniques from programming language semantics, such as dialogues, monads, and logical relations. We write this proof in intensional Martin-Löf type theory (MLTT) from scratch, in Agda notation. Because MLTT has a computational interpretation and Agda can be seen as a programming language, we can run our proof to compute moduli of (uniform) continuity of T-definable functions

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom