matita/matita/contribs/lambdadelta/static_2/static/feqg_feqg.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "static_2/static/reqg_reqg.ma".
  16 include "static_2/static/feqg.ma".
  17
  18 (* GENERIC EQUIVALENCE FOR CLOSURES ON REFERRED ENTRIES *********************)
  19
  20 (* Advanced properties ******************************************************)
  21
  22 lemma feqg_sym (S):
  23       reflexive … S → symmetric … S →
  24       tri_symmetric … (feqg S).
  25 #S #H1S #H2S #G1 #G2 #L1 #L2 #T1 #T2 * -G1 -L1 -T1
  26 /3 width=1 by feqg_intro_dx, reqg_sym, teqg_sym/
  27 qed-.
  28
  29 lemma feqg_dec (S):
  30       (∀s1,s2. Decidable … (S s1 s2)) →
  31       ∀G1,G2,L1,L2,T1,T2. Decidable (❨G1,L1,T1❩ ≛[S] ❨G2,L2,T2❩).
  32 #S #HS #G1 #G2 #L1 #L2 #T1 #T2
  33 elim (eq_genv_dec G1 G2) #HnG destruct
  34 [ elim (reqg_dec … HS L1 L2 T1) #HnL
  35   [ elim (teqg_dec … HS T1 T2) #HnT
  36     [ /3 width=1 by feqg_intro_sn, or_introl/ ]
  37   ]
  38 ]
  39 @or_intror #H
  40 elim (feqg_inv_gen_sn … H) -H #H #HL #HT destruct
  41 /2 width=1 by/
  42 qed-.
  43
  44 (* Main properties **********************************************************)
  45
  46 theorem feqg_trans (S):
  47         reflexive … S → symmetric … S → Transitive … S →
  48         tri_transitive … (feqg S).
  49 #S #H1S #H2S #H3S #G1 #G #L1 #L #T1 #T * -G -L -T
  50 #L #T #HL1 #HT1 #G2 #L2 #T2 * -G2 -L2 -T2
  51 /4 width=8 by feqg_intro_sn, reqg_trans, teqg_reqg_div, teqg_trans/
  52 qed-.
  53
  54 theorem feqg_canc_sn (S):
  55         reflexive … S → symmetric … S → Transitive … S →
  56         ∀G,G1,L,L1,T,T1. ❨G,L,T❩ ≛[S] ❨G1,L1,T1❩ →
  57         ∀G2,L2,T2. ❨G,L,T❩ ≛[S] ❨G2,L2,T2❩ → ❨G1,L1,T1❩ ≛[S] ❨G2,L2,T2❩.
  58 /3 width=5 by feqg_trans, feqg_sym/ qed-.
  59
  60 theorem feqg_canc_dx (S):
  61         reflexive … S → symmetric … S → Transitive … S →
  62         ∀G1,G,L1,L,T1,T. ❨G1,L1,T1❩ ≛[S] ❨G,L,T❩ →
  63         ∀G2,L2,T2. ❨G2,L2,T2❩ ≛[S] ❨G,L,T❩ → ❨G1,L1,T1❩ ≛[S] ❨G2,L2,T2❩.
  64 /3 width=5 by feqg_trans, feqg_sym/ qed-.
  65
  66 lemma feqg_reqg_trans (S) (G2) (L) (T2):
  67       reflexive … S → symmetric … S → Transitive … S →
  68       ∀G1,L1,T1. ❨G1,L1,T1❩ ≛[S] ❨G2,L,T2❩ →
  69       ∀L2. L ≛[S,T2] L2 → ❨G1,L1,T1❩ ≛[S] ❨G2,L2,T2❩.
  70 #S #G2 #L #T2 #H1S #H2S #H3S #G1 #L1 #T1 #H1 #L2 #HL2
  71 /4 width=5 by feqg_trans, feqg_intro_sn, teqg_refl/
  72 qed-.
  73
  74 (* Inversion lemmas with generic equivalence on terms ***********************)
  75
  76 (* Basic_2A1: uses: feqg_tneqg_repl_dx *)
  77 lemma feqg_tneqg_trans (S) (G1) (G2) (L1) (L2) (T):
  78       reflexive … S → symmetric … S → Transitive … S →
  79       ∀T1. ❨G1,L1,T1❩ ≛[S] ❨G2,L2,T❩ →
  80       ∀T2. (T ≛[S] T2 → ⊥) → (T1 ≛[S] T2 → ⊥).
  81 #S #G1 #G2 #L1 #L2 #T #H1S #H2S #H3S #T1 #H1 #T2 #HnT2 #HT12
  82 elim (feqg_inv_gen_sn … H1) -H1 #_ #_ #HnT1 -G1 -G2 -L1 -L2
  83 /3 width=3 by teqg_canc_sn/
  84 qed-.