💻 computer science

Formalizing the Real Numbers in Homotopy Type Theory with Cubical Agda

This paper presents a formalization of the Homotopy Type Theory construction of Cauchy real numbers in Cubical Agda, demonstrating that this approach avoids the countable choice, setoid overhead, and universe-level tracking issues inherent in other constructive definitions while type-checking without postulates.

Original authors: Jackson Brough

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jackson Brough

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 perfect, infinite ruler to measure everything in the universe. In the world of classical math, this ruler is easy to describe: you just take all the possible "approximate" measurements (like 3.1, 3.14, 3.141, etc.) and say, "If two sequences of measurements get closer and closer together, they represent the same point on the ruler."

However, in Constructive Mathematics—a style of math that insists you must be able to actually build or compute the thing you are talking about—this simple approach hits a wall. To prove that your ruler is complete, you have to make a magical choice: you have to pick one specific measurement from an infinite list of options to represent the final point. Constructive math says, "No magic allowed. If you can't show me how you picked it, you haven't built the ruler yet."

For decades, mathematicians had to compromise. They either used "bookkeeping" tricks that made every calculation messy, or they built the ruler in a way that required tracking complex "universe levels" (like keeping score of how big your boxes are).

The New Blueprint (HoTT Book Reals)
This thesis presents a new blueprint for building the ruler, taken from the famous Homotopy Type Theory (HoTT) book. Instead of building the ruler by gluing pieces together and then trying to smooth them out, this method builds the ruler and the "smoothness" rules simultaneously.

Think of it like building a house where the walls and the blueprint are being drawn at the exact same time.

The Bricks: You start with simple, known numbers (like fractions).
The Glue: You add a special rule that says, "If two points are close enough, they are actually the same point."
The Magic: Because the "closeness" rule is built into the definition of the house itself, you don't need to make those magical choices later. The house is complete the moment you finish laying the bricks.

The Challenge: The Computer Translator
The author, Jackson Brough, took this theoretical blueprint and tried to translate it into a language a computer can understand and verify: Cubical Agda.

Imagine trying to explain a complex dance routine to a robot that only understands strict, literal instructions.

The Problem: Previous attempts to translate this blueprint failed because the computer language didn't have the right "moves" (specifically, it couldn't handle the simultaneous definition of the ruler and the closeness rules). The translators had to say, "Assume this move exists," which is cheating in math.
The Solution: Cubical Agda is a newer, smarter robot that natively understands these complex moves. It allows the author to write the blueprint exactly as it was designed, without cheating.

What Happened During the Translation?
The thesis isn't just about typing code; it's about what happened when the author tried to make the computer understand the math. The computer's strictness forced the author to find hidden gaps in the original explanation:

The "Alternative" Map: The original book described how to check if two points are close. But when the author tried to write the code, they realized the book's method was like a "one-way street." You could prove points were close, but you couldn't easily work backward to see why. The author had to build a second, "computational" map (called an alternative relation) that acts like a reverse gear, allowing the computer to actually calculate the answer.
The Missing Ingredient: The book described a rule for building functions (like multiplication) as if the computer could "remember" the original list of approximations. The author's first code version forgot this memory. The computer rejected it. The author had to rewrite the rule to explicitly carry the memory along, realizing the original text had been too vague for a machine.
The Multi-Variable Puzzle: The book hinted that rules for single numbers could easily be applied to pairs or triplets of numbers. The computer wasn't convinced. The author had to prove a new, specific lemma showing that if a rule works for one variable, it works for two, provided you check them one at a time.

The Result
The final product is a massive, open-source library of code (over 13,000 lines) that proves the HoTT book reals work perfectly.

It proves that these numbers form a complete, ordered field (you can add, subtract, multiply, divide, and compare them).
It proves that the ruler is "Archimedean" (meaning no matter how small a gap you have, you can always find a fraction to fit inside it).
Most importantly, it does all this without cheating. The computer checked every single step, and the code runs without any "magic assumptions."

In Summary
This thesis is the story of taking a beautiful, high-level mathematical idea and forcing it to survive the rigorous, literal world of computer verification. By doing so, the author didn't just build a digital ruler; they polished the blueprint itself, revealing hidden details and making the theory stronger and more precise than it was before. The code is now available for anyone to use as a solid foundation for future mathematical discoveries.

1. Problem Statement

Constructive mathematics aims to provide computational interpretations for mathematical proofs, but the construction of real numbers ( $\mathbb{R}$ ) has historically required significant compromises:

Classical Cauchy Construction: Requires the Axiom of Countable Choice to select representatives from equivalence classes of Cauchy sequences to prove Cauchy completeness. This is non-constructive.
Bishop's Setoid Construction: Avoids choice by working with Cauchy sequences equipped with an explicit equivalence relation (setoids). However, this introduces persistent bookkeeping overhead, requiring explicit congruence proofs for every operation and theorem, which complicates algebraic structures.
Dedekind Cuts: In predicative type theory, Dedekind cuts require tracking universe levels (the reals live one level above their cuts), making developments cumbersome.

The HoTT Book (Homotopy Type Theory) proposes a solution: defining real numbers as a Higher Inductive-Inductive Type (HIIT). This construction avoids choice, eliminates setoid overhead by identifying $\epsilon$ -close reals via path constructors, and avoids universe-level tracking. However, previous formalizations (e.g., by Gilbert in Rocq) were incomplete because the proof assistants lacked native support for HIITs, forcing the author to postulate the path constructors and their computation rules rather than deriving them.

2. Methodology

The thesis presents a complete, machine-checked formalization of the HoTT book reals using Cubical Agda, a proof assistant based on Cubical Type Theory.

Native Support: Cubical Agda natively supports Higher Inductive Types (HITs) and Inductive-Inductive definitions. This allows the author to define the reals and the closeness relation simultaneously without postulates, ensuring that path constructors have native computation rules.
Formalization Scope: The work formalizes over 13,000 lines of code, covering:
1. The HIIT definition of $\mathbb{R}$ and the closeness relation ( $\sim_\epsilon$ ).
2. Induction and recursion principles.
3. Properties of the closeness relation (reflexivity, symmetry, triangle inequality, roundedness).
4. Extension principles for Lipschitz and non-expanding maps.
5. The construction of algebraic operations (addition, negation, min/max, multiplication, reciprocal).
6. Order theory (strict/non-strict inequalities, apartness).
7. The proof that $\mathbb{R}$ forms an Archimedean ordered field.
Tooling: The author utilized Claude Code (Anthropic's AI agent) to assist with navigating the large Cubical Agda standard library and converting informal proof sketches into formal Agda terms, significantly accelerating the development of complex proofs like the reciprocal construction.

3. Key Contributions

A. The First Complete Formalization of HoTT Reals

This is the first formalization of the HoTT book reals that does not rely on postulates. Previous attempts had to assume the existence of path constructors; this work derives them directly from the Cubical Agda type theory, ensuring all computation rules hold definitionally.

B. Resolution of Formalization Gaps

The process of formalization revealed subtle issues in the informal presentation of the HoTT book that required mathematical refinement:

Alternative Closeness Relation: The inductive definition of closeness ( $\sim$ ) provides sufficient conditions but not necessary ones for extracting witnesses. The formalization rigorously constructs an auxiliary relation ( $\approx$ ) that computes on constructors and proves $\sim \iff \approx$ , enabling case analysis on closeness hypotheses.
Enhanced Recursion Principle: The informal text's notation for the recursion principle tacitly assumed access to the domain approximation ( $x_\epsilon$ ) within the inductive hypothesis. The formalization required explicitly reformulating the recursion principle to carry both the approximation and the codomain assignment, a detail missed in initial naive transcriptions.
Multi-variable Continuity: The HoTT book implies that separate continuity suffices for extending identities to multiple variables. The formalization proved this explicitly (Lemma 2.3.4), showing that separate continuity is sufficient to extend binary and ternary identities from $\mathbb{Q}$ to $\mathbb{R}$ .

C. Construction of Multiplication and Reciprocal

Multiplication and reciprocal are not globally Lipschitz, so they cannot be defined via simple extension principles. The thesis adopts Gilbert's local-to-global strategy:

Define operations on restricted domains where Lipschitz bounds exist (e.g., fixing a bound on one factor).
Prove that these local definitions agree on overlaps.
Use Kraus's Theorem (maps from propositional truncations to sets) to eliminate the dependence on the specific bound, yielding a global definition.
This approach was implemented using the Cubical Agda standard library's SetElim module.

D. Computational Efficiency

Unlike the classical quotient construction in Lean (where $2+2=4$ on reals is not definitionally true), the HoTT construction in Cubical Agda allows arithmetic on rational inputs to compute definitionally. For example, rational(2) + rational(2) = rational(4) reduces to refl (reflexivity) directly in the type checker.

4. Results

Archimedean Ordered Field: The formalization successfully proves that the constructed type $\mathbb{R}$ satisfies all axioms of an Archimedean ordered field, including the existence of inverses for elements apart from zero.
Code Availability: The entire codebase (approx. 13,500 lines) is open source and type-checks without holes or postulates using the latest Cubical Agda standard library.
AI-Assisted Development: The thesis demonstrates the efficacy of using LLM-based coding agents for formal mathematics, specifically for navigating large libraries and translating high-level proof strategies into low-level dependent type terms.

5. Significance

Foundational for Constructive Analysis: This work provides a robust, machine-checked foundation for constructive analysis within the Univalent Foundations program. It removes the "bookkeeping" burden of setoids and the "choice" burden of classical quotients.
Proof Assistant Evolution: It validates Cubical Agda as a superior environment for HIIT-based mathematics compared to systems like Rocq (Coq) that lack native HIT support.
Future Work: The formalization sets the stage for extending constructive analysis to more complex structures (e.g., Riemann integration, differential equations) and generalizing concepts like locators (structures that allow computation on reals) to broader metric spaces.
Methodological Insight: The thesis highlights that formalization is not merely a verification exercise but a mathematical activity that can uncover implicit assumptions and refine theorems in ways that informal reading alone cannot.

In summary, Jackson Brough's thesis bridges the gap between the theoretical elegance of the HoTT book's real numbers and practical, executable mathematics, providing a verified, computationally efficient, and postulate-free foundation for real analysis in type theory.