Reference. Stratified Type Theory
A hierarchy of type universes is a rudimentary ingredient in the type theories of many proof assistants to prevent the logical inconsistency resulting from combining dependent functions and the type-in-type axiom. In this work, we argue that a universe hierarchy is not the only option for universes in type theory. Taking inspiration from Leivant’s Stratified System F, we introduce Stratified Type Theory (), where rather than stratifying universes by levels, we stratify typing judgements and restrict the domain of dependent functions to strictly lower levels. Even with type-in-type, this restriction suffices to enforce consistency. In , we consider a number of extensions beyond just stratified dependent functions. First, the subsystem employs McBride’s crude-but-effective stratification (also known as displacement) as a simple form of level polymorphism where global definitions with concrete levels can be displaced uniformly to any higher level. Second, to recover some expressivity lost due to the restriction on dependent function domains, the full includes a separate nondependent function type with a floating domain whose level matches that of the overall function type. Finally, we have implemented a prototype type checker for extended with datatypes and inference for level and displacement annotations, along with a small core library. We have proven to be consistent and to be type safe, but consistency of the full remains an open problem, largely due to the interaction between floating functions and cumulativity of judgements. Nevertheless, we believe to be consistent, and as evidence have verified the ill-typedness of some well-known type-theoretic paradoxes using our implementation.
Cite
Cited by (2)
Internalizing Extensions in Lattices of Type Theories chan-2025-internalizing
Many proof assistants allow the use of features and axioms that increase their expressive power. However, these extensions must be used with care, as some combinations are known to lead to logical inconsistencies. Therefore, proof assistants include mechanisms that track which extensions are used in a proof development or module, ensuring that incompatible extensions are not used simultaneously. Unfortunately, existing extension tracking mechanisms are external to the type system. This means that we cannot specify precisely which extensions a definition depends on. Having the ability to write more precise specifications means we are not picking an overapproximation of the extensions needed, which prevents reusing definitions in the presence of incompatible extensions. Furthermore, we cannot refer to definitions that use incompatible extensions even if they are never used in inconsistent ways. The reasoning principles of one extension therefore cannot be used as a metatheory to reason about the properties of an incompatible extension. In this report, I explore the use of the Dependent Calculus of Indistinguishability (DCOI) by Liu et al. for extension tracking. DCOI is a dependent type system with dependency tracking, where terms and variables are assigned dependency levels alongside their types. These dependency levels form a lattice that describes which levels are permitted to access what. To instead track extensions, each set of extensions would correspond to a dependency level, and the lattice would describe how extensions are permitted to interact.
Type Universes as Kripke Worlds koronkevich-2025-type
What are mutable references; what do they mean? The answers to these questions have spawned lots of important theoretical work and form the foundation of many impactful tools. However, existing semantics collapse a key distinction: which allocations does a reference depend on? In this paper, we deconstruct the space of mutable higher-order references. We formalize a novel distinction–splitting the design space of references not only into higher-order vs (full-)ground references, but also dependency of an allocation on past vs future allocations. This distinction is fundamental to a thorny issue that arises in constructing semantic models of mutable references–the type-world circularity. The issue disappears for what we call predicative references, those that only quantify over past, not future, allocations, and for non-higher-order impredicative references. We design a syntax and semantics for each point in our newly described space. The syntax relies on a type universe hierarchy, à la dependent type theory, to kind the types of allocated terms, and stratify allocations. Each type universe corresponds to a semantic Kripke world, giving a lightweight syntactic mechanism to design and restrict heap shapes. The semantics bear a resemblance to work on regions, and suggest some connection between universe systems and regions, which we describe in some detail.
Cites 41 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.
External (39)
- Artifact for Stratified Type Theory (2025)
- Martin-Löf à la Coq (2024)
- Mechanized consistency proof for MLTT (2024)
- Generic Programming with Extensible Data Types: Or, Making Ad Hoc Extensible Data Types Less Ad Hoc (2023)
- Towards Tagless Interpretation of Stratified System F (TyDe 2023 talk) (2023)
- The Coq Proof Assistant (v8.15) (2022)
- Implementing Dependent Types in pi-forall (2022)
- Generalized Universe Hierarchies and First-Class Universe Levels (2021)
- Decidability of conversion for type theory in type theory (2017)
- Dependent types and multi-monadic effects in F* (2016)
- Equations for Hereditary Substitution in Leivant's Predicative System F: A Case Study (2015)
- The Lean Theorem Prover (System Description) (2015)
- Arend - Proof-assistant assisted pedagogy (Master's thesis) (2015)
- Datatypes of Datatypes (summer school notes) (2015)
- [Agda] Simple contradiction from type-in-type (mailing list post) (2013)
- Crude but Effective Stratification (2011 blog post) (2011)
- Ott: Effective tool support for the working semanticist (2010)
- LNgen: Tool Support for Locally Nameless Representations (tech report) (2010)
- Hereditary substitution for stratified System F (2010)
- Engineering formal metatheory (2008)
- Towards a practical programming language based on dependent type theory (PhD thesis) (2007)
- Crude but Effective Stratification (2002 note) (2002)
- A general formulation of simultaneous inductive-recursive definitions in type theory (2000)
- Stratified polymorphism and primitive recursion (1999)
- A simplification of Girard's paradox (1995)
- The groupoid model refutes uniqueness of identity proofs (1994)
- Lambda calculi with types (1993)
- The paradox of trees in type theory (1992)
- Finitely stratified polymorphism (1991)
- Stratified polymorphism (1989)
- Automatic synthesis of typed Λ-programs on term algebras (1985)
- Number theoretic functions computable by polymorphic programs (1981)
- Towards a theory of type structure (1974)
- Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur (PhD thesis) (1972)
- An intuitionistic theory of types (1972)
- A theory of types (1971)
- The Principles of Mathematics (1903)
- Una questione sui numeri transfiniti (1897)
- Discours de métaphysique (1686)