cycle_cover_mutual_reach_setoid
def
The setoid of mutual reachability along a relation R: x ~ y iff x reaches y and y reaches x by an R-path. Its quotient is the set of strongly connected components; it does not require R to be reflexive.
Statement
def cycle_cover_mutual_reach_setoid {V : Type} (R : V → V → Prop) : Setoid V
- Source
- step towards cycle_cover_diameter_of_strongly_connected_components
- Verified
- 31 Oct 2026
- Axioms
- none listed
Lean source view module on GitHub
/-- Setoid of mutual reachability along R; its quotient is the set of strongly connected components. -/ def cycle_cover_mutual_reach_setoid {V : Type} (R : V → V → Prop) : Setoid V where r x y := Relation.ReflTransGen R x y ∧ Relation.ReflTransGen R y x iseqv := ⟨fun _ => ⟨Relation.ReflTransGen.refl, Relation.ReflTransGen.refl⟩, fun h => ⟨h.2, h.1⟩, fun h₁ h₂ => ⟨h₁.1.trans h₂.1, h₂.2.trans h₁.2⟩⟩