X-Git-Url: http://matita.cs.unibo.it/gitweb/?p=helm.git;a=blobdiff_plain;f=matita%2Fmatita%2Fcontribs%2Flambdadelta%2Fbasic_2%2Fdynamic%2Fnta_preserve.ma;h=eb8d953a23c649d61bc13a90853971f41297036e;hp=6de11fe1620e2e1a6bc251ebf708355b8fd54546;hb=bd53c4e895203eb049e75434f638f26b5a161a2b;hpb=3b7b8afcb429a60d716d5226a5b6ab0d003228b1 diff --git a/matita/matita/contribs/lambdadelta/basic_2/dynamic/nta_preserve.ma b/matita/matita/contribs/lambdadelta/basic_2/dynamic/nta_preserve.ma index 6de11fe16..eb8d953a2 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/dynamic/nta_preserve.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/dynamic/nta_preserve.ma @@ -22,11 +22,11 @@ include "basic_2/dynamic/nta.ma". (* Properties based on preservation *****************************************) lemma cnv_cpms_nta (h) (a) (G) (L): - ∀T. ⦃G,L⦄ ⊢ T ![h,a] → ∀U.⦃G,L⦄ ⊢ T ➡*[1,h] U → ⦃G,L⦄ ⊢ T :[h,a] U. + ∀T. ❪G,L❫ ⊢ T ![h,a] → ∀U.❪G,L❫ ⊢ T ➡*[1,h] U → ❪G,L❫ ⊢ T :[h,a] U. /3 width=4 by cnv_cast, cnv_cpms_trans/ qed. lemma cnv_nta_sn (h) (a) (G) (L): - ∀T. ⦃G,L⦄ ⊢ T ![h,a] → ∃U. ⦃G,L⦄ ⊢ T :[h,a] U. + ∀T. ❪G,L❫ ⊢ T ![h,a] → ∃U. ❪G,L❫ ⊢ T :[h,a] U. #h #a #G #L #T #HT elim (cnv_fwd_cpm_SO … HT) #U #HTU /4 width=2 by cnv_cpms_nta, cpm_cpms, ex_intro/ @@ -34,18 +34,18 @@ qed-. (* Basic_1: was: ty3_typecheck *) lemma nta_typecheck (h) (a) (G) (L): - ∀T,U. ⦃G,L⦄ ⊢ T :[h,a] U → ∃T0. ⦃G,L⦄ ⊢ ⓝU.T :[h,a] T0. + ∀T,U. ❪G,L❫ ⊢ T :[h,a] U → ∃T0. ❪G,L❫ ⊢ ⓝU.T :[h,a] T0. /3 width=1 by cnv_cast, cnv_nta_sn/ qed-. (* Basic_1: was: ty3_correct *) (* Basic_2A1: was: ntaa_fwd_correct *) lemma nta_fwd_correct (h) (a) (G) (L): - ∀T,U. ⦃G,L⦄ ⊢ T :[h,a] U → ∃T0. ⦃G,L⦄ ⊢ U :[h,a] T0. + ∀T,U. ❪G,L❫ ⊢ T :[h,a] U → ∃T0. ❪G,L❫ ⊢ U :[h,a] T0. /3 width=2 by nta_fwd_cnv_dx, cnv_nta_sn/ qed-. lemma nta_pure_cnv (h) (G) (L): - ∀T,U. ⦃G,L⦄ ⊢ T :[h,𝛚] U → - ∀V. ⦃G,L⦄ ⊢ ⓐV.U ![h,𝛚] → ⦃G,L⦄ ⊢ ⓐV.T :[h,𝛚] ⓐV.U. + ∀T,U. ❪G,L❫ ⊢ T :[h,𝛚] U → + ∀V. ❪G,L❫ ⊢ ⓐV.U ![h,𝛚] → ❪G,L❫ ⊢ ⓐV.T :[h,𝛚] ⓐV.U. #h #G #L #T #U #H1 #V #H2 elim (cnv_inv_cast … H1) -H1 #X0 #HU #HT #HUX0 #HTX0 elim (cnv_inv_appl … H2) #n #p #X1 #X2 #_ #HV #_ #HVX1 #HUX2 @@ -58,16 +58,16 @@ qed. (* Basic_1: uses: ty3_sred_wcpr0_pr0 *) lemma nta_cpr_conf_lpr (h) (a) (G): - ∀L1,T1,U. ⦃G,L1⦄ ⊢ T1 :[h,a] U → ∀T2. ⦃G,L1⦄ ⊢ T1 ➡[h] T2 → - ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T2 :[h,a] U. + ∀L1,T1,U. ❪G,L1❫ ⊢ T1 :[h,a] U → ∀T2. ❪G,L1❫ ⊢ T1 ➡[h] T2 → + ∀L2. ❪G,L1❫ ⊢ ➡[h] L2 → ❪G,L2❫ ⊢ T2 :[h,a] U. #h #a #G #L1 #T1 #U #H #T2 #HT12 #L2 #HL12 /3 width=6 by cnv_cpm_trans_lpr, cpm_cast/ qed-. (* Basic_1: uses: ty3_sred_pr2 ty3_sred_pr0 *) lemma nta_cpr_conf (h) (a) (G) (L): - ∀T1,U. ⦃G,L⦄ ⊢ T1 :[h,a] U → - ∀T2. ⦃G,L⦄ ⊢ T1 ➡[h] T2 → ⦃G,L⦄ ⊢ T2 :[h,a] U. + ∀T1,U. ❪G,L❫ ⊢ T1 :[h,a] U → + ∀T2. ❪G,L❫ ⊢ T1 ➡[h] T2 → ❪G,L❫ ⊢ T2 :[h,a] U. #h #a #G #L #T1 #U #H #T2 #HT12 /3 width=6 by cnv_cpm_trans, cpm_cast/ qed-. @@ -75,24 +75,24 @@ qed-. (* Note: this is the preservation property *) (* Basic_1: uses: ty3_sred_pr3 ty3_sred_pr1 *) lemma nta_cprs_conf (h) (a) (G) (L): - ∀T1,U. ⦃G,L⦄ ⊢ T1 :[h,a] U → - ∀T2. ⦃G,L⦄ ⊢ T1 ➡*[h] T2 → ⦃G,L⦄ ⊢ T2 :[h,a] U. + ∀T1,U. ❪G,L❫ ⊢ T1 :[h,a] U → + ∀T2. ❪G,L❫ ⊢ T1 ➡*[h] T2 → ❪G,L❫ ⊢ T2 :[h,a] U. #h #a #G #L #T1 #U #H #T2 #HT12 /3 width=6 by cnv_cpms_trans, cpms_cast/ qed-. (* Basic_1: uses: ty3_cred_pr2 *) lemma nta_lpr_conf (h) (a) (G): - ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[h,a] U → - ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T :[h,a] U. + ∀L1,T,U. ❪G,L1❫ ⊢ T :[h,a] U → + ∀L2. ❪G,L1❫ ⊢ ➡[h] L2 → ❪G,L2❫ ⊢ T :[h,a] U. #h #a #G #L1 #T #U #HTU #L2 #HL12 /2 width=3 by cnv_lpr_trans/ qed-. (* Basic_1: uses: ty3_cred_pr3 *) lemma nta_lprs_conf (h) (a) (G): - ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[h,a] U → - ∀L2. ⦃G,L1⦄ ⊢ ➡*[h] L2 → ⦃G,L2⦄ ⊢ T :[h,a] U. + ∀L1,T,U. ❪G,L1❫ ⊢ T :[h,a] U → + ∀L2. ❪G,L1❫ ⊢ ➡*[h] L2 → ❪G,L2❫ ⊢ T :[h,a] U. #h #a #G #L1 #T #U #HTU #L2 #HL12 /2 width=3 by cnv_lprs_trans/ qed-. @@ -100,8 +100,8 @@ qed-. (* Inversion lemmas based on preservation ***********************************) lemma nta_inv_ldef_sn (h) (a) (G) (K) (V): - ∀X2. ⦃G,K.ⓓV⦄ ⊢ #0 :[h,a] X2 → - ∃∃W,U. ⦃G,K⦄ ⊢ V :[h,a] W & ⇧*[1] W ≘ U & ⦃G,K.ⓓV⦄ ⊢ U ⬌*[h] X2 & ⦃G,K.ⓓV⦄ ⊢ X2 ![h,a]. + ∀X2. ❪G,K.ⓓV❫ ⊢ #0 :[h,a] X2 → + ∃∃W,U. ❪G,K❫ ⊢ V :[h,a] W & ⇧*[1] W ≘ U & ❪G,K.ⓓV❫ ⊢ U ⬌*[h] X2 & ❪G,K.ⓓV❫ ⊢ X2 ![h,a]. #h #a #G #Y #X #X2 #H elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2 elim (cnv_inv_zero … H1) -H1 #Z #K #V #HV #H destruct @@ -113,8 +113,8 @@ elim (cpms_inv_delta_sn … H2) -H2 * qed-. lemma nta_inv_lref_sn (h) (a) (G) (L): - ∀X2,i. ⦃G,L⦄ ⊢ #↑i :[h,a] X2 → - ∃∃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}. + ∀X2,i. ❪G,L❫ ⊢ #↑i :[h,a] X2 → + ∃∃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]. #h #a #G #L #X2 #i #H elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2 elim (cnv_inv_lref … H1) -H1 #I #K #Hi #H destruct @@ -126,9 +126,9 @@ elim (cpms_inv_lref_sn … H2) -H2 * qed-. lemma nta_inv_lref_sn_drops_cnv (h) (a) (G) (L): - ∀X2,i. ⦃G,L⦄ ⊢ #i :[h,a] X2 → - ∨∨ ∃∃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] - | ∃∃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]. + ∀X2,i. ❪G,L❫ ⊢ #i :[h,a] X2 → + ∨∨ ∃∃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] + | ∃∃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]. #h #a #G #L #X2 #i #H elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2 elim (cnv_inv_lref_drops … H1) -H1 #I #K #V #HLK #HV @@ -139,7 +139,7 @@ elim (cpms_inv_lref1_drops … H2) -H2 * /4 width=8 by cnv_cpms_nta, cpcs_cprs_sn, ex5_4_intro, or_introl/ | #n #Y #X #U #H #HVU #HUX1 #H0 destruct lapply (drops_mono … H … HLK) -H #H destruct - elim (lifts_total V (𝐔❴↑i❵)) #W #HVW + elim (lifts_total V (𝐔❨↑i❩)) #W #HVW lapply (cpms_lifts_bi … HVU (Ⓣ) … L … HVW … HUX1) -U [ /2 width=2 by drops_isuni_fwd_drop2/ ] #HWX1 /4 width=9 by cprs_div, ex5_3_intro, or_intror/ @@ -147,8 +147,8 @@ elim (cpms_inv_lref1_drops … H2) -H2 * qed-. lemma nta_inv_bind_sn_cnv (h) (a) (p) (I) (G) (K) (X2): - ∀V,T. ⦃G,K⦄ ⊢ ⓑ{p,I}V.T :[h,a] X2 → - ∃∃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]. + ∀V,T. ❪G,K❫ ⊢ ⓑ[p,I]V.T :[h,a] X2 → + ∃∃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]. #h #a #p * #G #K #X2 #V #T #H elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2 elim (cnv_inv_bind … H1) -H1 #HV #HT @@ -165,8 +165,8 @@ qed-. (* Basic_1: uses: ty3_gen_appl *) lemma nta_inv_appl_sn (h) (G) (L) (X2): - ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h,𝟐] X2 → - ∃∃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,𝟐]. + ∀V,T. ❪G,L❫ ⊢ ⓐV.T :[h,𝟐] X2 → + ∃∃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,𝟐]. #h #G #L #X2 #V #T #H elim (cnv_inv_cast … H) -H #X #HX2 #H1 #HX2 #H2 elim (cnv_inv_appl … H1) #n #p #W #U #H