← All papers
First page of Bounded First-Class Universe Levels in Dependent Type Theory

Bounded First-Class Universe Levels in Dependent Type Theory

Jonathan Chan, Stephanie Weirich

cs.PL Feb 27, 2025 · v1
Designs a dependent type theory with bounded first-class universe levels, mechanizing its metatheory from syntax to semantics in Lean.
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.

In dependent type theory, first-class universe levels with bounded polymorphism increase expressivity but have not had explicit syntax and typing rules written down. Prior type theories with bounded level polymorphism fail to satisfy subject reduction.

The authors design TTBFL, an explicit syntax for a type theory with bounded first-class universe levels, parametrized over arbitrary well-founded sets of levels. The theory supports dependent functions, predicative universes, and bounded universe levels. They prove metatheoretic properties (subject reduction, type safety, consistency, and canonicity) entirely mechanized from syntax to semantics in Lean.

The full metatheory of TTBFL is verified in Lean, establishing subject reduction, type safety, consistency, and canonicity for the first explicitly syntactified type theory with bounded first-class universe levels over arbitrary well-founded level sets.