💻 computer science

Definitional Inversion, Without Normalisation

This paper introduces a novel domain-theoretic proof technique that establishes definitional inversion properties for dependent type systems without relying on normalization, thereby enabling meta-theoretic analysis of non-normalizing systems like Idris and Lean as well as those with type-in-type.

Original authors: Mario Carneiro, Thierry Coquand, Adrien Frabetti Mathieu, Meven Lennon-Bertrand, Paul-André Melliès, Stephanie Weirich

Published 2026-07-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mario Carneiro, Thierry Coquand, Adrien Frabetti Mathieu, Meven Lennon-Bertrand, Paul-André Melliès, Stephanie Weirich

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, magical library where every book is a mathematical proof, and the shelves themselves are made of logic. This is the world of dependent type systems, the secret engine behind modern proof assistants like Lean and programming languages like Idris. In this world, the rules are incredibly strict: if you try to put a "cat" on a shelf labeled "numbers," the library's security system (the type checker) should immediately scream "Error!" and stop you. This security relies on a concept called definitional equality, which is the library's way of deciding if two things are essentially the same. For example, is a "square" just a "rectangle with equal sides"? If the system says yes, it treats them as identical.

However, checking these rules is tricky. Traditionally, to prove the library is safe, mathematicians had to show that every single book could be simplified down to its simplest, most basic form (a process called normalization). But many modern, powerful libraries are designed to be infinite or self-referential, meaning they can't be simplified down to a final stop. It's like trying to flatten a fractal; you just keep finding more detail. For a long time, if a system couldn't be simplified, we couldn't prove it was safe. This paper introduces a new way to check the library's safety without needing to flatten the fractal first.

The Infinite Puzzle and the Magic Mirror

Think of a dependent type system as a giant, self-checking puzzle. The pieces are types (like "numbers" or "functions"), and the goal is to make sure that when you snap two pieces together, they fit perfectly. The most critical rule in this puzzle is definitional inversion. It's the logic that says: "If two complex structures look the same, their parts must be the same too." For instance, if you have two function types that are identical, the paper proves that their input types and output types must also be identical. This is crucial because it allows the computer to safely break down complex code into smaller pieces without getting confused.

For decades, the only way to prove these pieces fit was to use a method called confluence (checking if different paths of simplification lead to the same result) or logical relations (a complex way of comparing how terms behave). But these old tools hit a wall. Confluence breaks down when you add certain "extensional" rules (like $\eta$ -laws, which say a function is defined entirely by what it does, not how it's written). Logical relations usually require the system to be "normalizing" (able to stop simplifying), which rules out many powerful, real-world programming languages that allow infinite loops or self-referential types.

The New Approach: A Map of Possibilities

The authors, a team of computer scientists and mathematicians, propose a fresh strategy based on domain theory. Instead of trying to force the puzzle pieces to simplify into a single final shape, they build a map of all possible behaviors.

Imagine you are trying to identify a mysterious creature in a dark forest.

The Old Way: You wait for the creature to stop moving and reveal its true, final form. If the creature never stops moving (because it's an infinite loop), you can't identify it, and the forest is unsafe.
The New Way: You don't wait for the creature to stop. Instead, you observe its footprints. You note that it leaves a "left-foot" print, then a "right-foot" print, then a "left-foot" print again. Even if the creature never stops walking, you can still deduce its shape by looking at the pattern of its steps.

In the paper's language, these "footprints" are called compact elements or finite observations. The authors construct a mathematical "domain" (a structured space) where every type is represented not by a final answer, but by the set of all the finite things we can observe about it. They use a technique called finitary projectors to slice this domain into manageable chunks.

What They Found

Using this "footprint" method, the team successfully proved that definitional inversion holds true even in systems that:

Never stop simplifying (non-normalizing), such as those with a "type-in-type" rule (where a type can contain itself).
Include $\eta$ -laws, which are tricky rules that make functions and pairs behave more intuitively but break traditional proof methods.

They demonstrated this on a small, core version of a type theory called MLTT $\eta$ (Martin-Löf Type Theory with $\eta$ -laws). They showed that even in this chaotic, potentially infinite system, if two types are equal, their building blocks must be equal too. This is a big deal because it proves that the "safety net" of the type system works even when the system is allowed to be messy and infinite.

Why This Matters

The authors didn't just solve a puzzle for a tiny toy system; they showed that their method is robust. They extended their proof to include:

Dependent sums (pairs of data).
Unit types (a type with only one value).
Fixed-point combinators (tools that allow for infinite recursion).
Natural numbers with pattern matching.
Identity types (proving two things are the same).
Proof-irrelevant propositions (where the content of a proof doesn't matter, only that it exists).

They even built a model for a "universe of strict propositions," showing that their technique can handle the complex features found in real-world tools like Lean, Agda, and Rocq.

The Limits and the Future

The paper is very clear about what it doesn't do. It does not prove that these systems are "normalizing" (that they always stop). In fact, it explicitly works for systems that don't stop. It also doesn't solve the problem of "neutrals" (variables that haven't been filled in yet) in the same way it solves for closed terms, though it hints at how that might be done in the future.

The authors have already turned their mathematical proofs into code, verifying them three times over in three different proof assistants (Agda, Lean, and Rocq). This suggests that their method is not just a theoretical idea but a practical tool.

The Takeaway

This paper is like handing the builders of the magical library a new pair of glasses. Before, they could only check the library's safety if the books were static and finished. Now, they can check the safety of books that are still being written, or books that refer to themselves forever. By focusing on the observable behavior (the footprints) rather than the final destination (the stop), they have opened the door to verifying the most powerful, complex, and potentially infinite type systems we can imagine. This paves the way for "Lean4Lean" and "MetaRocq"—projects where proof assistants verify their own code—making the tools we use to build mathematics and software even more trustworthy.

Technical Summary: Definitional Inversion, Without Normalisation

Problem
Dependent type systems underpin critical proof assistants (Agda, Lean, Rocq) and programming languages (Idris, dependent Haskell). Establishing their meta-theoretic properties, particularly definitional inversion principles (injectivity and no-confusion of type constructors), is essential for proving soundness, uniqueness of types, and kernel verification. However, existing meta-theoretic tools face severe limitations:

Confluence-based approaches: These struggle with modern features like $\eta$ -laws. While confluence works for $\beta$ -reduction, mixing it with typed conversion and $\eta$ -laws (e.g., for functions or pairs) often leads to non-confluent systems or requires complex, non-standard presentations.
Normalisation-based approaches (Logical Relations): Traditional logical relations rely on the existence of normal forms. They fail for non-normalising type theories (common in practice, e.g., those using Type:Type or fixed-point combinators). Furthermore, proving normalisation requires an ambient logic stronger than the object logic (often involving induction-recursion or impredicativity), which makes it impossible to study the meta-theory of proof assistants within themselves (e.g., Lean4Lean, MetaRocq).

The paper addresses the specific case of MLTT $\eta$ , a variation of Martin-Löf's type theory with dependent products, $\beta$ and $\eta$ equations, and a Type:Type universe. This system defeats confluence (due to $\eta$ ) and normalisation (due to Type:Type), leaving its definitional inversion properties unproven.

Methodology
The authors propose a new proof technique based on domain theory, specifically utilizing finitary projection models. The core insight is to interpret types not by their normal forms (which may not exist), but by their "observable behavior" via compact elements in a Scott domain.

Domain Construction: The authors construct a domain $D$ $D$ as the solution to a recursive domain equation representing the type constructors ( $\Pi$ $Π$ , $\mathcal{U}$ $U$ , etc.). The domain is built as the limit of an increasing sequence of finite approximations ( $C_n$ $C_{n}$ ), where elements are compact (representing finite observations).
- Crucially, the model identifies $\bot$ with $\lambda x.\bot$ to satisfy $\eta$ -laws for functions, while keeping $\Pi$ -constructors distinct from $\mathcal{U}$ to ensure disjointness.
Semantic Typing: A semantic typing relation is defined on the compact elements of the domain. This relation is formulated using finitary projectors (continuous maps $p: D \to D$ such that $p(\alpha) \le \alpha$ and $p(p(\alpha)) = p(\alpha)$ ). A type is interpreted as a finitary projector, and a term is related to a type if its denotation is a fixed point of that projector.
Logical Relation: A logical relation is defined over the syntactic terms and the semantic witnesses (compact elements). Unlike traditional logical relations that recurse on type normal forms, this relation recurses on the stage $n$ $n$ of the compact elements and the structure of the semantic witness.
- The relation handles open terms by interpreting neutral terms as $\bot$ , avoiding the complexity of Kripke-style quantification while still supporting inversion in open contexts.
- The relation is defined up to head reduction, incorporating $\beta$ and $\eta$ rules directly into the logical relation's structure.
Adequacy: The authors prove an adequacy theorem: if two terms are definitionally equal in the syntax, they are related in the logical relation. This allows deriving syntactic properties (like injectivity) from semantic properties (disjointness of domain elements).

Key Contributions

New Proof Technique: A domain-theoretic method to prove definitional inversion (injectivity and no-confusion) without relying on normalisation or confluence.
Handling $\eta$ and Non-Normalisation: The technique successfully proves injectivity for systems with $\eta$ -laws and Type:Type (or fixed-point combinators), a combination previously intractable for standard methods.
Weak Ambient Logic: The proof relies only on basic induction on natural numbers, avoiding strong logical principles (like induction-recursion) required for normalisation proofs. This makes it suitable for self-verification projects (e.g., proving properties of Lean within Lean).
Extensibility: The technique is demonstrated on MLTT $\eta$ and shown to scale to richer theories including:
- Dependent sums ( $\Sigma$ ) and Unit type ($1$) with $\eta$ -laws.
- General recursion via a fixed-point combinator ( $Y$ ).
- Natural numbers ( $\mathbb{N}$ ) with pattern matching.
- Proof-relevant identity types ($Id$) with transport.
- A universe of strict propositions ($Prop$) with definitional proof irrelevance.
Mechanisation: The results are mechanised in Agda, Lean, and Rocq, covering the various extensions listed above.

Results

Injectivity of $\Pi$ : The paper proves that if $\Pi x:A.B \equiv \Pi x:A'.B'$ , then $A \equiv A'$ and $B \equiv B'$ .
Disjointness: Type constructors are disjoint (e.g., $\Pi x:A.B \not\equiv \mathcal{U}$ ).
Subject Reduction and Progress: As consequences of the inversion principles, the authors derive progress and preservation theorems, establishing the soundness of the language as a programming language.
Failure of UIP: The model demonstrates that Uniqueness of Identity Proofs (UIP/K-rule) is not derivable in this system, as the domain model distinguishes between different proofs of identity.

Significance
The paper claims to fill a "blind spot" in the meta-theory of dependent type systems. By decoupling definitional inversion from normalisation, the technique enables the rigorous study of non-normalising systems and systems with rich equational theories (like $\eta$ ) that are prevalent in modern proof assistants and programming languages.

The authors position this work as a foundational step for projects like Lean4Lean and MetaRocq, which aim to verify the meta-theory of proof assistants within themselves. Since these projects cannot assume the normalisation of the object logic (due to Gödel's second incompleteness theorem), this domain-theoretic approach offers a viable path to verifying kernels and ensuring the correctness of type-checking algorithms without requiring a stronger ambient logic. The authors also suggest potential applications for dependently typed programming languages that utilize non-terminating features or gradual typing, where traditional termination-based meta-theory fails.