Algebraic Presentations of Type Dependency
C-systems were defined by Cartmell as the algebraic structures that correspond exactly to generalised algebraic theories. B-systems were defined by Voevodsky in his quest to formulate and prove an initiality conjecture for type theories. They play a crucial role in Voevodsky's construction of a syntactic C-system from a term monad. In this work, we construct an equivalence between the category of C-systems and the category of B-systems, thus proving a conjecture by Voevodsky. We construct this equivalence as the restriction of an equivalence between more general structures, called CE-systems and E-systems, respectively. To this end, we identify C-systems and B-systems as "stratified" CE-systems and E-systems, respectively; that is, systems whose contexts are built iteratively via context extension, starting from the empty context.
Authors
- Benedikt Ahrens (ORCID: https://orcid.org/0000-0002-6786-4538)
- Jacopo Emmenegger (ORCID: https://orcid.org/0000-0003-1383-2415)
- Paige Randall North (ORCID: https://orcid.org/0000-0001-7876-0956)
- Egbert Rijke (ORCID: https://orcid.org/0000-0002-5272-6175)
Publication Details
- Journal
- Logical Methods in Computer Science
- Published
- 2025-02-06
- DOI
- https://doi.org/10.46298/lmcs-21(1:14)2025
- Primary Topic
- Advanced Algebra and Logic
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Engineering and Physical Sciences Research Council