Built with Alectryon, running Coq+SerAPI v8.10.0+0.7.0. Coq sources are in this panel; goals and messages will appear in the other. Bubbles () indicate interactive fragments: hover for details, tap to reveal contents. Use Ctrl+↑ Ctrl+↓ to navigate, Ctrl+🖱️ to focus.
(************************************************************************)
(*         *   The Coq Proof Assistant / The Coq Development Team       *)
(*  v      *   INRIA, CNRS and contributors - Copyright 1999-2018       *)
(* <O___,, *       (see CREDITS file for the list of authors)           *)
(*   \VV/  **************************************************************)
(*    //   *    This file is distributed under the terms of the         *)
(*         *     GNU Lesser General Public License Version 2.1          *)
(*         *     (see LICENSE file for the text of the license)         *)
(************************************************************************)

Proper instances for propositional connectives.

Author: Matthieu Sozeau Institution: LRI, CNRS UMR 8623 - University Paris Sud 
Require Import Coq.Classes.Morphisms.
Require Import Coq.Program.Basics.
Require Import Coq.Program.Tactics.

Local Obligation Tactic := try solve [simpl_relation | firstorder auto].
Standard instances for not, iff and impl.
Logical negation. 
Instance not_impl_morphism :
  Proper (impl --> impl) not | 1.

Instance not_iff_morphism :
  Proper (iff ++> iff) not.
Logical conjunction. 
Instance and_impl_morphism :
  Proper (impl ==> impl ==> impl) and | 1.

Instance and_iff_morphism :
  Proper (iff ==> iff ==> iff) and.
Logical disjunction. 
Instance or_impl_morphism :
  Proper (impl ==> impl ==> impl) or | 1.

Instance or_iff_morphism :
  Proper (iff ==> iff ==> iff) or.
Logical implication impl is a morphism for logical equivalence. 
Instance iff_iff_iff_impl_morphism : Proper (iff ==> iff ==> iff) impl.
Morphisms for quantifiers 
Instance ex_iff_morphism {A : Type} : Proper (pointwise_relation A iff ==> iff) (@ex A).

Instance ex_impl_morphism {A : Type} :
  Proper (pointwise_relation A impl ==> impl) (@ex A) | 1.

Instance ex_flip_impl_morphism {A : Type} :
  Proper (pointwise_relation A (flip impl) ==> flip impl) (@ex A) | 1.

Instance all_iff_morphism {A : Type} :
  Proper (pointwise_relation A iff ==> iff) (@all A).

Instance all_impl_morphism {A : Type} :
  Proper (pointwise_relation A impl ==> impl) (@all A) | 1.

Instance all_flip_impl_morphism {A : Type} :
  Proper (pointwise_relation A (flip impl) ==> flip impl) (@all A) | 1.
Equivalent points are simultaneously accessible or not 
A:Type
E, R:A -> A -> Prop
H:Equivalence E
H0:Proper (E ==> E ==> iff) R
Proper (E ==> iff) (Acc R)


A:Type
E, R:A -> A -> Prop
H:Equivalence E
H0:Proper (E ==> E ==> iff) R
Proper (E ==> iff) (Acc R)

 
A:Type
E, R:A -> A -> Prop
H:Equivalence E
H0:Proper (E ==> E ==> iff) R
Proper (E ==> impl) (Acc R)

 
A:Type
E, R:A -> A -> Prop
H:Equivalence E
H0:Proper (E ==> E ==> iff) R
x, y:A
EQ:E x y
WF:Acc R x
Acc R y
 
A:Type
E, R:A -> A -> Prop
H:Equivalence E
H0:Proper (E ==> E ==> iff) R
x, y:A
EQ:E x y
WF:Acc R x
z:A
Hz:R z y
Acc R z


Tactic failure: Setoid library not loaded.
 now apply Acc_inv with x.
Qed.
Equivalent relations have the same accessible points 
Instance Acc_rel_morphism {A:Type} :
 Proper (relation_equivalence ==> 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 ==> iff) (@well_founded A).
Proof.
 unfold well_founded. solve_proper.
Qed.