💻 computer science

Directed proof-relevant logical relations in simplicial HoTT

This paper develops a directed, proof-relevant framework for logical relations within simplicial homotopy type theory by internalizing reductions as inequality types and utilizing contravariant families to construct models that prove directed Boolean canonicity and representation independence for dependent types.

Original authors: Runming Li, Harrison Grodin, Robert Harper

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Runming Li, Harrison Grodin, Robert Harper

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 giant, magical LEGO castle. In the world of computer science, this castle is a "type theory"—a set of rules for how programs are built and how they behave. Usually, when computer scientists check if a program works, they look at the finished bricks and ask, "Are these two bricks exactly the same?" If they are, they treat them as identical. This is like saying two LEGO structures are the same if they look identical from the outside.

But in this paper, the authors, Runming Li, Harrison Grodin, and Robert Harper, ask a different question: What if we care about the process of building? What if we want to track not just the final shape, but the fact that one brick reduced to another? Maybe a big, clunky brick snapped into a smaller, sleeker one. This "snapping" is called reduction, and it has a direction: big goes to small, but small doesn't magically grow back into big.

The Problem: The "Backwards" Puzzle

In the old way of doing things (using "equational" logic), scientists treated reduction like a two-way street. If Brick A turns into Brick B, they just said "A equals B." This made math easy, but it ignored the direction of the flow. It's like saying "walking to the store" is the same as "walking home." It's true you end up at the same place, but the journey is different!

The authors realized that to prove a program is "computable" (meaning it will eventually stop and give you a real answer), you need to be able to walk backwards along that journey. If you know the final, perfect brick is good, you need to prove that the messy, clunky brick that turned into it was also good. This is called the "expansion" property.

The Solution: A One-Way Street with a Magic Map

The authors built a new kind of LEGO set using a framework called Simplicial Homotopy Type Theory. Think of this as a special playground where they can draw one-way arrows (inequalities) instead of just equal signs.

Here is the magic trick they discovered:

The Direction: They replaced "equals" with "less than or equal to" (≤). So, if a term reduces, it goes from $A \le B$ . It's a one-way street.
The Backwards Walk: To prove things work backwards, they needed a special kind of map. In math, this is called a contravariant family.
- The Analogy: Imagine you have a backpack full of "proofs" (like tickets to a concert). If you walk forward along the one-way street, you might lose your tickets. But this special map is a reverse-time machine. If you have a ticket for the destination ( $B$ ), the map automatically generates a valid ticket for the starting point ( $A$ ).
- The paper proves that in their new system, this "reverse-time machine" isn't just a lucky guess; it's built into the very fabric of the math. It's a "proof-relevant" machine, meaning the ticket itself carries a little note explaining how it was generated, not just that it exists.

The Big Win: The Boolean Canonicity

To show this works, they tested it on the simplest building block of logic: Booleans (True and False).

The Goal: They wanted to prove that if you start with any closed Boolean term (a program that doesn't need outside help), it will eventually "reduce" (snap) into either true or false.
The Result: They proved that every such term reduces to a canonical answer. It's like guaranteeing that no matter how messy your LEGO instructions are, if you follow the rules, you will eventually end up with a perfect, recognizable brick. They didn't just say "it probably works"; they constructed a rigorous mathematical proof that it must work.

What They Didn't Do (and What They Avoided)

It's important to know what this paper doesn't claim:

No Magic Equality: They explicitly reject the idea that you can just pretend reduction is the same as equality. They argue that treating "reduction" as "equality" loses the directionality needed for their proof.
Not Just a Simulation: This isn't a computer simulation or a guess. They built a formal mathematical model and proved theorems about it. They even wrote a computer program (in a language called Cubical Agda) to check the simple parts of their logic, acting as a "proof of concept."
Not a Full Universe (Yet): While they proved this works for simple types (like Booleans and pairs) and even started on complex "dependent types" (where types can depend on values), the full, complex version with all the bells and whistles is still a work in progress. They showed the path is clear, but the whole mountain isn't climbed yet.

The "Flat" Modality: A Special Filter

When they tried to add "Universes" (a box that holds other boxes of types), they hit a snag. The one-way arrows got too messy to handle.

The Fix: They introduced a "flat modality" (denoted by a symbol like ♭). Think of this as a discretization filter. It takes a fuzzy, one-way street and forces it to become a crisp, two-way street only for the specific purpose of checking if types are the same. It's like putting on special glasses that make the direction disappear just long enough to compare two bricks, then taking them off to see the direction again. This allowed them to handle the complex "universe" rules without breaking their one-way street logic.

The Bigger Picture: Representation Independence

Finally, they showed this method works for binary logical relations. This is like checking if two different LEGO sets (maybe one made of plastic, one of wood) can do the same job.

They separated the "vertical" movement (how a single set changes over time) from the "horizontal" movement (how two different sets relate to each other).
By keeping these separate, they proved that you can swap out the internal parts of a program (the "representation") without changing what the program does (the "interface"). This is the mathematical heart of "representation independence," a crucial concept for writing reliable software.

Summary

In short, Li, Grodin, and Harper have built a new mathematical playground where direction matters. They showed that by treating program reduction as a one-way street and using a special "reverse-map" (contravariance), you can rigorously prove that programs will always finish and give you a real answer. They didn't just suggest it; they proved it for simple cases and laid out the blueprint for the complex ones, all while keeping the messy details of "how" the reduction happens right in the center of the math.

Technical Summary: Directed Proof-Relevant Logical Relations in Simplicial HoTT

Problem Statement
Traditional proof-relevant logical relations (often formulated via categorical gluing) interpret types as families of computable terms, where computability predicates are families of types rather than mere propositions. In equational presentations of type theory, judgmental equality is represented by meta-level equality, and logical relations rely on a "closure under expansion" lemma: if a term $M$ reduces to $M'$ , and $M'$ is computable, then $M$ is computable. However, this approach treats computation as a symmetric relation (via equality) or relies on manual proofs of backward closure. It does not natively internalize the directed nature of reduction, where terms step to other terms ( $M \to M'$ ) but not necessarily vice versa. The paper addresses the challenge of constructing a proof-relevant logical relation that accounts for directed reductions internally, without relying on external reduction relations or proof-irrelevant expansion lemmas.

Methodology
The authors develop their framework within simplicial homotopy type theory (HoTT), a directed extension of HoTT that includes a directed interval and inequality types ( $x \leq_A y$ ).

Directed Syntax via Directed QIITs:
The object-language syntax is presented as a directed quotient inductive-inductive type (directed QIIT). Unlike standard QIITs which quotient by judgmental equalities (path constructors), this syntax includes directed constructors that generate inequality types. For example, the $\beta$ -reduction for products is internalized as an inequality:
$\times\beta_1 : \text{fst}(\text{pair } a \, b) \leq a$
The syntax is constructed to be a "thin Segal type," ensuring that reductions compose and that inequalities between the same endpoints are unique (proof-irrelevant), modeling a preorder rather than a general category.
Contravariance as Proof-Relevant Expansion:
The core theoretical insight is that contravariant families in simplicial type theory provide the exact structure needed for proof-relevant closure under expansion. In this setting, a computability predicate $A^\bullet$ for a type $A$ is not just a family of types; it must be a contravariant family.
- Definition: A family $C: X \to \mathcal{U}$ is contravariant if for every inequality $f: x \leq_X y$ and witness $v: C(y)$ , the type of lifts $\sum_{u:C(x)} u \leq_{C(f)} v$ is contractible.
- Implication: This contractibility guarantees a unique, functorial "backward transport" operation $f^*: C(y) \to C(x)$ . This operation internalizes the expansion lemma: computability evidence can be transported backward along reductions in a way that respects identities and composition automatically.
Handling Dependent Types and Universes:
Extending this to dependent types introduces a conflict: type conversion requires symmetric equality, but the syntax only provides directed inequalities.
- Discretization: The authors discretize the type universe ($Ty$) by adding a constructor that turns type inequalities into equalities ( $A \leq Ty B \implies A = Ty B$ ). This allows standard type conversion while preserving directed reductions for terms.
- Flat Modality: To maintain proof-relevance for universe predicates without losing discreteness, the authors employ the flat modality ( $\flat$ ) from crisp type theory. Computability predicates for universes are stored as flat codes. Since $\flat X$ is discrete, inequalities between predicates collapse to equalities, ensuring the uniqueness required for the universe's computability witness.

Key Contributions

Directed Quotient Syntax: A formalization of type theory syntax where judgmental reductions are internalized as directed inequalities via directed QIITs.
Contravariance as Expansion: The identification of contravariant families in simplicial type theory as the proof-relevant generalization of the expansion lemma, providing built-in functoriality and universal properties for backward transport.
Unary Logical Relations Model: A construction of a unary logical relation model that proves directed Boolean canonicity: every closed Boolean term $M$ satisfies $M \leq \text{true}$ or $M \leq \text{false}$ .
Mechanization: A proof-of-concept mechanization in Cubical Agda for the simply-typed fragment (products, functions, Booleans), demonstrating the feasibility of the directed approach.
Extension to Dependent Types and Universes: A solution for dependent types using discretization of types and the flat modality to handle universe predicates.
Binary Parametricity: An adaptation of the method to binary logical relations, separating vertical reductions (contravariance) from horizontal parametricity, illustrated via a representation independence argument for queues.

Results

Directed Canonicity: The fundamental theorem of logical relations is established for the directed setting. For any closed Boolean term $M$ , the model yields a witness that $M$ reduces to a canonical boolean.
Representation Independence: The binary logical relation successfully separates the vertical dimension (reduction/contravariance) from the horizontal dimension (parametricity), allowing for proof-relevant accounts of representation independence where the relation is a span rather than a zig-zag.
Mechanization: The simply-typed fragment, including the construction of the directed syntax and the logical relation model, has been formalized in Cubical Agda.

Significance and Claims
The paper claims to provide a type-theoretic internalization of the idea that logical relations should validate canonicity and parametricity even when syntax is presented by reductions rather than equalities.

Theoretical Unification: It unifies the operational view of computation (directed reduction) with the semantic view of logical relations (proof-relevant gluing) by leveraging the native directed structure of simplicial type theory.
New Role for Contravariance: It elevates contravariant families from a tool for synthetic category theory to a fundamental mechanism for logical relations, replacing ad-hoc expansion lemmas with a universal property.
Modesty: The authors note that the result is "unsurprising" in its conclusion (logical relations should work for reductions) but significant in its internalization. They acknowledge that the dependently typed extension presents significant transport challenges and that the current mechanization is limited to the simply-typed case. They do not claim to have solved all issues regarding identity types in directed settings, suggesting future work involving phase distinctions or monadic modalities.

The work demonstrates that simplicial type theory is not only a tool for synthetic $\infty$ -category theory but also a viable metatheory for reasoning about the reduction semantics of programming languages and type theories.