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 lemma nta_pure_cnv (h) (G) (L):
  35       ∀T,U. ⦃G,L⦄ ⊢ T :*[h] U →
  36       ∀V. ⦃G,L⦄ ⊢ ⓐV.U !*[h] → ⦃G,L⦄ ⊢ ⓐV.T :*[h] ⓐV.U.
  37 #h #G #L #T #U #H1 #V #H2
  38 elim (cnv_inv_cast … H1) -H1 #X0 #HU #HT #HUX0 #HTX0
  39 elim (cnv_inv_appl … H2) #n #p #X1 #X2 #_ #HV #_ #HVX1 #HUX2
  40 elim (cnv_cpms_conf … HU … HUX0 … HUX2) -HU -HUX2
  41 <minus_O_n <minus_n_O #X #HX0 #H
  42 elim (cpms_inv_abst_sn … H) -H #X3 #X4 #HX13 #HX24 #H destruct
  43 @(cnv_cast … (ⓐV.X0)) [2:|*: /2 width=1 by cpms_appl_dx/ ]
  44 @(cnv_appl … X3) [4: |*: /2 width=7 by cpms_trans, cpms_cprs_trans/ ]
  45 #H destruct
  46 qed.
  47
  48 (* Inversion lemmas based on preservation ***********************************)
  49
  50 lemma nta_inv_bind_sn_cnv (a) (h) (p) (I) (G) (K) (X2):
  51       ∀V,T. ⦃G,K⦄ ⊢ ⓑ{p,I}V.T :[a,h] X2 →
  52       ∃∃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].
  53 #a #h #p * #G #K #X2 #V #T #H
  54 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
  55 elim (cnv_inv_bind … H1) -H1 #HV #HT
  56 [ elim (cpms_inv_abbr_sn_dx … H2) -H2 *
  57   [ #V0 #U #HV0 #HTU #H destruct
  58     /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
  59   | #U #HTU #HX1U #H destruct
  60     /4 width=5 by cnv_cpms_nta, cprs_div, cpms_zeta, ex4_intro/
  61   ]
  62 | elim (cpms_inv_abst_sn … H2) -H2 #V0 #U #HV0 #HTU #H destruct
  63   /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
  64 ]
  65 qed-.
  66
  67 (* Basic_1: uses: ty3_gen_appl *)
  68 lemma nta_inv_appl_sn (h) (G) (L) (X2):
  69       ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h] X2 →
  70       ∃∃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].
  71 #h #G #L #X2 #V #T #H
  72 elim (cnv_inv_cast … H) -H #X #HX2 #H1 #HX2 #H2
  73 elim (cnv_inv_appl … H1) * [ | #n ] #p #W #U #Hn #HV #HT #HVW #HTU
  74 [ lapply (cnv_cpms_trans … HT … HTU) #H
  75   elim (cnv_inv_bind … H) -H #_ #HU
  76   elim (cnv_fwd_cpm_SO … HU) #U0 #HU0 -HU
  77   lapply (cpms_step_dx … HTU 1 (ⓛ{p}W.U0) ?) -HTU [ /2 width=1 by cpm_bind/ ] #HTU
  78 | lapply (le_n_O_to_eq n ?) [ /3 width=1 by le_S_S_to_le/ ] -Hn #H destruct
  79 ]
  80 lapply (cpms_appl_dx … V V … HTU) [1,3: // ] #HVTU
  81 elim (cnv_cpms_conf … H1 … H2 … HVTU) -H1 -H2 -HVTU <minus_n_n #X0 #HX0 #HUX0
  82 @ex4_3_intro [6,13: |*: /2 width=5 by cnv_cpms_nta/ ]
  83 /3 width=5 by cprs_div, cprs_trans/
  84 qed-.
  85
  86 (* Basic_2A1: uses: nta_inv_cast1 *)
  87 lemma nta_inv_cast_sn (a) (h) (G) (L) (X2):
  88       ∀U,T. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] X2 →
  89       ∧∧ ⦃G,L⦄ ⊢ T :[a,h] U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
  90 #a #h #G #L #X2 #U #T #H
  91 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
  92 elim (cnv_inv_cast … H1) #X #HU #HT #HUX #HTX
  93 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
  94 [ #U0 #T0 #HU0 #HT0 #H destruct -HU -HU0
  95   elim (cnv_cpms_conf … HT … HTX … HT0) -HT -HTX -HT0
  96   <minus_n_n #T1 #HXT1 #HT01
  97   @and3_intro // @(cprs_div … T1) /3 width=4 by cprs_trans, cpms_eps/ (**) (* full auto too slow *)
  98 | #HTX0 -HU
  99   elim (cnv_cpms_conf … HT … HTX … HTX0) -HT -HTX -HTX0
 100   <minus_n_n #T1 #HXT1 #HXT01
 101   @and3_intro // @(cprs_div … T1) /2 width=3 by cprs_trans/ (**) (* full auto too slow *)
 102 | #m #HUX0 #H destruct -HT -HTX
 103   elim (cnv_cpms_conf … HU … HUX … HUX0) -HU -HUX0
 104   <minus_n_n #U1 #HXU1 #HXU01
 105   @and3_intro // @(cprs_div … U1) /2 width=3 by cprs_trans/ (**) (* full auto too slow *)
 106 ]
 107 qed-.
 108
 109 (* Forward lemmas based on preservation *************************************)
 110
 111 (* Basic_1: was: ty3_unique *)
 112 theorem nta_mono (a) (h) (G) (L) (T):
 113         ∀U1. ⦃G,L⦄ ⊢ T :[a,h] U1 → ∀U2. ⦃G,L⦄ ⊢ T :[a,h] U2 → ⦃G,L⦄  ⊢ U1 ⬌*[h] U2.
 114 #a #h #G #L #T #U1 #H1 #U2 #H2
 115 elim (cnv_inv_cast … H1) -H1 #X1 #_ #_ #HUX1 #HTX1
 116 elim (cnv_inv_cast … H2) -H2 #X2 #_ #HT #HUX2 #HTX2
 117 elim (cnv_cpms_conf … HT … HTX1 … HTX2) -T <minus_n_n #X #HX1 #HX2
 118 /3 width=5 by cprs_div, cprs_trans/
 119 qed-.