Impredicative Observational Equality
Loïc Pujet, Nicolas Tabareau
Abstract
In dependent type theory, impredicativity is a powerful logical principle that allows the definition of propositions that quantify over arbitrarily large types, potentially resulting in self-referential propositions. Impredicativity can provide a system with increased logical strength and flexibility, but in counterpart it comes with multiple incompatibility results. In particular, Abel and Coquand showed that adding definitional uniqueness of identity proofs (UIP) to the main proof assistants that support impredicative propositions (Coq and Lean) breaks the normalization procedure, and thus the type-checking algorithm. However, it was not known whether this stems from a fundamental incompatibility between UIP and impredicativity or if a more suitable algorithm could decide type-checking for a type theory that supports both. In this paper, we design a theory that handles both UIP and impredicativity by extending the recently introduced observational type theory TT obs with an impredicative universe of definitionally proof-irrelevant types, as initially proposed in the seminal work on observational equality of Altenkirch et al. We prove decidability of conversion for the resulting system, that we call CC obs , by harnessing proof-irrelevance to avoid computing with impredicative proof terms. Additionally, we prove normalization for CC obs in plain Martin-Löf type theory, thereby showing that adding proof-irrelevant impredicativity does not increase the computational content of the theory.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- AdapTT: Functoriality for Dependent Type Casts cites Observational equality: now for good
- Definitional Proof Irrelevance Made Accessible cites Observational equality: now for good
- A Dependent Type Theory for Meta-programming with Intensional Analysis cites Observational equality: now for good
Cited by top-tier papers4
- A Dependent Type Theory for Meta-programming with Intensional AnalysisJason Z. S. Hu, Brigitte PientkaPOPL 2025 · 2 citations
- AdapTT: Functoriality for Dependent Type CastsArthur Adjedj, Meven Lennon-Bertrand, Thibaut Benjamin, Kenji MaillardPOPL 2026 · 1 citation
- Canonicity for Indexed Inductive-Recursive TypesAndrás KovácsPOPL 2026 · 1 citation
- Definitional Proof Irrelevance Made AccessibleThiago Felicissimo, Yann Leray, Loïc Pujet, Nicolas Tabareau et al.LICS 2026
Builds on1
Related papers
- Consistency of a Dependent Calculus of IndistinguishabilityYiyun Liu, Jonathan Chan, Stephanie WeirichPOPL 2025 · 3 citations
- All Your Base Are Belong to Us: Sort Polymorphism for Proof AssistantsJosselin Poiret, Gaëtan Gilbert, Kenji Maillard, Pierre-Marie Pédrot et al.POPL 2025 · 6 citations
- Internalizing Indistinguishability with Dependent TypesYiyun Liu, Jonathan Chan, Jessica Shi, Stephanie WeirichPOPL 2024 · 3 citations
- Encode the Cake and Eat It Too: Controlling Computation in Type Theory, LocallyYann Leray, Théo WinterhalterPOPL 2026
- Internal and Observational Parametricity for Cubical AgdaAntoine Van Muylder, Andreas Nuyts, Dominique DevriesePOPL 2024 · 2 citations
