License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2021.3
URN: urn:nbn:de:0030-drops-167724
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16772/
Go to the corresponding LIPIcs Volume Portal

Bocquet, Rafaël

Strictification of Weakly Stable Type-Theoretic Structures Using Generic Contexts

pdf-format:
LIPIcs-TYPES-2021-3.pdf (0.5 MB)

Abstract

We present a new strictification method for type-theoretic structures that are only weakly stable under substitution. Given weakly stable structures over some model of type theory, we construct equivalent strictly stable structures by evaluating the weakly stable structures at generic contexts. These generic contexts are specified using the categorical notion of familial representability. This generalizes the local universes method of Lumsdaine and Warren.
We show that generic contexts can also be constructed in any category with families which is freely generated by collections of types and terms, without any definitional equality. This relies on the fact that they support first-order unification. These free models can only be equipped with weak type-theoretic structures, whose computation rules are given by typal equalities. Our main result is that any model of type theory with weakly stable weak type-theoretic structures admits an equivalent model with strictly stable weak type-theoretic structures.

BibTeX - Entry

@InProceedings{bocquet:LIPIcs.TYPES.2021.3,
  author =	{Bocquet, Rafa\"{e}l},
  title =	{{Strictification of Weakly Stable Type-Theoretic Structures Using Generic Contexts}},
  booktitle =	{27th International Conference on Types for Proofs and Programs (TYPES 2021)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-254-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{239},
  editor =	{Basold, Henning and Cockx, Jesper and Ghilezan, Silvia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16772},
  URN =		{urn:nbn:de:0030-drops-167724},
  doi =		{10.4230/LIPIcs.TYPES.2021.3},
  annote =	{Keywords: type theory, strictification, coherence, familial representability, unification}
}

Keywords: type theory, strictification, coherence, familial representability, unification
Collection: 27th International Conference on Types for Proofs and Programs (TYPES 2021)
Issue Date: 2022
Date of publication: 04.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI