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
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.
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.
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), . Such type systems are called cumulative if for any type A we have that implies . 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.
External (20)
- Functional Pearl: Short and Mechanized Logical Relation for Dependent Type Theories (2025)
- Correct and Complete Type Checking and Certified Erasure for Coq, in Coq (2024)
- The Coq Proof Assistant (version 8.20) (2024)
- Type Theory with Explicit Universe Polymorphism (2022)
- Practical generic programming over a universe of native datatypes (2022)
- Generalized Universe Hierarchies and First-Class Universe Levels (2021)
- A Proof and Formalization of the Initiality Conjecture of Dependent Type Theory (2020)
- Decidability of conversion for type theory in type theory (2017)
- Dependent types and multi-monadic effects in F* (2016)
- The Lean Theorem Prover (System Description) (2015)
- Towards a Formally Verified Proof Assistant (2014)
- Universe Polymorphism in Coq (2014)
- Towards a practical programming language based on dependent type theory (2007)
- Explicit Universes for the Calculus of Constructions (2002)
- Internal Type Theory (1995)
- A Simplification of Girard's Paradox (1995)
- Parallel Reductions in λ-Calculus (1995)
- Type Checking with Universes (1991)
- An Intuitionistic Theory of Types: Predicative Part (1975)
- Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur (PhD thesis) (1972)