💻 computer science

Constructing (Co)inductive Types via Large Sizes

This paper proposes a consistent extension of intensional type theory with a large type of sizes and parametric quantifiers to construct both inductive and coinductive types, overcoming the limitations of previous approaches and the inconsistency of Agda's current sized types implementation.

Original authors: Bastiaan Laarakker, Daniël Otten, Benno van den Berg

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bastiaan Laarakker, Daniël Otten, Benno van den Berg

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 building a massive, self-referential library of knowledge. In this library, every book (a "type") can contain references to other books, and sometimes a book refers to itself. To keep this library from collapsing into chaos or infinite loops, you need strict rules about how these books can be written and read.

This paper is about designing a better set of rules for a specific kind of library called a "Proof Assistant" (like Agda or Lean). These tools help mathematicians and programmers write code that is guaranteed to work and proofs that are guaranteed to be true.

Here is the breakdown of the paper's ideas using simple analogies:

1. The Problem: The "Stop Sign" vs. The "Speedometer"

Currently, proof assistants use a "Stop Sign" approach (called syntactic checks) to ensure programs don't run forever. They look at the code's shape. If a function calls itself, the computer checks: "Did you pass a smaller piece of data to the next call?" If yes, it's safe. If the code is complex, the computer might get confused and say, "Nope, I can't prove this stops," even if it actually does.

The Paper's Solution: Instead of looking at the shape of the code, the authors propose giving every piece of data a size tag (like a speedometer or a height marker).

Inductive types (like a list of numbers) are tagged with a "height." A recursive function must always go down in height.
Coinductive types (like an infinite stream of data) are tagged with a "depth." A recursive function must always go deeper to be productive.

2. The Flaw in the Current System: The "Magic Infinity"

In the current system (Agda), there is a special tag called Infinity ( $\infty$ ). It's supposed to be the "biggest possible size" that covers everything.

The Analogy: Imagine a ruler that has a mark for "Infinity" at the very end. The problem is that the authors of this paper found that if you try to use this ruler to measure things, you can accidentally prove that "Infinity is smaller than Infinity." This breaks the math, making the whole system inconsistent (like a ruler that says a meter is shorter than a meter).

3. The New Approach: The "Parametric Crowd"

The authors propose a new way to handle these sizes without using a single "Infinity" tag. They introduce two special tools: Parametric Existential ( $\exists$ ) and Parametric Universal ( $\forall$ ) quantifiers.

Think of these as two different ways to look at a crowd of people (the sizes):

The Inductive Type (The "Existential" Crowd):
- The Idea: A finite tree (like a family tree) has a specific height, but we don't need to know exactly how tall it is to use it. We just need to know that somewhere, there is a height limit.
- The Metaphor: Imagine you are looking for a specific person in a crowd. You don't need to see everyone; you just need to know that there exists a person in the crowd who fits the description. The "size" is kept abstract and hidden. You can't peek at the specific number; you just know a limit exists. This prevents the "Infinity is smaller than Infinity" paradox.
The Coinductive Type (The "Universal" Crowd):
- The Idea: An infinite stream (like a live video feed) can be observed for any amount of time.
- The Metaphor: Imagine you are watching a play. To say the play is "infinite," you must be able to watch it for any duration you choose. The "size" here is a promise that the data holds up no matter how deep you look.

4. The Magic Trick: Building the Library

The authors show how to build these complex types (the library books) using these "crowd" tools:

Step 1: They build "approximations" of the types at every possible size (like building a model of a house at 1 foot tall, 2 feet tall, etc.).
Step 2: They use the Existential tool to bundle all the "finite height" approximations into one real Inductive type.
Step 3: They use the Universal tool to bundle all the "infinite depth" approximations into one real Coinductive type.

Why is this better?
Previous attempts could only build "finite branching" trees (like a family tree where everyone has a limited number of children). This new method can build infinite branching trees (where a node can have an infinite number of children), which is much more powerful and flexible.

5. The Proof: The "Realist" Model

To prove their new system doesn't break math, they built a "Realisability Model."

The Analogy: Imagine a judge in a courtroom. The judge doesn't just take the lawyers' word for it; they check the evidence against a specific, very large, and very strict rulebook.
The Rulebook: They interpreted their "sizes" not as simple numbers, but as uncountable ordinals (a concept from advanced math that is "bigger" than the set of all natural numbers).
The Result: By treating sizes as these massive, uncountable numbers, they proved that their "Parametric" rules (hiding the specific size) work perfectly. The system is consistent, meaning it won't accidentally prove that "Infinity is smaller than Infinity."

Summary

The paper solves a bug in current proof assistants where a "magic infinity" tag causes logical contradictions. They replace it with a system that treats sizes as hidden, abstract limits.

For finite things: They say, "There is some limit, but we won't look at it."
For infinite things: They say, "It works for any limit you pick."

This allows them to construct complex, infinite data structures safely, ensuring the proof assistant remains a reliable tool for mathematics and programming.

1. Problem Statement

Proof assistants (e.g., Agda, Lean, Rocq) rely on dependent type theory to ensure consistency and decidability. A critical requirement is that all recursive functions must be total (terminating) and all corecursive functions must be productive.

Current Limitations: Most systems enforce totality via syntactic checks (e.g., structural recursion or size-change termination). These checks are often restrictive, non-modular, and sensitive to code refactoring.
Sized Types: A type-based alternative uses "sizes" (ordinals) to annotate types, allowing termination to be proven via well-founded induction on size.
The Agda Inconsistency: Agda implements sized types but introduces a largest size ( $\infty$ ) to define the full inductive/coinductive type as its approximation at $\infty$ . This leads to a logical inconsistency: the system proves $\infty < \infty$ , violating the irreflexivity of strict well-orders.
Previous Theoretical Work: Previous attempts to fix this using parametric quantifiers (existential $\exists$ for inductive, universal $\forall$ for coinductive) were limited. Specifically, they could only construct finitely-branching inductive types because the size type was interpreted as the set of natural numbers ( $\mathbb{N}$ ), which lacks limit ordinals necessary for infinitely-branching structures.

Goal: Construct a consistent type theory that supports all (co)inductive types (including infinitely-branching ones) using sized types and parametric quantifiers, without relying on an inconsistent largest size.

2. Methodology

The authors extend Martin-Löf Type Theory (MLTT) with specific features to achieve this construction and prove its consistency via a realizability model.

A. The Extended Type Theory

The theory includes standard MLTT features (universes, $\Sigma$ , $\Pi$ , identity types) plus:

A Type of Sizes (Size):
- Equipped with a zero ($0$) and successor ( $\uparrow i$ ).
- Ordered by a preorder ( $\leq$ ) encoded as a mere proposition.
- Crucially: Size is a large type (not in the universe $U$ ), but quantification over it can yield small types.
Parametric Quantifiers:
- $\exists i. A(i)$ (Existential): Represents the union of approximations. Terms are pairs $\langle s, a \rangle$ , but the size $s$ is abstracted (cannot be pattern-matched). Elimination is restricted to small types.
- $\forall i. A(i)$ (Universal): Represents the intersection of approximations. Functions act uniformly on any size.
- Parametricity Axioms: The theory includes axioms stating that these quantifiers commute with type constructors (e.g., $\Pi x:A. \exists i. B(x,i) \simeq \exists i. \Pi x:A. \exists j < i. B(x,j)$ ). This internalizes the idea that sizes are treated uniformly.
Well-Founded Induction (fix):
- A fixpoint operator allowing definition by induction on sizes: $fix\ f : \forall i. A(i)$ given $f : \forall i. ((\forall j < i. A(j)) \to A(i))$ .
- The $\beta$ -rule is propositional (not definitional) to preserve decidability of type checking.

B. Construction of (Co)inductive Types

The authors encode (co)inductive types as initial algebras and final coalgebras for polynomial endofunctors ( $F$ ).

Ordinal Approximations: They define size-indexed functors $F[\exists -]$ and $F[\forall -]$ . Using the fix operator, they construct initial algebras ( $\mu_3 F$ ) and final coalgebras ( $\nu_2 F$ ) for these size-indexed functors. These represent the type truncated at a specific size.
Full Types via Quantification:
- Inductive Types: Defined as $\mu F := \exists i. (\mu_3 F) i$ . The existential quantifier collects all terms bounded by some size.
- Coinductive Types: Defined as $\nu F := \forall i. (\nu_2 F) i$ . The universal quantifier ensures terms are observable at any depth.
Handling Infinitely-Branching Types: The key innovation is showing that polynomial functors weakly commute with the existential quantifier. This requires the existence of limit ordinals (suprema of sequences of sizes), which is impossible if sizes are just $\mathbb{N}$ .

C. Consistency Proof: Realizability Model

To prove the theory is consistent, the authors construct a realizability model based on Hyland's Effective Topos.

Interpretation of Types:
- Small Types: Interpreted as Partial Equivalence Relations (PERs) on natural numbers (computable data).
- Large Types: Interpreted as Assemblies (sets with computability relations).
Interpretation of Size:
- The type Size is interpreted as $\nabla \omega_1$ , where $\omega_1$ is the first uncountable ordinal (the set of all countable ordinals).
- It is given the "full" realizability relation, meaning morphisms must treat all sizes uniformly (parametricity).
Validation:
- Because $\omega_1$ contains limit ordinals, the model validates the parametricity axioms required for infinitely-branching inductive types.
- The model validates Impredicativity (quantifying over large types yields small types) and Uniqueness of Identity Proofs (UIP), even though the syntax does not assume them. This demonstrates the syntax is compatible with stronger theories (like Homotopy Type Theory) without being restricted by them.

3. Key Contributions

General Construction of (Co)inductive Types: Unlike previous parametric approaches limited to finitely-branching types, this work constructs all (co)inductive types, including infinitely-branching ones (e.g., Brouwer ordinals, constructive set theory models).
Resolution of Agda's Inconsistency: By replacing the inconsistent "largest size" ( $\infty$ ) with parametric quantifiers over a large type of sizes, the authors provide a consistent alternative to Agda's current implementation.
Parametric Quantifiers as a Mechanism: They demonstrate that internalizing parametricity via $\exists$ and $\forall$ over sizes effectively enforces the necessary abstraction to prevent non-terminating behavior and logical inconsistencies.
Robust Realizability Model: The construction of a model where Size is interpreted as $\omega_1$ provides a rigorous semantic justification for the theory, proving that the parametricity axioms are consistent.

4. Results

Theoretical Soundness: The paper proves that the initial algebra and final coalgebra for any polynomial endofunctor exist within the extended theory.
Consistency: The realizability model confirms the theory is consistent. It shows that the axioms for parametric quantifiers hold when sizes are interpreted as an uncountable ordinal.
Compatibility: The constructions do not rely on UIP or impredicativity in the syntax, making the results compatible with Homotopy Type Theory (HoTT), despite the model satisfying these properties.

5. Significance and Future Work

Impact on Proof Assistants: This work offers a path to implement sized types in proof assistants (like Agda) without the current inconsistency caused by the $\infty$ size. It allows for more modular and compositional termination checking.
Computational Behavior: The authors acknowledge that while the theory is consistent, the current syntax lacks computational behavior for the parametricity axioms (they are axioms, not reduction rules). Future work needs to connect this with internal parametricity (e.g., via bridge types or cubical type theory) to ensure decidability and canonicity in practice.
Decidability of Inequality: The model implies that inequality on sizes is not generally decidable (due to suprema). The authors suggest a hybrid approach (definitional vs. propositional inequality) for practical implementation.
Generalization: The model could potentially be generalized to other partial combinatory algebras or integrated with effects and univalence.

In summary, the paper successfully bridges the gap between the theoretical need for parametric sized types and the practical requirement for consistency, enabling the construction of complex (co)inductive types in a sound type-theoretic framework.