Reference. The category of iterative sets in homotopy type theory and univalent foundations

When working in homotopy type theory and univalent foundations, the traditional role of the category of sets, 𝒮︀ℯ︀𝓉︀ , is replaced by the category 𝒽︀𝒮︀ℯ︀𝓉︀ of homotopy sets (h-sets); types with h-propositional identity types. Many of the properties of 𝒮︀ℯ︀𝓉︀ hold for 𝒽︀𝒮︀ℯ︀𝓉︀ ((co)completeness, exactness, local cartesian closure, etc.). Notably, however, the univalence axiom implies that 𝖮𝖻𝒽︀𝒮︀ℯ︀𝓉︀ is not itself an h-set, but an h-groupoid. This is expected in univalent foundations, but it is sometimes useful to also have a stricter universe of sets, for example, when constructing internal models of type theory. In this work, we equip the type of iterative sets 𝖵0 , due to Gylterud ((2018). The Journal of Symbolic Logic 83 (3) 1132–1146) as a refinement of the pioneering work of Aczel ((1978). Logic Colloquium’77 , Studies in Logic and the Foundations of Mathematics, vol. 96, Elsevier, 55–66.) on universes of sets in type theory, with the structure of a Tarski universe and show that it satisfies many of the good properties of h-sets. In particular, we organize 𝖵0 into a (non-univalent strict) category and prove that it is locally cartesian closed. This enables us to organize it into a category with families with the structure necessary to model extensional type theory internally in HoTT/UF. We do this in a rather minimal univalent type theory with W-types, in particular we do not rely on any HITs, or other complex extensions of type theory. Furthermore, the construction of 𝖵0 and the model is fully constructive and predicative, while still being very convenient to work with as the decoding from 𝖵0 into h-sets commutes definitionally for all type constructors. Almost all of the paper has been formalized in 𝙰𝚐𝚍𝚊 using the 𝚊𝚐𝚍𝚊 - 𝚞𝚗𝚒𝚖𝚊𝚝𝚑 library of univalent mathematics.

Cite

Cite as @gratzer-2024-the (helia, typst) · \cite{gratzer-2024-the} (LaTeX)
BibTeX
bibtex · 1 line
@article{gratzer-2024-the, title={The category of iterative sets in homotopy type theory and univalent foundations}, volume={34}, ISSN={1469-8072}, url={http://dx.doi.org/10.1017/s0960129524000288}, DOI={10.1017/s0960129524000288}, number={9}, journal={Mathematical Structures in Computer Science}, publisher={Cambridge University Press (CUP)}, author={Gratzer, Daniel and Gylterud, Håkon Robbestad and Mörtberg, Anders and Stenholm, Elisabeth}, year={2024}, month=Oct, pages={945–970} }
hayagriva YAML (typst)
yaml · 20 lines
gratzer-2024-the:
  type: article
  title: The category of iterative sets in homotopy type theory and univalent foundations
  author:
  - Gratzer, Daniel
  - Gylterud, Håkon Robbestad
  - Mörtberg, Anders
  - Stenholm, Elisabeth
  date: 2024-10
  page-range: 945-970
  url: http://dx.doi.org/10.1017/s0960129524000288
  serial-number:
    doi: 10.1017/s0960129524000288
    issn: 1469-8072
  parent:
    type: periodical
    title: Mathematical Structures in Computer Science
    publisher: Cambridge University Press (CUP)
    issue: 9
    volume: 34
Cited by (1)

The internal languages of univalent categories vanderweide-2025-the

DOI · arXiv
Cites 51 works (5 here)
With notes (5)

Internalizing representation independence with univalence angiuli-2021-internalizing

In their usual form, representation independence metatheorems provide an external guarantee that two implementations of an abstract interface are interchangeable when they are related by an operation-preserving correspondence. If our programming language is dependently-typed, however, we would like to appeal to such invariance results within the language itself, in order to obtain correctness theorems for complex implementations by transferring them from simpler, related implementations. Recent work in proof assistants has shown that Voevodsky’s univalence principle allows transferring theorems between isomorphic types, but many instances of representation independence in programming involve non-isomorphic representations. In this paper, we develop techniques for establishing internal relational representation independence results in dependent type theory, by using higher inductive types to simultaneously quotient two related implementation types by a heterogeneous correspondence between them. The correspondence becomes an isomorphism between the quotiented types, thereby allowing us to obtain an equality of implementations by univalence. We illustrate our techniques by considering applications to matrices, queues, and finite multisets. Our results are all formalized in Cubical Agda, a recent extension of Agda which supports univalence and higher inductive types in a computationally well-behaved way.
PDF · DOI · pldb

Univalent categories and the Rezk completion ahrens_etal_2015

We develop category theory within Univalent Foundations, which is a foundational system for mathematics based on a homotopical interpretation of dependent type theory. In this system, we propose a definition of ‘category’ for which equality and equivalence of categories agree. Such categories satisfy a version of the univalence axiom, saying that the type of isomorphisms between any two objects is equivalent to the identity type between these objects; we call them ‘saturated’ or ‘univalent’ categories. Moreover, we show that any category is weakly equivalent to a univalent one in a universal way. In homotopical and higher-categorical semantics, this construction corresponds to a truncated version of the Rezk completion for Segal spaces, and also to the stack completion of a prestack.
DOI · arXiv

Homotopy Type Theory: Univalent Foundations of Mathematics hottbook

Web · arXiv

Categorical Logic and Type Theory jacobs-1999

This book is an attempt to give a systematic presentation of both logic and type theory from a categorical perspective, using the unifying concept of fibred category. Its intended audience consists of logicians, type theorists, category theorists and (theoretical) computer scientists.

Syntax and semantics of dependent types Hofmann_1997

DOI
External (46)
gratzer-2024-the reference entries/refs/gratzer-2024-the/gratzer-2024-the.hel