The Church–Rosser theorem for free groups
ProvedFamousTheorems.free_group_reduction_church_rosserThe Church–Rosser theorem for free groups. Consider words over the alphabet , and let mean that is obtained from by a finite sequence of deletions of adjacent inverse pairs . If and , then there is a word with and .
The confluence of free reduction implies that every word has a unique reduced form. This gives the normal form for elements of a free group and solves its word problem.
Formalization note. Mathlib's FreeGroup.Red.church_rosser. Words are List (α × Bool), FreeGroup.Red is the reflexive-transitive closure of one-step reduction, and Relation.Join FreeGroup.Red L₂ L₃ says that and reduce to a common word.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem free_group_reduction_church_rosser {α : Type*} {L₁ L₂ L₃ : List (α × Bool)} (h₁₂ : FreeGroup.Red L₁ L₂) (h₁₃ : FreeGroup.Red L₁ L₃) :
Relation.Join FreeGroup.Red L₂ L₃ := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `FreeGroup.Red.church_rosser`. Proof here reduces to that Mathlib result.