Abstract Church–Rosser lemma (strip lemma for relations)
ProvedFamousTheorems.church_rosser_abstract_7aAbstract Church–Rosser lemma. Let be a binary relation on a set , with reflexive-transitive closure and reflexive closure . Suppose that whenever and there is with and . Then is confluent: if and , there is with and .
This is the diagram-chasing lemma behind the Church–Rosser theorem of Church and Rosser (1936) for the -calculus. It reduces confluence of a rewriting system to a one-step condition. Confluence implies that normal forms are unique when they exist, which is basic in term rewriting and the semantics of programming languages.
Formalization note. Mathlib's Relation.church_rosser. Relation.ReflGen r and Relation.ReflTransGen r are the reflexive and reflexive-transitive closures of . Relation.Join R b c means that there is with and .
import Mathlib
namespace FamousTheorems
theorem church_rosser_abstract_7a {α : Type*} {r : α → α → Prop} {a b c : α}
(h : ∀ a b c, r a b → r a c → ∃ d, Relation.ReflGen r b d ∧ Relation.ReflTransGen r c d)
(hab : Relation.ReflTransGen r a b) (hac : Relation.ReflTransGen r a c) :
Relation.Join (Relation.ReflTransGen r) b c := by sorry
end FamousTheorems