Formalizing Computational Paths and Fundamental Groups in Lean

Arthur F. Ramos, Anjolina G. de Oliveira, Ruy J. G. B. de Queiroz, Tiago M. L. de Veras · 2025

Read Formalizing Computational Paths and Fundamental Groups in Lean by Arthur F. Ramos, Anjolina G. de Oliveira, Ruy J. G. B. de Queiroz, Tiago M. L. de Veras (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-19142.txt.

Introduction

Arthur F. Ramos and three co-authors formalize computational paths in Lean 4, a proof assistant that checks mathematics by computer. Computational paths treat equality as an explicit path built from labeled steps and rewrite rules. That view gives equality a weak groupoid structure, meaning paths can be joined and reversed in a loose sense.

The team builds a reusable library, ComputationalPathsLean, covering path formation, joining, inverses, and rewrites that remove needless steps. They then apply it to six standard topology examples. Among the results, the fundamental groups of the circle, the cylinder, and the Möbius band are each proved equal to the integers inside Lean.

Catalog record

CREATORArthur F. Ramos, Anjolina G. de Oliveira, Ruy J. G. B. de Queiroz, Tiago M. L. de Veras
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-19142

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Formalizing Computational Paths and Fundamental Groups in Lean Arthur F. Ramos, Anjolina G. de Oliveira, Ruy J. G. B. de Queiroz, Tiago M. L. de Veras Abstract Computational paths treat propositional equality as explicit paths built from labelled deduction steps and rewrite rules. This view originates in work by de Queiroz and collaborators de Queiroz et al. 2016 and yields a weak groupoid structure for equality, together with a computational account of homotopy inspired by homotopy type theory. In this paper we present a complete mechanization of this framework in Lean 4 and show how it supports concrete homotopy theoretic computations. Our contributions are threefold. First, we formalize the theory of computational paths in Lean, including path formation, composition, inverses, and a rewrite system that identifies redundant or trivial paths. We prove that equality types with computational paths carry a weak groupoid structure in the sense of the original theory. Second, we organize this material into a reusable Lean library, ComputationalPathsLean , which exposes an interface for paths, rewrites, and loop spaces. This library allows later developments to treat computational paths as a drop-in replacement for propositional equality when reasoning about homotopical structure. Third, we apply the library to six canonical examples in algebraic topology. We give Lean proofs that the fundamental group of the circle is isomorphic to the integers, the cylinder and Möbius band also have fundamental group isomorphic to the integers (via retraction to the circle), the fundamental group of the torus is isomorphic to the product of two copies of the integers, the fundamental group of the Klein bottle is isomorphic to the semidirect product ℤ ⋊ ℤ \mathbb{Z}\rtimes\mathbb{Z} , and the fundamental group of the real projective plane is isomorphic to ℤ 2 \mathbb{Z}_{2} . These case studies demonstrate that the computational paths approach scales to nontrivial homotopical computations in a modern proof assistant. All the definitions and proofs described here are available in an open-source Lean 4 repository Ramos et al. 2025 . keywords Computational paths, Lean theorem prover, Homotopy type theory, Fundamental groups 1 Introduction Homotopy type theory and higher category theory have reshaped our understanding of equality in type theory Awodey 2012 ; Univalent Foundations Program 2013 . In this perspective, an equality between elements of a type is not a mere proposition but carries a structure that behaves like a path in a space. This insight links type theory to homotopy theory and suggests that proof assistants based on type theory can serve as practical tools for mechanized homotopy theory. Computational paths offer a complementary viewpoint de Queiroz et al. 2016 . Instead of treating equalities abstractly, they describe equalities as explicitly labelled paths generated by inference rules in a natural deduction system. These paths can be composed, inverted, and simplified by a rewrite system. The resulting structure forms a weak groupoid of equalities, where associativity and inverse laws hold up to path rewrites. The theory of computational paths has been developed in a series of papers that describe the underlying logical system, the associated rewrite rules, and applications to homotopy theoretic constructions such as fundamental groups de Queiroz et al. 2016 ; de Veras et al. 2019 ; Ramos 2018 . However, until now, this theory has lived mostly on paper. Its mechanization in a modern proof assistant brings several benefits. It increases confidence in the correctness of the constructions, exposes hidden subtleties in the interplay of rewrite rules, and provides a reusable platform for further developments. In this paper we report on the first full formalization of computational paths in Lean 4. We build a Lean library that captures the main ideas of the original theory and we use it to compute nontrivial fundamental groups. The work reported here combines logical, algebraic, and engineering aspects and is distributed as the ComputationalPathsLean repository Ramos et al. 2025 . Contributions More concretely, the main contributions of this work are: • A Lean formalization of computational paths for propositional equality, including: – a type of paths between elements of a type, – operations for reflexivity, symmetry, and transitivity, – congruence rules for functions and dependent functions, – a rewrite system that removes trivial or redundant path structure. • A proof, mechanized in Lean, that equality types equipped with computational paths form a weak groupoid. In particular, we formalize path composition and inverses and show that the groupoid laws hold up to rewrite equality. • A Lean implementation of loop spaces and fundamental groups based on computational paths. • Six full case studies: – a computation of the fundamental group of the circle and an isomorphism with the integers, – a computation of the fundamental group of the cylinder, showing it retracts to the circle and thus has fundamental group \mathbb{Z} , – a computation of the fundamental group of the Möbius band, also retracting to the circle with fundamental group \mathbb{Z} , – a computation of the fundamental group of the torus and an isomorphism with the product of two copies of the integers, – a computation of the fundamental group of the Klein bottle and an isomorphism with the semidirect product \mathbb{Z}\rtimes\mathbb{Z} , – a computation of the fundamental group of the real projective plane and an isomorphism with \mathbb{Z}_{2} . • A reusable Lean library, structured as a hierarchy of modules, which can be extended with further spaces and homotopy theoretic constructions. To our knowledge this is the first mechanization of the computational paths framework in any major proof assistant and the first demonstration that this framework can support the computation of classical fundamental groups inside a fully checked environment. Structure of the paper Section 2 recalls computational paths and their weak groupoid structure, as well as the basic notions of loop spaces and fundamental groups. Section 3 describes our Lean environment and overall library layout. Section 4 gives the core definitions of paths and rewrites. Section 5 presents the formalization of the weak groupoid structure. Section 6 describes the computation of the fundamental group of the circle. Section 7 presents the cylinder, which retracts to the circle. Section 8 treats the Möbius band similarly. Section 9 does the same for the torus. Section 10 presents the Klein bottle and its semidirect product fundamental group. Section 11 establishes the fundamental group of the real projective plane. Section 12 discusses engineering aspects of the development, including library design and automation. Section 13 situates our work in the landscape of homotopy inspired formalizations. Section 14 concludes and sketches directions for future work. 2 Background 2.1 Computational paths In the traditional formulation of intensional Martin Löf type theory Martin-L"of 1984 , equality between elements of a type is given by the identity type. A proof of equality can be seen as a path connecting its endpoints. Homotopy type theory makes this interpretation explicit and develops a rich story about higher path structure Univalent Foundations Program 2013 . Computational paths start from a different point of view de Queiroz et al. 2016 ; Ramos 2018 . Instead of treating equality as a primitive type with constructors and eliminators, one derives equalities from a natural deduction system for a typed lambda calculus. Each equality step is labelled by the corresponding reduction or expansion rule, such

Read the complete text