matita/matita/contribs/lambdadelta/basic_2/static/lfxs_drops.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 "basic_2/relocation/drops_cext2.ma".
  16 include "basic_2/relocation/drops_lexs.ma".
  17 include "basic_2/static/frees_drops.ma".
  18 include "basic_2/static/lfxs.ma".
  19
  20 (* GENERIC EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ****)
  21
  22 definition dedropable_sn: predicate (relation3 lenv term term) ≝
  23                           λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≡ K1 →
  24                           ∀K2,T. K1 ⪤*[R, T] K2 → ∀U. ⬆*[f] T ≡ U →
  25                           ∃∃L2. L1 ⪤*[R, U] L2 & ⬇*[b, f] L2 ≡ K2 & L1 ≡[f] L2.
  26
  27 definition dropable_sn: predicate (relation3 lenv term term) ≝
  28                         λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≡ K1 → 𝐔⦃f⦄ →
  29                         ∀L2,U. L1 ⪤*[R, U] L2 → ∀T. ⬆*[f] T ≡ U →
  30                         ∃∃K2. K1 ⪤*[R, T] K2 & ⬇*[b, f] L2 ≡ K2.
  31
  32 definition dropable_dx: predicate (relation3 lenv term term) ≝
  33                         λR. ∀L1,L2,U. L1 ⪤*[R, U] L2 →
  34                         ∀b,f,K2. ⬇*[b, f] L2 ≡ K2 → 𝐔⦃f⦄ → ∀T. ⬆*[f] T ≡ U →
  35                         ∃∃K1. ⬇*[b, f] L1 ≡ K1 & K1 ⪤*[R, T] K2.
  36
  37 (* Properties with generic slicing for local environments *******************)
  38
  39 lemma lfxs_liftable_dedropable_sn: ∀R. (∀L. reflexive ? (R L)) →
  40                                    d_liftable2_sn … lifts R → dedropable_sn R.
  41 #R #H1R #H2R #b #f #L1 #K1 #HLK1 #K2 #T * #f1 #Hf1 #HK12 #U #HTU
  42 elim (frees_total L1 U) #f2 #Hf2
  43 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #Hf
  44 elim (lexs_liftable_co_dedropable_sn … HLK1 … HK12 … Hf) -f1 -K1
  45 /3 width=6 by cext2_d_liftable2_sn, cfull_lift_sn, ext2_refl, ex3_intro, ex2_intro/
  46 qed-.
  47
  48 (* Inversion lemmas with generic slicing for local environments *************)
  49
  50 (* Basic_2A1: uses: llpx_sn_inv_lift_le llpx_sn_inv_lift_be llpx_sn_inv_lift_ge *)
  51 (* Basic_2A1: was: llpx_sn_drop_conf_O *)
  52 lemma lfxs_dropable_sn: ∀R. dropable_sn R.
  53 #R #b #f #L1 #K1 #HLK1 #H1f #L2 #U * #f2 #Hf2 #HL12 #T #HTU
  54 elim (frees_total K1 T) #f1 #Hf1
  55 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #H2f
  56 elim (lexs_co_dropable_sn … HLK1 … HL12 … H2f) -f2 -L1
  57 /3 width=3 by ex2_intro/
  58 qed-.
  59
  60 (* Basic_2A1: was: llpx_sn_drop_trans_O *)
  61 (* Note: the proof might be simplified *)
  62 lemma lfxs_dropable_dx: ∀R. dropable_dx R.
  63 #R #L1 #L2 #U * #f2 #Hf2 #HL12 #b #f #K2 #HLK2 #H1f #T #HTU
  64 elim (drops_isuni_ex … H1f L1) #K1 #HLK1
  65 elim (frees_total K1 T) #f1 #Hf1
  66 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -K1 #H2f
  67 elim (lexs_co_dropable_dx … HL12 … HLK2 … H2f) -L2
  68 /4 width=9 by frees_inv_lifts, ex2_intro/
  69 qed-.
  70
  71 (* Basic_2A1: uses: llpx_sn_inv_lift_O *)
  72 lemma lfxs_inv_lifts_bi: ∀R,L1,L2,U. L1 ⪤*[R, U] L2 → ∀b,f. 𝐔⦃f⦄ →
  73                          ∀K1,K2. ⬇*[b, f] L1 ≡ K1 → ⬇*[b, f] L2 ≡ K2 →
  74                          ∀T. ⬆*[f] T ≡ U → K1 ⪤*[R, T] K2.
  75 #R #L1 #L2 #U #HL12 #b #f #Hf #K1 #K2 #HLK1 #HLK2 #T #HTU
  76 elim (lfxs_dropable_sn … HLK1 … HL12 … HTU) -L1 -U // #Y #HK12 #HY
  77 lapply (drops_mono … HY … HLK2) -b -f -L2 #H destruct //
  78 qed-.
  79
  80 lemma lfxs_inv_lref_pair_sn: ∀R,L1,L2,i. L1 ⪤*[R, #i] L2 → ∀I,K1,V1. ⬇*[i] L1 ≡ K1.ⓑ{I}V1 →
  81                              ∃∃K2,V2. ⬇*[i] L2 ≡ K2.ⓑ{I}V2 & K1 ⪤*[R, V1] K2 & R K1 V1 V2.
  82 #R #L1 #L2 #i #HL12 #I #K1 #V1 #HLK1 elim (lfxs_dropable_sn … HLK1 … HL12 (#0)) -HLK1 -HL12 //
  83 #Y #HY #HLK2 elim (lfxs_inv_zero_pair_sn … HY) -HY
  84 #K2 #V2 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
  85 qed-.
  86
  87 lemma lfxs_inv_lref_pair_dx: ∀R,L1,L2,i. L1 ⪤*[R, #i] L2 → ∀I,K2,V2. ⬇*[i] L2 ≡ K2.ⓑ{I}V2 →
  88                              ∃∃K1,V1. ⬇*[i] L1 ≡ K1.ⓑ{I}V1 & K1 ⪤*[R, V1] K2 & R K1 V1 V2.
  89 #R #L1 #L2 #i #HL12 #I #K2 #V2 #HLK2 elim (lfxs_dropable_dx … HL12 … HLK2 … (#0)) -HLK2 -HL12 //
  90 #Y #HLK1 #HY elim (lfxs_inv_zero_pair_dx … HY) -HY
  91 #K1 #V1 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
  92 qed-.
  93
  94 lemma lfxs_inv_lref_unit_sn: ∀R,L1,L2,i. L1 ⪤*[R, #i] L2 → ∀I,K1. ⬇*[i] L1 ≡ K1.ⓤ{I} →
  95                              ∃∃f,K2. ⬇*[i] L2 ≡ K2.ⓤ{I} & K1 ⪤*[cext2 R, cfull, f] K2 & 𝐈⦃f⦄.
  96 #R #L1 #L2 #i #HL12 #I #K1 #HLK1 elim (lfxs_dropable_sn … HLK1 … HL12 (#0)) -HLK1 -HL12 //
  97 #Y #HY #HLK2 elim (lfxs_inv_zero_unit_sn … HY) -HY
  98 #f #K2 #Hf #HK12 #H destruct /2 width=5 by ex3_2_intro/
  99 qed-.
 100
 101 lemma lfxs_inv_lref_unit_dx: ∀R,L1,L2,i. L1 ⪤*[R, #i] L2 → ∀I,K2. ⬇*[i] L2 ≡ K2.ⓤ{I} →
 102                              ∃∃f,K1. ⬇*[i] L1 ≡ K1.ⓤ{I} & K1 ⪤*[cext2 R, cfull, f] K2 & 𝐈⦃f⦄.
 103 #R #L1 #L2 #i #HL12 #I #K2 #HLK2 elim (lfxs_dropable_dx … HL12 … HLK2 … (#0)) -HLK2 -HL12 //
 104 #Y #HLK1 #HY elim (lfxs_inv_zero_unit_dx … HY) -HY
 105 #f #K2 #Hf #HK12 #H destruct /2 width=5 by ex3_2_intro/
 106 qed-.