Modal dependent type theory and dependent right adjoints
- 12 December 2019
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 30 (2) , 118-138
Abstract
In recent years, we have seen several new models of dependent type theory extended with some form of modal necessity operator, including nominal type theory, guarded and clocked type theory and spatial and cohesive type theory. In this paper, we study modal dependent type theory: dependent type theory with an operator satisfying (a dependent version of) the K axiom of modal logic. We investigate both semantics and syntax. For the semantics, we introduce categories with families with a dependent right adjoint (CwDRA) and show that the examples above can be presented as such. Indeed, we show that any category with finite limits and an adjunction of endofunctors give rise to a CwDRA via the local universe construction. For the syntax, we introduce a dependently typed extension of Fitch-style modal λ-calculus, show that it can be interpreted in any CwDRA, and build a term model. We extend the syntax and semantics with universes.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- A Dependent Type Theory with Abstractable NamesElectronic Notes in Theoretical Computer Science, 2015
- Integrating Linear and Dependent Types2015
- Programming and Reasoning with Guarded Recursion for Coinductive Types2015
- The biequivalence of locally cartesian closed categories and Martin-Löf type theoriesMathematical Structures in Computer Science, 2014
- Intensional Type Theory with Guarded Recursive Types qua Fixed Points on Universes2013
- First steps in synthetic guarded domain theory: step-indexing in the topos of treesLogical Methods in Computer Science, 2012
- Propositions as [Types]Journal of Logic and Computation, 2004
- A modality for recursion2002
- A modal analysis of staged computationJournal of the ACM, 2001
- A Computational Interpretation of Modal Proofs1996