Modal Dependent Type Theory and Dependent Right Adjoints
Authors:
- Ranald CloustonRCRanald Clouston
- Bassel MannaaBMBassel Mannaa
- Rasmus Ejlers MøgelbergRMRasmus Ejlers Møgelberg
- Bas SpittersBSBas Spitters
Preprint
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 finite limit category with an adjunction of endofunctors gives rise to a CwDRA via the local universe construction. For the syntax, we introduce a dependently typed extension of Fitch-style modal lambda-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 12 references indexed in Scilit:
- Denotational semantics for guarded dependent type theoryMathematical Structures in Computer Science, 2020
- Guarded Cubical Type TheoryJournal of Automated Reasoning, 2018
- Parametric quantifiers for dependent type theoryProceedings of the ACM on Programming Languages, 2017
- Brouwer's fixed-point theorem in real-cohesive homotopy type theoryMathematical Structures in Computer Science, 2017
- A Dependent Type Theory with Abstractable NamesElectronic Notes in Theoretical Computer Science, 2015
- Integrating Linear and Dependent TypesACM SIGPLAN Notices, 2015
- First Steps in Synthetic Guarded Domain Theory: Step-Indexing in the Topos of Trees2011
- Propositions as [Types]Journal of Logic and Computation, 2004
- A modal analysis of staged computationJournal of the ACM, 2001
- On the interpretation of type theory in locally cartesian closed categories1995