Certified shape reasoning for the Rzk proof assistant
Master Project


Context

Rzk is a proof assistant for synthetic ∞-category theory. Its proofs use geometric shapes, such as the triangle 0 ≤ s ≤ t ≤ 1, described by constraints called topes. Type checking constantly asks whether one tope follows from others, for example whether every point with s = 0 lies in the triangle. Rzk answers these questions with a built-in solver. The solver’s soundness has not been mechanised, so a bug in it can make the whole checker accept wrong proofs.

SAT solving faced the same problem and solved it with proof certificates: the solver emits a proof, and a small, independently verified checker validates it (the DRAT format of Wetzler, Heule and Hunt is the best-known example). This project brings that approach to Rzk’s tope logic.

The logic is small. Its formulas use only ⊤, ⊥, conjunction, disjunction, and atomic constraints s ≤ t and s = t between points of an interval. Its theory is coherent, so for the questions Rzk asks, classical and intuitionistic provability coincide (Barr’s theorem; see Negri). It appears that each question can be decided by checking finitely many linear orders of the points involved. Making this precise is part of the project. Hence certificates can use classical reasoning, and intuitionistic proofs are only needed for possible extensions of the logic with implication.

Tasks

  1. Fix the logic and its semantics, and design a certificate format, for example a case split over orderings of the points, or a derivation in a sequent calculus with the interval axioms as rules.
  2. Make a solver emit certificates: Rzk’s existing solver or a small new one in Haskell. A complete decision procedure is being developed in another ongoing student thesis. This project does not depend on it.
  3. Write a certificate checker in Agda, Lean, or Rocq, and prove it sound with respect to the semantics.
  4. Evaluate on the tope queries arising from Rzk’s sHoTT library: certificate size, checking time, and the overhead for the solver.
  5. Optionally, identify where intuitionistic reasoning becomes necessary once implication is added, and what certificates would look like there.

What you will learn

Sequent calculi and proof search, decision procedures, proof certificates, and verified programming in a proof assistant.

Prerequisites

A course on logic or formal methods, and some experience with a proof assistant or with functional programming. No category theory is needed.

Reading

  • Nathan Wetzler, Marijn Heule, and Warren Hunt. DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs. SAT 2014, LNCS 8561.
  • Sara Negri. Contraction-free sequent calculi for geometric theories with an application to Barr’s theorem. Archive for Mathematical Logic, 2003. https://doi.org/10.1007/s001530100124
  • Nikolai Kudasov, Violetta Sim, and Benedikt Ahrens. Rzk: a Proof Assistant for Synthetic ∞-Categories. 2026. https://arxiv.org/abs/2607.12207 (§2 for shapes and topes)
  • Emily Riehl and Michael Shulman. A type theory for synthetic ∞-categories. Higher Structures, 2017. https://arxiv.org/abs/1705.07442 (§2 for the tope logic)

Certified shape reasoning for the Rzk proof assistant

Supervisor(s): Benedikt Ahrens
Posted: November 04, 2026