Homotopy type theory enables strict models from flexible ones
A General Construction of Strict Models in HoTT
Logic in Computer ScienceProgramming Languages
Summary
Type theory is a framework to describe and reason about mathematical and computational structures. Homotopy type theory (HoTT) extends this framework, offering new principles that help study how these descriptions behave. The authors show how to turn approximate or flexible models within HoTT into fully strict, reliable models that align perfectly with the theory’s rules, using an existing universe construction method. Their work clarifies how these strict models can be built more generally and applies this approach to multiple examples, all verified in a formal system.
What this means in practice
- •For type theory tool developers: Implement more general methods to construct sound and strict models of type theories within homotopy type theory-based proof assistants.
- •For programming language designers: Use the construction of strict models in HoTT to better understand semantics of advanced type systems ensuring soundness of language features.
Authors
Niyousha Najmaei, Niels van der Weide
Abstract
Homotopy type theory (HoTT) provides a natural setting for studying the metatheory of type theory, as it comes with additional extensionality principles compared to ordinary Martin-Löf type theory. In particular, it is especially suitable for developing semantics of type theory, where one distinguishes two kinds of models: strict models, which give us sound interpretations, and pseudomodels. Pseudomodels are useful as they occur prevalently and can be turned into strict models by constructions called strictifications. However, the commonly used strictifications do not translate well to HoTT, as they require assumptions that are generally not satisfied by concrete examples of models. We show how to carry out the universe model construction, due to Voevodsky, in HoTT. Under this construction, every pseudomodel together with a universe type closed under enough type formers gives rise to a strict model. We also show how to interpret type formers in the resulting model assuming that the universe is closed under them. Finally, we demonstrate that this construction generalises existing instances of strict set models in the literature, and we apply it to more examples, yielding presheaf models and assembly models of type theory in HoTT. Our results are formalised in Rocq using the UniMath library.