💻 computer science

Rzk: a Proof Assistant for Synthetic $\infty$ -Categories

This paper introduces Rzk, a practical proof assistant implementing a refined, computational variant of Riehl and Shulman's simplicial type theory to enable synthetic reasoning about $\infty$ -categories, while establishing its faithfulness and conservativity relative to the original theory and providing a tutorial on its usage and implementation.

Original authors: Nikolai Kudasov, Violetta Sim, Benedikt Ahrens

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikolai Kudasov, Violetta Sim, Benedikt Ahrens

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 the universe of mathematics as a giant, infinite playground. For a long time, the most popular game here was Homotopy Type Theory (HoTT). In this game, everything is made of "shapes" that are perfectly flexible. If you have a path from point A to point B, you can always walk it backward. It's like a world of elastic bands where every stretch can be snapped back to its original state. This is great for studying "spaces" (mathematical objects where everything is reversible), but it's a bit too perfect for the messy, real world of categories where some paths are one-way streets.

Enter Rzk, a new proof assistant built by Nikolai Kudasov, Violetta Sim, and Benedikt Ahrens. Think of Rzk as a specialized construction kit designed to build directed shapes. In this new playground, you can have a path from A to B that cannot be walked backward. It's like building with LEGO bricks where some connections are permanent: you can snap a piece on, but you can't un-snap it without breaking the model. This allows mathematicians to reason about $\infty$ -categories, which are complex structures where arrows (morphisms) have directions and don't always reverse.

The Big Idea: A New Way to Build

The paper introduces Rzk as a tool that implements a specific theory called Simplicial Type Theory (RSTT), originally proposed by Emily Riehl and Michael Shulman.

Here is the clever trick Rzk uses:
In the original theory (RSTT), there was a special "magic box" called an extension type. This box let you define a function that behaves in a specific way on the edges of a shape (like a triangle) and does whatever it wants in the middle. It was powerful but a bit like a black box; the rules for how it worked were sometimes hidden in the fine print.

Rzk takes this magic box and splits it open.

The Shape: It separates the "shape" part (the triangle or interval) from the "boundary" part (the rules for the edges).
The Rules: It introduces a new, explicit rule called coercion-free subtyping. Imagine you have a toy car that fits in a small box. In the old system, the system would just assume the car fits in a bigger box without checking. In Rzk, the system explicitly checks that the car fits, but it doesn't force you to wrap the car in extra packaging (a "coercion") to make it fit. It just says, "Yes, this car is also a toy, so it belongs in the toy box." This makes the logic cleaner and easier for computers to check.

What Rzk Can Do (and Can't Do)

The authors have built a "standard library" for this new system called sHoTT. It's already massive, containing over 25,000 lines of code and nearly 1,500 top-level declarations. This library has successfully formalized complex concepts like the $\infty$ -categorical Yoneda lemma (a fundamental theorem in category theory) and various types of "fibrations" (ways to stack categories on top of each other).

However, the paper is very careful about what it claims to have proven:

It is Faithful: The authors proved that anything you can prove in the original theory (RSTT) can also be proven in Rzk. It's a perfect translation.
It is Conservative (with a caveat): They proved that Rzk doesn't invent any new truths about the old theory. If Rzk proves something about an old shape, the old theory could have proven it too. But, this proof only works for a specific "natural fragment" of derivations. The authors admit they haven't fully proved this for every possible weird case yet; they suspect it holds true generally, but it's still a conjecture for the full system.
It is Practical: The tool works right now. It runs in a web browser, has a VS Code extension, and has been used in summer schools and master's theses.

The "Shape Solver"

One of the hardest parts of this math is checking if one shape fits inside another (e.g., is this triangle inside this square?). Rzk uses an automated "tope solver" to do this.

How it works: It's a bit like a detective trying to solve a puzzle. It looks at the rules (topes) and tries to see if they fit.
How good is it? In tests on the sHoTT library, the solver handled over 25,000 questions. Most were solved instantly (in a single step). A few were very hard, taking thousands of steps, but the solver managed them.
The Limit: The solver is incomplete. It's a prototype. It works great for the problems it sees, but the authors admit it might miss some tricky solutions because it doesn't try every possible path. They plan to build a "perfect" solver in the future, but for now, the current one is "sufficient in practice."

What Rzk Rejects

The paper explicitly argues against the idea that you need to manually prove every tiny inclusion of shapes. In older systems, you might have to write out a long proof just to say "this triangle is inside this square." Rzk rejects this manual labor; it automates it.

It also rejects the idea of coercions (adding extra layers of packaging to make things fit). The authors show that you can have a system that understands subtypes without forcing the computer to insert invisible conversion steps that complicate the math.

The Bottom Line

Rzk is a working, usable tool that brings the abstract theory of directed infinity-categories into the real world of computer-checked proofs. It splits complex mathematical "magic boxes" into simpler, transparent parts and proves that it doesn't break the old rules while adding new capabilities.

The authors are confident that Rzk faithfully implements the theory and that their library works. They are sure the tool is useful for teaching and research today. However, they are less certain about the full theoretical guarantees for every single possible edge case (the "full conservativity" conjecture) and admit their shape-solver is a prototype that could be improved. They haven't solved the problem of making the system terminate for all possible inputs (normalization), which remains an open challenge for the future.

In short: Rzk is a working, verified, and growing engine for a new kind of math, built with a fresh design that makes the computer's job easier without losing the magic of the original theory.

Problem Statement
The paper addresses the need for a proof assistant capable of synthetic reasoning about $\infty$ -categories, specifically $(\infty, 1)$ -categories. While Homotopy Type Theory (HoTT) provides a synthetic framework for $\infty$ -groupoids (where all morphisms are invertible), it lacks the machinery to handle directed morphisms, which are essential for category theory. Riehl and Shulman's Simplicial Type Theory (RSTT) was proposed as a solution, introducing "shapes" (like directed intervals and triangles) and "extension types" to define morphisms and higher cells definitionally. However, RSTT remains largely a theoretical framework; it has not been implemented in a practical proof assistant. The primary challenges in implementing RSTT include making type checking computationally feasible, handling the complex boundary conditions of extension types, and formalizing the meta-theoretic assumptions (such as shape inclusions) that RSTT theorems often rely on schematically.

Methodology
The authors present Rzk, a proof assistant implementing a computational refinement of RSTT. The methodology involves three main layers of development:

Theoretical Refinement (Declarative Rzk): The authors define a declarative variant of RSTT (dRzk) that introduces two key structural changes to make the theory more amenable to implementation:
- Split Extension Types: Instead of a single extension type former, dRzk separates the concept into a shape-indexed function type ( $\Pi$ -type over a shape) and a type restriction (attaching a definitional boundary to an arbitrary type). This allows the type checker to handle intermediate types where a function is applied but its boundary conditions are not yet fully resolved.
- Coercion-Free Subtyping: To handle the "silent" identifications often made in paper proofs (e.g., treating a restricted type as its underlying type), dRzk introduces an explicit, coercion-free subtyping relation. This ensures that terms remain unchanged during subtyping checks, avoiding coherence issues.
Meta-Theoretic Formalization: The authors formalize the "Meta-Theoretic Parameter Layer" (MPL). RSTT theorems are often stated schematically over abstract cubes, topes (logical formulas on cubes), and type families. Rzk internalizes these as first-class parameters within definitions, allowing the system to handle shape inclusions and side conditions explicitly rather than as implicit meta-level assumptions.
Algorithmic Implementation: The authors implement an algorithmic version (aRzk) featuring:
- Bidirectional Type Checking: A standard bidirectional algorithm adapted to carry the tope context through all judgments.
- Type-Directed Computation: Normalization is defined on elaborated terms that cache their types, as reduction depends on type information (specifically, whether a boundary tope holds).
- Automated Tope Solver: A prototype solver for the logic of shapes (intuitionistic propositional logic over directed intervals) that automatically checks entailments required for shape inclusions and boundary conditions.
- Subtyping Integration: Subtyping is folded into the definitional equality check using a variance flag, avoiding the insertion of explicit coercions.

Key Contributions

Rzk Proof Assistant: The first implementation of a simplicial type theory for synthetic $\infty$ -category theory. It is written in Haskell and runs as a browser-based playground and via a VS Code extension.
Formal Translation and Conservativity: The paper defines a translation $\tau$ from RSTT to dRzk and a back-translation $\sigma$ . They prove that the translation is faithful (every RSTT proof translates to an Rzk proof) and conservative on a natural fragment of derivations (dRzk proves nothing new about RSTT types). This fragment requires that "free-standing" restrictions (restrictions not attached to a shape- $\Pi$ codomain) are not assumed as hypotheses, only concluded.
sHoTT Library: The authors demonstrate the utility of Rzk through the sHoTT library, a standard library containing over 25,000 lines of code and nearly 1,500 declarations. This library formalizes core concepts of synthetic $(\infty, 1)$ -category theory, including Segal and Rezk types, covariant families, adjunctions, and the first formalization of the $\infty$ -categorical Yoneda lemma.
Implementation Details: The paper details the specific algorithms for handling tope logic, bidirectional typing with tope contexts, and the integration of subtyping into definitional equality.

Results

Correctness: The system successfully type-checks the sHoTT library. The authors report that the tope solver, while incomplete, handles the vast majority of queries in the library efficiently (59% in a single step, 99% within 35 steps).
Bug Fixes: The rigorous comparison between the declarative theory and the implementation uncovered two soundness bugs in previous versions (v0.7.7) related to identity type comparison and asymmetric subtyping checks, which were fixed in v0.7.8.
Performance: The solver accounts for approximately 10% of the total type-checking time. The system is capable of handling complex proofs, such as the Yoneda lemma, without manual intervention for shape inclusions.

Significance and Claims
The paper claims that Rzk is the first and only proof assistant for RSTT, bridging the gap between the theoretical proposal of Riehl and Shulman and practical formalization. Its significance lies in:

Enabling Synthetic $\infty$ -Category Theory: It allows mathematicians to reason about $(\infty, 1)$ -categories directly within the type theory, using extension types to define hom-types and composition definitionally, without propositional bookkeeping.
Practical Usability: The existence of sHoTT demonstrates that the theory is not just theoretically sound but practically usable for non-trivial mathematics.
Theoretical Rigor: By proving faithfulness and conservativity, the authors ensure that Rzk is a faithful implementation of the original RSTT proposal, not a divergent variant.

The authors remain modest regarding open problems. They acknowledge that full conservativity for all dRzk derivations (including those with free-standing restrictions in hypotheses) is currently a conjecture. They also note that the termination of normalization for RSTT is not known in general, and the tope solver is a prototype that is sound but incomplete. Future work includes mechanizing the meta-theory, implementing a normalisation-by-evaluation backend, and adding support for implicit arguments and higher inductive types.

The Big Idea: A New Way to Build

What Rzk Can Do (and Can't Do)

The "Shape Solver"

What Rzk Rejects

The Bottom Line

More like this