🔢 mathematics

Impredicativity in Linear Dependent Type Theory

This paper presents a formal construction of a realizability model for linear dependent type theory using a linear combinatory algebra, introducing an impredicative universe and specific rules that enable the encoding of linear inductive types.

Original authors: Sam Speight, Niels van der Weide

Published 2026-02-10

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Sam Speight, Niels van der Weide

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 a master chef in a high-end, hyper-organized kitchen. This paper is essentially a blueprint for a new kind of "super-kitchen" management system that handles two very different types of ingredients at the same time.

To understand the paper, we need to look at the three big ideas it tackles: Linearity, Impredicativity, and Inductive Types.

1. The Two Types of Ingredients (Linearity)

In a normal kitchen (standard programming), if you have a recipe for a sauce, you can use the "salt" ingredient as many times as you want, or you can just throw it in the bin without using it. The ingredients are "unlimited."

In this paper’s kitchen, we introduce Linearity. Imagine "Linear Ingredients" are precious, one-of-a-kind items—like a single, perfect truffle.

The Rule: If a recipe calls for a truffle, you must use it exactly once. You cannot duplicate it (no magic cloning), and you cannot ignore it (no wasting).
The Benefit: This is incredibly useful for things like quantum computing or managing memory in computers, where you need to know exactly when a resource is used and when it's gone.

The paper deals with a "Mixed Kitchen" where you have both Standard Ingredients (unlimited salt) and Linear Ingredients (the one-and-only truffle) working together in the same recipes.

2. The "Infinite Recipe Book" (Impredicativity)

Now, imagine you have a "Master Recipe Book" (a Universe). This book contains every possible recipe in the kitchen.

Impredicativity is a bit of a brain-bender. It means that you can write a recipe inside the Master Recipe Book that actually refers to the Master Recipe Book itself.

Think of it like this: You write a recipe called "The Ultimate Soup." The instructions for this soup say, "To make this, you must follow every recipe ever written in the Master Recipe Book."

Usually, this sounds like a logical paradox (like saying "This sentence is a lie"), but in mathematics, if done correctly, it is a superpower. It allows you to define complex things using very simple, universal building blocks. This paper proves that you can have this "looping" power even while still following the strict "use the truffle exactly once" rules of the linear kitchen.

3. Building from Scratch (Inductive Types)

The authors wanted to see if this kitchen was actually functional. To test it, they tried to "build" a List (like a shopping list) using only the rules of the Master Recipe Book.

In many systems, if you try to define a "List" using the "Infinite Recipe Book" method, you get a "ghost list"—it looks like a list, but it doesn't behave perfectly. It might be missing the ability to perform certain mathematical proofs (the "induction principle").

The authors used a clever mathematical trick (called an Equalizer) to "filter" these ghost lists. They essentially said: "We will take all the possible recipes for lists, and then we will only keep the ones that behave perfectly and follow the rules of the kitchen."

They successfully proved that their method creates a "Perfect List" that is mathematically solid.

Summary: The Big Picture

If you were to summarize this paper to a friend at a coffee shop, you’d say:

"Computer scientists are trying to build languages that are both incredibly strict about resources (so they don't waste memory) and incredibly powerful (so they can do complex math). This paper provides the mathematical proof that you can have both. They built a model that allows for 'infinite' logic loops while still respecting the 'use-it-once' rule of precious resources, and they proved it works by successfully building a perfect 'List' from scratch."

Technical Summary: Impredicativity in Linear Dependent Type Theory

1. Problem Statement

The paper addresses a fundamental gap in the semantics of substructural type theories: the integration of impredicativity within Linear Dependent Type Theory (LDTT).

While higher-order type theories (like the Calculus of Constructions) rely on impredicativity—the ability to define a type by quantifying over a universe that includes the type itself—to achieve high expressive power, most existing models of linear type theory struggle to incorporate this feature. Impredicativity is essential for polymorphic encodings (e.g., encoding inductive types like lists as functions), but standard linear systems often lack the necessary categorical structure to support these encodings while maintaining consistency and the ability to prove induction principles.

2. Methodology

The authors employ realizability semantics to construct a model for LDTT. The construction follows these technical steps:

Foundational Structure: They start with a Linear Combinatory Algebra (LCA), an applicative structure equipped with a unary operation ( $!$ ) and specific combinators ( $B, I, C, W, K, D, \delta, F$ ) that satisfy the axioms of linear logic.
Categorical Framework: They utilize Linear Comprehension Categories. This framework extends standard comprehension categories (used to model dependent type theory) by incorporating two distinct fibrations: one for cartesian types (intuitionistic) and one for linear types (substructural).
Linear-Non-Linear Adjunction: To bridge the two sides, they implement a symmetric monoidal adjunction ( $L \dashv M$ ) between the linear and cartesian fibrations. This allows for the interpretation of modalities that turn linear terms into cartesian ones.
Universe Construction: They construct an impredicative Tarski-style universe $U$ using the notion of modest sets and Partial Equivalence Relations (PERs). By leveraging the equivalence between modest sets and PERs, they show that the universe is closed under both large cartesian dependent products and large linear dependent products.
Formalization: The entire construction is fully formalized in the Rocq (formerly Coq) proof assistant using the UniMath library, ensuring the mathematical rigor of the categorical constructions.

3. Key Contributions

A New Model for LDTT: The construction of a realizability model that successfully marries linearity with impredicativity.
Dual-Decoding Universe: The introduction of a universe $U$ with two decoding operations: $El^C$ (mapping codes to cartesian types) and $El^L$ (mapping codes to linear types).
New Type-Theoretic Rules: The paper proposes and justifies several rules previously unconsidered in LDTT, including:
- Equalizers on the linear side.
- Injectivity of the modality $M$ (ensuring the faithfulness of the functor).
- Function Extensionality for linear dependent functions.
Refined Impredicative Encodings: A method to move beyond "weakly initial" algebras to "initial" algebras in a linear setting.

4. Results

Consistency: The model demonstrates that impredicativity is consistent with the rules of LDTT.
Initial Algebra Construction: As a case study, the authors use the impredicative universe to encode the type of lists over a linear type.
Resolution of the Induction Problem: Standard impredicative encodings often fail to satisfy the required induction principles. The authors apply a refinement technique (inspired by Awodey, Frey, and Speight) using equalizers to construct a subtype of the encoded list. They prove that this refined type is indeed the initial algebra, satisfying both the recursion principle and the necessary uniqueness/induction properties.

5. Significance

This work is significant for both theoretical computer science and formal logic. It provides a mathematical foundation for programming languages that require both resource management (linearity) and high-level abstraction/polymorphism (impredicativity).

By proving that one can encode inductive types (like lists) linearly and still recover their full induction principles, the paper paves the way for more expressive quantum programming languages, session-typed systems, and advanced formal verification tools that operate under substructural constraints.