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.

Algebraic Presentations of Type Dependency / Ahrens, B., Emmenegger, J., Randall North, P., Rijke, E.. - In: LOGICAL METHODS IN COMPUTER SCIENCE. - ISSN 1860-5974. - 21:1(2025), pp. 1-71.

Algebraic Presentations of Type Dependency

Jacopo Emmenegger;
2025

Abstract

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.
2025
.
01 Pubblicazione su rivista::01a Articolo in rivista
Algebraic Presentations of Type Dependency / Ahrens, B., Emmenegger, J., Randall North, P., Rijke, E.. - In: LOGICAL METHODS IN COMPUTER SCIENCE. - ISSN 1860-5974. - 21:1(2025), pp. 1-71.
File allegati a questo prodotto
File Dimensione Formato  
Ahrens_Algebraic-presentantions_2025.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 965.45 kB
Formato Adobe PDF
965.45 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1779207
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact