TY - JOUR
T1 - Modal dependent type theory and dependent right adjoints
AU - Birkedal, Lars
AU - Clouston, Ranald
AU - Mannaa, Bassel
AU - Møgelberg, Rasmus Ejlers
AU - M. Pitts, Andrew
AU - Spitters, Bas
PY - 2019/12
Y1 - 2019/12
N2 - 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.
AB - 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.
KW - Dependent type theory
KW - modal logic
KW - category theory
KW - Dependent type theory
KW - modal logic
KW - category theory
U2 - 10.1017/S0960129519000197
DO - 10.1017/S0960129519000197
M3 - Journal article
SN - 0960-1295
JO - Mathematical Structures in Computer Science
JF - Mathematical Structures in Computer Science
ER -