← All papers
First page of Computational Paths Form a Weak ω-Groupoid

Computational Paths Form a Weak ω-Groupoid

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

cs.LO Nov 29, 2025 · v1
Formalizes the weak ω-groupoid structure of computational paths in Lean 4 with machine-checked coherence witnesses.
Lumsdaine (2010) and van den Berg-Garner (2011) proved that types in Martin-Löf type theory carry the structure of weak ω-groupoids. Their proofs, while foundational, rely on abstract properties of the identity type without providing explicit computational content for coherence witnesses. We establish an analogous result for computational paths -- an alternative formulation of equality where witnesses are explicit sequences of rewrites from the LNDEQ-TRS term rewriting system. Our main result is that computational paths on any type form a weak ω-groupoid with fully explicit coherence data. The groupoid operations -- identity, composition, and inverse -- are defined at every dimension, and the coherence laws (associativity, unit laws, inverse laws) are witnessed by concrete rewrite derivations rather than abstract existence proofs. The construction provides: (i) a proper tower of n-cells for all dimensions, with 2-cells as derivations between paths and higher cells mediating between lower-dimensional witnesses; (ii) explicit pentagon and triangle coherences built from the rewrite rules; and (iii) contractibility at dimensions $\geq 3$, ensuring all parallel higher cells are connected. The contractibility property is derived from the normalization algorithm of the rewrite system, grounding the higher-dimensional structure in concrete computational content. The entire construction has been formalized in Lean 4, providing machine-checked verification of the weak ω-groupoid structure.

Lumsdaine and van den Berg-Garner proved that types in Martin-Lof type theory carry weak omega-groupoid structure, but their proofs rely on abstract properties of the identity type without providing explicit computational content for coherence witnesses.

The authors establish that computational paths (explicit sequences of rewrites from the LNDEQ-TRS term rewriting system) on any type form a weak omega-groupoid with fully explicit coherence data. Groupoid operations (identity, composition, inverse) are defined at every dimension, and coherence laws are witnessed by concrete rewrite derivations. Contractibility at dimensions >= 3 is derived from the normalization algorithm. The entire construction is formalized in Lean 4.

The construction provides: a proper tower of n-cells for all dimensions with 2-cells as derivations between paths; explicit pentagon and triangle coherences from rewrite rules; and contractibility at dimensions >= 3 ensuring all parallel higher cells are connected. The full weak omega-groupoid structure is machine-checked in Lean 4.