From fec1a061eeca5e7e05b4f0c3e299983b163569c3 Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Wed, 20 Jun 2012 18:50:32 +0000 Subject: [PATCH] - star.ma: constructor inj of star conflicts with previous constructor inj of TC. constructor inj of star renamed to sstep and constructor injl of starl renamed to sstepl - lambda_delta: bug fix in reduction rule tpr_zeta which now has the structure of like tpr_delta. More lemas towards subject reduction of native typing --- .../basic_2/computation/cprs_delift.ma | 1 + .../basic_2/computation/cprs_lcprs.ma | 16 ++- .../basic_2/computation/cprs_tstc.ma | 10 +- .../basic_2/computation/cprs_tstc_vector.ma | 8 +- .../basic_2/computation/csn_lcpr.ma | 12 +- .../lambda_delta/basic_2/dynamic/nta_ltpr.ma | 94 +++----------- .../lambda_delta/basic_2/dynamic/nta_sta.ma | 37 +++--- .../lambda_delta/basic_2/dynamic/nta_thin.ma | 3 +- .../basic_2/equivalence/cpcs_cpcs.ma | 4 + .../basic_2/equivalence/cpcs_delift.ma | 47 +++++++ .../lambda_delta/basic_2/reducibility/cpr.ma | 20 --- .../basic_2/reducibility/cpr_cpr.ma | 2 +- .../basic_2/reducibility/cpr_lift.ma | 25 +++- .../basic_2/reducibility/ltpr_aaa.ma | 14 +- .../basic_2/reducibility/ltpr_ldrop.ma | 2 +- .../basic_2/reducibility/tnf_tif.ma | 4 +- .../lambda_delta/basic_2/reducibility/tpr.ma | 63 +++++---- .../basic_2/reducibility/tpr_delift.ma | 2 +- .../basic_2/reducibility/tpr_lift.ma | 40 +++--- .../basic_2/reducibility/tpr_tpr.ma | 48 ++++--- .../basic_2/reducibility/tpr_tpss.ma | 31 ++--- .../lambda_delta/basic_2/static/sta_lift.ma | 6 +- .../lambda_delta/basic_2/static/sta_ltpss.ma | 122 ++++++++++++++++++ .../basic_2/substitution/lift_lift.ma | 8 ++ .../basic_2/substitution/lsubs_sfr.ma | 5 + .../lambda_delta/basic_2/unfold/tpss_tpss.ma | 8 +- .../lambda_delta/ground_2/xoa.conf.xml | 2 +- .../contribs/lambda_delta/ground_2/xoa.ma | 16 +-- .../lambda_delta/ground_2/xoa_notation.ma | 20 +-- matita/matita/lib/basics/star.ma | 12 +- 30 files changed, 406 insertions(+), 276 deletions(-) create mode 100644 matita/matita/contribs/lambda_delta/basic_2/static/sta_ltpss.ma diff --git a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_delift.ma b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_delift.ma index 3965d1619..5ce6bb59c 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_delift.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_delift.ma @@ -20,6 +20,7 @@ include "basic_2/computation/cprs.ma". (* Properties on inverse basic term relocation ******************************) +(* Note: this should be stated with tprs *) lemma cprs_zeta_delift: ∀L,V,T1,T2. L.ⓓV ⊢ T1 ▼*[O, 1] ≡ T2 → L ⊢ ⓓV.T1 ➡* T2. #L #V #T1 #T2 * #T #HT1 #HT2 @(cprs_strap2 … (ⓓV.T)) [ /3 width=3/ | @inj /3 width=3/ ] (**) (* explicit constructor, /5 width=3/ is too slow *) diff --git a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_lcprs.ma b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_lcprs.ma index 1c9e28ad8..5efdb4fa2 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_lcprs.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_lcprs.ma @@ -25,6 +25,10 @@ lemma lcprs_cprs_trans: ∀L1,L2. L1 ⊢ ➡* L2 → #L1 #L2 #HL12 @(lcprs_ind … HL12) -L2 // /3 width=3/ qed. +lemma lcprs_cpr_trans: ∀L1,L2. L1 ⊢ ➡* L2 → + ∀T1,T2. L2 ⊢ T1 ➡ T2 → L1 ⊢ T1 ➡* T2. +/3 width=3 by lcprs_cprs_trans, inj/ qed. + (* Advanced inversion lemmas ************************************************) (* Basic_1: was pr3_gen_abbr *) @@ -32,7 +36,7 @@ lemma cprs_inv_abbr1: ∀L,V1,T1,U2. L ⊢ ⓓV1. T1 ➡* U2 → (∃∃V2,T2. L ⊢ V1 ➡* V2 & L. ⓓV1 ⊢ T1 ➡* T2 & U2 = ⓓV2. T2 ) ∨ - ∃∃U. ⇧[0, 1] U2 ≡ U & L. ⓓV1 ⊢ T1 ➡* U. + ∃∃T2. L. ⓓV1 ⊢ T1 ➡* T2 & ⇧[0, 1] U2 ≡ T2. #L #V1 #T1 #U2 #H @(cprs_ind … H) -U2 /3 width=5/ #U0 #U2 #_ #HU02 * * [ #V0 #T0 #HV10 #HT10 #H destruct @@ -41,12 +45,12 @@ lemma cprs_inv_abbr1: ∀L,V1,T1,U2. L ⊢ ⓓV1. T1 ➡* U2 → lapply (cpr_intro … HV0 … HV2) -HV2 #HV02 lapply (ltpr_cpr_trans (L.ⓓV0) … HT02) /2 width=1/ -V #HT02 lapply (lcprs_cprs_trans (L. ⓓV1) … HT02) -HT02 /2 width=1/ /4 width=5/ - | -V0 #T2 #HT20 #HTU2 - elim (lift_total U2 0 1) #U0 #HU20 - lapply (cpr_lift (L.ⓓV1) … HT20 … HU20 HTU2) -T2 /2 width=1/ /4 width=5/ + | #T2 #HT02 #HUT2 + lapply (lcprs_cpr_trans (L.ⓓV1) … HT02) -HT02 /2 width=1/ -V0 #HT02 + lapply (cprs_trans … HT10 … HT02) -T0 /3 width=3/ ] -| #U1 #HU01 #HTU1 +| #U1 #HTU1 #HU01 elim (lift_total U2 0 1) #U #HU2 - lapply (cpr_lift (L.ⓓV1) … HU01 … HU2 HU02) -U0 /2 width=1/ /4 width=5/ + lapply (cpr_lift (L.ⓓV1) … HU01 … HU2 HU02) -U0 /2 width=1/ /4 width=3/ ] qed-. diff --git a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc.ma b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc.ma index eb59c5f84..879b0bdae 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc.ma @@ -61,11 +61,11 @@ elim (cprs_inv_appl1 … H) -H * | #V0 #W #T0 #HV10 #HT0 #HU elim (cprs_inv_abbr1 … HT0) -HT0 * [ #V3 #T3 #_ #_ #H destruct - | #X #H #HT2 + | #X #HT2 #H elim (lift_inv_bind1 … H) -H #W2 #T2 #HW2 #HT02 #H destruct @or_intror @(cprs_trans … HU) -U (**) (* explicit constructor *) @(cprs_trans … (ⓓV.ⓐV2.ⓛW2.T2)) [ /3 width=1/ ] -T - @(cprs_strap2 … (ⓐV1.ⓛW.T0)) [ /5 width=3/ ] -V -V2 -W2 -T2 + @(cprs_strap2 … (ⓐV1.ⓛW.T0)) [ /5 width=7/ ] -V -V2 -W2 -T2 @(cprs_strap2 … (ⓓV1.T0)) [ /3 width=1/ ] -W /2 width=1/ ] | #V3 #V4 #V0 #T0 #HV13 #HV34 #HT0 #HU @@ -74,12 +74,12 @@ elim (cprs_inv_appl1 … H) -H * [ #V5 #T5 #HV5 #HT5 #H destruct lapply (cprs_lift (L.ⓓV) … HV12 … HV13 … HV34) -V1 -V3 /2 width=1/ /3 width=1/ - | #X #H #HT1 + | #X #HT1 #H elim (lift_inv_bind1 … H) -H #V5 #T5 #HV05 #HT05 #H destruct lapply (cprs_lift (L.ⓓV0) … HV12 … HV13 … HV34) -V3 /2 width=1/ #HV24 @(cprs_trans … (ⓓV.ⓐV2.ⓓV5.T5)) [ /3 width=1/ ] -T - @(cprs_strap2 … (ⓐV1.ⓓV0.T0)) [ /5 width=3/ ] -V -V5 -T5 - @(cprs_strap2 … (ⓓV0.ⓐV2.T0)) [ /3 width=3/ ] -V1 /3 width=9/ + @(cprs_strap2 … (ⓐV1.ⓓV0.T0)) [ /5 width=7/ ] -V -V5 -T5 + @(cprs_strap2 … (ⓓV0.ⓐV2.T0)) [ /3 width=3/ ] -V1 /3 width=1/ ] ] qed-. diff --git a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc_vector.ma b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc_vector.ma index 5a4c2bc34..a6aedd799 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc_vector.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/computation/cprs_tstc_vector.ma @@ -105,10 +105,10 @@ elim (cprs_inv_appl1 … H) -H * @(cprs_trans … HU) -U elim (cprs_inv_abbr1 … HT0) -HT0 * [ -HV12a -HV12b -HV10a #V1 #T1 #_ #_ #H destruct - | -V1b #X #H #HT1 + | -V1b #X #HT1 #H elim (lift_inv_bind1 … H) -H #W1 #T1 #HW01 #HT01 #H destruct @(cprs_trans … (ⓓV.ⓐV2a.ⓛW1.T1)) [ /3 width=1/ ] -T -V2b -V2s - @(cprs_strap2 … (ⓐV1a.ⓛW0.T0)) [ /5 width=3/ ] -V -V2a -W1 -T1 + @(cprs_strap2 … (ⓐV1a.ⓛW0.T0)) [ /5 width=7/ ] -V -V2a -W1 -T1 @(cprs_strap2 … (ⓓV1a.T0)) [ /3 width=1/ ] -W0 /2 width=1/ ] ] @@ -122,11 +122,11 @@ elim (cprs_inv_appl1 … H) -H * [ #V1 #T1 #HV1 #HT1 #H destruct lapply (cprs_lift (L.ⓓV) … HV12a … HV10a … HV0a) -V1a -V0a [ /2 width=1/ ] #HV2a @(cprs_trans … (ⓓV.ⓐV2a.T1)) [ /3 width=1/ ] -T -V2b -V2s /3 width=1/ - | #X #H #HT1 + | #X #HT1 #H elim (lift_inv_bind1 … H) -H #V1 #T1 #HW01 #HT01 #H destruct lapply (cprs_lift (L.ⓓV0) … HV12a … HV10a … HV0a) -V0a [ /2 width=1/ ] #HV2a @(cprs_trans … (ⓓV.ⓐV2a.ⓓV1.T1)) [ /3 width=1/ ] -T -V2b -V2s - @(cprs_strap2 … (ⓐV1a.ⓓV0.T0)) [ /5 width=3/ ] -V -V1 -T1 + @(cprs_strap2 … (ⓐV1a.ⓓV0.T0)) [ /5 width=7/ ] -V -V1 -T1 @(cprs_strap2 … (ⓓV0.ⓐV2a.T0)) [ /3 width=3/ ] -V1a /3 width=1/ ] ] diff --git a/matita/matita/contribs/lambda_delta/basic_2/computation/csn_lcpr.ma b/matita/matita/contribs/lambda_delta/basic_2/computation/csn_lcpr.ma index 3cd83733e..4b1b9d2fc 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/computation/csn_lcpr.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/computation/csn_lcpr.ma @@ -40,8 +40,9 @@ elim (cpr_inv_abbr1 … H1) -H1 * @(csn_lcpr_conf (L. ⓓV)) /2 width=1/ -HLV1 /2 width=3/ | -IHV -HLV1 * #H destruct /3 width=1/ ] -| -IHV -IHT -H2 #T0 #HT0 #HLT0 - lapply (csn_inv_lift … HT … HT0) -HT /2 width=3/ +| -IHV -IHT -H2 #T0 #HLT0 #HT0 + lapply (csn_cpr_trans … HT … HLT0) -T #HLT0 + lapply (csn_inv_lift … HLT0 … HT0) -T0 /2 width=3/ ] qed. @@ -99,9 +100,10 @@ elim (cpr_inv_appl1 … HL) -HL * lapply (ltpr_cpr_trans (L. ⓓV) … HLT3) /2 width=1/ -HLT3 #HLT3 @(IHVT … H … HV05) -IHVT // -H -HV05 /3 width=1/ ] - | -H -IHVT #T0 #HT0 #HLT0 - @(csn_cpr_trans … (ⓐV1.T0)) /2 width=1/ -V0 -Y - @(csn_inv_lift … 0 1 HVT) /2 width=1/ + | -H -IHVT #T0 #HLT0 #HT0 + lapply (csn_cpr_trans … HVT (ⓐV2.T0) ?) /2 width=1/ -T #HVT0 + lapply (csn_inv_lift L … 1 HVT0 ? ? ?) -HVT0 [ /2 width=4/ |2,3: skip | /2 width=1/ ] -V2 -T0 #HVY + @(csn_cpr_trans … HVY) /2 width=1/ ] | -HV -HV12 -HVT -IHVT -H #V0 #W0 #T0 #T1 #_ #_ #H destruct | -IHVT -H #V0 #V3 #W0 #W1 #T0 #T1 #HLV10 #HLW01 #HLT01 #HV03 #H1 #H2 destruct diff --git a/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_ltpr.ma b/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_ltpr.ma index 3799dcbb8..c461e9f7e 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_ltpr.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_ltpr.ma @@ -12,94 +12,38 @@ (* *) (**************************************************************************) -(* FRAGMENT 0 -include "basic_2/unfold/delift_lift.ma". - - -include "basic_2/equivalence/cpcs_cpcs.ma". -include "basic_2/unfold/delift_delift.ma". - - - -axiom pippo1: ∀T1,V. ∃∃T2. ⓓV.T1 ➡ T2 & ⋆.ⓓV ⊢ T1 ▼*[0, 1] ≡ T2. -(* -#T1 #V elim (pippo0 (⋆.ⓓV) 0 1 ? T1) -[ #T2 #HT12 @(ex2_1_intro … HT12) - @tpr -*) - -axiom pippo: ∀L,V,T1. ∃∃T2. L ⊢ ⓓV.T1 ➡ T2 & L.ⓓV ⊢ T1 ▼*[0, 1] ≡ T2. - -axiom cprs_inv_appl1_cpcs: ∀L,V1,T1,U2. L ⊢ ⓐV1. T1 ➡* U2 → ( - ∃∃V2,T2. L ⊢ V1 ➡* V2 & L ⊢ T1 ➡* T2 & - L ⊢ U2 ➡* ⓐV2. T2 - ) ∨ - ∃∃V2,W,T. L ⊢ V1 ➡* V2 & - L ⊢ T1 ➡* ⓛW. T & L ⊢ ⓓV2. T ⬌* U2. -#L #V1 #T1 #U2 #H @(cprs_ind … H) -U2 /3 width=5/ -#U #U2 #_ #HU2 * * -[ #V0 #T0 #HV10 #HT10 #HUT0 - elim (cprs_strip … HUT0 … HU2) -U #U #H #HU2 - elim (cpr_inv_appl1 … H) -H * - [ #V2 #T2 #HV02 #HT02 #H destruct /4 width=5/ - | #V2 #W2 #T #T2 #HV02 #HT2 #H1 #H2 destruct - lapply (cprs_strap1 … HV10 HV02) -V0 #HV12 - lapply (cprs_div ? (ⓓV2.T) ? ? ? HU2) -HU2 /2 width=1/ /3 width=6/ - | #V #V2 #W0 #W2 #T #T2 #HV0 #HW02 #HT2 #HV2 #H1 #H2 destruct - lapply (cprs_strap1 … HV10 HV0) -V0 #HV1 - lapply (cprs_trans … HT10 (ⓓW2.T2) ?) -HT10 /2 width=1/ -W0 -T #HT1 - elim (pippo L W2 T2) #T3 #H1T3 #H2T3 - elim (pippo L W2 (ⓐV2.T2)) #X #H1X #H - elim (delift_inv_flat1 … H) -H #V3 #Y #HV23 #HY #H destruct - - - @or_introl @(ex3_2_intro … HV1 HT1) -HV1 -HT1 - - ] -| /4 width=8/ -] -qed-. - - -include "basic_2/computation/cprs_lcprs.ma". +include "basic_2/equivalence/cpcs_delift.ma". include "basic_2/dynamic/nta.ma". - -axiom cprs_inv_appl_abst: ∀L,V,T,W,U. L ⊢ ⓐV.T ➡* ⓛW.U → - ∃∃V0,W0,T0,W1,U1. ⇧[O, 1] W ≡ W1 & - ⇧[O + 1, 1] U ≡ U1 & - L ⊢ V ➡* V0 & L ⊢ T ➡* ⓛW0.T0 & - L.ⓓV0 ⊢ T0 ➡* ⓛW1.U1. -#L #V #T #W #U #H -elim (cprs_inv_appl1 … H) -H * -[ #V0 #T0 #_ #_ #H destruct -| #V0 #W0 #T0 #HV0 #HT0 #H - elim (cprs_inv_abbr1 … H) -H * - [ #V1 #T1 #_ #_ #H destruct - | #X #H #HT01 - elim (lift_inv_bind1 … H) -H #W1 #U1 #HW1 #HU1 #H destruct /2 width=10/ - ] -| #V0 #V1 #V2 #T0 #HV0 #HV01 #HT0 #H - elim (cprs_inv_abbr1 … H) -H * - [ #V3 #T3 #_ #_ #H destruct - | #X #H #HT3 - elim (lift_inv_bind1 … H) -H #W3 #U3 #HW3 #HU3 #H destruct /2 width=10/ - -axiom pippo: ∀h,L,T,U. ⦃h, L⦄ ⊢ T : U → ∀X,Y. L ⊢ T ➡* ⓛX.Y → +(* +lemma pippo: ∀h,L,T,U. ⦃h, L⦄ ⊢ T : U → ∀X,Y. L ⊢ T ➡* ⓛX.Y → ∃Z. L ⊢ U ➡* ⓛX.Z. #h #L #T #U #H elim H -L -T -U [ | | | -| -| #L #V #W #T #U #HTU #HUW #IHTU #IHUW #X #Y #HTY - elim (cprs_inv_appl1 … HTY) -HTY * +| #L #V #W #T #U #_ #_ #IHVW #IHTU #X #Y #H +| #L #V #W #T #U #_ #HUW #IHTU #IHUW #X #Y #HTY + elim (cprs_inv_appl_abst … HTY) -HTY #W1 #T1 #W2 #T2 #HT1 #HT12 #HYT2 + elim (IHTU … HT1) -IHTU -HT1 #U1 #HU1 + + + + * [ #V0 #T0 #_ #_ #H destruct | #V0 #W0 #T0 #HV0 #HT0 #HTY elim (IHTU … HT0) -IHTU -HT0 #Z #HUZ elim (cprs_inv_abbr1 … HTY) -HTY * [ #V1 #T1 #_ #_ #H destruct #X0 +*) + +(* + +include "basic_2/computation/cprs_lcprs.ma". + + + include "basic_2/dynamic/nta_ltpss.ma". include "basic_2/dynamic/nta_thin.ma". diff --git a/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_sta.ma b/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_sta.ma index d064d2e7d..6268b98b1 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_sta.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_sta.ma @@ -13,35 +13,30 @@ (**************************************************************************) include "basic_2/static/sta.ma". -include "basic_2/dynamic/nta_lift.ma". +include "basic_2/equivalence/cpcs_cpcs.ma". +include "basic_2/dynamic/nta.ma". (* NATIVE TYPE ASSIGNMENT ON TERMS ******************************************) -axiom pippo: ∀h,L,X,Y1,U. ⦃h, L⦄ ⊢ ⓐX.Y1 : U → ∀Y2. L ⊢ Y1 ⬌* Y2 → - ∀U2. ⦃h, L⦄ ⊢ Y2 : U2 → ⦃h, L⦄ ⊢ ⓐX.Y2 : U. - (* Properties on static type assignment *************************************) lemma nta_fwd_sta: ∀h,L,T,U. ⦃h, L⦄ ⊢ T : U → - ∃∃U0. ⦃h, L⦄ ⊢ T • U0 & L ⊢ U0 ⬌* U & ⦃h, L⦄ ⊢ T : U0. + ∃∃U0. ⦃h, L⦄ ⊢ T • U0 & L ⊢ U0 ⬌* U. #h #L #T #U #H elim H -L -T -U -[ /2 width=4/ -| #L #K #V #W1 #V1 #i #HLK #_ #HWV1 * #W0 #H1VW0 #HW01 #H2VW0 +[ /2 width=3/ +| #L #K #V #W1 #V1 #i #HLK #_ #HWV1 * #W0 #HVW0 #HW01 elim (lift_total W0 0 (i+1)) #V0 #HWV0 lapply (ldrop_fwd_ldrop2 … HLK) #HLK0 - lapply (cpcs_lift … HLK0 … HWV0 … HWV1 HW01) -HLK0 -HWV1 -HW01 /3 width=9/ -| #L #K #W #V1 #W1 #i #HLK #HWV1 #HW1 * /3 width=9/ -| #I #L #V #W #T #U #_ #_ * #W0 #_ #_ #H2VW0 * /3 width=4/ -| #L #V #W #T #U #_ #_ * #W0 #_ #HW0 #H2VW0 * #X #H1 #HX #H2 - elim (sta_inv_bind1 … H1) -H1 #U0 #HTU0 #H destruct - elim (nta_inv_bind1 … H2) /4 width=4/ -| #L #V #W #T #U #_ #_ * #U0 #H1TU0 #HU0 #H2TU0 * #W0 #_ #_ #H2UW0 -W - elim (nta_fwd_correct … H2TU0) #T0 #HUT0 - @(ex3_1_intro … (ⓐV.U0)) /2 width=1/ -H1TU0 - @(nta_pure … W0 … H2TU0) -T /3 width=3/ -| #L #T #U #HTU * #U0 #H1TU0 #HU0 #H2TU0 - elim (nta_fwd_correct … H2TU0) -H2TU0 /4 width=8/ -| #L #T #U1 #U2 #V2 #_ #HU12 #_ * #U0 #H1TU0 #HU01 #H2TU0 #_ - lapply (cpcs_trans … HU01 … HU12) -U1 /2 width=4/ + lapply (cpcs_lift … HLK0 … HWV0 … HWV1 HW01) -HLK0 -HWV1 -HW01 /3 width=6/ +| #L #K #W #V1 #W1 #i #HLK #HWV1 #HW1 * /3 width=6/ +| #I #L #V #W #T #U #_ #_ * #W0 #_ #_ * /3 width=3/ +| #L #V #W #T #U #_ #_ * #W0 #_ #HW0 * #X #H #HX + elim (sta_inv_bind1 … H) -H #U0 #HTU0 #H destruct + @(ex2_1_intro … (ⓐV.ⓛW.U0)) /2 width=1/ /3 width=1/ +| #L #V #W #T #U #_ #_ * #U0 #HTU0 #HU0 #_ -W + @(ex2_1_intro … (ⓐV.U0)) /2 width=1/ +| #L #T #U #HTU * #U0 #HTU0 #HU0 /3 width=3/ +| #L #T #U1 #U2 #V2 #_ #HU12 #_ * #U0 #HTU0 #HU01 #_ + lapply (cpcs_trans … HU01 … HU12) -U1 /2 width=3/ ] qed-. diff --git a/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_thin.ma b/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_thin.ma index e2e568d3a..f927f841a 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_thin.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/dynamic/nta_thin.ma @@ -12,14 +12,13 @@ (* *) (**************************************************************************) -include "basic_2/unfold/delift_lift.ma". include "basic_2/unfold/thin_ldrop.ma". include "basic_2/equivalence/cpcs_delift.ma". include "basic_2/dynamic/nta_lift.ma". (* NATIVE TYPE ASSIGNMENT ON TERMS ******************************************) -(* Properties on basic local environment thibbing ***************************) +(* Properties on basic local environment thinning ***************************) (* Note: this is known as the substitution lemma *) (* Basic_1: was only: ty3_gen_cabbr *) diff --git a/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_cpcs.ma b/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_cpcs.ma index d67e66630..fcad182e0 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_cpcs.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_cpcs.ma @@ -73,6 +73,10 @@ elim (cprs_inv_abst1 Abst W1 … H1) -H1 #W2 #T2 #HW12 #HT12 #H destruct @(ex2_2_intro … H2) -H2 /2 width=2/ (**) (* explicit constructor, /3 width=6/ is slow *) qed-. +lemma cpcs_inv_abst2: ∀L,W1,T1,T. L ⊢ T ⬌* ⓛW1.T1 → + ∃∃W2,T2. L ⊢ T ➡* ⓛW2.T2 & L ⊢ ⓛW1.T1 ➡* ⓛW2.T2. +/3 width=1 by cpcs_inv_abst1, cpcs_sym/ qed-. + (* Basic_1: was: pc3_gen_lift *) lemma cpcs_inv_lift: ∀L,K,d,e. ⇩[d, e] L ≡ K → ∀T1,U1. ⇧[d, e] T1 ≡ U1 → ∀T2,U2. ⇧[d, e] T2 ≡ U2 → diff --git a/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_delift.ma b/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_delift.ma index b812830ee..c568941a5 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_delift.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_delift.ma @@ -12,12 +12,59 @@ (* *) (**************************************************************************) +include "basic_2/unfold/delift_lift.ma". include "basic_2/unfold/delift_delift.ma". include "basic_2/computation/cprs_delift.ma". include "basic_2/equivalence/cpcs_cpcs.ma". (* CONTEXT-SENSITIVE PARALLEL EQUIVALENCE ON TERMS **************************) +(* Advanced inversion lemmas ************************************************) + +lemma cprs_inv_appl1_cpcs: ∀L,V1,T1,U2. L ⊢ ⓐV1. T1 ➡* U2 → ( + ∃∃V2,T2. L ⊢ V1 ➡* V2 & L ⊢ T1 ➡* T2 & + L ⊢ U2 ➡* ⓐV2. T2 + ) ∨ + ∃∃V2,W,T. L ⊢ V1 ➡* V2 & + L ⊢ T1 ➡* ⓛW. T & L ⊢ ⓓV2. T ⬌* U2. +#L #V1 #T1 #U2 #H @(cprs_ind … H) -U2 /3 width=5/ +#U #U2 #_ #HU2 * * +[ #V0 #T0 #HV10 #HT10 #HUT0 + elim (cprs_strip … HUT0 … HU2) -U #U #H #HU2 + elim (cpr_inv_appl1 … H) -H * + [ #V2 #T2 #HV02 #HT02 #H destruct /4 width=5/ + | #V2 #W2 #T #T2 #HV02 #HT2 #H1 #H2 destruct + lapply (cprs_strap1 … HV10 HV02) -V0 #HV12 + lapply (cprs_div ? (ⓓV2.T) ? ? ? HU2) -HU2 /2 width=1/ /3 width=6/ + | #V #V2 #W0 #W2 #T #T2 #HV0 #HW02 #HT2 #HV2 #H1 #H2 destruct + lapply (cprs_strap1 … HV10 HV0) -V0 #HV1 + lapply (cprs_trans … HT10 (ⓓW2.T2) ?) -HT10 /2 width=1/ -W0 -T #HT1 + elim (sfr_delift (L.ⓓW2) (ⓐV2.T2) 0 1 ? ?) // #X #H1 + lapply (cprs_zeta_delift … H1) #H2 + lapply (cprs_trans … HU2 … H2) -HU2 -H2 #HU2T3 + elim (delift_inv_flat1 … H1) -H1 #V3 #T3 #HV23 #HT23 #H destruct + lapply (delift_inv_lift1_eq … HV23 … HV2) -V2 [ /2 width=1/ | skip ] #H destruct + lapply (cprs_zeta_delift … HT23) -HT23 #H + lapply (cprs_trans … HT1 … H) -W2 -T2 /3 width=5/ + ] +| /4 width=8/ +] +qed-. + +lemma cprs_inv_appl_abst: ∀L,V,T,W,U. L ⊢ ⓐV.T ➡* ⓛW.U → + ∃∃W0,T0,V1,T1. L ⊢ T ➡* ⓛW0.T0 & + L ⊢ ⓓV.T0 ➡* ⓛV1.T1 & + L ⊢ ⓛW.U ➡* ⓛV1.T1. +#L #V #T #W #U #H +elim (cprs_inv_appl1_cpcs … H) -H * +[ #V0 #T0 #HV0 #HT0 #H + elim (cprs_inv_abst1 Abst W … H) -H #W0 #U0 #_ #_ #H destruct +| #V0 #W0 #T0 #HV0 #HT0 #H + elim (cpcs_inv_abst2 … H) -H #V1 #T1 #H1 #H2 + lapply (cprs_trans … (ⓓV.T0) … H1) -H1 /2 width=1/ -V0 /2 width=7/ +] +qed-. + (* Properties on inverse basic term relocation ******************************) lemma cpcs_zeta_delift_comm: ∀L,V,T1,T2. L.ⓓV ⊢ T1 ▼*[O, 1] ≡ T2 → diff --git a/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr.ma b/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr.ma index 401a4be64..5a572d5e1 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr.ma @@ -75,26 +75,6 @@ lemma cpr_inv_sort1: ∀L,T2,k. L ⊢ ⋆k ➡ T2 → T2 = ⋆k. >(tpss_inv_sort1 … H) -H // qed-. -(* Basic_1: was pr2_gen_abbr *) -lemma cpr_inv_abbr1: ∀L,V1,T1,U2. L ⊢ ⓓV1. T1 ➡ U2 → - (∃∃V,V2,T2. V1 ➡ V & L ⊢ V ▶* [O, |L|] V2 & - L. ⓓV ⊢ T1 ➡ T2 & - U2 = ⓓV2. T2 - ) ∨ - ∃∃T. ⇧[0,1] T ≡ T1 & L ⊢ T ➡ U2. -#L #V1 #T1 #Y * #X #H1 #H2 -elim (tpr_inv_abbr1 … H1) -H1 * -[ #V #T0 #T #HV1 #HT10 #HT0 #H destruct - elim (tpss_inv_bind1 … H2) -H2 #V2 #T2 #HV2 #HT2 #H destruct - lapply (tps_lsubs_trans … HT0 (L. ⓓV) ?) -HT0 /2 width=1/ #HT0 - lapply (tps_weak_all … HT0) -HT0 #HT0 - lapply (tpss_lsubs_trans … HT2 (L. ⓓV) ?) -HT2 /2 width=1/ #HT2 - lapply (tpss_weak_all … HT2) -HT2 #HT2 - lapply (tpss_strap … HT0 HT2) -T /4 width=7/ -| /4 width=5/ -] -qed-. - (* Basic_1: was: pr2_gen_cast *) lemma cpr_inv_cast1: ∀L,V1,T1,U2. L ⊢ ⓝV1. T1 ➡ U2 → ( ∃∃V2,T2. L ⊢ V1 ➡ V2 & L ⊢ T1 ➡ T2 & diff --git a/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr_cpr.ma b/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr_cpr.ma index 583726cd4..87eaa161f 100644 --- a/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr_cpr.ma +++ b/matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr_cpr.ma @@ -31,7 +31,7 @@ lemma cpr_bind_dx: ∀I,L,V1,V2,T1,T2. V1 ➡ V2 → L. ⓑ{I} V2 ⊢ T1 ➡ T2 #I #L #V1 #V2 #T1 #T2 #HV12 * #T #HT1 normalize #HT2 elim (tpss_split_up … HT2 1 ? ?) -HT2 // #T0 (lift_inv_sort2 … H) -X /2 width=3/ diff --git a/matita/matita/contribs/lambda_delta/basic_2/static/sta_ltpss.ma b/matita/matita/contribs/lambda_delta/basic_2/static/sta_ltpss.ma new file mode 100644 index 000000000..b0232f5a6 --- /dev/null +++ b/matita/matita/contribs/lambda_delta/basic_2/static/sta_ltpss.ma @@ -0,0 +1,122 @@ +(**************************************************************************) +(* ___ *) +(* ||M|| *) +(* ||A|| A project by Andrea Asperti *) +(* ||T|| *) +(* ||I|| Developers: *) +(* ||T|| The HELM team. *) +(* ||A|| http://helm.cs.unibo.it *) +(* \ / *) +(* \ / This file is distributed under the terms of the *) +(* v GNU General Public License Version 2 *) +(* *) +(**************************************************************************) + +include "basic_2/unfold/tpss_tpss.ma". +include "basic_2/unfold/ltpss_tpss.ma". +include "basic_2/static/sta_lift.ma". + +(* STATIC TYPE ASSIGNMENT ON TERMS ******************************************) + +(* Properties about parallel unfold *****************************************) + +lemma sta_ltpss_tpss_conf: ∀h,L1,T1,U1. ⦃h, L1⦄ ⊢ T1 • U1 → + ∀L2,d,e. L1 ▶* [d, e] L2 → + ∀T2. L2 ⊢ T1 ▶* [d, e] T2 → + ∃∃U2. ⦃h, L2⦄ ⊢ T2 • U2 & L2 ⊢ U1 ▶* [d, e] U2. +#h #L1 #T1 #U #H elim H -L1 -T1 -U +[ #L1 #k1 #L2 #d #e #_ #T2 #H + >(tpss_inv_sort1 … H) -H /2 width=3/ +| #L1 #K1 #V1 #W1 #U1 #i #HLK1 #HVW1 #HWU1 #IHVW1 #L2 #d #e #HL12 #T2 #H + elim (tpss_inv_lref1 … H) -H [ | -HVW1 ] + [ #H destruct + elim (lt_or_ge i d) #Hdi [ -HVW1 | ] + [ elim (ltpss_ldrop_conf_le … HL12 … HLK1 ?) -L1 /2 width=2/ #X #H #HLK2 + elim (ltpss_inv_tpss11 … H ?) -H /2 width=1/ #K2 #V2 #HK12 #HV12 #H destruct + elim (IHVW1 … HK12 … HV12) -IHVW1 -HK12 -HV12 #W2 #HVW2 #HW12 + lapply (ldrop_fwd_ldrop2 … HLK2) #H + elim (lift_total W2 0 (i+1)) #U2 #HWU2 + lapply (tpss_lift_ge … HW12 … H … HWU1 … HWU2) // -HW12 -H -HWU1 + >minus_plus minus_plus #H + lapply (tpss_weak … H d e ? ?) [1,2: normalize [ >commutative_plus minus_plus #H + lapply (tpss_weak … H d e ? ?) [1,2: normalize [ >commutative_plus minus_plus minus_plus #H + lapply (tpss_weak … H d e ? ?) [1,2: normalize [ >commutative_plus 3 1 3 2 3 3 + 3 4 4 2 4 3 4 4 5 2 5 3 5 4 - 5 5 6 4 6 6 7 6 diff --git a/matita/matita/contribs/lambda_delta/ground_2/xoa.ma b/matita/matita/contribs/lambda_delta/ground_2/xoa.ma index 6214557bb..d96b471e6 100644 --- a/matita/matita/contribs/lambda_delta/ground_2/xoa.ma +++ b/matita/matita/contribs/lambda_delta/ground_2/xoa.ma @@ -80,6 +80,14 @@ inductive ex3_3 (A0,A1,A2:Type[0]) (P0,P1,P2:A0→A1→A2→Prop) : Prop ≝ interpretation "multiple existental quantifier (3, 3)" 'Ex P0 P1 P2 = (ex3_3 ? ? ? P0 P1 P2). +(* multiple existental quantifier (3, 4) *) + +inductive ex3_4 (A0,A1,A2,A3:Type[0]) (P0,P1,P2:A0→A1→A2→A3→Prop) : Prop ≝ + | ex3_4_intro: ∀x0,x1,x2,x3. P0 x0 x1 x2 x3 → P1 x0 x1 x2 x3 → P2 x0 x1 x2 x3 → ex3_4 ? ? ? ? ? ? ? +. + +interpretation "multiple existental quantifier (3, 4)" 'Ex P0 P1 P2 = (ex3_4 ? ? ? ? P0 P1 P2). + (* multiple existental quantifier (4, 2) *) inductive ex4_2 (A0,A1:Type[0]) (P0,P1,P2,P3:A0→A1→Prop) : Prop ≝ @@ -128,14 +136,6 @@ inductive ex5_4 (A0,A1,A2,A3:Type[0]) (P0,P1,P2,P3,P4:A0→A1→A2→A3→Prop) interpretation "multiple existental quantifier (5, 4)" 'Ex P0 P1 P2 P3 P4 = (ex5_4 ? ? ? ? P0 P1 P2 P3 P4). -(* multiple existental quantifier (5, 5) *) - -inductive ex5_5 (A0,A1,A2,A3,A4:Type[0]) (P0,P1,P2,P3,P4:A0→A1→A2→A3→A4→Prop) : Prop ≝ - | ex5_5_intro: ∀x0,x1,x2,x3,x4. P0 x0 x1 x2 x3 x4 → P1 x0 x1 x2 x3 x4 → P2 x0 x1 x2 x3 x4 → P3 x0 x1 x2 x3 x4 → P4 x0 x1 x2 x3 x4 → ex5_5 ? ? ? ? ? ? ? ? ? ? -. - -interpretation "multiple existental quantifier (5, 5)" 'Ex P0 P1 P2 P3 P4 = (ex5_5 ? ? ? ? ? P0 P1 P2 P3 P4). - (* multiple existental quantifier (6, 4) *) inductive ex6_4 (A0,A1,A2,A3:Type[0]) (P0,P1,P2,P3,P4,P5:A0→A1→A2→A3→Prop) : Prop ≝ diff --git a/matita/matita/contribs/lambda_delta/ground_2/xoa_notation.ma b/matita/matita/contribs/lambda_delta/ground_2/xoa_notation.ma index e1e2240ce..44453eae0 100644 --- a/matita/matita/contribs/lambda_delta/ground_2/xoa_notation.ma +++ b/matita/matita/contribs/lambda_delta/ground_2/xoa_notation.ma @@ -94,6 +94,16 @@ notation < "hvbox(∃∃ ident x0 , ident x1 , ident x2 break . term 19 P0 break non associative with precedence 20 for @{ 'Ex (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.$P0) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.$P1) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.$P2) }. +(* multiple existental quantifier (3, 4) *) + +notation > "hvbox(∃∃ ident x0 , ident x1 , ident x2 , ident x3 break . term 19 P0 break & term 19 P1 break & term 19 P2)" + non associative with precedence 20 + for @{ 'Ex (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.$P0) (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.$P1) (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.$P2) }. + +notation < "hvbox(∃∃ ident x0 , ident x1 , ident x2 , ident x3 break . term 19 P0 break & term 19 P1 break & term 19 P2)" + non associative with precedence 20 + for @{ 'Ex (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P0) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P1) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P2) }. + (* multiple existental quantifier (4, 2) *) notation > "hvbox(∃∃ ident x0 , ident x1 break . term 19 P0 break & term 19 P1 break & term 19 P2 break & term 19 P3)" @@ -154,16 +164,6 @@ notation < "hvbox(∃∃ ident x0 , ident x1 , ident x2 , ident x3 break . term non associative with precedence 20 for @{ 'Ex (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P0) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P1) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P2) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P3) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.$P4) }. -(* multiple existental quantifier (5, 5) *) - -notation > "hvbox(∃∃ ident x0 , ident x1 , ident x2 , ident x3 , ident x4 break . term 19 P0 break & term 19 P1 break & term 19 P2 break & term 19 P3 break & term 19 P4)" - non associative with precedence 20 - for @{ 'Ex (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.λ${ident x4}.$P0) (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.λ${ident x4}.$P1) (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.λ${ident x4}.$P2) (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.λ${ident x4}.$P3) (λ${ident x0}.λ${ident x1}.λ${ident x2}.λ${ident x3}.λ${ident x4}.$P4) }. - -notation < "hvbox(∃∃ ident x0 , ident x1 , ident x2 , ident x3 , ident x4 break . term 19 P0 break & term 19 P1 break & term 19 P2 break & term 19 P3 break & term 19 P4)" - non associative with precedence 20 - for @{ 'Ex (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.λ${ident x4}:$T4.$P0) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.λ${ident x4}:$T4.$P1) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.λ${ident x4}:$T4.$P2) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.λ${ident x4}:$T4.$P3) (λ${ident x0}:$T0.λ${ident x1}:$T1.λ${ident x2}:$T2.λ${ident x3}:$T3.λ${ident x4}:$T4.$P4) }. - (* multiple existental quantifier (6, 4) *) notation > "hvbox(∃∃ ident x0 , ident x1 , ident x2 , ident x3 break . term 19 P0 break & term 19 P1 break & term 19 P2 break & term 19 P3 break & term 19 P4 break & term 19 P5)" diff --git a/matita/matita/lib/basics/star.ma b/matita/matita/lib/basics/star.ma index c8d2a9473..1e2a48000 100644 --- a/matita/matita/lib/basics/star.ma +++ b/matita/matita/lib/basics/star.ma @@ -46,7 +46,7 @@ qed. (* star *) inductive star (A:Type[0]) (R:relation A) (a:A): A → Prop ≝ - |inj: ∀b,c.star A R a b → R b c → star A R a c + |sstep: ∀b,c.star A R a b → R b c → star A R a c |refl: star A R a a. lemma R_to_star: ∀A,R,a,b. R a b → star A R a b. @@ -93,22 +93,22 @@ qed. (* right associative version of star *) inductive starl (A:Type[0]) (R:relation A) : A → A → Prop ≝ - |injl: ∀a,b,c.R a b → starl A R b c → starl A R a c + |sstepl: ∀a,b,c.R a b → starl A R b c → starl A R a c |refll: ∀a.starl A R a a. lemma starl_comp : ∀A,R,a,b,c. starl A R a b → R b c → starl A R a c. #A #R #a #b #c #Hstar elim Hstar - [#a1 #b1 #c1 #Rab #sbc #Hind #a1 @(injl … Rab) @Hind // - |#a1 #Rac @(injl … Rac) // + [#a1 #b1 #c1 #Rab #sbc #Hind #a1 @(sstepl … Rab) @Hind // + |#a1 #Rac @(sstepl … Rac) // ] qed. lemma star_compl : ∀A,R,a,b,c. R a b → star A R b c → star A R a c. #A #R #a #b #c #Rab #Hstar elim Hstar - [#b1 #c1 #sbb1 #Rb1c1 #Hind @(inj … Rb1c1) @Hind - |@(inj … Rab) // + [#b1 #c1 #sbb1 #Rb1c1 #Hind @(sstep … Rb1c1) @Hind + |@(sstep … Rab) // ] qed. -- 2.39.2