Reference. Bounded First-Class Universe Levels in Dependent Type Theory

In dependent type theory, being able to refer to a type universe as a term itself increases its expressive power, but requires mechanisms in place to prevent Girard’s paradox from introducing logical inconsistency in the presence of type-in-type. The simplest mechanism is a hierarchy of universes indexed by a sequence of levels, typically the naturals. To improve reusability of definitions, they can be made level polymorphic, abstracting over level variables and adding a notion of level expressions. For even more expressive power, level expressions can be made first-class as terms themselves, and level polymorphism is subsumed by dependent functions quantifying over levels. Furthermore, bounded level polymorphism provides more expressivity by being able to explicitly state constraints on level variables. While semantics for first-class levels with constraints are known, syntax and typing rules have not been explicitly written down. Yet pinning down a well-behaved syntax is not trivial; there exist prior type theories with bounded level polymorphism that fail to satisfy subject reduction. In this work, we design an explicit syntax for a type theory with bounded first-class levels, parametrized over arbitrary well-founded sets of levels. We prove the metatheoretic properties of subject reduction, type safety, consistency, and canonicity, entirely mechanized from syntax to semantics in Lean.

Cite

Cite as @chan-2025-bounded (helia, typst) · \cite{chan-2025-bounded} (LaTeX)
BibTeX
bibtex · 8 lines
@misc{chan-2025-bounded,
  author = {Jonathan Chan and Stephanie Weirich},
  title = {Bounded First-Class Universe Levels in Dependent Type Theory},
  year = {2025},
  month = {2},
  eprint = {2502.20485},
  archiveprefix = {arXiv}
}
hayagriva YAML (typst)
yaml · 9 lines
chan-2025-bounded:
  type: misc
  title: Bounded First-Class Universe Levels in Dependent Type Theory
  author:
  - Chan, Jonathan
  - Weirich, Stephanie
  date: 2025-02
  serial-number:
    arxiv: '2502.20485'
Cited by (1)

Normalisation for First-Class Universe Levels danielsson-2026-normalisation

Various mechanisms are available for managing universe levels in proof assistants based on type theory. The Agda proof assistant implements a strong form of universe polymorphism in which universe levels are internalised as a type, making levels first-class objects and permitting higher-rank quantification via ordinary Π-types. We prove normalisation and decidability of equality and type-checking for a type theory with first-class universe levels inspired by Agda. We also show that level primitives can safely be erased in extracted programs. Our development is formalised in Agda itself and builds upon previous work which uses logical relations on extrinsically typed syntax.
PDF · DOI · pldb
Cites 22 works (2 here)
With notes (2)

An Order-Theoretic Analysis of Universe Polymorphism houfavonia-2023-an

We present a novel formulation of universe polymorphism in dependent type theory in terms of monads on the category of strict partial orders, and a novel algebraic structure, displacement algebras, on top of which one can implement a generalized form of McBride’s “crude but effective stratification” scheme for lightweight universe polymorphism. We give some examples of exotic but consistent universe hierarchies, and prove that every universe hierarchy in our sense can be embedded in a displacement algebra and hence implemented via our generalization of McBride’s scheme. Many of our technical results are mechanized in Agda, and we have an OCaml library for universe levels based on displacement algebras, for use in proof assistant implementations.
PDF · DOI · pldb

Cumulative Inductive Types In Coq timany-2018-cumulative

In order to avoid well-known paradoxes associated with self-referential definitions, higher-order dependent type theories stratify the theory using a countably infinite hierarchy of universes (also known as sorts), Type0:Type1:…. Such type systems are called cumulative if for any type A we have that 𝐴:Type𝑖 implies 𝐴:Type𝑖+1. The Predicative Calculus of Inductive Constructions (pCIC) which forms the basis of the Coq proof assistant, is one such system. In this paper we present the Predicative Calculus of Cumulative Inductive Constructions (pCuIC) which extends the cumulativity relation to inductive types. We discuss cumulative inductive types as present in Coq 8.7 and their application to formalization and definitional translations.
DOI
External (20)
chan-2025-bounded reference entries/refs/chan-2025-bounded/chan-2025-bounded.hel