💻 computer science

Directed type theory, with a twist

This paper introduces Twisted Type Theory (TTT), a new directed type theory featuring a novel "twisting" operation and its semantics via dependent 2-sided fibrations, which enables HoTT-style reasoning about categories and provides a syntactic proof of Yoneda's lemma.

Original authors: Fernando Rafael Chu Rivera, Paige Randall North

Published 2026-02-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fernando Rafael Chu Rivera, Paige Randall North

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 a universal language for describing the world. For a long time, mathematicians and computer scientists have been using a language called Homotopy Type Theory (HoTT). Think of HoTT as a language designed to describe spaces and shapes (like a rubber band or a donut). In this world, everything is perfectly symmetrical. If you can go from point A to point B, you can always go back from B to A. It's like walking on a perfectly smooth, reversible path.

However, the real world isn't always like that. In computer science and many areas of math, we deal with categories. Think of a category as a map of a city with one-way streets. You can drive from your house to the grocery store, but you can't necessarily drive back the same way (maybe there's a "Do Not Enter" sign). The old language (HoTT) struggled to describe these one-way streets naturally.

This paper introduces a new language called Twisted Type Theory (TTT). It's designed specifically to handle these one-way streets (directed structures) while keeping the powerful tools of the old language.

Here is the breakdown of their big idea, using some everyday analogies:

1. The Problem: The "One-Way Street" Dilemma

In the old language, if you wanted to talk about a "path" between two things, you had to pretend the path could go both ways. But in a category (like a flow of data or a hierarchy of tasks), the direction matters.

The Old Way: Trying to describe a one-way street by pretending it's a two-way street. It works, but it's clumsy and requires a lot of extra mental gymnastics to prove things.
The Goal: Create a language where "going forward" is a natural, first-class citizen, just like "being equal" is in the old language.

2. The Solution: The "Twist" Operation

The authors introduce a magical tool called a "Twist."

Imagine you have a piece of fabric that is printed with a pattern.

On the left side of the fabric, the pattern is printed "backwards" (contravariant).
On the right side, it's printed "forwards" (covariant).
If you try to use this fabric to make a shirt, it's messy because the two sides don't match up nicely.

The Twist is like a magical sewing machine that takes this messy, two-sided fabric and folds it perfectly so that the whole thing now faces the same direction. Suddenly, you have a clean, usable shirt (a type that depends only on the "forward" direction).

In technical terms, the paper says: "If you have a type that depends on variables in a confusing mix of forward and backward directions, we can 'twist' it to make it depend only in the forward direction."

3. The Secret Sauce: "Dependent 2-Sided Fibrations"

To make sure this "Twist" actually works and isn't just a magic trick, the authors had to invent a new kind of mathematical structure called Dependent 2-Sided Fibrations (D2SFibs).

Think of this as a specialized highway system:

Imagine a highway where cars can enter from the side (covariant) but also have specific rules for how they merge from the opposite lane (contravariant).
The "Twist" operation is the traffic control system that ensures all these cars end up driving in the same direction without crashing.
The authors proved that this highway system is mathematically sound and can be mapped back and forth to the original "messy" patterns. This is their Straightening-Unstraightening Theorem. It's like proving that you can fold a map into a pocket (Twist) and unfold it back out perfectly (Unstraightening) without tearing it.

4. The Big Win: Proving the "Yoneda Lemma"

Why does this matter? The authors use their new language to prove a famous theorem called Yoneda's Lemma.

The Analogy: Imagine you want to know everything about a specific person (let's call him Bob).
- Old Way: You have to ask everyone in the world, "What do you know about Bob?" and then try to piece together a picture. It's tedious.
- Yoneda's Lemma: It says, "You don't need to ask everyone. You just need to know how Bob interacts with everyone else." If you know all of Bob's relationships, you know exactly who Bob is.

In the world of categories (one-way streets), proving this is usually very hard. But because the new Twisted Type Theory has a special rule for "Hom-types" (the rules for how things connect), the authors were able to write a proof that feels like a standard, clean math proof. They didn't have to do the messy, low-level work; the language did the heavy lifting for them.

Summary

The Old Language (HoTT): Great for reversible, symmetrical worlds (spaces).
The New Language (TTT): Great for directional, one-way worlds (categories).
The Magic Trick: The "Twist" operation, which cleans up messy dependencies so you can reason about them easily.
The Result: A powerful new tool that lets computer scientists and mathematicians build and prove things about complex, directed systems (like software architectures or data flows) with the same ease as they do with simple shapes.

In short, the authors built a new pair of glasses that lets us see the "direction" in mathematics clearly, making it much easier to navigate the one-way streets of the digital and mathematical world.

1. Problem Statement

Homotopy Type Theory (HoTT) has successfully established itself as a foundation for mathematics and a synthetic language for reasoning about $\infty$ -groupoids (spaces). However, many areas of mathematics and computer science rely on categories rather than groupoids. While several "directed type theories" (theories with non-symmetric equality) have been proposed to model categories, existing approaches fail to satisfy a specific set of three desiderata simultaneously:

Types as Categories: Every closed type should semantically correspond to a category (avoiding the need to prove a type is a category via extra conditions).
Emergent Categorical Structure: The theory should possess intrinsic Hom-types (directed equalities) that allow encoding $n$ -cells via iteration, similar to how Identity types encode $\infty$ -groupoids.
Trivial Directed Equalities via Path Objects: The theory must support a Hom-introduction rule that corresponds to the factorization of the diagonal map through the arrow category ( $A \to A^\to \to A \times A$ ), enabling the reasoning about natural transformations.

Existing works (e.g., Licata & Harper, North, Riehl & Shulman) satisfy one or two of these criteria but fail to satisfy all three. Specifically, they struggle to provide a syntactic mechanism for natural transformations or require types that are not categories to be part of the base universe.

2. Methodology

The authors propose Twisted Type Theory (TTT), an extension of Martin-Löf Type Theory (MLTT) and North's category model. The methodology involves:

Semantic Foundation: Building upon North's category model where contexts are categories and types are indexed categories.
Dependent 2-Sided Fibrations (D2SFibs): Introducing a new semantic concept generalizing Street's 2-sided fibrations. These are used to interpret a novel syntactic operation called "twisting."
The "Twist" Operation: A syntactic rule that transforms a type depending on variables both contravariantly and covariantly into a type depending only covariantly.
- Semantics: The twist of a type corresponds to the "unstraightening" of a dependent profunctor, resulting in a dependent 2-sided fibration.
- Key Insight: The twist of the Hom-type of a category $A$ yields the arrow category $A^\to$ .
Synthetic Reasoning: Developing elimination rules for Hom-types that mimic the structure of Identity type elimination in HoTT but are adapted for the directed setting.

3. Key Contributions

A. Twisted Type Theory (TTT)

TTT extends MLTT with:

Twisted Types: A new formation rule Twist that converts a type $\Gamma, b: B^{op}, a: A \vdash C$ into a displayed type $\Gamma, b: B, a: A \vdash C[\bar{b}/b]$ .
Hom-types: A directed equality type Hom_A(a, b).
New Rules:
- Hom-Intro: A rule allowing the formation of refl for Hom-types, interpreted as the identity arrow in the arrow category.
- Hom-Elim: A specialized elimination rule that allows reasoning over Hom-types by lifting against D2SFibs. This rule is crucial for proving properties like the Yoneda lemma.

B. Dependent 2-Sided Fibrations (D2SFibs)

The authors define D2SFibs as a generalization of Street's 2-sided fibrations to the dependent setting.

Definition: A span of functors satisfying specific fibration and opfibration conditions locally and globally.
Theorem (Straightening-Unstraightening): They prove a fibred equivalence between the category of dependent profunctors and the category of D2SFibs. This theorem provides the semantic justification for the "twist" operation.

C. Synthetic Category Theory

TTT allows for the internalization of category theory concepts:

Natural Transformations: The twist operation allows the syntax to capture natural transformations between functors. A term of type Hom(Fa, Ga) corresponds to a natural transformation.
Directed Univalence: For sets, the type of functions $A \to B$ is equivalent to the Hom-set HomSet(A, B).
Yoneda Lemma: The authors provide a syntactic proof of the Yoneda lemma within TTT, demonstrating the theory's power.

4. Results

Satisfaction of Desiderata: TTT is the first theory to satisfy all three criteria:
- Closed types are categories (unlike Simplicial Type Theory).
- Hom-types exist and generate higher cells (unlike earlier directed theories).
- The Hom-introduction rule correctly models the arrow category factorization, enabling natural transformation reasoning (solving a previous difficulty in the field).
Proof of Yoneda's Lemma: The paper presents a syntactic derivation of the Yoneda lemma. The proof relies on the Hom-Elim rule, showing that the elimination principle for Hom-types essentially encapsulates the Yoneda lemma.
Relationship to Other Constructs:
- Twisted types characterize the opposite of $\Sigma$ -types.
- They relate to $\Pi$ -types and lax ends.
- They allow for "directed function extensionality."

5. Significance

Foundational Advancement: TTT bridges the gap between Homotopy Type Theory (groupoids) and Category Theory (categories) by providing a unified syntactic framework where categories are the primary semantic objects.
Synthetic Reasoning: It enables mathematicians and computer scientists to reason about categories and natural transformations using type-theoretic syntax without leaving the internal language, similar to how HoTT allows reasoning about spaces.
New Mathematical Structures: The introduction of D2SFibs and the straightening-unstraightening theorem for them contributes new tools to categorical logic and higher category theory.
Future Directions: The paper identifies that while TTT works for 1-categories, the theory of D2SFibs needs further development to generalize to higher dimensions (e.g., $(\infty, 1)$ -categories) and to handle core-types (types that are neither purely covariant nor contravariant) more naturally.

In summary, "Directed type theory, with a twist" introduces a novel mechanism (the twist) that resolves long-standing issues in directed type theory, allowing for a robust, synthetic treatment of category theory that mirrors the success of HoTT in treating homotopy theory.