💻 computer science

Reflexive graph lenses in univalent foundations

This paper introduces reflexive graph lenses as a new intermediate abstraction that simplifies the characterization of identity types for complex structures within univalent foundations, demonstrating their utility through case studies and establishing an equivalence between reflexive graph fibrations and univalent reflexive graph lenses.

Original authors: Jonathan Sterling

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jonathan Sterling

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 massive, complex Lego castle. In the world of mathematics and computer science, this castle is made of "types" (the shapes of the blocks) and "identities" (the rules that tell you when two blocks are effectively the same).

For a long time, mathematicians had a generic, one-size-fits-all rule for saying "these two things are equal." It worked, but it was like trying to describe the difference between a red brick and a blue brick by just saying, "They are both bricks." It was true, but it didn't capture the specific, colorful details that made each structure unique.

This paper, written by Jonathan Sterling, introduces a new set of tools called Reflexive Graph Lenses to help describe these specific details much more easily. Here is the breakdown using everyday analogies:

1. The Problem: The "Generic" Equality

In standard math logic, every object has a built-in "identity type." Think of this as a generic stamp that says, "I am the same as myself."

The Issue: If you want to prove that two complex structures (like a specific type of graph or a list of data) are the same, you usually have to prove it from scratch every time, using very heavy, complicated machinery. It's like trying to prove two houses are identical by measuring every single atom in the walls, rather than just looking at the blueprint.

2. The Old Solution: "Reflexive Graphs"

Mathematicians previously developed a way to organize these proofs using Reflexive Graphs.

The Analogy: Imagine a map of a city.
- Vertices (Points): These are the objects (the houses).
- Edges (Lines): These are the connections or "paths" between them.
- Reflexivity: Every house has a tiny loop connecting it to itself (it's always equal to itself).
The Goal: If you can describe the "paths" between houses correctly, you can prove the houses are the same. This is called a Path Object. It's a way of saying, "If you can walk from House A to House B and back without getting lost, they are effectively the same."

3. The New Tool: "Lenses"

The paper argues that while "Path Objects" are great, building them for complex structures is still too hard. You have to manually define how to move from one part of the structure to another.

Enter Reflexive Graph Lenses.

The Analogy: Think of a Lens like a camera lens or a pair of glasses.
- When you look at a complex structure through a "lens," it automatically handles the movement for you.
- Pushforward (The "Forward" Lens): If you have a piece of data in one part of the structure and you move to a new location, the lens automatically "pushes" that data along with you, adjusting it so it still makes sense.
- Pullback (The "Backward" Lens): If you are at a new location and want to know what the data looked like back at the start, the lens "pulls" the information back for you.
The Magic: The paper shows that if you have these "lenses" (rules for pushing and pulling data), you don't need to manually build the complex "Path Object" from scratch. The lens automatically generates the correct path object for you. It simplifies the math by turning a hard construction problem into a simple algebraic rule.

4. The "Unbiased" Lens

Sometimes, the structure is so weird that you can't just push forward or pull back; you need to do both at the same time or in a mixed way.

The Analogy: Imagine a translator who speaks two languages. Sometimes they translate from English to French, sometimes French to English, and sometimes they have to switch back and forth mid-sentence.
The paper introduces an "Unbiased Dependent Lens" that acts like this translator. It handles complex, mixed-direction movements, allowing mathematicians to describe even the trickiest structures (like the structure of "reflexive graphs" themselves) without getting bogged down in tedious proofs.

5. The Big Result: Fibrations and Lenses are Twins

The paper concludes with a surprising discovery: Lenses and Fibrations are the same thing.

The Analogy: Imagine you have a stack of transparent sheets (a "fibration"). You can slide a marker from one sheet to the next.
The paper proves that the mathematical rules for "sliding a marker" (Fibrations) are exactly the same as the rules for "using a lens to push/pull data" (Lenses).
Why it matters: This means mathematicians can choose whichever tool they prefer. If they like the "lens" metaphor, they can use it to prove things about "fibrations," and vice versa. It unifies two different ways of thinking about the same mathematical reality.

Summary

Jonathan Sterling's paper is essentially a user manual for a new kind of mathematical toolkit.

Old way: Build complex equality proofs by hand, brick by brick.
New way: Use Lenses. These are pre-made tools that automatically handle the "movement" of data between different parts of a structure.
Result: It makes proving that complex mathematical structures are "equal" much faster, cleaner, and less prone to error. It's like upgrading from hand-drawing a map to using a GPS that automatically calculates the route for you.

Technical Summary: Reflexive Graph Lenses in Univalent Foundations

Problem Statement
In Martin-Löf's intensional type theory, identity types provide a generic notion of equality, but characterizing the identity types of specific mathematical structures (e.g., groups, graphs, or dependent sums) often requires tedious, structure-specific proofs. While the "Structure Identity Principle" (SIP) establishes that identity types for algebraic structures correspond to isomorphisms, extending this to complex or dependent structures typically relies on "displayed" structures (specifically displayed reflexive graphs). However, working directly with displayed reflexive graphs can be cumbersome, as it often requires proving univalence for the entire displayed structure from scratch, even when the underlying components are already known to be univalent. The paper addresses the need for a more modular, algebraic framework to characterize identity types for complex structures without re-proving univalence at every step.

Methodology
The paper operates within Martin-Löf's intensional dependent type theory, utilizing the framework of reflexive graphs and path objects (univalent reflexive graphs). The core methodology involves introducing a new class of intermediate abstractions called reflexive graph lenses. These lenses sit between families of reflexive graphs and displayed reflexive graphs.

The authors define three primary types of lenses:

Oplax Covariant Lenses: A family of reflexive graphs indexed by a base reflexive graph, equipped with a "pushforward" operation and an oplax unitor (a witness that pushing forward along a reflexivity edge yields a result connected by an edge to the original, rather than definitionally equal).
Lax Contravariant Lenses: The dual notion, featuring a "pullback" operation and a lax unitor.
Unbiased Dependent Lenses: A generalization capable of handling mixed variance (e.g., reflexivity data in graphs), featuring both left and right extension operations (lext and rext) and coherence laws.

The central technical insight is that these lenses can be "displayed" to form displayed reflexive graphs. The paper proves that if the components of a lens are path objects (univalent), the resulting displayed reflexive graph is automatically a path object. This allows the univalence of complex structures to be derived compositionally from the univalence of their components and the algebraic properties of the lens.

Key Contributions

Reflexive Graph Lenses: The introduction of oplax covariant, lax contravariant, and unbiased dependent lenses as a new family of abstractions. These structures simplify the characterization of identity types by separating the "transport" mechanism (pushforward/pullback) from the univalence proof.
Automatic Univalence: The demonstration that the display of a lens of path objects is itself a path object (Lemma 60, 61, 65). This obviates the need to prove univalence lemmas for many naturally occurring displayed structures, provided they arise from a lens structure.
Definitional Lenses and Flattening: The identification of a subclass of "definitional lenses" where the unit law holds definitionally. The paper provides a "flattening" construction (Construction 81) that reparameterizes any lens into a definitional lens over a modified base, facilitating the application of polynomial type operators.
Polynomials and Partial Products: The generalization of polynomial type operators to lenses, defining covariant and contravariant partial products of reflexive graphs. This allows for the construction of path objects for structures like lists and homotopy unordered pairs.
Equivalence of Fibrations and Lenses: The establishment of a precise equivalence between covariant (resp. contravariant) fibrations of reflexive graphs and oplax covariant (resp. lax contravariant) lenses of path objects (Corollary 129). This is achieved via a "straightening" and "unstraightening" process that converts displayed edges into vertical edges in the underlying family.

Results and Case Studies
The paper validates the utility of reflexive graph lenses through several case studies:

Classifying Reflexive Graphs: The authors construct a path object classifying $U$ -small reflexive graphs. They demonstrate that while reflexivity data for graphs involves mixed variance (preventing a simple covariant or contravariant lens), it is naturally captured by an unbiased dependent lens.
Displayed Reflexive Graphs: The paper constructs path objects for displayed reflexive graphs over fixed and variable bases, showing how the lens framework handles the complexity of displayed reflexivity data.
Polynomial Types: The theory is applied to polynomial type operators, yielding path object structures for lists and homotopy unordered pairs (based on Buchholtz's work), derived from the path object of finite ordinals.

Significance
The paper claims that reflexive graph lenses serve as "organizational devices" to simplify the methods of univalent mathematics, particularly the characterization of identity types. By abstracting the transport operations into lenses, the authors argue that many complex univalence proofs can be reduced to verifying the lens structure and the univalence of the fiber components.

The most significant theoretical result is the equivalence between reflexive graph fibrations and univalent reflexive graph lenses. This result bridges the gap between the geometric intuition of fibrations (where lifts are unique up to homotopy) and the algebraic convenience of lenses (where lifts are chosen but satisfy a unit law). This equivalence suggests that the theory of path objects can be developed entirely within the language of lenses, offering a more modular toolkit for formalizing univalent mathematics in libraries such as Agda. The paper positions itself as a refinement of existing work by Schipp von Branitz, Buchholtz, and Rijke, providing a more granular toolkit for handling dependent types and identity types without altering the underlying type theory.