(****************************************************************************)
(*                 The Calculus of Inductive Constructions                  *)
(*                                                                          *)
(*                                Projet Coq                                *)
(*                                                                          *)
(*                     INRIA        LRI-CNRS        ENS-CNRS                *)
(*              Rocquencourt         Orsay          Lyon                    *)
(*                                                                          *)
(*                                 Coq V6.2                                 *)
(*                               May 1st 1998                               *)
(*                                                                          *)
(****************************************************************************)
(*                       Relation_Definitions.v                             *)
(****************************************************************************)

Section Relation_Definition.

   Variable A: Set.
   
   Definition relation :=  A -> A -> Prop.

   Variable R: relation.
   

Section General_Properties_of_Relations.

  Definition reflexive : Prop :=  (x: A) (R x x).
  Definition transitive : Prop :=  (x,y,z: A) (R x y) -> (R y z) -> (R x z).
  Definition symmetric : Prop :=  (x,y: A) (R x y) -> (R y x).
  Definition antisymmetric : Prop :=  (x,y: A) (R x y) -> (R y x) -> x=y.

  (* for compatibility with Equivalence in  ../PROGRAMS/ALG/  *)
  Definition equiv := reflexive /\ transitive /\ symmetric.

End General_Properties_of_Relations.



Section Sets_of_Relations.

   Record preorder : Prop := {
       preord_refl  : reflexive;
       preord_trans : transitive }.

   Record order : Prop := {
       ord_refl    : reflexive;
       ord_trans   : transitive;
       ord_antisym : antisymmetric }.

   Record equivalence : Prop := {
       equiv_refl  : reflexive;
       equiv_trans : transitive;
       equiv_sym   : symmetric }.
   
   Record PER : Prop := {
       per_sym   : symmetric;
       per_trans : transitive }.

End Sets_of_Relations.



Section Relations_of_Relations.

  Definition inclusion : relation -> relation -> Prop :=
      [R1,R2: relation] (x,y:A) (R1 x y) -> (R2 x y).

  Definition same_relation : relation -> relation -> Prop :=
      [R1,R2: relation] (inclusion R1 R2) /\ (inclusion R2 R1).
   
  Definition commut : relation -> relation -> Prop :=
      [R1,R2:relation] (x,y:A) (R1 y x) -> (z:A) (R2 z y)
                          -> (EX y':A |(R2 y' x) & (R1 z y')).

End Relations_of_Relations.

   
End Relation_Definition.

Hint Unfold reflexive.
Hint Unfold transitive.
Hint Unfold antisymmetric.
Hint Unfold symmetric.

Hint Build_preorder Build_order Build_equivalence Build_PER.
Hint preord_refl preord_trans.
Hint ord_refl ord_trans ord_antisym.
Hint equiv_refl equiv_trans equiv_sym.
Hint per_sym per_trans.

Hint Unfold inclusion.
Hint Unfold same_relation.
Hint Unfold commut.

(* $Id: Relation_Definitions.v,v 1.5 1998/04/30 16:45:53 mohring Exp $ *)
