1
(************************************************************************)
2
(* v * The Coq Proof Assistant / The Coq Development Team *)
3
(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
4
(* \VV/ **************************************************************)
5
(* // * This file is distributed under the terms of the *)
6
(* * GNU Lesser General Public License Version 2.1 *)
7
(************************************************************************)
9
(*i $Id: Relation_Definitions.v 9245 2006-10-17 12:53:34Z notin $ i*)
11
Section Relation_Definition.
15
Definition relation := A -> A -> Prop.
17
Variable R : relation.
20
Section General_Properties_of_Relations.
22
Definition reflexive : Prop := forall x:A, R x x.
23
Definition transitive : Prop := forall x y z:A, R x y -> R y z -> R x z.
24
Definition symmetric : Prop := forall x y:A, R x y -> R y x.
25
Definition antisymmetric : Prop := forall x y:A, R x y -> R y x -> x = y.
27
(* for compatibility with Equivalence in ../PROGRAMS/ALG/ *)
28
Definition equiv := reflexive /\ transitive /\ symmetric.
30
End General_Properties_of_Relations.
34
Section Sets_of_Relations.
36
Record preorder : Prop :=
37
{ preord_refl : reflexive; preord_trans : transitive}.
39
Record order : Prop :=
40
{ ord_refl : reflexive;
41
ord_trans : transitive;
42
ord_antisym : antisymmetric}.
44
Record equivalence : Prop :=
45
{ equiv_refl : reflexive;
46
equiv_trans : transitive;
47
equiv_sym : symmetric}.
49
Record PER : Prop := {per_sym : symmetric; per_trans : transitive}.
51
End Sets_of_Relations.
54
Section Relations_of_Relations.
56
Definition inclusion (R1 R2:relation) : Prop :=
57
forall x y:A, R1 x y -> R2 x y.
59
Definition same_relation (R1 R2:relation) : Prop :=
60
inclusion R1 R2 /\ inclusion R2 R1.
62
Definition commut (R1 R2:relation) : Prop :=
64
R1 y x -> forall z:A, R2 z y -> exists2 y' : A, R2 y' x & R1 z y'.
66
End Relations_of_Relations.
69
End Relation_Definition.
71
Hint Unfold reflexive transitive antisymmetric symmetric: sets v62.
73
Hint Resolve Build_preorder Build_order Build_equivalence Build_PER
74
preord_refl preord_trans ord_refl ord_trans ord_antisym equiv_refl
75
equiv_trans equiv_sym per_sym per_trans: sets v62.
77
Hint Unfold inclusion same_relation commut: sets v62.