Fuss-free cumulative universes: theory and practice
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Fuss-free cumulative universes: theory and practice".
Jane: Here's the gist of the paper. Universes are central to dependent type theory, and they are notoriously difficult to handle in a way that is both correct and usable The authors propose a new “fuss-free” generalised algebraic presentation for polymorphic cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of a simpler formulation, which they prove equivalent by means of a normalisation theorem for the former Evidence for the utility of the fuss-free formulation is provided in the form of (1) an abstract specification of its bidirectional elaboration algorithm, and (2) a concrete implementation in Haskell.
Tom: Simplifying Cumulative Hierarchy Design The paper addresses the complexity arising from cumulative universes, which is often handled by a hierarchy of universes U0, U1,..., and the question of cumulativity: whether given i ≤ j and term Γ ⊢ M: Ui, there exists some term Γ ⊢ M′: Uj such that elj(M') = eli(M) type.
Jane: The authors contrast non-cumulative hierarchies, which are favored in production systems for being easy to specify and compatible with all Grothendieck ∞-toposes, with cumulative hierarchies that require complex equational rules for lifting operations.
Tom: They argue that the intricate functoriality and naturality laws required for cumulative hierarchies can be replaced by a single injectivity law derived from the injectivity of decoding.
Paper summary: Tom: So, to summarize what this paper is about, it tackles the huge difficulty in handling cumulative universes in dependent type theory by proposing a "fuss-free" generalized algebraic presentation.
Jane: The core claim is that they replace the intricate theory of coherent universe coercions with a much simpler formulation and then prove that this simpler version is equivalent to the more complicated one using a normalisation theorem for the fuss-free calculus.
Lu: Essentially, they are taking the injectivity of decoding seriously and just replacing each universe U i with its image in the class of all types, which creates a calculus with judgemental smallness.
Meng: So, they're simplifying the problem by using this notion of judgemental smallness to give uniform introduction and elimination rules, making it easy to specify and use.
Tom: And they claim this simplified calculus is equivalent up to admissibility with the more complicated cumulative hierarchy that has all those functorial lifting operations and naturality laws.
Jane: The evidence for why this is useful comes in two ways: first, an abstract specification of this bidirectional elaboration algorithm, and second, a concrete implementation in Haskell.
Lu: Plus, they describe an extension of the fuss-free universe hierarchy using a judgemental notion of datatype description which lets them derive prior notions of cumulative inductive types.
Meng: That part about describing datatypes seems really practical because it unifies generative and introspective metaprogramming for building models at different levels.
Tom: It really sounds like they are trying to bridge the gap between the theoretical complexity of these hierarchies and what's actually practical for building systems right now.
Jane: So, the paper is essentially offering a new way to define universes that is easier to specify, easier to implement, and claims to be equivalent in its power.
Lu: It sets up a framework where you can assess the design space for universe hierarchies on informed grounds instead of just guessing how the formalisms should work.
Conclusion: Tom: Looking at this paper, "Fuss-free cumulative universes: theory and practice," I think the main point is that they’ve managed to strip away a lot of the messy theoretical baggage associated with handling universe levels.
Jane: They've achieved a simpler algebraic presentation, and by proving equivalence through normalisation, they give us this tool that should make designing these complex type hierarchies much more informed.
Lu: It means for future implementers of dependently typed systems, they don't have to get lost in the specific rules for lifting or naturality laws right away.
Meng: So, when you're looking at a new system, you can look at this fuss-free calculus and know that it’s equivalent to the more complex one they studied, which is a nice safety check.
Tom: It gives us a way to manage universe levels as something that can be handled in a much cleaner manner, minimizing the places where we need these concepts to appear in the code.
Jane: And for someone who only listens to this show, it means there's a clearer path forward for building advanced type systems that handle cumulative inductive datatypes.
Lu: The authors suggest focusing future work on figuring out a principled account of the postponement of both coercion and unification problems, treating unification as just a special case of coercion.
Meng: And they also flag that for higher toposes, the matter gets slightly murkier regarding those injective lifting coercions, which is an important limitation they admit upfront.
Tom: So in the end, it's about making universe levels simpler to work with while proving that the fuss-free presentation is actually a viable and usable alternative.
RAPHAËL STERBAC, JONATHAN STERLING
ENS Paris-Saclay · University of Cambridge
cs.PL, cs.LO, math.LO
Submitted: 2026-07-13
Updated: 2026-11-06
Comments: Extended version of a paper to appear in POPL 2027
Code: https://github.com/bobatkey/foveran
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 100/100
The gist: Universes are central to dependent type theory, and they are notoriously difficult to handle in a way that is both correct and usable The authors propose a new “fuss-free” generalised algebraic…
Key concepts
- Cumulative Universes
- This refers to a hierarchy of types, like U0, U1, etc., where terms in a lower universe can be viewed as types in a higher one. The paper contrasts this with non-cumulative systems favored for simplicity.
- 'Fuss-Free' Approach
- This is the core idea: instead of complex functorial rules for cumulative hierarchies, the authors simplify things by treating the injectivity of decoding seriously. This leads to a calculus with judgemental smallness that is easy to specify and use.
- Injectivity of Decoding
- This means that if two terms decode to the same type in a universe, they must be identical. The paper proves this property holds in their simplified system, which is key to showing its equivalence with the more complex cumulative hierarchy.
Terminology
Summary
Universes are central to dependent type theory, and they are notoriously difficult to handle in a way that is both correct and usable The authors propose a new “fuss-free” generalised algebraic presentation for polymorphic cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of a simpler formulation, which they prove equivalent by means of a normalisation theorem for the former Evidence for the utility of the fuss-free formulation is provided in the form of (1) an abstract specification of its bidirectional elaboration algorithm, and (2) a concrete implementation in Haskell. p. 0 We propose a new “fuss-free” generalised algebraic presentation for polymorphic
cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of
a simpler formulation, which we prove equivalent by means of a normalisation theorem for the former. Evidence for the utility of the fuss-free formulation is provided in the form of (1) an abstract specification of
its bidirectional elaboration algorithm, and (2) a concrete implementation in Haskell.Where the paper says it
Simplifying Cumulative Hierarchy Design
The paper addresses the complexity arising from cumulative universes, which is often handled by a hierarchy of universes U0, U1,..., and the question of cumulativity: whether given i ≤ j and term Γ ⊢ M: Ui, there exists some term Γ ⊢ M′: Uj such that elj(M') = eli(M) type. The authors contrast non-cumulative hierarchies, which are favored in production systems for being easy to specify and compatible with all Grothendieck ∞-toposes, with cumulative hierarchies that require complex equational rules for lifting operations. p. 1 We aim here only to draw out the
important distinctions between different systems. There are technical reasons why non-cumulative hierarchies are favoured in production systems:
(1) Non-cumulative hierarchies are very easy to specify, and their rules are similar to those of
Pure Type Systems [7]. Replacing all functoriality and naturality rules with a single injectivity law is already a significant
simplification, but we can go further. At the moment, our syntax must have constructors for type
connectives at every universe level which duplicate the corresponding constructors at the type level;
this duplication must then be mediated by decoding laws like dfun-decoding.Where the paper says it
Where the paper says it
The Fuss-Free Approach to Universes
The core idea of the fuss-free approach is to take the injectivity of decoding seriously and simply replace Ui with its image in the class of all types, which amounts to defining a judgemental notion of smallness and using this to give uniform introduction and elimination rules. This leads to a calculus with judgemental smallness, which is described as being easy to specify, easy to implement, and easy to use. p. 3 In particular, we define a new form of judgement
Γ ⊢ 𝐴 small𝑖 presupposing Γ ⊢ 𝐴 type and close it under rules that express the closure properties of
the type connectives:2
dfun-small
Γ ⊢ 𝐴 small𝑖 Γ, 𝑥 : 𝐴 ⊢ 𝐵[𝑥] small𝑖
Γ ⊢ (𝑥 : 𝐴) → 𝐵[𝑥] small𝑖
univ-small
Γ ⊢ 𝑖 < 𝑗
Γ ⊢ U𝑖 small𝑗
small-mono
Γ ⊢ 𝑖 ≤ 𝑗 Γ ⊢ 𝐴 small𝑖
Γ ⊢ 𝐴 small𝑗
Then introduction and elimination rules for U𝑖 are given with respect to the smallness judgement,
satisfying appropriate 𝛽- and extensionality laws:3
univ-intro
Γ ⊢ 𝐴 small𝑖
Γ ⊢ ⇓𝑖𝐴 : U𝑖
univ-elim
Γ ⊢ 𝑀 : U𝑖
Γ ⊢ ⇑𝑖𝑀 type, ⇑𝑖𝑀 small
univ-beta
Γ ⊢ 𝐴 small𝑖
Γ ⊢ ⇑𝑖⇓𝑖𝐴 = 𝐴 type
univ-ext
Γ ⊢ ⇑𝑖𝑀 = ⇑𝑖𝑁 type
Γ ⊢ 𝑀 = 𝑁 : U𝑖
In fact, our rules for universes are parametric in any notion of smallness and therefore can be
made to modularly accommodate a variety of systems in both theory and implementation. Because it is easy to specify, easy to implement, and easy to use, we refer to the calculus with
judgemental smallness as the fuss-free approach to universes. 2 Syntactic equivalence of fuss-free universes. We will show that, up to admissibility, the
simplified calculus with judgemental smallness is equivalent to the more complicated cumulative
hierarchy with functorial lifting operations and naturality laws.Where the paper says it
Where the paper says it
Equivalence and Normalisation Proof
The paper establishes a syntactic equivalence between the fuss-free calculus and the more complex cumulative hierarchy by proving normalisation for NatHier, which implies the admissibility of injectivity laws for universe decoding and lifting in NatHier. The authors construct an equivalence of CwRs between the syntactic categories of NatHierInj and FussFree, showing that their (2,1)-categories of models are (2,1)-equivalent. p. 5 material perspective. We have so far adopted a “structural” or generalised
algebraic perspective on type theory in which we treat different form of judgement as ranging
over disjoint syntactic categories (e. ) to a general notion
of model that makes sense in any category. This is important: present-day applications of type
theory to both computer science and general mathematics rely on constructing models not only in
the category of sets, but also in other toposes [12, 16, 29, 43, 50] and even quasi-toposes [32]; in
these cases, a structural approach is not just desirable but required.Where the paper says it
Where the paper says it
Handling Inductive Datatypes
The fuss-free methodology allows for a particularly simple account of inductive datatypes, including large ones, by introducing a judgemental notion of datatype description. This involves defining a sort Desc and an extension operator JDK: Tp → Tp for descriptions. p. 3 Our final simplification is to take the injectivity of
decoding seriously, and simply replace U𝑖 with its image in the class of all types. In type theory,
this amounts to defining a judgemental notion of smallness and then using this to give uniform
introduction and elimination rules to each universe. 2 Martin-Löf type theory and natural universe hierarchies
We will describe here an “orthodox” presentation of a version of Martin-Löf type theory (MLTT) that
will serve as the basis for two presentations of universes that we will later show to be equivalent
up to admissibility. Although we have in § 1 for familiarity’s sake used a traditional notation
to informally describe the rules of type theory, we shall now switch to a more precise “logical
framework” presentation in the doctrine of second-order generalised algebraic theories [33, 54].Where the paper says it
Where the paper says it
Practical Implementation and Evaluation
The paper describes a bidirectional type checking algorithm for the fuss-free calculus, which is implemented in Haskell. This implementation incorporates the elaboration of user-written datatype declarations to descriptions in the style of Dagand. p. 7 §§ 6–7 We describe a bidirectional type checking algorithm for the fuss-free calculus, which we
then implement in Haskell. Our implementation incorporates the elaboration of user-written
datatype declarations to descriptions in the style of Dagand [20], as well as record types. In a practical system, one
would implement the elaboration algorithm from user-facing inductive definitions to the underlying
internal description. This was one of the core aspects of the experimental language Epigram 2,
based on the work of Chapman et al.Where the paper says it
Where the paper says it
Conclusion and Future Work
The authors conclude that their fuss-free presentation is the closest thing possible to an algebraic version of Martin-Löf’s universes à la Russell extended by universe polymorphism. They suggest future work should focus on a principled account of the postponement of both coercion and unification problems, treating unification as a special case of coercion. p. 1 There are technical reasons why non-cumulative hierarchies are favoured in production systems:
(1) Non-cumulative hierarchies are very easy to specify, and their rules are similar to those of
Pure Type Systems [7]. (2) Non-cumulative universes can avoid difficult implementation problems, including the
contention between higher-order unification and the insertion of subtyping coercions. (2) Non-cumulative universes can avoid difficult implementation problems, including the
contention between higher-order unification and the insertion of subtyping coercions. 1
(3) Non-cumulative hierarchies are compatible with a broad range of semantic models, including
all Grothendieck ∞-toposes [44]. We propose a new “fuss-free” generalised algebraic presentation for polymorphic
cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of
a simpler formulation, which we prove equivalent by means of a normalisation theorem for the former. Evidence for the utility of the fuss-free formulation is provided in the form of (1) an abstract specification of
its bidirectional elaboration algorithm, and (2) a concrete implementation in Haskell.Where the paper says it
Where the paper says it
Where the paper says it
References
[1] Andreas Abel. 2013. Normalization by Evaluation: Dependent Types and Impredicativity
[5] Thorsten Altenkirch and Ambrus Kaposi. 2016. Normalisation by Evaluation for Dependent Types
[8] Bruno Barras. 2012. Semantical Investigations in Intuitionistic Set Theory and Type Theories with Inductive Families
[9] Marc Bezem and Thierry Coquand. 2022. Loop-checking and the uniform word problem for join-semilattices with an inflationary endomorphism
[10] Marc Bezem, Thierry Coquand, Peter Dybjer, and Martín Escardó. 2023. Type Theory with Explicit Universe Polymorphism
[18] Thierry Coquand. 2012. Presheaf model of type theory
[54] Taichi Uemura. 2021. Abstract and Concrete Type Theories
[55] Yannick Zakowski. 2023. Universe inconsistency when paired with RelationAlgebra (
[48] Jonathan Sterling. 2021. First Steps in Synthetic Tait Computability: The Objective Metatheory of Cubical Type Theory
[53] Amin Timany and Matthieu Sozeau. 2018. Cumulative Inductive Types In Coq
[46] Matthieu Sozeau and Marc Bezem. 2025. Algebraic Universes and Variances For All
[50] Jonathan Sterling and Robert Harper. 2021. Logical Relations as Types: Proof-Relevant Parametricity for Program Modules
[54] Taichi Uemura. 2021. Abstract and Concrete Type Theories
[55] Yannick Zakowski. 2023. Universe inconsistency when paired with RelationAlgebra (
Excursion on Natural Hierarchy
The authors substantiate the categorical concepts of functoriality and naturality in their design of the so-called “natural universe hierarchy” by working internally to a conservative higher-order extension of the logical framework of second-order algebraic theories. They define a signature NatHier extending MLTT + LVL by a number of new rules for universe types, decoding, and lifting. p. 8 Formally, we define the signature NatHier extending MLTT + LVL by a number of
new rules. NatHier ≫ universe types, decoding, and lifting Formally, we define the signature NatHier extending MLTT + LVL by a number of
new rules. NatHier ≫ universe types, decoding, and lifting 10 Raphaël Sterbac and Jonathan Sterling
𝑗 : Lvl
U𝑗
: Tp
𝑀 : U𝑖
el𝑖(𝑀) : Tp
𝑖, 𝑗 : Lvl _ : 𝑖 ≤ 𝑗 𝑀 : Tm(U𝑖)
↑
𝑗
𝑖 𝑀 : Tm(U𝑗)
𝑖, 𝑗 : Lvl _ : 𝑖 ≤ 𝑗 𝑀 : Tm(U𝑖)
el𝑗
↑
𝑗
𝑖 𝑀
= el𝑖(𝑀) : Tp
𝑖 : Lvl 𝑀 : Tm(U𝑖)
↑
𝑖
𝑖𝑀 = 𝑀 : Tm(U𝑖)
𝑖, 𝑗, 𝑘 : Lvl _ : 𝑖 ≤ 𝑗 _ : 𝑗 ≤ 𝑘 𝑀 : Tm(U𝑖)
↑
𝑘
𝑗
↑
𝑗
𝑖 𝑀 = ↑
𝑘
𝑖 𝑀 : Tm(U𝑘 )
Next we must add codes inside each universe for the universes themselves as well as other type
connectives (including dependent function types). NatHier ≫ codes for types in universes
𝑖, 𝑗 : Lvl _ : 𝑖
+ ≤ 𝑗
u
𝑗
𝑖
: Tm(U𝑗)
𝑀 : Tm(U𝑖) 𝑁 : Tm(el𝑖(𝑀)) → Tm(U𝑖)
π𝑖(𝑀, 𝑁) : Tm(U𝑖)
𝑀 : Lvl → Tm(U𝑖)
π
𝑖
Lvl(𝑀) : Tm(U𝑖)
𝑖, 𝑗 : Lvl _ : 𝑖
+ ≤ 𝑗
el𝑗
u
𝑗
𝑖
= U𝑖
: Tp
𝑀 : Tm(U𝑖) 𝑁 : Tm(el𝑖(𝑀)) → Tm(U𝑖)
el𝑖(π𝑖(𝑀, 𝑁)) = Π(el𝑖(𝑀), 𝜆𝑥. 10 Raphaël Sterbac and Jonathan Sterling
𝑗 : Lvl
U𝑗
: Tp
𝑀 : U𝑖
el𝑖(𝑀) : Tp
𝑖, 𝑗 : Lvl _ : 𝑖 ≤ 𝑗 𝑀 : Tm(U𝑖)
↑
𝑗
𝑖 𝑀 : Tm(U𝑗)
𝑖, 𝑗 : Lvl _ : 𝑖 ≤ 𝑗 𝑀 : Tm(U𝑖)
el𝑗
↑
𝑗
𝑖 𝑀
= el𝑖(𝑀) : Tp
𝑖 : Lvl 𝑀 : Tm(U𝑖)
↑
𝑖
𝑖𝑀 = 𝑀 : Tm(U𝑖)
𝑖, 𝑗, 𝑘 : Lvl _ : 𝑖 ≤ 𝑗 _ : 𝑗 ≤ 𝑘 𝑀 : Tm(U𝑖)
↑
𝑘
𝑗
↑
𝑗
𝑖 𝑀 = ↑
𝑘
𝑖 𝑀 : Tm(U𝑘 )
Next we must add codes inside each universe for the universes themselves as well as other type
connectives (including dependent function types). NatHier ≫ codes for types in universes
𝑖, 𝑗 : Lvl _ : 𝑖
+ ≤ 𝑗
u
𝑗
𝑖
: Tm(U𝑗)
𝑀 : Tm(U𝑖) 𝑁 : Tm(el𝑖(𝑀)) → Tm(U𝑖)
π𝑖(𝑀, 𝑁) : Tm(U𝑖)
𝑀 : Lvl → Tm(U𝑖)
π
𝑖
Lvl(𝑀) : Tm(U𝑖)
𝑖, 𝑗 : Lvl _ : 𝑖
+ ≤ 𝑗
el𝑗
u
𝑗
𝑖
= U𝑖
: Tp
𝑀 : Tm(U𝑖) 𝑁 : Tm(el𝑖(𝑀)) → Tm(U𝑖)
el𝑖(π𝑖(𝑀, 𝑁)) = Π(el𝑖(𝑀), 𝜆𝑥.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Normalisation Model Construction
The authors define a displayed higher-order model Se over the variable parameterisation S [var], showing only a representative fragment of the full definition. This model equips each type with a (proof-relevant) Tait computability structure and quotation/unquotation yoga. p. 5 Conversely, even the syntactic
metatheory (normalisation, decidability, etc. ) calls for a structural notion of model in which Tait’s
method of computability can be phrased in terms of Artin glueing [5, 13, 25, 49]. Conversely, even the syntactic
metatheory (normalisation, decidability, etc. ) calls for a structural notion of model in which Tait’s
method of computability can be phrased in terms of Artin glueing [5, 13, 25, 49]. In type theory,
this amounts to defining a judgemental notion of smallness and then using this to give uniform
introduction and elimination rules to each universe. In particular, we define a new form of judgement
Γ ⊢ 𝐴 small𝑖 presupposing Γ ⊢ 𝐴 type and close it under rules that express the closure properties of
the type connectives:2
dfun-small
Γ ⊢ 𝐴 small𝑖 Γ, 𝑥 : 𝐴 ⊢ 𝐵[𝑥] small𝑖
Γ ⊢ (𝑥 : 𝐴) → 𝐵[𝑥] small𝑖
univ-small
Γ ⊢ 𝑖 < 𝑗
Γ ⊢ U𝑖 small𝑗
small-mono
Γ ⊢ 𝑖 ≤ 𝑗 Γ ⊢ 𝐴 small𝑖
Γ ⊢ 𝐴 small𝑗
Then introduction and elimination rules for U𝑖 are given with respect to the smallness judgement,
satisfying appropriate 𝛽- and extensionality laws:3
univ-intro
Γ ⊢ 𝐴 small𝑖
Γ ⊢ ⇓𝑖𝐴 : U𝑖
univ-elim
Γ ⊢ 𝑀 : U𝑖
Γ ⊢ ⇑𝑖𝑀 type, ⇑𝑖𝑀 small
univ-beta
Γ ⊢ 𝐴 small𝑖
Γ ⊢ ⇑𝑖⇓𝑖𝐴 = 𝐴 type
univ-ext
Γ ⊢ ⇑𝑖𝑀 = ⇑𝑖𝑁 type
Γ ⊢ 𝑀 = 𝑁 : U𝑖
In fact, our rules for universes are parametric in any notion of smallness and therefore can be
made to modularly accommodate a variety of systems in both theory and implementation. In type theory,
this amounts to defining a judgemental notion of smallness and then using this to give uniform
introduction and elimination rules to each universe. In particular, we define a new form of judgement
Γ ⊢ 𝐴 small𝑖 presupposing Γ ⊢ 𝐴 type and close it under rules that express the closure properties of
the type connectives:2
dfun-small
Γ ⊢ 𝐴 small𝑖 Γ, 𝑥 : 𝐴 ⊢ 𝐵[𝑥] small𝑖
Γ ⊢ (𝑥 : 𝐴) → 𝐵[𝑥] small𝑖
univ-small
Γ ⊢ 𝑖 < 𝑗
Γ ⊢ U𝑖 small𝑗
small-mono
Γ ⊢ 𝑖 ≤ 𝑗 Γ ⊢ 𝐴 small𝑖
Γ ⊢ 𝐴 small𝑗
Then introduction and elimination rules for U𝑖 are given with respect to the smallness judgement,
satisfying appropriate 𝛽- and extensionality laws:3
univ-intro
Γ ⊢ 𝐴 small𝑖
Γ ⊢ ⇓𝑖𝐴 : U𝑖
univ-elim
Γ ⊢ 𝑀 : U𝑖
Γ ⊢ ⇑𝑖𝑀 type, ⇑𝑖𝑀 small
univ-beta
Γ ⊢ 𝐴 small𝑖
Γ ⊢ ⇑𝑖⇓𝑖𝐴 = 𝐴 type
univ-ext
Γ ⊢ ⇑𝑖𝑀 = ⇑𝑖𝑁 type
Γ ⊢ 𝑀 = 𝑁 : U𝑖
In fact, our rules for universes are parametric in any notion of smallness and therefore can be
made to modularly accommodate a variety of systems in both theory and implementation. LVL ≫ judgemental levels preorder
Lvl : RepSort
𝑖, 𝑗 : Lvl
𝑖 ≤ 𝑗 : Sort
𝑖, 𝑗 : Lvl 𝑝, 𝑞 : 𝑖 ≤ 𝑗
𝑝 = 𝑞 : 𝑖 ≤ 𝑗
𝑖 : Lvl
_ : 𝑖 ≤ 𝑖
𝑖, 𝑗, 𝑘 : Lvl _ : 𝑖 ≤ 𝑗 _ : 𝑗 ≤ 𝑘
_ : 𝑖 ≤ 𝑘 0 : Lvl
𝑖 : Lvl
𝑖
+
: Lvl
𝑖 : Lvl
_ : 0 ≤ 𝑖
𝑖 : Lvl
_ : 𝑖 ≤ 𝑖
+
By virtue of the third rule above establishing the judgemental proof irrelevance of the level
inequality sort, we have felt free to write the rules in an implicit form with underscores. Formally,
there are of course explicit named generators and witnesses for these but because the choice does
not matter, we may leave them out as a matter of notation.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Injectivity of Decoding in NatHier
Theorem 5.6 proves that in the initial or syntactic model of NatHier, the universe decoding operation A: Ui ⊢ eli(A): Tp is injective. p. 9 ↑
𝑗
𝑖 𝑁 (𝑥)
: Tm(U𝑗)
2. 4 A theory with injective decoding and coercion
We finally consider the extension NatHierInj of NatHier by an injectivity law for the universe
decoding operation. ↑
𝑗
𝑖 𝑁 (𝑥)
: Tm(U𝑗)
2. 4 A theory with injective decoding and coercion
We finally consider the extension NatHierInj of NatHier by an injectivity law for the universe
decoding operation. Our work primarily concerns the comparison of implicit and explicit presentations of Russellian
(open) universes from the structural point of view, with direct applications to the practical implementation of dependently typed programming languages and interactive proof assistants. Notably,
the recent work of Coquand and Sterbac [19] presents a syntactic equivalence of the explicit and
implicit presentation which shows the complexity of relating the two systems. Our work primarily concerns the comparison of implicit and explicit presentations of Russellian
(open) universes from the structural point of view, with direct applications to the practical implementation of dependently typed programming languages and interactive proof assistants. Notably,
the recent work of Coquand and Sterbac [19] presents a syntactic equivalence of the explicit and
implicit presentation which shows the complexity of relating the two systems. Fuss-free cumulative universes: theory and practice
Extended version with supplementary appendices
RAPHAËL STERBAC, ENS Paris-Saclay — Université Paris-Saclay, France
JONATHAN STERLING, University of Cambridge, United Kingdom
Universes are central to dependent type theory, and they are notoriously difficult to handle in a way that is
both correct and usable. We propose a new “fuss-free” generalised algebraic presentation for polymorphic
cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of
a simpler formulation, which we prove equivalent by means of a normalisation theorem for the former. Fuss-free cumulative universes: theory and practice
Extended version with supplementary appendices
RAPHAËL STERBAC, ENS Paris-Saclay — Université Paris-Saclay, France
JONATHAN STERLING, University of Cambridge, United Kingdom
Universes are central to dependent type theory, and they are notoriously difficult to handle in a way that is
both correct and usable. We propose a new “fuss-free” generalised algebraic presentation for polymorphic
cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of
a simpler formulation, which we prove equivalent by means of a normalisation theorem for the former.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Bidirectional Elaboration Algorithm
The authors describe a bidirectional elaboration algorithm by dividing the raw syntax into two different sorts: the synthesizable and checkable terms. This involves four mutually recursive judgements that handle type synthesis, checking, and coercion operations. p. 7 Normalisation
implies the admissibility of injectivity laws for universe decoding and lifting in NatHier,
from which we deduce that NatHier and FussFree are equivalent up to syntactic translation. §§ 6–7 We describe a bidirectional type checking algorithm for the fuss-free calculus, which we
then implement in Haskell.Where the paper says it
Conclusion on Practical Utility
The authors conclude that their fuss-free presentation is considerably simpler to implement and is justified by their metatheoretic results. The system's design aims to make working with universe levels as simple as possible, minimizing the number of places where they need to appear. They note that the fuss-free calculus is already impacting the design of new implementations of type theory, such as Lynch [38] using it for a static/dynamic phase distinction. p. 7 Our implementation incorporates the elaboration of user-written
datatype declarations to descriptions in the style of Dagand [20], as well as record types. We note that our fuss-free calculus is already impacting the design of new implementations
of type theory; for example, Lynch [38] uses the fuss-free approach to seamlessly introduce a
static/dynamic phase distinction [50] only at small types.Where the paper says it
[4] Stuart Frazier Allen. 1987. A Non-Type-Theoretic Definition of Martin-Löf’s Types
[5] Thorsten Altenkirch and Ambrus Kaposi. 2016. Normalisation by Evaluation for Dependent Types
[8] Bruno Barras. 2012. Semantical Investigations in Intuitionistic Set Theory and Type Theories with Inductive Families
[9] Marc Bezem and Thierry Coquand. 2022. Loop-checking and the uniform word problem for join-semilattices with an inflationary endomorphism
[10] Marc Bezem, Thierry Coquand, Peter Dybjer, and Martín Escardó. 2023. Type Theory with Explicit Universe Polymorphism
[18] Thierry Coquand. 2012. Presheaf model of type theory
[54] Taichi Uemura. 2021. Abstract and Concrete Type Theories
[55] Yannick Zakowski. 2023. Universe inconsistency when paired with RelationAlgebra
Excursion on What is Natural About a Natural Universe Hierarchy
The authors substantiate the categorical concepts of functoriality and naturality in their design of the so-called “natural universe hierarchy” by working internally to a conservative higher-order extension of the logical framework of second-order algebraic theories. They define a signature NatHier extending MLTT + LVL by a number of new rules for universe types, decoding, and lifting. This extension includes rules for codes inside each universe for the universes themselves as well as other type connectives.
Construction of Displayed Models
The authors define a displayed higher-order model Se over the variable parameterisation S [var], showing only a representative fragment of the full definition. This model equips each type with a (proof-relevant) Tait computability structure and quotation/unquotation yoga. The construction involves defining displayed universes Se.U(i,n) for each n: Se.Lvl(i). This construction includes computability witnesses for elements of a neutral type, which are given by neutral elements of that neutral type. p. 0 1 Introduction
In dependently typed programming languages like Lean, Rocq, and Agda, universes turn types into
ordinary data that can be taken as arguments, returned from functions, and even embedded in more
complex data structures. This is achieved by introducing a type U whose elements encode types:
univ-formation
Γ ⊢ U type
univ-decoding
Γ ⊢ 𝐴 : U
Γ ⊢ el(𝐴) type
It is important that we do not have an inverse to the decoding function el, for if U can be encoded
by an element of U, then the type system becomes inconsistent in the sense that every type becomes
inhabited.Where the paper says it
Injectivity of Decoding for NatHier
Theorem 5.6 proves that in the initial or syntactic model of NatHier, the universe decoding operation A: Ui ⊢ eli(A): Tp is injective. This result is derived by induction on normal forms and relies on Corollary 5.4, which shows that the Π, ΠLvl, and Σ constructors are injective in S [var]. The final result is Theorem 5.6: For any M, N: S [var].Tm(1, Ui) such that eli(M) = eli(N), we have M = N.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Fuss-free cumulative universes can be implemented in Haskell to provide a concrete, usable implementation of polymorphic cumulative universes that dispenses with
intricate theory of coherent universe coercions.
-
The system can handle large inductive datatypes by introducing a
judgemental notion of datatype description,
allowing the system to define datatypes without requiringexcessive level parameterisation
in other systems. -
A bidirectional type checking algorithm is provided that elaborates raw syntax into the core theory, allowing for a streamlined treatment of conversion relative to more bureaucratic systems.
-
The system can distinguish between synthesizable and checkable terms, enabling a two-phase approach: one for type synthesis and one for type checking, which simplifies implementation compared to standard algorithms.
-
The theory admits an interpretation in any Grothendieck topos, providing a model that is
not just in the category of sets,
which is crucial for applications in non-univalent type theory.
Abstract
Universes are central to dependent type theory, and they are notoriously difficult to handle in a way that is both correct and usable. We propose a new "fuss-free" generalised algebraic presentation for polymorphic cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of a simpler formulation, which we prove equivalent by means of a normalisation theorem for the former. We study the fuss-free formulation by means of (1) an abstract specification of its bidirectional elaboration algorithm, and (2) a concrete implementation in Haskell. We also describe and implement an extension of the fuss-free universe hierarchy with a judgemental notion of datatype description from which prior notions of cumulative inductive type may be derived.
Sources
- A Note on Generalized Algebraic Theories and Categories with Families
- First steps in synthetic guarded domain theory: step-indexing in the topos of trees
- Syntactic categories for dependent type theory: sketching and adequacy
- All $(\infty,1)$-toposes have strict univalent universes
- Normalization for Cubical Type Theory
- Logical Relations as Types: Proof-Relevant Parametricity for Program Modules
Related papers
- The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures
- Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA
- High-Level Synthesis of Efficient Pipelines with Visibility Control
- Model Checking Probabilistic Multiparty Session Types
- A Type System for Communication-Safe Hardware Design
- RECURSUM: Automated Code Generation for Recurrence Relations Exceeds Expert Optimization via LayeredCodegen