matita/matita/contribs/lambdadelta/basic_2/dynamic/nta_preserve.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/rt_equivalence/cpcs_cprs.ma".
  16 include "basic_2/dynamic/cnv_preserve.ma".
  17 include "basic_2/dynamic/nta.ma".
  18
  19 (* NATIVE TYPE ASSIGNMENT FOR TERMS *****************************************)
  20
  21 (* Properties based on preservation *****************************************)
  22
  23 lemma cnv_cpms_nta (a) (h) (G) (L):
  24       ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∀U.⦃G,L⦄ ⊢ T ➡*[1,h] U → ⦃G,L⦄ ⊢ T :[a,h] U.
  25 /3 width=4 by cnv_cast, cnv_cpms_trans/ qed.
  26
  27 lemma cnv_nta_sn (a) (h) (G) (L):
  28       ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∃U. ⦃G,L⦄ ⊢ T :[a,h] U.
  29 #a #h #G #L #T #HT
  30 elim (cnv_fwd_cpm_SO … HT) #U #HTU
  31 /4 width=2 by cnv_cpms_nta, cpm_cpms, ex_intro/
  32 qed-.
  33
  34 (* Basic_1: was: ty3_typecheck *)
  35 lemma nta_typecheck (a) (h) (G) (L):
  36       ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] T0.
  37 /3 width=1 by cnv_cast, cnv_nta_sn/ qed-.
  38
  39 (* Basic_1: was: ty3_correct *)
  40 (* Basic_2A1: was: ntaa_fwd_correct *)
  41 lemma nta_fwd_correct (a) (h) (G) (L):
  42       ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ U :[a,h] T0.
  43 /3 width=2 by nta_fwd_cnv_dx, cnv_nta_sn/ qed-.
  44
  45 lemma nta_pure_cnv (h) (G) (L):
  46       ∀T,U. ⦃G,L⦄ ⊢ T :*[h] U →
  47       ∀V. ⦃G,L⦄ ⊢ ⓐV.U !*[h] → ⦃G,L⦄ ⊢ ⓐV.T :*[h] ⓐV.U.
  48 #h #G #L #T #U #H1 #V #H2
  49 elim (cnv_inv_cast … H1) -H1 #X0 #HU #HT #HUX0 #HTX0
  50 elim (cnv_inv_appl … H2) #n #p #X1 #X2 #_ #HV #_ #HVX1 #HUX2
  51 elim (cnv_cpms_conf … HU … HUX0 … HUX2) -HU -HUX2
  52 <minus_O_n <minus_n_O #X #HX0 #H
  53 elim (cpms_inv_abst_sn … H) -H #X3 #X4 #HX13 #HX24 #H destruct
  54 @(cnv_cast … (ⓐV.X0)) [2:|*: /2 width=1 by cpms_appl_dx/ ]
  55 @(cnv_appl … X3) [4: |*: /2 width=7 by cpms_trans, cpms_cprs_trans/ ]
  56 #H destruct
  57 qed.
  58
  59 (* Inversion lemmas based on preservation ***********************************)
  60
  61 lemma nta_inv_ldef_sn (a) (h) (G) (K) (V):
  62       ∀X2. ⦃G,K.ⓓV⦄ ⊢ #0 :[a,h] X2 →
  63       ∃∃W,U. ⦃G,K⦄ ⊢ V :[a,h] W & ⬆*[1] W ≘ U & ⦃G,K.ⓓV⦄ ⊢ U ⬌*[h] X2 & ⦃G,K.ⓓV⦄ ⊢ X2 ![a,h].
  64 #a #h #G #Y #X #X2 #H
  65 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
  66 elim (cnv_inv_zero … H1) -H1 #Z #K #V #HV #H destruct
  67 elim (cpms_inv_delta_sn … H2) -H2 *
  68 [ #_ #H destruct
  69 | #W #HVW #HWX1
  70   /3 width=5 by cnv_cpms_nta, cpcs_cprs_sn, ex4_2_intro/
  71 ]
  72 qed-.
  73
  74 lemma nta_inv_lref_sn (a) (h) (G) (L):
  75       ∀X2,i. ⦃G,L⦄ ⊢ #↑i :[a,h] X2 →
  76       ∃∃I,K,T2,U2. ⦃G,K⦄ ⊢ #i :[a,h] T2 & ⬆*[1] T2 ≘ U2 & ⦃G,K.ⓘ{I}⦄ ⊢ U2 ⬌*[h] X2 & ⦃G,K.ⓘ{I}⦄ ⊢ X2 ![a,h] & L = K.ⓘ{I}.
  77 #a #h #G #L #X2 #i #H
  78 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
  79 elim (cnv_inv_lref … H1) -H1 #I #K #Hi #H destruct
  80 elim (cpms_inv_lref_sn … H2) -H2 *
  81 [ #_ #H destruct
  82 | #X #HX #HX1
  83   /3 width=9 by cnv_cpms_nta, cpcs_cprs_sn, ex5_4_intro/
  84 ]
  85 qed-.
  86
  87 lemma nta_inv_lref_sn_drops_cnv (a) (h) (G) (L):
  88       ∀X2, i. ⦃G,L⦄ ⊢ #i :[a,h] X2 →
  89       ∨∨ ∃∃K,V,W,U. ⬇*[i] L ≘ K.ⓓV & ⦃G,K⦄ ⊢ V :[a,h] W & ⬆*[↑i] W ≘ U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h]
  90        | ∃∃K,W,U. ⬇*[i] L ≘ K. ⓛW & ⦃G,K⦄ ⊢ W ![a,h] & ⬆*[↑i] W ≘ U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
  91 #a #h #G #L #X2 #i #H
  92 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
  93 elim (cnv_inv_lref_drops … H1) -H1 #I #K #V #HLK #HV
  94 elim (cpms_inv_lref1_drops … H2) -H2 *
  95 [ #_ #H destruct
  96 | #Y #X #W #H #HVW #HUX1
  97   lapply (drops_mono … H … HLK) -H #H destruct
  98   /4 width=8 by cnv_cpms_nta, cpcs_cprs_sn, ex5_4_intro, or_introl/
  99 | #n #Y #X #U #H #HVU #HUX1 #H0 destruct
 100   lapply (drops_mono … H … HLK) -H #H destruct
 101   elim (lifts_total V (𝐔❴↑i❵)) #W #HVW
 102   lapply (cpms_lifts_bi … HVU (Ⓣ) … L … HVW … HUX1) -U
 103   [ /2 width=2 by drops_isuni_fwd_drop2/ ] #HWX1
 104   /4 width=9 by cprs_div, ex5_3_intro, or_intror/
 105 ]
 106 qed-.
 107
 108 lemma nta_inv_bind_sn_cnv (a) (h) (p) (I) (G) (K) (X2):
 109       ∀V,T. ⦃G,K⦄ ⊢ ⓑ{p,I}V.T :[a,h] X2 →
 110       ∃∃U. ⦃G,K⦄ ⊢ V ![a,h] & ⦃G,K.ⓑ{I}V⦄ ⊢ T :[a,h] U & ⦃G,K⦄ ⊢ ⓑ{p,I}V.U ⬌*[h] X2 & ⦃G,K⦄ ⊢ X2 ![a,h].
 111 #a #h #p * #G #K #X2 #V #T #H
 112 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
 113 elim (cnv_inv_bind … H1) -H1 #HV #HT
 114 [ elim (cpms_inv_abbr_sn_dx … H2) -H2 *
 115   [ #V0 #U #HV0 #HTU #H destruct
 116     /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
 117   | #U #HTU #HX1U #H destruct
 118     /4 width=5 by cnv_cpms_nta, cprs_div, cpms_zeta, ex4_intro/
 119   ]
 120 | elim (cpms_inv_abst_sn … H2) -H2 #V0 #U #HV0 #HTU #H destruct
 121   /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
 122 ]
 123 qed-.
 124
 125 (* Basic_1: uses: ty3_gen_appl *)
 126 lemma nta_inv_appl_sn (h) (G) (L) (X2):
 127       ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h] X2 →
 128       ∃∃p,W,U. ⦃G,L⦄ ⊢ V :[h] W & ⦃G,L⦄ ⊢ T :[h] ⓛ{p}W.U & ⦃G,L⦄ ⊢ ⓐV.ⓛ{p}W.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h].
 129 #h #G #L #X2 #V #T #H
 130 elim (cnv_inv_cast … H) -H #X #HX2 #H1 #HX2 #H2
 131 elim (cnv_inv_appl … H1) * [ | #n ] #p #W #U #Hn #HV #HT #HVW #HTU
 132 [ lapply (cnv_cpms_trans … HT … HTU) #H
 133   elim (cnv_inv_bind … H) -H #_ #HU
 134   elim (cnv_fwd_cpm_SO … HU) #U0 #HU0 -HU
 135   lapply (cpms_step_dx … HTU 1 (ⓛ{p}W.U0) ?) -HTU [ /2 width=1 by cpm_bind/ ] #HTU
 136 | lapply (le_n_O_to_eq n ?) [ /3 width=1 by le_S_S_to_le/ ] -Hn #H destruct
 137 ]
 138 lapply (cpms_appl_dx … V V … HTU) [1,3: // ] #HVTU
 139 elim (cnv_cpms_conf … H1 … H2 … HVTU) -H1 -H2 -HVTU <minus_n_n #X0 #HX0 #HUX0
 140 @ex4_3_intro [6,13: |*: /2 width=5 by cnv_cpms_nta/ ]
 141 /3 width=5 by cprs_div, cprs_trans/
 142 qed-.
 143 (*
 144  (ltc_ind
 145  :∀A: Type \sub 0
 146   .(A→A→A)
 147    →∀B: Type \sub 0
 148     .relation3 A B B
 149      →∀Q_:∀x_3:A.∀x_2:B.∀x_1:B.ltc A __6 B __4 x_3 x_2 x_1→Prop
 150       .(∀a:A
 151         .∀b1:B
 152          .∀b2:B.∀x_5:__5 a b1 b2.Q_ a b1 b2 (ltc_rc A __8 B __6 a b1 b2 x_5))
 153        →(∀a1:A
 154          .∀a2:A
 155           .∀b1:B
 156            .∀b:B
 157             .∀b2:B
 158              .∀x_7:ltc A __10 B __8 a1 b1 b
 159               .∀x_6:ltc A __11 B __9 a2 b b2
 160                .Q_ a1 b1 b x_7
 161                 →Q_ a2 b b2 x_6
 162                  →Q_ (__14 a1 a2) b1 b2
 163                   (ltc_trans A __14 B __12 a1 a2 b1 b b2 x_7 x_6))
 164         →∀x_3:A
 165          .∀x_2:B.∀x_1:B.∀x_4:ltc A __9 B __7 x_3 x_2 x_1.Q_ x_3 x_2 x_1 x_4)
 166
 167 lemma nta_inv_pure_sn_cnv (h) (G) (L) (X2):
 168                           ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :*[h] X2 →
 169                           ∨∨ ∃∃p,W,T0,U0. ⦃G,L⦄ ⊢ V :*[h] W & ⦃G,L⦄ ⊢ ⓛ{p}W.T0 :*[h] ⓛ{p}W.U0 & ⦃G,L⦄ ⊢ T ➡*[h] ⓛ{p}W.T0 & ⦃G,L⦄ ⊢ ⓐV.ⓛ{p}W.U0 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 !*[h]
 170                            | ∃∃U. ⦃G,L⦄ ⊢ T :*[h] U & ⦃G,L⦄ ⊢ ⓐV.U !*[h] & ⦃G,L⦄ ⊢ ⓐV.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 !*[h].
 171 #h #G #L #X2 #V #T #H
 172 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H
 173 elim (cnv_inv_appl … H1) -H1 * [| #n ] #p #W0 #T0 #_ #HV #HT #HW0 #HT0
 174 lapply (cnv_cpms_trans … HT … HT0) #H
 175 elim (cnv_inv_bind … H) -H #_ #H1T0
 176 [ elim (cpms_inv_appl_sn_decompose … H) -H #U #HTU #HUX1
 177
 178
 179   [ #V0 #U0 #HV0 #HU0 #H destruct
 180     elim (cnv_cpms_conf … HT … HT0 … HU0)
 181     <minus_O_n <minus_n_O #X #H #HU0X
 182     elim (cpms_inv_abst_sn … H) -H #W1 #U1 #HW01 #HU01 #H destruct
 183     @or_introl
 184     @(ex5_4_intro … U1 … HT0 … HX2) -HX2
 185     [ /2 width=1 by cnv_cpms_nta/
 186     | @nta_bind_cnv /2 width=4 by cnv_cpms_trans/ /2 width=3 by cnv_cpms_nta/
 187     | @(cpcs_cprs_div … HX21) -HX21
 188       @(cprs_div … (ⓐV0.ⓛ{p}W1.U1))
 189       /3 width=1 by cpms_appl, cpms_appl_dx, cpms_bind/
 190     ]
 191 *)
 192 (* Basic_2A1: uses: nta_inv_cast1 *)
 193 lemma nta_inv_cast_sn (a) (h) (G) (L) (X2):
 194       ∀U,T. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] X2 →
 195       ∧∧ ⦃G,L⦄ ⊢ T :[a,h] U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
 196 #a #h #G #L #X2 #U #T #H
 197 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
 198 elim (cnv_inv_cast … H1) #X #HU #HT #HUX #HTX
 199 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
 200 [ #U0 #T0 #HU0 #HT0 #H destruct -HU -HU0
 201   elim (cnv_cpms_conf … HT … HTX … HT0) -HT -HTX -HT0
 202   <minus_n_n #T1 #HXT1 #HT01
 203   @and3_intro // @(cprs_div … T1) /3 width=4 by cprs_trans, cpms_eps/ (**) (* full auto too slow *)
 204 | #HTX0 -HU
 205   elim (cnv_cpms_conf … HT … HTX … HTX0) -HT -HTX -HTX0
 206   <minus_n_n #T1 #HXT1 #HXT01
 207   @and3_intro // @(cprs_div … T1) /2 width=3 by cprs_trans/ (**) (* full auto too slow *)
 208 | #m #HUX0 #H destruct -HT -HTX
 209   elim (cnv_cpms_conf … HU … HUX … HUX0) -HU -HUX0
 210   <minus_n_n #U1 #HXU1 #HXU01
 211   @and3_intro // @(cprs_div … U1) /2 width=3 by cprs_trans/ (**) (* full auto too slow *)
 212 ]
 213 qed-.
 214
 215 (* Basic_1: uses: ty3_gen_cast *)
 216 lemma nta_inv_cast_sn_old (a) (h) (G) (L) (X2):
 217       ∀T0,T1. ⦃G,L⦄ ⊢ ⓝT1.T0 :[a,h] X2 →
 218       ∃∃T2. ⦃G,L⦄ ⊢ T0 :[a,h] T1 & ⦃G,L⦄ ⊢ T1 :[a,h] T2 & ⦃G,L⦄ ⊢ ⓝT2.T1 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
 219 #a #h #G #L #X2 #T0 #T1 #H
 220 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
 221 elim (cnv_inv_cast … H1) #X #HT1 #HT0 #HT1X #HT0X
 222 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
 223 [ #U1 #U0 #HTU1 #HTU0 #H destruct
 224   elim (cnv_cpms_conf … HT0 … HT0X … HTU0) -HT0 -HT0X -HTU0
 225   <minus_n_n #X0 #HX0 #HUX0
 226   lapply (cprs_trans … HT1X … HX0) -X #HT1X0
 227   /5 width=7 by cnv_cpms_nta, cpcs_cprs_div, cprs_div, cpms_cast, ex4_intro/
 228 | #HTX0
 229   elim (cnv_cpms_conf … HT0 … HT0X … HTX0) -HT0 -HT0X -HTX0
 230   <minus_n_n #X1 #HX1 #HX01
 231   elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
 232   lapply (cprs_trans … HT1X … HX1) -X #HTX1
 233   lapply (cprs_trans … HX20 … HX01) -X0 #HX21
 234   /4 width=5 by cprs_div, cpms_eps, ex4_intro/
 235 | #n #HT1X0 #H destruct -X -HT0
 236   elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
 237   /4 width=5 by cprs_div, cpms_eps, ex4_intro/
 238 ]
 239 qed-.
 240
 241 (* Forward lemmas based on preservation *************************************)
 242
 243 (* Basic_1: was: ty3_unique *)
 244 theorem nta_mono (a) (h) (G) (L) (T):
 245         ∀U1. ⦃G,L⦄ ⊢ T :[a,h] U1 → ∀U2. ⦃G,L⦄ ⊢ T :[a,h] U2 → ⦃G,L⦄  ⊢ U1 ⬌*[h] U2.
 246 #a #h #G #L #T #U1 #H1 #U2 #H2
 247 elim (cnv_inv_cast … H1) -H1 #X1 #_ #_ #HUX1 #HTX1
 248 elim (cnv_inv_cast … H2) -H2 #X2 #_ #HT #HUX2 #HTX2
 249 elim (cnv_cpms_conf … HT … HTX1 … HTX2) -T <minus_n_n #X #HX1 #HX2
 250 /3 width=5 by cprs_div, cprs_trans/
 251 qed-.