Reference. Towards Computational UIP in Cubical Agda

Some advantages of Cubical Type Theory, as implemented by Cubical Agda, over intensional Martin-Löf Type Theory include Quotient Inductive Types (QITs), which exist as instances of Higher Inductive Types, and functional extensionality, which is provable in Cubical Type Theory. However, HoTT features an infinite hierarchy of equalities that may become unwieldy in formalisations. Fortunately, QITs and functional extensionality are both preserved even if the equality levels of Cubical Type Theory are truncated to only homotopical Sets (h-Sets). In other words, removing the univalence axiom from Cubical Type Theory and instead postulating a conflicting axiom: the Uniqueness of Identity Proofs (UIP) postulate. Since univalence is proved in Cubical Type Theory from the so-called Glue Types, therefore, it is known that one can first remove the Glue Types (thus removing univalence) and then set-truncate all equalities (essentially assuming UIP), à la XTT. The result is a “h-Set Cubical Type Theory” that retains features such as functional extensionality and QITs.

However, in Cubical Agda, there are currently only two unsatisfying ways to achieve h-Set Cubical Type Theory. The first is to give up on the canonicity of the theory and simply postulate the UIP axiom, while the second way is to use a standard result stating “type formers preserve h-levels” to manually prove UIP for every defined type. The latter is, however, laborious work best suited for an automatic implementation by the proof assistant. In this project, we analyse formulations of UIP and detail their computation rules for Cubical Agda, and evaluate their suitability for implementation. We also implement a variant of Cubical Agda without Glue, which is already compatible with postulated UIP, in anticipation of a future implementation of UIP in Cubical Agda.

Cite

Cite as @tan_etal_2025 (helia, typst) · \cite{tan_etal_2025} (LaTeX)
BibTeX
bibtex · 8 lines
@article{tan_etal_2025,
 title = {Towards Computational UIP in Cubical Agda},
 author = {Yee-Jian Tan and Andreas Nuyts and Dominique Devriese},
 year = {2025},
 eprint = {2511.21209},
 archiveprefix = {arXiv},
 url = {https://arxiv.org/abs/2511.21209}
}
hayagriva YAML (typst)
yaml · 13 lines
tan_etal_2025:
  type: article
  title: Towards Computational UIP in Cubical Agda
  author:
  - Tan, Yee-Jian
  - Nuyts, Andreas
  - Devriese, Dominique
  date: 2025
  url: https://arxiv.org/abs/2511.21209
  serial-number:
    arxiv: '2511.21209'
  parent:
    type: periodical
Cited by (1)

Can We Formalise Type Theory Intrinsically without Any Compromise? A Case Study in Cubical Agda chen_etal_2026

We present an intrinsic representation of type theory in the proof assistant Cubical Agda, inspired by Awodey’s natural models of type theory. The initial natural model is defined as quotient inductive-inductive-recursive types, leading us to a syntax accepted by Cubical Agda without using any transports, postulates, or custom rewrite rules. We formalise some meta-properties such as the standard model, normalisation by evaluation for typed terms, and strictification constructions. Since our formalisation is carried out using Cubical Agda’s native support for quotient inductive types, all our constructions compute at a reasonable speed. When we try to develop more sophisticated metatheory, however, the ‘transport hell’ problem reappears. Ultimately, it remains a considerable struggle to develop the metatheory of type theory using an intrinsic representation that lacks strict equations. The effort required is about the same whether or not the notion of natural model is used.
PDF · DOI · pldb
Cites 25 works (4 here)
With notes (4)

A Cubical Language for Bishop Sets sterling-2022-a

We present XTT, a version of Cartesian cubical type theory specialized for Bishop sets à la Coquand, in which every type enjoys a definitional version of the uniqueness of identity proofs. Using cubical notions, XTT reconstructs many of the ideas underlying Observational Type Theory, a version of intensional type theory that supports function extensionality. We prove the canonicity property of XTT (that every closed boolean is definitionally equal to a constant) using Artin gluing.
DOI

Normalization for Cubical Type Theory sterling_angiuli_2021

We prove normalization for (univalent, Cartesian) cubical type theory, closing the last major open problem in the syntactic metatheory of cubical type theory. Our normalization result is reduction-free, in the sense of yielding a bijection between equivalence classes of terms in context and a tractable language of β/η-normal forms. As corollaries we obtain both decidability of judgmental equality and the injectivity of type constructors.
Web

Homotopy Type Theory: Univalent Foundations of Mathematics hottbook

Web · arXiv

Syntax and semantics of dependent types Hofmann_1997

DOI
External (21)
tan_etal_2025 reference entries/refs/tan_etal_2025/tan_etal_2025.hel