diff options
author | 2013-05-08 18:03:54 +0200 | |
---|---|---|
committer | 2013-05-08 18:03:54 +0200 | |
commit | db38bb4ad9aff74576d3b7f00028d48f0447d5bd (patch) | |
tree | 09dafc3e5c7361d3a28e93677eadd2b7237d4f9f /theories/Classes/Morphisms_Prop.v | |
parent | 6e34b272d789455a9be589e27ad3a998cf25496b (diff) | |
parent | 499a11a45b5711d4eaabe84a80f0ad3ae539d500 (diff) |
Merge branch 'experimental/upstream' into upstream
Diffstat (limited to 'theories/Classes/Morphisms_Prop.v')
-rw-r--r-- | theories/Classes/Morphisms_Prop.v | 32 |
1 files changed, 31 insertions, 1 deletions
diff --git a/theories/Classes/Morphisms_Prop.v b/theories/Classes/Morphisms_Prop.v index 5a2482d4..2252e42f 100644 --- a/theories/Classes/Morphisms_Prop.v +++ b/theories/Classes/Morphisms_Prop.v @@ -1,6 +1,6 @@ (************************************************************************) (* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2011 *) +(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2012 *) (* \VV/ **************************************************************) (* // * This file is distributed under the terms of the *) (* * GNU Lesser General Public License Version 2.1 *) @@ -107,3 +107,33 @@ Program Instance all_inverse_impl_morphism {A : Type} : unfold pointwise_relation, all in *. intuition ; specialize (H x0) ; intuition. Qed. + +(** Equivalent points are simultaneously accessible or not *) + +Instance Acc_pt_morphism {A:Type}(E R : A->A->Prop) + `(Equivalence _ E) `(Proper _ (E==>E==>iff) R) : + Proper (E==>iff) (Acc R). +Proof. + apply proper_sym_impl_iff; auto with *. + intros x y EQ WF. apply Acc_intro; intros z Hz. + rewrite <- EQ in Hz. now apply Acc_inv with x. +Qed. + +(** Equivalent relations have the same accessible points *) + +Instance Acc_rel_morphism {A:Type} : + Proper (@relation_equivalence A ==> Logic.eq ==> iff) (@Acc A). +Proof. + apply proper_sym_impl_iff_2. red; now symmetry. red; now symmetry. + intros R R' EQ a a' Ha WF. subst a'. + induction WF as [x _ WF']. constructor. + intros y Ryx. now apply WF', EQ. +Qed. + +(** Equivalent relations are simultaneously well-founded or not *) + +Instance well_founded_morphism {A : Type} : + Proper (@relation_equivalence A ==> iff) (@well_founded A). +Proof. + unfold well_founded. solve_proper. +Qed. |