Library UniMath.Combinatorics.Equivalence_Relations

Author: Floris van Doorn, december 2017

Equivalence relations.

Contents:

construction of the equivalence relation generated by an arbitrary relation, defined as the truncation of paths in a graph

Definition eqrel_closure_hrel {X : UU} (R : hrel X) : hrel X :=
  λ x y, ∥ gpaths (symmetric_closure R) x y ∥.

Lemma iseqrel_closure {X : UU} (R : hrel X) : iseqrel (eqrel_closure_hrel R).
Proof.
  use iseqrelconstr.
  - intros x y z. apply hinhfun2. apply concat.
  - intro x. apply hinhpr. apply nil.
  - intros x y. apply hinhfun. apply reverse_in_closure.
Defined.

Definition eqrel_closure {X : UU} (R : hrel X) : eqrel X :=
  eqrelpair _ (iseqrel_closure R).

Lemma eqrel_closure_minimal {X : UU} {R : hrel X} (S : eqrel X) (H : ∏ x x', R x x' → S x x') {x x' : X} :
  eqrel_closure R x x' → S x x'.
Proof.
  apply hinhuniv. revert x. apply gpaths_ind.
  - apply eqrelrefl.
  - intros x y r p HS. refine (eqreltrans S _ _ _ _ HS).
    induction r as [r|r].
    + apply H. exact r.
    + apply eqrelsymm. apply H. exact r.
Defined.