💻 computer science

A Generalized Algebraic Theory for Type Theory with Explicit Universe Polymorphism

This paper presents generalized algebraic theories that provide abstract, grammar-independent characterizations of Martin-Löf type theory with both external towers and explicit universe polymorphism as initial models, thereby highlighting their high-level categorical structure and offering insights relevant to Voevodsky's initiality conjecture.

Original authors: Marc Bezem, Thierry Coquand, Peter Dybjer, Martín Escardó

Published 2026-03-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Marc Bezem, Thierry Coquand, Peter Dybjer, Martín Escardó

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build the ultimate, perfect LEGO set. You want a set that can build anything: houses, spaceships, castles, and even other LEGO sets. But there's a catch: the instructions for building these sets are incredibly complex, filled with thousands of tiny rules about which bricks fit where, how to snap them together, and what happens if you try to build a castle inside a spaceship.

This paper is about stepping back from the thousands of tiny rules and looking at the blueprint of the LEGO system itself. The authors (Marc Bezem, Thierry Coquand, Peter Dybjer, and Martín Escardó) are trying to describe the "rules of the game" for a specific kind of mathematical logic called Type Theory in a way that is cleaner, more abstract, and easier to understand.

Here is the story of their paper, broken down into simple concepts.

1. The Problem: Too Many Rules

In computer science and math, "Type Theory" is like the grammar of a language that computers use to prove things. Usually, we write these rules down like a long list of instructions (like a recipe).

The Issue: When you add a feature called "Universe Polymorphism" (which is like having a box of LEGO bricks that can hold any other box of bricks, no matter how big), the recipe gets messy. You have to write rules for every single size of box, and the instructions become a tangled web of "if this, then that."

The authors say: "Let's stop writing the recipe. Let's describe the kitchen instead."

2. The Solution: The "Generalized Algebraic Theory" (GAT)

Instead of listing every single rule, the authors use a tool called a Generalized Algebraic Theory (GAT). Think of a GAT as a schematic diagram or a structural blueprint.

The Old Way (The Recipe): "Take a red brick, put it on a blue brick, then add a yellow one. If the yellow one is size 5, do X. If it's size 6, do Y."
The New Way (The Blueprint): "We have a container for bricks. We have a rule that says 'you can put a brick inside a container.' We have a rule that says 'containers can hold other containers.'"

By using this blueprint approach, they strip away the messy details (like specific variable names or the order of steps) and focus on the high-level structure. It's like describing a car not by listing every bolt, but by saying, "It has an engine, wheels, and a steering wheel, and they must connect in this specific way."

3. The Two Blueprints They Built

The paper presents two specific blueprints for two different versions of this "LEGO system":

A. The "External Tower" (The Ladder)

Imagine a ladder where each rung is a box.

Rung 1: Holds small toys.
Rung 2: Holds boxes that contain small toys.
Rung 3: Holds boxes that contain boxes from Rung 2.
The Catch: The rungs are numbered by an outside observer (1, 2, 3...). You can't use the ladder to build a new rung; the ladder is fixed from the outside.
The Paper's Contribution: They created a perfect mathematical blueprint for this fixed ladder system. This helps prove that if you build a model of this system, it's the "only" correct one (a concept called Initiality).

B. The "Internal Polymorphism" (The Magic Box)

Now, imagine a magic box that doesn't just hold toys; it holds instructions on how to make boxes.

Inside this system, the "size" of the box isn't fixed by an outside number. Instead, the box can ask, "How big do I need to be?" and adjust itself.
This is Universe Polymorphism. It's like a LEGO set that can automatically resize itself to fit whatever you are building, whether it's a tiny car or a giant castle.
The Paper's Contribution: This is the harder, more complex version. They created a blueprint where the "levels" (sizes) are part of the system itself, not just numbers on a piece of paper. They even added a special "equality check" to make sure the system knows when two levels are the same.

4. Why Does This Matter? (The Voevodsky Connection)

The paper mentions a famous mathematician, Vladimir Voevodsky, who had a big dream: to create a computer system that could verify all mathematical proofs automatically.

The Dream: Voevodsky wanted to say, "If I give you a set of rules, there is only one perfect, initial model of that system." This is called the Initiality Conjecture.
The Problem: Proving this is hard because the rules are so messy.
The Paper's Help: By using these clean blueprints (GATs), the authors make it much easier to prove that "Yes, there is only one perfect model." It's like proving that if you follow the blueprint of a house, you will always get the same house, regardless of who builds it.

5. The "Level" Metaphor

To make the complex "polymorphism" part easier to understand, think of Universe Levels as floors in a skyscraper.

Old System: You have to manually assign every room to Floor 1, Floor 2, or Floor 3. If you want to build a room that can hold rooms from any floor, you have to write a special rule for every single floor.
New System (This Paper): The building has a "smart elevator." You can say, "Put this room on the floor that is one level higher than the room it contains." The system figures out the math automatically. The authors' blueprint shows exactly how that smart elevator works without getting stuck in the gears.

Summary

This paper is a mathematical architecture project.

The Goal: To clean up the messy instructions of advanced computer logic.
The Method: Replace long lists of rules with elegant, high-level blueprints (Generalized Algebraic Theories).
The Result: They created two blueprints: one for a fixed "ladder" of universes and one for a flexible, self-adjusting "magic box" system.
The Impact: This makes it easier to prove that these logical systems are solid, unique, and ready to be used by computers to verify mathematics.

In short, they didn't just build a better LEGO set; they wrote a better instruction manual for how to build any LEGO set, ensuring that everyone who follows it ends up with the exact same masterpiece.

1. Problem Statement

The paper addresses the challenge of providing a rigorous, high-level mathematical characterization of dependent type theories, specifically those involving universe polymorphism.

The Issue: Traditional presentations of type theory rely on grammars and inference rules. While functional for implementation, these presentations are sensitive to syntactic choices (e.g., specific equality rules, bookkeeping) and lack a uniform algebraic structure. This makes it difficult to prove general metatheoretic properties or establish the uniqueness of the "abstract notion" of a type theory.
Voevodsky's Initiality Conjecture: The authors aim to contribute to Vladimir Voevodsky's project, which posits that the term model of a type theory should be the initial object in the category of its models. Proving this requires a formulation of type theories that abstracts away from specific syntactic details.
Specific Gap: Previous work on universe polymorphism (e.g., in Agda or Coq) often treats universe levels either as an external tower (fixed hierarchy) or as an internal type. The authors' previous work [5] introduced explicit universe polymorphism with internal level judgments and level-indexed products. This paper seeks to formalize these theories using Generalized Algebraic Theories (GATs) to prove their initiality properties.

2. Methodology

The authors employ Generalized Algebraic Theories (GATs) and Categories with Families (Cwfs) as their primary mathematical tools.

GATs: Introduced by Cartmell, GATs generalize many-sorted algebraic theories by allowing sort symbols and operator symbols to have dependent types. This allows for a precise algebraic specification of type theories without relying on raw syntax.
Categories with Families (Cwfs): Cwfs serve as the semantic models for dependent type theories. They consist of a category of contexts and a presheaf of families of types and terms.
Two-Stage Approach: The paper constructs GATs for two specific variations of Martin-Löf Type Theory (MLTT):
1. External Tower of Universes: Universes $U_l$ indexed by external natural numbers $l \in \mathbb{N}$ .
2. Explicit Universe Polymorphism: Universes indexed by internal level terms, allowing for level-indexed products and internal constraints.

3. Key Contributions

A. GAT for External Tower of Universes ( $\Sigma_{tower}$ )

The authors present an infinitary GAT ( $\Sigma_{tower}$ ) corresponding to MLTT with an external tower of universes.

Structure: It extends the standard GAT for Cwfs (with $\Pi, \Sigma, N, W, Id$ ) with operator symbols for a tower of universes $U_l$ indexed by $l \in \mathbb{N}$ .
Operators: Includes decoding maps $T_l$ , codes for $\Pi$ -types within universes ( $\Pi_{l,l'}$ ), and inclusion maps for cumulative towers ( $T^m_l$ ).
Initiality: Although the GAT is infinitary (due to the infinite number of universe levels), the authors show that the initial model can be constructed as the union of initial models for finite truncations ( $\Sigma_n$ ). This yields an initial object in the category of Cwfs with an external tower structure.

B. GAT for Explicit Universe Polymorphism ( $\Sigma_{up}$ )

The core contribution is the presentation of a finitary GAT ( $\Sigma_{up}$ ) for MLTT with explicit universe polymorphism.

Level-Indexed Cwfs: Instead of a single Cwf, the model is a level-indexed Cwf. This is a presheaf $P: L^{op} \to \text{CwF}$ , where $L$ is the category of level contexts.
The UCwf of Levels: The base category $L$ $L$ is a Unityped Cwf (UCwf) representing universe levels.
- Sorts: Level contexts ($lctx$), level morphisms ($lhom$), and level terms ($ltm$).
- Operations: Includes a "next level" operator ( $+$ ) and a "join" operator ( $\vee$ ), forming an upper semilattice.
- Level Equality Sorts: A crucial innovation is the introduction of a new sort symbol leq for level equality. Since GATs cannot use equations as assumptions, leq acts as a propositional equality sort. An operator r (reflexivity) generates proofs of equality. This allows the theory to express constraints like $l < m$ (defined as $l^+ \vee m = m$ ) within the type system.
Level-Indexed Products: The theory includes operators for level-indexed products $[\alpha]A$ (universal quantification over levels), with corresponding abstraction and application operators.
Finitary Nature: Unlike the external tower, this GAT is finitary because the universe levels are internal terms generated by a finite set of operators ( $+, \vee$ ), rather than an external infinite set.

C. Initiality and Externalization

The paper demonstrates that the term models of these GATs are initial objects in their respective categories of models:

Explicit Substitution: The construction relies on the general method from the authors' previous work [6], where the initial model is built using explicit substitution (raw syntax with explicit substitution operators).
Implicit Substitution (Initiality Conjecture): The authors outline how to construct the initial model using implicit substitution (standard syntax where substitution is defined by induction). They argue that the term model of the type theory (with implicit substitution) is isomorphic to the externalization of the initial GAT model.
Externalization: They define a process to "externalize" a model of a GAT (which has an internal structure) into a standard Cwf, bridging the gap between the abstract GAT and the concrete type theory used in practice.

4. Results

Abstract Characterization: The paper successfully characterizes MLTT with external universes and MLTT with explicit universe polymorphism as the initial models of their respective GATs ( $\Sigma_{tower}$ and $\Sigma_{up}$ ).
Uniqueness: By framing these theories as initial models, the authors establish that the mathematical essence of these type theories is unique, independent of specific syntactic choices (e.g., specific equality rules or variable naming conventions).
Handling Level Constraints: The introduction of the leq sort provides a robust mechanism for handling universe level constraints (like $l < m$ ) within the algebraic framework, solving a problem where standard GATs struggle with equational assumptions.
Connection to Voevodsky's Project: The work provides a concrete realization of Voevodsky's vision that formal deduction systems can be specified as quasi-equational theories (GATs) with initial models, advancing the "Initiality Conjecture" for complex type theories with universe polymorphism.

5. Significance

Uniform Categorical Logic: The paper serves as a case study for a uniform approach to categorical logic. It demonstrates that GATs and Cwfs can capture complex features like universe polymorphism and level-indexed products, extending the scope beyond simple type theories.
Bridging Syntax and Semantics: It provides a rigorous bridge between the syntactic presentation of type theories (inference rules) and their semantic models (Cwfs). This is essential for proving metatheoretic properties like canonicity or normalization in a generic way.
Foundation for Proof Assistants: By formalizing the structure of universe polymorphism algebraically, this work aids in the development of more robust and flexible proof assistants (like Agda, Coq, or Lean) that support universe polymorphism.
Future Directions: The authors note that their approach can be extended to other logical systems (e.g., predicate logic, cubical type theories) and compared with Logical Frameworks (LF) and Second-Order GATs (SOGATs). The use of leq sorts opens the door to formalizing equational constraints between universe levels, a feature present in modern proof assistants.

In summary, this paper elevates the study of universe polymorphism from a syntactic exercise to a structural algebraic one, proving that these complex type theories are the unique initial models of well-defined Generalized Algebraic Theories.