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 , 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 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 and the model is fully constructive and predicative, while still being very convenient to work with as the decoding from 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
Cited by (1)
The internal languages of univalent categories vanderweide-2025-the
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.
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.
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
External (46)
- Set-Theoretic and Type-Theoretic Ordinals Coincide (2023)
- Iterative multisets, iterative sets, and iterative ordinals in the TypeTopology library (2023)
- Univalent Material Set Theory (2023)
- The Agda Programming Language (2023)
- Constructive Final Semantics of Finite Bags (2023)
- The simplicial model of Univalent Foundations (after Voevodsky) (2021)
- Cubical Agda: A dependently typed programming language with univalence and higher inductive types (2021)
- The Coq Proof Assistant (2021)
- Type-Theoretic Constructions of the Final Coalgebra of the Finite Powerset Functor (2021)
- The agda-unimath library (2021)
- Multisets in type theory (2020)
- UniMath - a computer-checked library of univalent mathematics (2020)
- From type theory to setoids and back (2019)
- The finite-multiset construction in HoTT (2019)
- Introduction to univalent foundations of mathematics with Agda (2019)
- Natural models of homotopy type theory (2018)
- From multisets to sets in homotopy type theory (2018)
- Finite sets in homotopy type theory (2018)
- Cubical Type Theory: A Constructive Interpretation of the Univalence Axiom (2018)
- Category structures on well-ordered sets in UniMath (2018)
- Higher inductive types in programming (2017)
- Type category structure on h-set valued presheaves in UniMath (2017)
- Parts of a CwF structure on h-set valued presheaves in Cubical Agda (2017)
- The join construction (2017)
- Type theory in type theory using quotient inductive types (2016)
- An experimental library of formalized Mathematics based on the univalent foundations (2015)
- Sets in homotopy type theory (2015)
- Revisiting the categorical interpretation of dependent type theory (2014)
- Structuralism, Invariance, and Univalence (2014)
- Discrete Generalised Polynomial Functors (2012)
- Semantical investigations in intuitionistic set theory and type theories with inductive families (2012)
- Sets in Coq, Coq in sets (2010)
- The equivalence axiom and univalent models of type theory (2010)
- Stack semantics and the comparison of material and structural set theories (2010)
- On Relating Type Theories and Set Theories (1999)
- Sets in Types, Types in Sets (1997)
- Internal type theory (1996)
- Comprehension Categories and the Semantics of Type Dependency (1993)
- Semantics of Type Theory (1991)
- Generalised algebraic theories and contextual categories (1986)
- Locally cartesian closed categories and type theory (1984)
- Typeteori - en studie (1984)
- Constructive mathematics and computer programming (1982)
- The Type Theoretic Interpretation of Constructive Set Theory (1978)
- Formal Systems for Constructive Mathematics (1976)
- An Intuitionistic Theory of Types: Predicative Part (1975)