Fuss-free cumulative universes: theory and practice

arXiv:2607.11329 · cs.PL, cs.LO, math.LO · Submitted 2026-07-13 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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].

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. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

The authors show that this simplified calculus is equivalent up to admissibility with the more complicated cumulative hierarchy with functorial lifting operations and naturality laws. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

This equivalence is demonstrated by constructing algebras M F and M G for the respective theories. p. 5
Where the paper says it

) 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.

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

Where the paper says it

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.

They show how this framework can be used to define the type Data(DescD i) at each level i, which is shown to be i+-small. p. 7
Where the paper says it

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].

This allows them to treat both generative and introspective metaprogramming in a unified way.

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

Where the paper says it

§§ 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.

The evaluation and conversion checking algorithms are described using a semantic domain defined by VSize, VTp, and VTm datatypes. This approach provides great simplification for the core language of a practical system, notably for the evaluation algorithm. p. 6
Where the paper says it

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.

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

Where the paper says it

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.

Furthermore, they note that for higher toposes, the matter is slightly murkier regarding injective lifting coercions. p. 1
Where the paper says it

(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].

The paper also provides a tutorial implementation in Haskell. p. 0
Where the paper says it

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.

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

Where the paper says it

Formally, we define the signature NatHier extending MLTT + LVL by a number of new rules. NatHier ≫ universe types, decoding, and lifting

p. 8
Where the paper says it

Formally, we define the signature NatHier extending MLTT + LVL by a number of new rules. NatHier ≫ universe types, decoding, and lifting

This extension includes rules for codes inside each universe for the universes themselves as well as other type connectives. p. 9
Where the paper says it

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𝑖(𝑀), 𝜆𝑥.

p. 9
Where the paper says it

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𝑖(𝑀), 𝜆𝑥.

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

Where the paper says it

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].

p. 5
Where the paper says it

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].

The construction involves defining displayed universes Se. p. 3
Where the paper says it

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.

p. 3
Where the paper says it

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.

U(i,n) for each n: Se.Lvl(i). This construction includes computability witnesses for type codes, which are defined by a normal form M•. p. 8
Where the paper says it

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.

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

Where the paper says it

↑ 𝑗 𝑖 𝑁 (𝑥) : 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.

p. 9
Where the paper says it

↑ 𝑗 𝑖 𝑁 (𝑥) : 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.

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]. p. 6
Where the paper says it

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.

p. 6
Where the paper says it

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.

The final result is Theorem 5. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

6: For any M, N: S [var].Tm(1, Ui) such that eli(M) = eli(N), we have M = N.

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

Where the paper says it

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.

The main addition to standard type-checking algorithms is the optional size parameter of the judgement chktp.

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

Where the paper says it

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.

The system's ability to handle cumulative inductive datatypes via judgemental descriptions is a key practical advantage.

[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

Where the paper says it

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.

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

  1. 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.

  2. The system can handle large inductive datatypes by introducing a judgemental notion of datatype description, allowing the system to define datatypes without requiring excessive level parameterisation in other systems.

  3. 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.

  4. 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.

  5. 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

Related papers