Paperlane

no. 11 · Monday 9 November 2026

Fuss-free cumulative universes: theory and practice

Raphaël Sterbac and Jonathan Sterling

math.LO · v2

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.

comments
Extended version of a paper to appear in POPL 2027
fields
Logic
pdf ↗ page arXiv:2607.11329 ↗