matita/matita/contribs/lambdadelta/static_2/static/rex_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 "static_2/relocation/drops_cext2.ma".
  16 include "static_2/relocation/drops_sex.ma".
  17 include "static_2/static/frees_drops.ma".
  18 include "static_2/static/rex.ma".
  19
  20 (* GENERIC EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ****)
  21
  22 definition f_dedropable_sn:
  23            predicate (relation3 lenv term term) ≝ λR.
  24            ∀b,f,L1,K1. ⇩*[b,f] L1 ≘ K1 →
  25            ∀K2,T. K1 ⪤[R,T] K2 → ∀U. ⇧*[f] T ≘ U →
  26            ∃∃L2. L1 ⪤[R,U] L2 & ⇩*[b,f] L2 ≘ K2 & L1 ≡[f] L2.
  27
  28 definition f_dropable_sn:
  29            predicate (relation3 lenv term term) ≝ λR.
  30            ∀b,f,L1,K1. ⇩*[b,f] L1 ≘ K1 → 𝐔❪f❫ →
  31            ∀L2,U. L1 ⪤[R,U] L2 → ∀T. ⇧*[f] T ≘ U →
  32            ∃∃K2. K1 ⪤[R,T] K2 & ⇩*[b,f] L2 ≘ K2.
  33
  34 definition f_dropable_dx:
  35            predicate (relation3 lenv term term) ≝ λR.
  36            ∀L1,L2,U. L1 ⪤[R,U] L2 →
  37            ∀b,f,K2. ⇩*[b,f] L2 ≘ K2 → 𝐔❪f❫ → ∀T. ⇧*[f] T ≘ U →
  38            ∃∃K1. ⇩*[b,f] L1 ≘ K1 & K1 ⪤[R,T] K2.
  39
  40 definition f_transitive_next:
  41            relation3 … ≝ λR1,R2,R3.
  42            ∀f,L,T. L ⊢ 𝐅+❪T❫ ≘ f →
  43            ∀g,I,K,i. ⇩[i] L ≘ K.ⓘ[I] → ↑g = ⫰*[i] f →
  44            R_pw_transitive_sex (cext2 R1) (cext2 R2) (cext2 R3) (cext2 R1) cfull g K I.
  45
  46 definition f_confluent1_next: relation2 … ≝ λR1,R2.
  47            ∀f,L,T. L ⊢ 𝐅+❪T❫ ≘ f →
  48            ∀g,I,K,i. ⇩[i] L ≘ K.ⓘ[I] → ↑g = ⫰*[i] f →
  49            R_pw_confluent1_sex (cext2 R1) (cext2 R1) (cext2 R2) cfull g K I.
  50
  51 (* Properties with generic slicing for local environments *******************)
  52
  53 lemma rex_liftable_dedropable_sn (R):
  54       (∀L. reflexive ? (R L)) →
  55       d_liftable2_sn … lifts R → f_dedropable_sn R.
  56 #R #H1R #H2R #b #f #L1 #K1 #HLK1 #K2 #T * #f1 #Hf1 #HK12 #U #HTU
  57 elim (frees_total L1 U) #f2 #Hf2
  58 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #Hf
  59 elim (sex_liftable_co_dedropable_sn … HLK1 … HK12 … Hf) -f1 -K1
  60 /3 width=6 by cext2_d_liftable2_sn, cfull_lift_sn, ext2_refl, ex3_intro, ex2_intro/
  61 qed-.
  62
  63 lemma rex_trans_next (R1) (R2) (R3):
  64       R_transitive_rex R1 R2 R3 → f_transitive_next R1 R2 R3.
  65 #R1 #R2 #R3 #HR #f #L1 #T #Hf #g #I1 #K1 #n #HLK #Hgf #I #H
  66 generalize in match HLK; -HLK elim H -I1 -I
  67 [ #I #_ #L2 #_ #I2 #H
  68   lapply (ext2_inv_unit_sn … H) -H #H destruct
  69   /2 width=1 by ext2_unit/
  70 | #I #V1 #V #HV1 #HLK1 #L2 #HL12 #I2 #H
  71   elim (ext2_inv_pair_sn … H) -H #V2 #HV2 #H destruct
  72   elim (frees_inv_drops_next … Hf … HLK1 … Hgf) -f -HLK1 #f #Hf #Hfg
  73   /5 width=5 by ext2_pair, sle_sex_trans, ex2_intro/
  74 ]
  75 qed.
  76
  77 lemma rex_conf1_next (R1) (R2):
  78       R_confluent1_rex R1 R2 → f_confluent1_next R1 R2.
  79 #R1 #R2 #HR #f #L1 #T #Hf #g #I1 #K1 #n #HLK #Hgf #I #H
  80 generalize in match HLK; -HLK elim H -I1 -I
  81 [ /2 width=1 by ext2_unit/
  82 | #I #V1 #V2 #HV12 #HLK1 #K2 #HK12
  83   elim (frees_inv_drops_next … Hf … HLK1 … Hgf) -f -HLK1 #f #Hf #Hfg
  84   /5 width=5 by ext2_pair, sle_sex_trans, ex2_intro/
  85 ]
  86 qed.
  87
  88 (* Inversion lemmas with generic slicing for local environments *************)
  89
  90 (* Basic_2A1: uses: llpx_sn_inv_lift_le llpx_sn_inv_lift_be llpx_sn_inv_lift_ge *)
  91 (* Basic_2A1: was: llpx_sn_drop_conf_O *)
  92 lemma rex_dropable_sn (R):
  93       f_dropable_sn R.
  94 #R #b #f #L1 #K1 #HLK1 #H1f #L2 #U * #f2 #Hf2 #HL12 #T #HTU
  95 elim (frees_total K1 T) #f1 #Hf1
  96 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #H2f
  97 elim (sex_co_dropable_sn … HLK1 … HL12 … H2f) -f2 -L1
  98 /3 width=3 by ex2_intro/
  99 qed-.
 100
 101 (* Basic_2A1: was: llpx_sn_drop_trans_O *)
 102 (* Note: the proof might be simplified *)
 103 lemma rex_dropable_dx (R):
 104       f_dropable_dx R.
 105 #R #L1 #L2 #U * #f2 #Hf2 #HL12 #b #f #K2 #HLK2 #H1f #T #HTU
 106 elim (drops_isuni_ex … H1f L1) #K1 #HLK1
 107 elim (frees_total K1 T) #f1 #Hf1
 108 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -K1 #H2f
 109 elim (sex_co_dropable_dx … HL12 … HLK2 … H2f) -L2
 110 /4 width=9 by frees_inv_lifts, ex2_intro/
 111 qed-.
 112
 113 (* Basic_2A1: uses: llpx_sn_inv_lift_O *)
 114 lemma rex_inv_lifts_bi (R):
 115       ∀L1,L2,U. L1 ⪤[R,U] L2 → ∀b,f. 𝐔❪f❫ →
 116       ∀K1,K2. ⇩*[b,f] L1 ≘ K1 → ⇩*[b,f] L2 ≘ K2 →
 117       ∀T. ⇧*[f] T ≘ U → K1 ⪤[R,T] K2.
 118 #R #L1 #L2 #U #HL12 #b #f #Hf #K1 #K2 #HLK1 #HLK2 #T #HTU
 119 elim (rex_dropable_sn … HLK1 … HL12 … HTU) -L1 -U // #Y #HK12 #HY
 120 lapply (drops_mono … HY … HLK2) -b -f -L2 #H destruct //
 121 qed-.
 122
 123 lemma rex_inv_lref_pair_sn (R):
 124       ∀L1,L2,i. L1 ⪤[R,#i] L2 → ∀I,K1,V1. ⇩[i] L1 ≘ K1.ⓑ[I]V1 →
 125       ∃∃K2,V2. ⇩[i] L2 ≘ K2.ⓑ[I]V2 & K1 ⪤[R,V1] K2 & R K1 V1 V2.
 126 #R #L1 #L2 #i #HL12 #I #K1 #V1 #HLK1 elim (rex_dropable_sn … HLK1 … HL12 (#0)) -HLK1 -HL12 //
 127 #Y #HY #HLK2 elim (rex_inv_zero_pair_sn … HY) -HY
 128 #K2 #V2 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
 129 qed-.
 130
 131 lemma rex_inv_lref_pair_dx (R):
 132       ∀L1,L2,i. L1 ⪤[R,#i] L2 → ∀I,K2,V2. ⇩[i] L2 ≘ K2.ⓑ[I]V2 →
 133       ∃∃K1,V1. ⇩[i] L1 ≘ K1.ⓑ[I]V1 & K1 ⪤[R,V1] K2 & R K1 V1 V2.
 134 #R #L1 #L2 #i #HL12 #I #K2 #V2 #HLK2 elim (rex_dropable_dx … HL12 … HLK2 … (#0)) -HLK2 -HL12 //
 135 #Y #HLK1 #HY elim (rex_inv_zero_pair_dx … HY) -HY
 136 #K1 #V1 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
 137 qed-.
 138
 139 lemma rex_inv_lref_pair_bi (R) (L1) (L2) (i):
 140       L1 ⪤[R,#i] L2 →
 141       ∀I1,K1,V1. ⇩[i] L1 ≘ K1.ⓑ[I1]V1 →
 142       ∀I2,K2,V2. ⇩[i] L2 ≘ K2.ⓑ[I2]V2 →
 143       ∧∧ K1 ⪤[R,V1] K2 & R K1 V1 V2 & I1 = I2.
 144 #R #L1 #L2 #i #H12 #I1 #K1 #V1 #H1 #I2 #K2 #V2 #H2
 145 elim (rex_inv_lref_pair_sn … H12 … H1) -L1 #Y2 #X2 #HLY2 #HK12 #HV12
 146 lapply (drops_mono … HLY2 … H2) -HLY2 -H2 #H destruct
 147 /2 width=1 by and3_intro/
 148 qed-.
 149
 150 lemma rex_inv_lref_unit_sn (R):
 151       ∀L1,L2,i. L1 ⪤[R,#i] L2 → ∀I,K1. ⇩[i] L1 ≘ K1.ⓤ[I] →
 152       ∃∃f,K2. ⇩[i] L2 ≘ K2.ⓤ[I] & K1 ⪤[cext2 R,cfull,f] K2 & 𝐈❪f❫.
 153 #R #L1 #L2 #i #HL12 #I #K1 #HLK1 elim (rex_dropable_sn … HLK1 … HL12 (#0)) -HLK1 -HL12 //
 154 #Y #HY #HLK2 elim (rex_inv_zero_unit_sn … HY) -HY
 155 #f #K2 #Hf #HK12 #H destruct /2 width=5 by ex3_2_intro/
 156 qed-.
 157
 158 lemma rex_inv_lref_unit_dx (R):
 159       ∀L1,L2,i. L1 ⪤[R,#i] L2 → ∀I,K2. ⇩[i] L2 ≘ K2.ⓤ[I] →
 160       ∃∃f,K1. ⇩[i] L1 ≘ K1.ⓤ[I] & K1 ⪤[cext2 R,cfull,f] K2 & 𝐈❪f❫.
 161 #R #L1 #L2 #i #HL12 #I #K2 #HLK2 elim (rex_dropable_dx … HL12 … HLK2 … (#0)) -HLK2 -HL12 //
 162 #Y #HLK1 #HY elim (rex_inv_zero_unit_dx … HY) -HY
 163 #f #K2 #Hf #HK12 #H destruct /2 width=5 by ex3_2_intro/
 164 qed-.