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 "ground_2/xoa/ex_5_3.ma".
  16 include "basic_2/rt_equivalence/cpcs_cpcs.ma".
  17 include "basic_2/dynamic/cnv_preserve_cpcs.ma".
  18 include "basic_2/dynamic/nta.ma".
  19
  20 (* NATIVE TYPE ASSIGNMENT FOR TERMS *****************************************)
  21
  22 (* Properties based on preservation *****************************************)
  23
  24 lemma cnv_cpms_nta (h) (a) (G) (L):
  25       ∀T. ❪G,L❫ ⊢ T ![h,a] → ∀U.❪G,L❫ ⊢ T ➡*[1,h] U → ❪G,L❫ ⊢ T :[h,a] U.
  26 /3 width=4 by cnv_cast, cnv_cpms_trans/ qed.
  27
  28 lemma cnv_nta_sn (h) (a) (G) (L):
  29       ∀T. ❪G,L❫ ⊢ T ![h,a] → ∃U. ❪G,L❫ ⊢ T :[h,a] U.
  30 #h #a #G #L #T #HT
  31 elim (cnv_fwd_cpm_SO … HT) #U #HTU
  32 /4 width=2 by cnv_cpms_nta, cpm_cpms, ex_intro/
  33 qed-.
  34
  35 (* Basic_1: was: ty3_typecheck *)
  36 lemma nta_typecheck (h) (a) (G) (L):
  37       ∀T,U. ❪G,L❫ ⊢ T :[h,a] U → ∃T0. ❪G,L❫ ⊢ ⓝU.T :[h,a] T0.
  38 /3 width=1 by cnv_cast, cnv_nta_sn/ qed-.
  39
  40 (* Basic_1: was: ty3_correct *)
  41 (* Basic_2A1: was: ntaa_fwd_correct *)
  42 lemma nta_fwd_correct (h) (a) (G) (L):
  43       ∀T,U. ❪G,L❫ ⊢ T :[h,a] U → ∃T0. ❪G,L❫ ⊢ U :[h,a] T0.
  44 /3 width=2 by nta_fwd_cnv_dx, cnv_nta_sn/ qed-.
  45
  46 lemma nta_pure_cnv (h) (G) (L):
  47       ∀T,U. ❪G,L❫ ⊢ T :[h,𝛚] U →
  48       ∀V. ❪G,L❫ ⊢ ⓐV.U ![h,𝛚] → ❪G,L❫ ⊢ ⓐV.T :[h,𝛚] ⓐV.U.
  49 #h #G #L #T #U #H1 #V #H2
  50 elim (cnv_inv_cast … H1) -H1 #X0 #HU #HT #HUX0 #HTX0
  51 elim (cnv_inv_appl … H2) #n #p #X1 #X2 #_ #HV #_ #HVX1 #HUX2
  52 elim (cnv_cpms_conf … HU … HUX0 … HUX2) -HU -HUX2
  53 <minus_O_n <minus_n_O #X #HX0 #H
  54 elim (cpms_inv_abst_sn … H) -H #X3 #X4 #HX13 #HX24 #H destruct
  55 @(cnv_cast … (ⓐV.X0)) [2:|*: /2 width=1 by cpms_appl_dx/ ] (**) (* full auto a bit slow *)
  56 /3 width=10 by cnv_appl, cpms_trans, cpms_cprs_trans/
  57 qed.
  58
  59 (* Basic_1: uses: ty3_sred_wcpr0_pr0 *)
  60 lemma nta_cpr_conf_lpr (h) (a) (G):
  61       ∀L1,T1,U. ❪G,L1❫ ⊢ T1 :[h,a] U → ∀T2. ❪G,L1❫ ⊢ T1 ➡[h] T2 →
  62       ∀L2. ❪G,L1❫ ⊢ ➡[h] L2 → ❪G,L2❫ ⊢ T2 :[h,a] U.
  63 #h #a #G #L1 #T1 #U #H #T2 #HT12 #L2 #HL12
  64 /3 width=6 by cnv_cpm_trans_lpr, cpm_cast/
  65 qed-.
  66
  67 (* Basic_1: uses: ty3_sred_pr2 ty3_sred_pr0 *)
  68 lemma nta_cpr_conf (h) (a) (G) (L):
  69       ∀T1,U. ❪G,L❫ ⊢ T1 :[h,a] U →
  70       ∀T2. ❪G,L❫ ⊢ T1 ➡[h] T2 → ❪G,L❫ ⊢ T2 :[h,a] U.
  71 #h #a #G #L #T1 #U #H #T2 #HT12
  72 /3 width=6 by cnv_cpm_trans, cpm_cast/
  73 qed-.
  74
  75 (* Note: this is the preservation property *)
  76 (* Basic_1: uses: ty3_sred_pr3 ty3_sred_pr1 *)
  77 lemma nta_cprs_conf (h) (a) (G) (L):
  78       ∀T1,U. ❪G,L❫ ⊢ T1 :[h,a] U →
  79       ∀T2. ❪G,L❫ ⊢ T1 ➡*[h] T2 → ❪G,L❫ ⊢ T2 :[h,a] U.
  80 #h #a #G #L #T1 #U #H #T2 #HT12
  81 /3 width=6 by cnv_cpms_trans, cpms_cast/
  82 qed-.
  83
  84 (* Basic_1: uses: ty3_cred_pr2 *)
  85 lemma nta_lpr_conf (h) (a) (G):
  86       ∀L1,T,U. ❪G,L1❫ ⊢ T :[h,a] U →
  87       ∀L2. ❪G,L1❫ ⊢ ➡[h] L2 → ❪G,L2❫ ⊢ T :[h,a] U.
  88 #h #a #G #L1 #T #U #HTU #L2 #HL12
  89 /2 width=3 by cnv_lpr_trans/
  90 qed-.
  91
  92 (* Basic_1: uses: ty3_cred_pr3 *)
  93 lemma nta_lprs_conf (h) (a) (G):
  94       ∀L1,T,U. ❪G,L1❫ ⊢ T :[h,a] U →
  95       ∀L2. ❪G,L1❫ ⊢ ➡*[h] L2 → ❪G,L2❫ ⊢ T :[h,a] U.
  96 #h #a #G #L1 #T #U #HTU #L2 #HL12
  97 /2 width=3 by cnv_lprs_trans/
  98 qed-.
  99
 100 (* Inversion lemmas based on preservation ***********************************)
 101
 102 lemma nta_inv_ldef_sn (h) (a) (G) (K) (V):
 103       ∀X2. ❪G,K.ⓓV❫ ⊢ #0 :[h,a] X2 →
 104       ∃∃W,U. ❪G,K❫ ⊢ V :[h,a] W & ⇧*[1] W ≘ U & ❪G,K.ⓓV❫ ⊢ U ⬌*[h] X2 & ❪G,K.ⓓV❫ ⊢ X2 ![h,a].
 105 #h #a #G #Y #X #X2 #H
 106 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
 107 elim (cnv_inv_zero … H1) -H1 #Z #K #V #HV #H destruct
 108 elim (cpms_inv_delta_sn … H2) -H2 *
 109 [ #_ #H destruct
 110 | #W #HVW #HWX1
 111   /3 width=5 by cnv_cpms_nta, cpcs_cprs_sn, ex4_2_intro/
 112 ]
 113 qed-.
 114
 115 lemma nta_inv_lref_sn (h) (a) (G) (L):
 116       ∀X2,i. ❪G,L❫ ⊢ #↑i :[h,a] X2 →
 117       ∃∃I,K,T2,U2. ❪G,K❫ ⊢ #i :[h,a] T2 & ⇧*[1] T2 ≘ U2 & ❪G,K.ⓘ[I]❫ ⊢ U2 ⬌*[h] X2 & ❪G,K.ⓘ[I]❫ ⊢ X2 ![h,a] & L = K.ⓘ[I].
 118 #h #a #G #L #X2 #i #H
 119 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
 120 elim (cnv_inv_lref … H1) -H1 #I #K #Hi #H destruct
 121 elim (cpms_inv_lref_sn … H2) -H2 *
 122 [ #_ #H destruct
 123 | #X #HX #HX1
 124   /3 width=9 by cnv_cpms_nta, cpcs_cprs_sn, ex5_4_intro/
 125 ]
 126 qed-.
 127
 128 lemma nta_inv_lref_sn_drops_cnv (h) (a) (G) (L):
 129       ∀X2,i. ❪G,L❫ ⊢ #i :[h,a] X2 →
 130       ∨∨ ∃∃K,V,W,U. ⇩*[i] L ≘ K.ⓓV & ❪G,K❫ ⊢ V :[h,a] W & ⇧*[↑i] W ≘ U & ❪G,L❫ ⊢ U ⬌*[h] X2 & ❪G,L❫ ⊢ X2 ![h,a]
 131        | ∃∃K,W,U. ⇩*[i] L ≘ K. ⓛW & ❪G,K❫ ⊢ W ![h,a] & ⇧*[↑i] W ≘ U & ❪G,L❫ ⊢ U ⬌*[h] X2 & ❪G,L❫ ⊢ X2 ![h,a].
 132 #h #a #G #L #X2 #i #H
 133 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
 134 elim (cnv_inv_lref_drops … H1) -H1 #I #K #V #HLK #HV
 135 elim (cpms_inv_lref1_drops … H2) -H2 *
 136 [ #_ #H destruct
 137 | #Y #X #W #H #HVW #HUX1
 138   lapply (drops_mono … H … HLK) -H #H destruct
 139   /4 width=8 by cnv_cpms_nta, cpcs_cprs_sn, ex5_4_intro, or_introl/
 140 | #n #Y #X #U #H #HVU #HUX1 #H0 destruct
 141   lapply (drops_mono … H … HLK) -H #H destruct
 142   elim (lifts_total V (𝐔❨↑i❩)) #W #HVW
 143   lapply (cpms_lifts_bi … HVU (Ⓣ) … L … HVW … HUX1) -U
 144   [ /2 width=2 by drops_isuni_fwd_drop2/ ] #HWX1
 145   /4 width=9 by cprs_div, ex5_3_intro, or_intror/
 146 ]
 147 qed-.
 148
 149 lemma nta_inv_bind_sn_cnv (h) (a) (p) (I) (G) (K) (X2):
 150       ∀V,T. ❪G,K❫ ⊢ ⓑ[p,I]V.T :[h,a] X2 →
 151       ∃∃U. ❪G,K❫ ⊢ V ![h,a] & ❪G,K.ⓑ[I]V❫ ⊢ T :[h,a] U & ❪G,K❫ ⊢ ⓑ[p,I]V.U ⬌*[h] X2 & ❪G,K❫ ⊢ X2 ![h,a].
 152 #h #a #p * #G #K #X2 #V #T #H
 153 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
 154 elim (cnv_inv_bind … H1) -H1 #HV #HT
 155 [ elim (cpms_inv_abbr_sn_dx … H2) -H2 *
 156   [ #V0 #U #HV0 #HTU #H destruct
 157     /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
 158   | #U #HTU #HX1U #H destruct
 159     /4 width=5 by cnv_cpms_nta, cprs_div, cpms_zeta, ex4_intro/
 160   ]
 161 | elim (cpms_inv_abst_sn … H2) -H2 #V0 #U #HV0 #HTU #H destruct
 162   /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
 163 ]
 164 qed-.
 165
 166 (* Basic_1: uses: ty3_gen_appl *)
 167 lemma nta_inv_appl_sn (h) (G) (L) (X2):
 168       ∀V,T. ❪G,L❫ ⊢ ⓐV.T :[h,𝟐] X2 →
 169       ∃∃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,𝟐].
 170 #h #G #L #X2 #V #T #H
 171 elim (cnv_inv_cast … H) -H #X #HX2 #H1 #HX2 #H2
 172 elim (cnv_inv_appl … H1) #n #p #W #U #H <H -n #HV #HT #HVW #HTU
 173 /5 width=11 by cnv_cpms_nta, cnv_cpms_conf_eq, cpcs_cprs_div, cpms_appl_dx, ex4_3_intro/
 174 qed-.
 175
 176 (* Basic_2A1: uses: nta_fwd_pure1 *)
 177 lemma nta_inv_pure_sn_cnv (h) (G) (L) (X2):
 178       ∀V,T. ❪G,L❫ ⊢ ⓐV.T :[h,𝛚] X2 →
 179       ∨∨ ∃∃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,𝛚]
 180        | ∃∃U. ❪G,L❫ ⊢ T :[h,𝛚] U & ❪G,L❫ ⊢ ⓐV.U ![h,𝛚] & ❪G,L❫ ⊢ ⓐV.U ⬌*[h] X2 & ❪G,L❫ ⊢ X2 ![h,𝛚].
 181 #h #G #L #X2 #V #T #H
 182 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H
 183 elim (cnv_inv_appl … H1) * [| #n ] #p #W0 #T0 #Hn #HV #HT #HW0 #HT0
 184 [ lapply (cnv_cpms_trans … HT … HT0) #H0
 185   elim (cnv_inv_bind … H0) -H0 #_ #HU
 186   elim (cnv_fwd_cpm_SO … HU) #U0 #HU0 -HU
 187   lapply (cpms_step_dx … HT0 1 (ⓛ[p]W0.U0) ?) -HT0 [ /2 width=1 by cpm_bind/ ] #HT0
 188   lapply (cpms_appl_dx … V V … HT0) [ // ] #HTU0
 189   lapply (cnv_cpms_conf_eq … H1 … HTU0 … H) -H1 -H -HTU0 #HU0X1
 190   /4 width=8 by cnv_cpms_nta, cpcs_cprs_div, ex4_3_intro, or_introl/
 191 | elim (cnv_cpms_fwd_appl_sn_decompose …  H1 … H) -H1 -H #X0 #_ #H #HX01
 192   elim (cpms_inv_plus … 1 n … HT0) #U #HTU #HUT0
 193   lapply (cnv_cpms_trans … HT … HTU) #HU
 194   lapply (cnv_cpms_conf_eq … HT … HTU … H) -H #HUX0
 195   @or_intror @(ex4_intro … U … HX2) -HX2
 196   [ /2 width=1 by cnv_cpms_nta/
 197   | /4 width=7 by cnv_appl, lt_to_le/
 198   | /4 width=3 by cpcs_trans, cpcs_cprs_div, cpcs_flat/
 199   ]
 200 ]
 201 qed-.
 202
 203 (* Basic_2A1: uses: nta_inv_cast1 *)
 204 lemma nta_inv_cast_sn (h) (a) (G) (L) (X2):
 205       ∀U,T. ❪G,L❫ ⊢ ⓝU.T :[h,a] X2 →
 206       ∧∧ ❪G,L❫ ⊢ T :[h,a] U & ❪G,L❫ ⊢ U ⬌*[h] X2 & ❪G,L❫ ⊢ X2 ![h,a].
 207 #h #a #G #L #X2 #U #T #H
 208 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
 209 elim (cnv_inv_cast … H1) #X #HU #HT #HUX #HTX
 210 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
 211 [ #U0 #T0 #HU0 #HT0 #H destruct -HU -HU0
 212   lapply (cnv_cpms_conf_eq … HT … HTX … HT0) -HT -HT0 -HTX #HXT0
 213   lapply (cprs_step_dx … HX20 T0 ?) -HX20 [ /2 width=1 by cpm_eps/ ] #HX20
 214 | #HTX0 -HU
 215   lapply (cnv_cpms_conf_eq … HT … HTX … HTX0) -HT -HTX -HTX0 #HX0
 216 | #m #HUX0 #H destruct -HT -HTX
 217   lapply (cnv_cpms_conf_eq … HU … HUX … HUX0) -HU -HUX0 #HX0
 218 ]
 219 /4 width=3 by cpcs_cprs_div, cpcs_cprs_step_sn, and3_intro/
 220 qed-.
 221
 222 (* Basic_1: uses: ty3_gen_cast *)
 223 lemma nta_inv_cast_sn_old (h) (a) (G) (L) (X2):
 224       ∀T0,T1. ❪G,L❫ ⊢ ⓝT1.T0 :[h,a] X2 →
 225       ∃∃T2. ❪G,L❫ ⊢ T0 :[h,a] T1 & ❪G,L❫ ⊢ T1 :[h,a] T2 & ❪G,L❫ ⊢ ⓝT2.T1 ⬌*[h] X2 & ❪G,L❫ ⊢ X2 ![h,a].
 226 #h #a #G #L #X2 #T0 #T1 #H
 227 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
 228 elim (cnv_inv_cast … H1) #X #HT1 #HT0 #HT1X #HT0X
 229 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
 230 [ #U1 #U0 #HTU1 #HTU0 #H destruct
 231   lapply (cnv_cpms_conf_eq … HT0 … HT0X … HTU0) -HT0 -HT0X -HTU0 #HXU0
 232   /5 width=5 by cnv_cpms_nta, cpcs_cprs_div, cpcs_cprs_step_sn, cpcs_flat, ex4_intro/
 233 | #HTX0
 234   elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
 235   lapply (cnv_cpms_conf_eq … HT0 … HT0X … HTX0) -HT0 -HT0X -HTX0 #HX0
 236   lapply (cprs_step_sn … (ⓝU1.T1) … HT1X) -HT1X [ /2 width=1 by cpm_eps/ ] #HT1X
 237   /4 width=5 by cpcs_cprs_div, cpcs_cprs_step_sn, ex4_intro/
 238 | #n #HT1X0 #H destruct -X -HT0
 239   elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
 240   /4 width=5 by cprs_div, cpms_eps, ex4_intro/
 241 ]
 242 qed-.
 243
 244 (* Basic_1: uses: ty3_gen_lift *)
 245 (* Note: "❪G, L❫ ⊢ U2 ⬌*[h] X2" can be "❪G, L❫ ⊢ X2 ➡*[h] U2" *)
 246 lemma nta_inv_lifts_sn (h) (a) (G):
 247       ∀L,T2,X2. ❪G,L❫ ⊢ T2 :[h,a] X2 →
 248       ∀b,f,K. ⇩*[b,f] L ≘ K → ∀T1. ⇧*[f] T1 ≘ T2 →
 249       ∃∃U1,U2. ❪G,K❫ ⊢ T1 :[h,a] U1 & ⇧*[f] U1 ≘ U2 & ❪G,L❫ ⊢ U2 ⬌*[h] X2 & ❪G,L❫ ⊢ X2 ![h,a].
 250 #h #a #G #L #T2 #X2 #H #b #f #K #HLK #T1 #HT12
 251 elim (cnv_inv_cast … H) -H #U2 #HX2 #HT2 #HXU2 #HTU2
 252 lapply (cnv_inv_lifts … HT2 … HLK … HT12) -HT2 #HT1
 253 elim (cpms_inv_lifts_sn … HTU2 … HLK … HT12) -T2 -HLK #U1 #HU12 #HTU1
 254 /3 width=5 by cnv_cpms_nta, cpcs_cprs_sn, ex4_2_intro/
 255 qed-.
 256
 257 (* Forward lemmas based on preservation *************************************)
 258
 259 (* Basic_1: was: ty3_unique *)
 260 theorem nta_mono (h) (a) (G) (L) (T):
 261         ∀U1. ❪G,L❫ ⊢ T :[h,a] U1 → ∀U2. ❪G,L❫ ⊢ T :[h,a] U2 → ❪G,L❫  ⊢ U1 ⬌*[h] U2.
 262 #h #a #G #L #T #U1 #H1 #U2 #H2
 263 elim (cnv_inv_cast … H1) -H1 #X1 #_ #_ #HUX1 #HTX1
 264 elim (cnv_inv_cast … H2) -H2 #X2 #_ #HT #HUX2 #HTX2
 265 lapply (cnv_cpms_conf_eq … HT … HTX1 … HTX2) -T #HX12
 266 /3 width=3 by cpcs_cprs_div, cpcs_cprs_step_sn/
 267 qed-.
 268
 269 (* Advanced properties ******************************************************)
 270
 271 (* Basic_1: uses: ty3_sconv_pc3 *)
 272 lemma nta_cpcs_bi (h) (a) (G) (L):
 273       ∀T1,U1. ❪G,L❫ ⊢ T1 :[h,a] U1 → ∀T2,U2. ❪G,L❫ ⊢ T2 :[h,a] U2 →
 274       ❪G,L❫ ⊢ T1 ⬌*[h] T2 → ❪G,L❫ ⊢ U1 ⬌*[h] U2.
 275 #h #a #G #L #T1 #U1 #HTU1 #T2 #U2 #HTU2 #HT12
 276 elim (cpcs_inv_cprs … HT12) -HT12 #T0 #HT10 #HT02
 277 /3 width=6 by nta_mono, nta_cprs_conf/
 278 qed-.