From 5117f4af452934db436f22326f35d90f757bdf8a Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Sun, 31 Aug 2014 18:13:55 +0000 Subject: [PATCH] - new stand-alone definition of lstas (sta and old lstas parked in etc) - PARTIAL COMMIT: we issue just the components "static" and "unfold" --- .../lambdadelta/basic_2/etc/sta/da_aaa.ma | 24 ++ .../basic_2/{static => etc/sta}/da_sta.ma | 0 .../lambdadelta/basic_2/etc/sta/lstas.ma | 133 ++++++++++ .../lambdadelta/basic_2/etc/sta/lstas_aaa.ma | 23 ++ .../basic_2/{unfold => etc/sta}/lstas_alt.ma | 0 .../lambdadelta/basic_2/etc/sta/lstas_da.ma | 40 +++ .../lambdadelta/basic_2/etc/sta/lstas_lift.ma | 81 +++++++ .../basic_2/etc/sta/lstas_lstas.ma | 51 ++++ .../basic_2/{static => etc/sta}/sta.ma | 0 .../basic_2/{static => etc/sta}/sta_aaa.ma | 0 .../basic_2/{static => etc/sta}/sta_lift.ma | 0 .../{static => etc/sta}/sta_llpx_sn.ma | 0 .../basic_2/{static => etc/sta}/sta_sta.ma | 0 .../relations => etc/sta}/statictype_5.ma | 0 .../sta}/statictypestaralt_6.ma | 0 .../lambdadelta/basic_2/static/da_aaa.ma | 13 +- .../lambdadelta/basic_2/unfold/lstas.ma | 229 +++++++++++------- .../lambdadelta/basic_2/unfold/lstas_aaa.ma | 39 ++- .../lambdadelta/basic_2/unfold/lstas_da.ma | 79 +++++- .../lambdadelta/basic_2/unfold/lstas_lift.ma | 202 +++++++++++---- .../lambdadelta/basic_2/unfold/lstas_lstas.ma | 111 +++++++-- 21 files changed, 853 insertions(+), 172 deletions(-) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/sta/da_aaa.ma rename matita/matita/contribs/lambdadelta/basic_2/{static => etc/sta}/da_sta.ma (100%) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_aaa.ma rename matita/matita/contribs/lambdadelta/basic_2/{unfold => etc/sta}/lstas_alt.ma (100%) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_da.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_lift.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_lstas.ma rename matita/matita/contribs/lambdadelta/basic_2/{static => etc/sta}/sta.ma (100%) rename matita/matita/contribs/lambdadelta/basic_2/{static => etc/sta}/sta_aaa.ma (100%) rename matita/matita/contribs/lambdadelta/basic_2/{static => etc/sta}/sta_lift.ma (100%) rename matita/matita/contribs/lambdadelta/basic_2/{static => etc/sta}/sta_llpx_sn.ma (100%) rename matita/matita/contribs/lambdadelta/basic_2/{static => etc/sta}/sta_sta.ma (100%) rename matita/matita/contribs/lambdadelta/basic_2/{notation/relations => etc/sta}/statictype_5.ma (100%) rename matita/matita/contribs/lambdadelta/basic_2/{notation/relations => etc/sta}/statictypestaralt_6.ma (100%) diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/sta/da_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/da_aaa.ma new file mode 100644 index 000000000..dccb10f9b --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/da_aaa.ma @@ -0,0 +1,24 @@ +(**************************************************************************) +(* ___ *) +(* ||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/static/da_sta.ma". +include "basic_2/static/sta_aaa.ma". + +(* DEGREE ASSIGNMENT FOR TERMS **********************************************) + +(* Properties on atomic arity assignment for terms **************************) + +lemma aaa_da: ∀h,g,G,L,T,A. ⦃G, L⦄ ⊢ T ⁝ A → ∃l. ⦃G, L⦄ ⊢ T ▪[h, g] l. +#h #g #G #L #T #A #H elim (aaa_sta h … H) -A /2 width=2 by sta_da/ +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/da_sta.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/da_sta.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/static/da_sta.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/da_sta.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas.ma new file mode 100644 index 000000000..feed03e3f --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas.ma @@ -0,0 +1,133 @@ +(**************************************************************************) +(* ___ *) +(* ||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/notation/relations/statictypestar_6.ma". +include "basic_2/static/sta.ma". + +(* NAT-ITERATED STATIC TYPE ASSIGNMENT FOR TERMS ****************************) + +definition lstas: ∀h. genv → lenv → nat → relation term ≝ + λh,G,L. lstar … (sta h G L). + +interpretation "nat-iterated static type assignment (term)" + 'StaticTypeStar h G L l T U = (lstas h G L l T U). + +(* Basic eliminators ********************************************************) + +lemma lstas_ind_sn: ∀h,G,L,U2. ∀R:relation2 nat term. + R 0 U2 → ( + ∀l,T,U1. ⦃G, L⦄ ⊢ T •[h] U1 → ⦃G, L⦄ ⊢ U1 •* [h, l] U2 → + R l U1 → R (l+1) T + ) → + ∀l,T. ⦃G, L⦄ ⊢ T •*[h, l] U2 → R l T. +/3 width=5 by lstar_ind_l/ qed-. + +lemma lstas_ind_dx: ∀h,G,L,T. ∀R:relation2 nat term. + R 0 T → ( + ∀l,U1,U2. ⦃G, L⦄ ⊢ T •* [h, l] U1 → ⦃G, L⦄ ⊢ U1 •[h] U2 → + R l U1 → R (l+1) U2 + ) → + ∀l,U. ⦃G, L⦄ ⊢ T •*[h, l] U → R l U. +/3 width=5 by lstar_ind_r/ qed-. + +(* Basic inversion lemmas ***************************************************) + +lemma lstas_inv_O: ∀h,G,L,T,U. ⦃G, L⦄ ⊢ T •*[h, 0] U → T = U. +/2 width=4 by lstar_inv_O/ qed-. + +lemma lstas_inv_SO: ∀h,G,L,T,U. ⦃G, L⦄ ⊢ T •*[h, 1] U → ⦃G, L⦄ ⊢ T •[h] U. +/2 width=1 by lstar_inv_step/ qed-. + +lemma lstas_inv_step_sn: ∀h,G,L,T1,T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l+1] T2 → + ∃∃T. ⦃G, L⦄ ⊢ T1 •[h] T & ⦃G, L⦄ ⊢ T •*[h, l] T2. +/2 width=3 by lstar_inv_S/ qed-. + +lemma lstas_inv_step_dx: ∀h,G,L,T1,T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l+1] T2 → + ∃∃T. ⦃G, L⦄ ⊢ T1 •*[h, l] T & ⦃G, L⦄ ⊢ T •[h] T2. +/2 width=3 by lstar_inv_S_dx/ qed-. + +lemma lstas_inv_sort1: ∀h,G,L,X,k,l. ⦃G, L⦄ ⊢ ⋆k •*[h, l] X → X = ⋆((next h)^l k). +#h #G #L #X #k #l #H @(lstas_ind_dx … H) -X -l // +#l #X #X0 #_ #H #IHX destruct +lapply (sta_inv_sort1 … H) -H #H destruct +>iter_SO // +qed-. + +lemma lstas_inv_gref1: ∀h,G,L,X,p,l. ⦃G, L⦄ ⊢ §p •*[h, l+1] X → ⊥. +#h #G #L #X #p #l #H elim (lstas_inv_step_sn … H) -H +#U #H #HUX elim (sta_inv_gref1 … H) +qed-. + +lemma lstas_inv_bind1: ∀h,a,I,G,L,V,T,X,l. ⦃G, L⦄ ⊢ ⓑ{a,I}V.T •*[h, l] X → + ∃∃U. ⦃G, L.ⓑ{I}V⦄ ⊢ T •*[h, l] U & X = ⓑ{a,I}V.U. +#h #a #I #G #L #V #T #X #l #H @(lstas_ind_dx … H) -X -l /2 width=3 by ex2_intro/ +#l #X #X0 #_ #HX0 * #U #HTU #H destruct +elim (sta_inv_bind1 … HX0) -HX0 #U0 #HU0 #H destruct /3 width=3 by lstar_dx, ex2_intro/ +qed-. + +lemma lstas_inv_appl1: ∀h,G,L,V,T,X,l. ⦃G, L⦄ ⊢ ⓐV.T •*[h, l] X → + ∃∃U. ⦃G, L⦄ ⊢ T •*[h, l] U & X = ⓐV.U. +#h #G #L #V #T #X #l #H @(lstas_ind_dx … H) -X -l /2 width=3 by ex2_intro/ +#l #X #X0 #_ #HX0 * #U #HTU #H destruct +elim (sta_inv_appl1 … HX0) -HX0 #U0 #HU0 #H destruct /3 width=3 by lstar_dx, ex2_intro/ +qed-. + +lemma lstas_inv_cast1: ∀h,G,L,W,T,U,l. ⦃G, L⦄ ⊢ ⓝW.T •*[h, l+1] U → ⦃G, L⦄ ⊢ T •*[h, l+1] U. +#h #G #L #W #T #X #l #H elim (lstas_inv_step_sn … H) -H +#U #H #HUX lapply (sta_inv_cast1 … H) -H /2 width=3 by lstar_S/ +qed-. + +(* Basic properties *********************************************************) + +lemma lstas_refl: ∀h,G,L. reflexive … (lstas h G L 0). +// qed. + +lemma sta_lstas: ∀h,G,L,T,U. ⦃G, L⦄ ⊢ T •[h] U → ⦃G, L⦄ ⊢ T •*[h, 1] U. +/2 width=1 by lstar_step/ qed. + +lemma lstas_step_sn: ∀h,G,L,T1,U1,U2,l. ⦃G, L⦄ ⊢ T1 •[h] U1 → ⦃G, L⦄ ⊢ U1 •*[h, l] U2 → + ⦃G, L⦄ ⊢ T1 •*[h, l+1] U2. +/2 width=3 by lstar_S/ qed. + +lemma lstas_step_dx: ∀h,G,L,T1,T2,U2,l. ⦃G, L⦄ ⊢ T1 •*[h, l] T2 → ⦃G, L⦄ ⊢ T2 •[h] U2 → + ⦃G, L⦄ ⊢ T1 •*[h, l+1] U2. +/2 width=3 by lstar_dx/ qed. + +lemma lstas_split: ∀h,G,L. inv_ltransitive … (lstas h G L). +/2 width=1 by lstar_inv_ltransitive/ qed-. + +lemma lstas_sort: ∀h,G,L,l,k. ⦃G, L⦄ ⊢ ⋆k •*[h, l] ⋆((next h)^l k). +#h #G #L #l @(nat_ind_plus … l) -l // +#l #IHl #k >iter_SO /2 width=3 by sta_sort, lstas_step_dx/ +qed. + +lemma lstas_bind: ∀h,I,G,L,V,T,U,l. ⦃G, L.ⓑ{I}V⦄ ⊢ T •*[h, l] U → + ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V.T •*[h, l] ⓑ{a,I}V.U. +#h #I #G #L #V #T #U #l #H @(lstas_ind_dx … H) -U -l /3 width=3 by sta_bind, lstar_O, lstas_step_dx/ +qed. + +lemma lstas_appl: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l] U → + ∀V.⦃G, L⦄ ⊢ ⓐV.T •*[h, l] ⓐV.U. +#h #G #L #T #U #l #H @(lstas_ind_dx … H) -U -l /3 width=3 by sta_appl, lstar_O, lstas_step_dx/ +qed. + +lemma lstas_cast: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l+1] U → + ∀W. ⦃G, L⦄ ⊢ ⓝW.T •*[h, l+1] U. +#h #G #L #T #U #l #H elim (lstas_inv_step_sn … H) -H /3 width=3 by sta_cast, lstas_step_sn/ +qed. + +(* Basic_1: removed theorems 7: + sty1_abbr sty1_appl sty1_bind sty1_cast2 + sty1_correct sty1_lift sty1_trans +*) diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_aaa.ma new file mode 100644 index 000000000..7497f44b6 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_aaa.ma @@ -0,0 +1,23 @@ +(**************************************************************************) +(* ___ *) +(* ||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/static/sta_aaa.ma". +include "basic_2/unfold/lstas.ma". + +(* NAT-ITERATED STATIC TYPE ASSIGNMENT FOR TERMS ****************************) + +(* Properties on atomic arity assignment for terms **************************) + +lemma lstas_aaa_conf: ∀h,G,L,l. Conf3 … (aaa G L) (lstas h G L l). +/3 width=6 by sta_aaa_conf, lstar_Conf3/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_alt.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_alt.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_alt.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_alt.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_da.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_da.ma new file mode 100644 index 000000000..8b11d1dc0 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/lstas_da.ma @@ -0,0 +1,40 @@ +(**************************************************************************) +(* ___ *) +(* ||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/lstas.ma". +include "basic_2/static/da_sta.ma". + +(* NAT-ITERATED STATIC TYPE ASSIGNMENT FOR TERMS ****************************) + +(* Properties on degree assignment for terms ********************************) + +lemma lstas_da_conf: ∀h,g,G,L,T,U,l1. ⦃G, L⦄ ⊢ T •*[h, l1] U → + ∀l2. ⦃G, L⦄ ⊢ T ▪[h, g] l2 → ⦃G, L⦄ ⊢ U ▪[h, g] l2-l1. +#h #g #G #L #T #U #l1 #H @(lstas_ind_dx … H) -U -l1 // +#l1 #U #U0 #_ #HU0 #IHTU #l2 #HT +(plus_minus_m_m … Hl12) in ⊢ (%→?); -Hl12 >commutative_plus #H +elim (lstas_split … H) -H #U #HTU +>(lstas_mono … HTU … HTU1) -T // +qed-. + +(* Advanced properties ******************************************************) + +lemma lstas_sta_conf_pos: ∀h,G,L,T,U1. ⦃G, L⦄ ⊢ T •[h] U1 → + ∀U2,l. ⦃G, L⦄ ⊢ T •*[h, l+1] U2 → ⦃G, L⦄ ⊢ U1 •*[h, l] U2. +#h #G #L #T #U1 #HTU1 #U2 #l #HTU2 +lapply (lstas_conf_le … T U1 1 … HTU2) -HTU2 /2 width=1 by sta_lstas/ +qed-. + +lemma lstas_strip_pos: ∀h,G,L,T1,U1. ⦃G, L⦄ ⊢ T1 •[h] U1 → + ∀T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l+1] T2 → + ∃∃U2. ⦃G, L⦄ ⊢ T2 •[h] U2 & ⦃G, L⦄ ⊢ U1 •*[h, l+1] U2. +#h #G #L #T1 #U1 #HTU1 #T2 #l #HT12 +elim (lstas_fwd_correct … HTU1 … HT12) +lapply (lstas_sta_conf_pos … HTU1 … HT12) -T1 /3 width=5 by lstas_step_dx, ex2_intro/ +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/sta.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/static/sta.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/sta_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_aaa.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/static/sta_aaa.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_aaa.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/sta_lift.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_lift.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/static/sta_lift.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_lift.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/sta_llpx_sn.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_llpx_sn.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/static/sta_llpx_sn.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_llpx_sn.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/sta_sta.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_sta.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/static/sta_sta.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/sta_sta.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/statictype_5.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/statictype_5.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/notation/relations/statictype_5.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/statictype_5.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/statictypestaralt_6.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/sta/statictypestaralt_6.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/notation/relations/statictypestaralt_6.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/sta/statictypestaralt_6.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/da_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/static/da_aaa.ma index dccb10f9b..7e9e4cc88 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/static/da_aaa.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/static/da_aaa.ma @@ -12,13 +12,20 @@ (* *) (**************************************************************************) -include "basic_2/static/da_sta.ma". -include "basic_2/static/sta_aaa.ma". +include "basic_2/static/aaa_lift.ma". +include "basic_2/static/da.ma". (* DEGREE ASSIGNMENT FOR TERMS **********************************************) (* Properties on atomic arity assignment for terms **************************) lemma aaa_da: ∀h,g,G,L,T,A. ⦃G, L⦄ ⊢ T ⁝ A → ∃l. ⦃G, L⦄ ⊢ T ▪[h, g] l. -#h #g #G #L #T #A #H elim (aaa_sta h … H) -A /2 width=2 by sta_da/ +#h #g #G #L #T #A #H elim H -G -L -T -A +[ #G #L #k elim (deg_total h g k) /3 width=2 by da_sort, ex_intro/ +| * #G #L #K #V #B #i #HLK #_ * /3 width=5 by da_ldef, da_ldec, ex_intro/ +| #a #G #L #V #T #B #A #_ #_ #_ * /3 width=2 by da_bind, ex_intro/ +| #a #G #L #V #T #B #A #_ #_ #_ * /3 width=2 by da_bind, ex_intro/ +| #G #L #V #T #B #A #_ #_ #_ * /3 width=2 by da_flat, ex_intro/ +| #G #L #W #T #A #_ #_ #_ * /3 width=2 by da_flat, ex_intro/ +] qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas.ma b/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas.ma index feed03e3f..2a81f4c06 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas.ma @@ -13,119 +13,176 @@ (**************************************************************************) include "basic_2/notation/relations/statictypestar_6.ma". -include "basic_2/static/sta.ma". +include "basic_2/grammar/genv.ma". +include "basic_2/substitution/drop.ma". +include "basic_2/static/sh.ma". (* NAT-ITERATED STATIC TYPE ASSIGNMENT FOR TERMS ****************************) -definition lstas: ∀h. genv → lenv → nat → relation term ≝ - λh,G,L. lstar … (sta h G L). +(* activate genv *) +inductive lstas (h): nat → relation4 genv lenv term term ≝ +| lstas_sort: ∀G,L,l,k. lstas h l G L (⋆k) (⋆((next h)^l k)) +| lstas_ldef: ∀G,L,K,V,W,U,i,l. ⇩[i] L ≡ K.ⓓV → lstas h l G K V W → + ⇧[0, i+1] W ≡ U → lstas h l G L (#i) U +| lstas_zero: ∀G,L,K,W,V,i. ⇩[i] L ≡ K.ⓛW → lstas h 0 G K W V → + lstas h 0 G L (#i) (#i) +| lstas_succ: ∀G,L,K,W,V,U,i,l. ⇩[i] L ≡ K.ⓛW → lstas h l G K W V → + ⇧[0, i+1] V ≡ U → lstas h (l+1) G L (#i) U +| lstas_bind: ∀a,I,G,L,V,T,U,l. lstas h l G (L.ⓑ{I}V) T U → + lstas h l G L (ⓑ{a,I}V.T) (ⓑ{a,I}V.U) +| lstas_appl: ∀G,L,V,T,U,l. lstas h l G L T U → lstas h l G L (ⓐV.T) (ⓐV.U) +| lstas_cast: ∀G,L,W,T,U,l. lstas h l G L T U → lstas h l G L (ⓝW.T) U +. interpretation "nat-iterated static type assignment (term)" - 'StaticTypeStar h G L l T U = (lstas h G L l T U). - -(* Basic eliminators ********************************************************) - -lemma lstas_ind_sn: ∀h,G,L,U2. ∀R:relation2 nat term. - R 0 U2 → ( - ∀l,T,U1. ⦃G, L⦄ ⊢ T •[h] U1 → ⦃G, L⦄ ⊢ U1 •* [h, l] U2 → - R l U1 → R (l+1) T - ) → - ∀l,T. ⦃G, L⦄ ⊢ T •*[h, l] U2 → R l T. -/3 width=5 by lstar_ind_l/ qed-. - -lemma lstas_ind_dx: ∀h,G,L,T. ∀R:relation2 nat term. - R 0 T → ( - ∀l,U1,U2. ⦃G, L⦄ ⊢ T •* [h, l] U1 → ⦃G, L⦄ ⊢ U1 •[h] U2 → - R l U1 → R (l+1) U2 - ) → - ∀l,U. ⦃G, L⦄ ⊢ T •*[h, l] U → R l U. -/3 width=5 by lstar_ind_r/ qed-. + 'StaticTypeStar h G L l T U = (lstas h l G L T U). (* Basic inversion lemmas ***************************************************) -lemma lstas_inv_O: ∀h,G,L,T,U. ⦃G, L⦄ ⊢ T •*[h, 0] U → T = U. -/2 width=4 by lstar_inv_O/ qed-. - -lemma lstas_inv_SO: ∀h,G,L,T,U. ⦃G, L⦄ ⊢ T •*[h, 1] U → ⦃G, L⦄ ⊢ T •[h] U. -/2 width=1 by lstar_inv_step/ qed-. - -lemma lstas_inv_step_sn: ∀h,G,L,T1,T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l+1] T2 → - ∃∃T. ⦃G, L⦄ ⊢ T1 •[h] T & ⦃G, L⦄ ⊢ T •*[h, l] T2. -/2 width=3 by lstar_inv_S/ qed-. - -lemma lstas_inv_step_dx: ∀h,G,L,T1,T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l+1] T2 → - ∃∃T. ⦃G, L⦄ ⊢ T1 •*[h, l] T & ⦃G, L⦄ ⊢ T •[h] T2. -/2 width=3 by lstar_inv_S_dx/ qed-. +fact lstas_inv_sort1_aux: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l] U → ∀k0. T = ⋆k0 → + U = ⋆((next h)^l k0). +#h #G #L #T #U #l * -G -L -T -U -l +[ #G #L #l #k #k0 #H destruct // +| #G #L #K #V #W #U #i #l #_ #_ #_ #k0 #H destruct +| #G #L #K #W #V #i #_ #_ #k0 #H destruct +| #G #L #K #W #V #U #i #l #_ #_ #_ #k0 #H destruct +| #a #I #G #L #V #T #U #l #_ #k0 #H destruct +| #G #L #V #T #U #l #_ #k0 #H destruct +| #G #L #W #T #U #l #_ #k0 #H destruct +qed-. +(* Basic_1: was just: sty0_gen_sort *) lemma lstas_inv_sort1: ∀h,G,L,X,k,l. ⦃G, L⦄ ⊢ ⋆k •*[h, l] X → X = ⋆((next h)^l k). -#h #G #L #X #k #l #H @(lstas_ind_dx … H) -X -l // -#l #X #X0 #_ #H #IHX destruct -lapply (sta_inv_sort1 … H) -H #H destruct ->iter_SO // +/2 width=5 by lstas_inv_sort1_aux/ qed-. -lemma lstas_inv_gref1: ∀h,G,L,X,p,l. ⦃G, L⦄ ⊢ §p •*[h, l+1] X → ⊥. -#h #G #L #X #p #l #H elim (lstas_inv_step_sn … H) -H -#U #H #HUX elim (sta_inv_gref1 … H) +fact lstas_inv_lref1_aux: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l] U → ∀j. T = #j → ∨∨ + (∃∃K,V,W. ⇩[j] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V •*[h, l] W & + ⇧[0, j+1] W ≡ U + ) | + (∃∃K,W,V. ⇩[j] L ≡ K.ⓛW & ⦃G, K⦄ ⊢ W •*[h, 0] V & + U = #j & l = 0 + ) | + (∃∃K,W,V,l0. ⇩[j] L ≡ K.ⓛW & ⦃G, K⦄ ⊢ W •*[h, l0] V & + ⇧[0, j+1] V ≡ U & l = l0+1 + ). +#h #G #L #T #U #l * -G -L -T -U -l +[ #G #L #l #k #j #H destruct +| #G #L #K #V #W #U #i #l #HLK #HVW #HWU #j #H destruct /3 width=6 by or3_intro0, ex3_3_intro/ +| #G #L #K #W #V #i #HLK #HWV #j #H destruct /3 width=5 by or3_intro1, ex4_3_intro/ +| #G #L #K #W #V #U #i #l #HLK #HWV #HWU #j #H destruct /3 width=8 by or3_intro2, ex4_4_intro/ +| #a #I #G #L #V #T #U #l #_ #j #H destruct +| #G #L #V #T #U #l #_ #j #H destruct +| #G #L #W #T #U #l #_ #j #H destruct +] qed-. -lemma lstas_inv_bind1: ∀h,a,I,G,L,V,T,X,l. ⦃G, L⦄ ⊢ ⓑ{a,I}V.T •*[h, l] X → - ∃∃U. ⦃G, L.ⓑ{I}V⦄ ⊢ T •*[h, l] U & X = ⓑ{a,I}V.U. -#h #a #I #G #L #V #T #X #l #H @(lstas_ind_dx … H) -X -l /2 width=3 by ex2_intro/ -#l #X #X0 #_ #HX0 * #U #HTU #H destruct -elim (sta_inv_bind1 … HX0) -HX0 #U0 #HU0 #H destruct /3 width=3 by lstar_dx, ex2_intro/ +lemma lstas_inv_lref1: ∀h,G,L,X,i,l. ⦃G, L⦄ ⊢ #i •*[h, l] X → ∨∨ + (∃∃K,V,W. ⇩[i] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V •*[h, l] W & + ⇧[0, i+1] W ≡ X + ) | + (∃∃K,W,V. ⇩[i] L ≡ K.ⓛW & ⦃G, K⦄ ⊢ W •*[h, 0] V & + X = #i & l = 0 + ) | + (∃∃K,W,V,l0. ⇩[i] L ≡ K.ⓛW & ⦃G, K⦄ ⊢ W •*[h, l0] V & + ⇧[0, i+1] V ≡ X & l = l0+1 + ). +/2 width=3 by lstas_inv_lref1_aux/ qed-. -lemma lstas_inv_appl1: ∀h,G,L,V,T,X,l. ⦃G, L⦄ ⊢ ⓐV.T •*[h, l] X → - ∃∃U. ⦃G, L⦄ ⊢ T •*[h, l] U & X = ⓐV.U. -#h #G #L #V #T #X #l #H @(lstas_ind_dx … H) -X -l /2 width=3 by ex2_intro/ -#l #X #X0 #_ #HX0 * #U #HTU #H destruct -elim (sta_inv_appl1 … HX0) -HX0 #U0 #HU0 #H destruct /3 width=3 by lstar_dx, ex2_intro/ +lemma lstas_inv_lref1_O: ∀h,G,L,X,i. ⦃G, L⦄ ⊢ #i •*[h, 0] X → + (∃∃K,V,W. ⇩[i] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V •*[h, 0] W & + ⇧[0, i+1] W ≡ X + ) ∨ + (∃∃K,W,V. ⇩[i] L ≡ K.ⓛW & ⦃G, K⦄ ⊢ W •*[h, 0] V & + X = #i + ). +#h #G #L #X #i #H elim (lstas_inv_lref1 … H) -H * /3 width=6 by ex3_3_intro, or_introl, or_intror/ +#K #W #V #l #_ #_ #_ iter_SO /2 width=3 by sta_sort, lstas_step_dx/ -qed. +fact lstas_inv_appl1_aux: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l] U → ∀X,Y. T = ⓐY.X → + ∃∃Z. ⦃G, L⦄ ⊢ X •*[h, l] Z & U = ⓐY.Z. +#h #G #L #T #U #l * -G -L -T -U -l +[ #G #L #l #k #X #Y #H destruct +| #G #L #K #V #W #U #i #l #_ #_ #_ #X #Y #H destruct +| #G #L #K #W #V #i #_ #_ #X #Y #H destruct +| #G #L #K #W #V #U #i #l #_ #_ #_ #X #Y #H destruct +| #a #I #G #L #V #T #U #l #_ #X #Y #H destruct +| #G #L #V #T #U #l #HTU #X #Y #H destruct /2 width=3 by ex2_intro/ +| #G #L #W #T #U #l #_ #X #Y #H destruct +] +qed-. -lemma lstas_bind: ∀h,I,G,L,V,T,U,l. ⦃G, L.ⓑ{I}V⦄ ⊢ T •*[h, l] U → - ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V.T •*[h, l] ⓑ{a,I}V.U. -#h #I #G #L #V #T #U #l #H @(lstas_ind_dx … H) -U -l /3 width=3 by sta_bind, lstar_O, lstas_step_dx/ -qed. +(* Basic_1: was just: sty0_gen_appl *) +lemma lstas_inv_appl1: ∀h,G,L,V,T,X,l. ⦃G, L⦄ ⊢ ⓐV.T •*[h, l] X → + ∃∃U. ⦃G, L⦄ ⊢ T •*[h, l] U & X = ⓐV.U. +/2 width=3 by lstas_inv_appl1_aux/ +qed-. -lemma lstas_appl: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l] U → - ∀V.⦃G, L⦄ ⊢ ⓐV.T •*[h, l] ⓐV.U. -#h #G #L #T #U #l #H @(lstas_ind_dx … H) -U -l /3 width=3 by sta_appl, lstar_O, lstas_step_dx/ -qed. +fact lstas_inv_cast1_aux: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l] U → ∀X,Y. T = ⓝY.X → + ⦃G, L⦄ ⊢ X •*[h, l] U. +#h #G #L #T #U #l * -G -L -T -U -l +[ #G #L #l #k #X #Y #H destruct +| #G #L #K #V #W #U #i #l #_ #_ #_ #X #Y #H destruct +| #G #L #K #W #V #i #_ #_ #X #Y #H destruct +| #G #L #K #W #V #U #i #l #_ #_ #_ #X #Y #H destruct +| #a #I #G #L #V #T #U #l #_ #X #Y #H destruct +| #G #L #V #T #U #l #_ #X #Y #H destruct +| #G #L #W #T #U #l #HTU #X #Y #H destruct // +] +qed-. -lemma lstas_cast: ∀h,G,L,T,U,l. ⦃G, L⦄ ⊢ T •*[h, l+1] U → - ∀W. ⦃G, L⦄ ⊢ ⓝW.T •*[h, l+1] U. -#h #G #L #T #U #l #H elim (lstas_inv_step_sn … H) -H /3 width=3 by sta_cast, lstas_step_sn/ -qed. +(* Basic_1: was just: sty0_gen_cast *) +lemma lstas_inv_cast1: ∀h,G,L,W,T,U,l. ⦃G, L⦄ ⊢ ⓝW.T •*[h, l] U → ⦃G, L⦄ ⊢ T •*[h, l] U. +/2 width=4 by lstas_inv_cast1_aux/ +qed-. (* Basic_1: removed theorems 7: sty1_abbr sty1_appl sty1_bind sty1_cast2 diff --git a/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_aaa.ma index 7497f44b6..434c6e991 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_aaa.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_aaa.ma @@ -12,12 +12,43 @@ (* *) (**************************************************************************) -include "basic_2/static/sta_aaa.ma". -include "basic_2/unfold/lstas.ma". +include "basic_2/static/aaa_lift.ma". +include "basic_2/unfold/lstas_lstas.ma". (* NAT-ITERATED STATIC TYPE ASSIGNMENT FOR TERMS ****************************) (* Properties on atomic arity assignment for terms **************************) -lemma lstas_aaa_conf: ∀h,G,L,l. Conf3 … (aaa G L) (lstas h G L l). -/3 width=6 by sta_aaa_conf, lstar_Conf3/ qed-. +lemma aaa_lstas: ∀h,G,L,T,A. ⦃G, L⦄ ⊢ T ⁝ A → ∀l. + ∃∃U. ⦃G, L⦄ ⊢ T •*[h, l] U & ⦃G, L⦄ ⊢ U ⁝ A. +#h #G #L #T #A #H elim H -G -L -T -A +[ /2 width=3 by ex2_intro/ +| * #G #L #K #V #B #i #HLK #HV #IHV #l + [ elim (IHV l) -IHV #W + elim (lift_total W 0 (i+1)) + lapply (drop_fwd_drop2 … HLK) + /3 width=10 by lstas_ldef, aaa_lift, ex2_intro/ + | @(nat_ind_plus … l) -l + [ elim (IHV 0) -IHV /3 width=7 by lstas_zero, aaa_lref, ex2_intro/ + | #l #_ elim (IHV l) -IHV #W + elim (lift_total W 0 (i+1)) + lapply (drop_fwd_drop2 … HLK) + /3 width=10 by lstas_succ, aaa_lift, ex2_intro/ + ] + ] +| #a #G #L #V #T #B #A #HV #_ #_ #IHT #l elim (IHT l) -IHT + /3 width=7 by lstas_bind, aaa_abbr, ex2_intro/ +| #a #G #L #V #T #B #A #HV #_ #_ #IHT #l elim (IHT l) -IHT + /3 width=6 by lstas_bind, aaa_abst, ex2_intro/ +| #G #L #V #T #B #A #HV #_ #_ #IHT #l elim (IHT l) -IHT + /3 width=6 by lstas_appl, aaa_appl, ex2_intro/ +| #G #L #W #T #A #HW #_ #_ #IHT #l elim (IHT l) -IHT + /3 width=3 by lstas_cast, aaa_cast, ex2_intro/ +] +qed-. + +lemma lstas_aaa_conf: ∀h,G,L,l. Conf3 … (aaa G L) (lstas h l G L). +#h #G #L #l #A #T #HT #U #HTU +elim (aaa_lstas h … HT l) -HT #X #HTX +lapply (lstas_mono … HTX … HTU) -T // +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_da.ma b/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_da.ma index 8b11d1dc0..8d1feca9f 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_da.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/unfold/lstas_da.ma @@ -12,29 +12,84 @@ (* *) (**************************************************************************) -include "basic_2/unfold/lstas.ma". -include "basic_2/static/da_sta.ma". +include "basic_2/static/da_da.ma". +include "basic_2/unfold/lstas_lstas.ma". (* NAT-ITERATED STATIC TYPE ASSIGNMENT FOR TERMS ****************************) (* Properties on degree assignment for terms ********************************) -lemma lstas_da_conf: ∀h,g,G,L,T,U,l1. ⦃G, L⦄ ⊢ T •*[h, l1] U → - ∀l2. ⦃G, L⦄ ⊢ T ▪[h, g] l2 → ⦃G, L⦄ ⊢ U ▪[h, g] l2-l1. -#h #g #G #L #T #U #l1 #H @(lstas_ind_dx … H) -U -l1 // -#l1 #U #U0 #_ #HU0 #IHTU #l2 #HT -(lift_inv_sort1 … H1) -X1 + >(lift_inv_sort1 … H2) -X2 // +| #G #L1 #K1 #V1 #W1 #W #i #l #HLK1 #_ #HW1 #IHVW1 #L2 #s #d #e #HL21 #X #H #U2 #HWU2 + elim (lift_inv_lref1 … H) * #Hid #H destruct + [ elim (lift_trans_ge … HW1 … HWU2) -W // #W2 #HW12 #HWU2 + elim (drop_trans_le … HL21 … HLK1) -L1 /2 width=2 by lt_to_le/ #X #HLK2 #H + elim (drop_inv_skip2 … H) -H /2 width=1 by lt_plus_to_minus_r/ -Hid #K2 #V2 #HK21 #HV12 #H destruct + /3 width=9 by lstas_ldef/ + | lapply (lift_trans_be … HW1 … HWU2 ? ?) -W /2 width=1 by le_S/ #HW1U2 + lapply (drop_trans_ge … HL21 … HLK1 ?) -L1 /3 width=9 by lstas_ldef, drop_inv_gen/ + ] +| #G #L1 #K1 #V1 #W1 #i #HLK1 #_ #IHVW1 #L2 #s #d #e #HL21 #X #H #U2 #HWU2 + >(lift_mono … HWU2 … H) -U2 + elim (lift_inv_lref1 … H) * #Hid #H destruct + [ elim (lift_total W1 (d-i-1) e) #W2 #HW12 + elim (drop_trans_le … HL21 … HLK1) -L1 /2 width=2 by lt_to_le/ #X #HLK2 #H + elim (drop_inv_skip2 … H) -H /2 width=1 by lt_plus_to_minus_r/ -Hid #K2 #V2 #HK21 #HV12 #H destruct + /3 width=10 by lstas_zero/ + | lapply (drop_trans_ge … HL21 … HLK1 ?) -L1 + /3 width=10 by lstas_zero, drop_inv_gen/ + ] +| #G #L1 #K1 #W1 #V1 #W #i #l #HLK1 #_ #HW1 #IHWV1 #L2 #s #d #e #HL21 #X #H #U2 #HWU2 + elim (lift_inv_lref1 … H) * #Hid #H destruct + [ elim (lift_trans_ge … HW1 … HWU2) -W // (lift_inv_sort2 … H) -X /2 width=3 by lstas_sort, lift_sort, ex2_intro/ +| #G #L2 #K2 #V2 #W2 #W #i #l #HLK2 #HVW2 #HW2 #IHVW2 #L1 #s #d #e #HL21 #X #H + elim (lift_inv_lref2 … H) * #Hid #H destruct [ -HVW2 | -IHVW2 ] + [ elim (drop_conf_lt … HL21 … HLK2) -L2 // #K1 #V1 #HLK1 #HK21 #HV12 + elim (IHVW2 … HK21 … HV12) -K2 -V2 #W1 #HW12 #HVW1 + elim (lift_trans_le … HW12 … HW2) -W2 // >minus_plus minus_minus_m_m /3 width=8 by lstas_ldef, le_S, ex2_intro/ + ] +| #G #L2 #K2 #W2 #V2 #i #HLK2 #HWV2 #IHWV2 #L1 #s #d #e #HL21 #X #H + elim (lift_inv_lref2 … H) * #Hid #H destruct [ -HWV2 | -IHWV2 ] + [ elim (drop_conf_lt … HL21 … HLK2) -L2 // #K1 #W1 #HLK1 #HK21 #HW12 + elim (IHWV2 … HK21 … HW12) -K2 + /3 width=5 by lstas_zero, lift_lref_lt, ex2_intro/ + | lapply (drop_conf_ge … HL21 … HLK2 ?) -L2 + /3 width=5 by lstas_zero, lift_lref_ge_minus, ex2_intro/ + ] +| #G #L2 #K2 #W2 #V2 #W #i #l #HLK2 #HWV2 #HW2 #IHWV2 #L1 #s #d #e #HL21 #X #H + elim (lift_inv_lref2 … H) * #Hid #H destruct [ -HWV2 | -IHWV2 ] + [ elim (drop_conf_lt … HL21 … HLK2) -L2 // #K1 #W1 #HLK1 #HK21 #HW12 + elim (IHWV2 … HK21 … HW12) -K2 #V1 #HV12 #HWV1 + elim (lift_trans_le … HV12 … HW2) -W2 // >minus_plus minus_minus_m_m /3 width=8 by lstas_succ, le_S, ex2_intro/ + ] +| #a #I #G #L2 #V2 #T2 #U2 #l #_ #IHTU2 #L1 #s #d #e #HL21 #X #H + elim (lift_inv_bind2 … H) -H #V1 #T1 #HV12 #HT12 #H destruct + elim (IHTU2 (L1.ⓑ{I}V1) … HT12) -IHTU2 -HT12 /3 width=5 by lstas_bind, drop_skip, lift_bind, ex2_intro/ +| #G #L2 #V2 #T2 #U2 #l #_ #IHTU2 #L1 #s #d #e #HL21 #X #H + elim (lift_inv_flat2 … H) -H #V1 #T1 #HV12 #HT12 #H destruct + elim (IHTU2 … HL21 … HT12) -L2 -HT12 /3 width=5 by lstas_appl, lift_flat, ex2_intro/ +| #G #L2 #W2 #T2 #U2 #l #_ #IHTU2 #L1 #s #d #e #HL21 #X #H + elim (lift_inv_flat2 … H) -H #W1 #T1 #_ #HT12 #H destruct + elim (IHTU2 … HL21 … HT12) -L2 -HT12 /3 width=3 by lstas_cast, ex2_intro/ +] +qed-. (* Advanced inversion lemmas ************************************************) -lemma lstas_inv_lref1: ∀h,G,L,U,i,l. ⦃G, L⦄ ⊢ #i •*[h, l+1] U → - (∃∃K,V,W. ⇩[i] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V •*[h, l+1] W & - ⇧[0, i+1] W ≡ U - ) ∨ - (∃∃K,W,V,V0. ⇩[i] L ≡ K.ⓛW & ⦃G, K⦄ ⊢ W •[h] V0 & - ⦃G, K⦄ ⊢ W •*[h, l] V & ⇧[0, i+1] V ≡ U - ). -#h #G #L #U #i #l #H elim (lstas_inv_step_sn … H) -H -#X #H #HXU elim (sta_inv_lref1 … H) -H -* #K #V #W #HLK #HVW #HWX -lapply (drop_fwd_drop2 … HLK) #H0LK -elim (lstas_inv_lift1 … HXU … H0LK … HWX) -H0LK -X -/4 width=8 by lstas_step_sn, ex4_4_intro, ex3_3_intro, or_introl, or_intror/ +lemma zero_eq_plus: ∀x,y. 0 = x + y → 0 = x ∧ 0 = y. +* /2 width=1 by conj/ #x #y normalize #H destruct qed-. -(* Advanced forward lemmas **************************************************) - -lemma lstas_fwd_correct: ∀h,G,L,T1,U1. ⦃G, L⦄ ⊢ T1 •[h] U1 → - ∀T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l] T2 → - ∃U2. ⦃G, L⦄ ⊢ T2 •[h] U2. -#h #G #L #T1 #U1 #HTU1 #T2 #l #H @(lstas_ind_dx … H) -l -T2 /2 width=3 by ex_intro/ -HTU1 -#l #T #T2 #_ #HT2 #_ -T1 -U1 -l -elim (sta_fwd_correct … HT2) -T /2 width=2 by ex_intro/ +lemma lstas_split_aux: ∀h,G,L,T1,T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l] T2 → ∀l1,l2. l = l1 + l2 → + ∃∃T. ⦃G, L⦄ ⊢ T1 •*[h, l1] T & ⦃G, L⦄ ⊢ T •*[h, l2] T2. +#h #G #L #T1 #T2 #l #H elim H -G -L -T1 -T2 -l +[ #G #L #l #k #l1 #l2 #H destruct + >commutative_plus >iter_plus /2 width=3 by lstas_sort, ex2_intro/ +| #G #L #K #V1 #V2 #U2 #i #l #HLK #_ #VU2 #IHV12 #l1 #l2 #H destruct + elim (IHV12 l1 l2) -IHV12 // #V + elim (lift_total V 0 (i+1)) + lapply (drop_fwd_drop2 … HLK) + /3 width=12 by lstas_lift, lstas_ldef, ex2_intro/ +| #G #L #K #W1 #W2 #i #HLK #HW12 #_ #l1 #l2 #H + elim (zero_eq_plus … H) -H #H1 #H2 destruct + /3 width=5 by lstas_zero, ex2_intro/ +| #G #L #K #W1 #W2 #U2 #i #l #HLK #HW12 #HWU2 #IHW12 #l1 @(nat_ind_plus … l1) -l1 + [ #l2 normalize #H destruct + elim (IHW12 0 l) -IHW12 // + lapply (drop_fwd_drop2 … HLK) + /3 width=8 by lstas_succ, lstas_zero, ex2_intro/ + | #l1 #_ #l2 (lstas_inv_sort1 … H) -X + (lstas_inv_sort1 … H) -X // +| #G #L #K #V #V1 #U1 #i #l #HLK #_ #HVU1 #IHV1 #X #H + elim (lstas_inv_lref1 … H) -H * + #K0 #V0 #W0 [3: #l0 ] #HLK0 + lapply (drop_mono … HLK0 … HLK) -HLK -HLK0 #H destruct + #HVW0 #HX lapply (IHV1 … HVW0) -IHV1 -HVW0 #H destruct + /2 width=5 by lift_mono/ +| #G #L #K #W #W1 #i #HLK #_ #_ #X #H + elim (lstas_inv_lref1_O … H) -H * + #K0 #V0 #W0 #HLK0 + lapply (drop_mono … HLK0 … HLK) -HLK -HLK0 #H destruct // +| #G #L #K #W #W1 #U1 #i #l #HLK #_ #HWU1 #IHWV #X #H + elim (lstas_inv_lref1_S … H) -H * #K0 #W0 #V0 #HLK0 + lapply (drop_mono … HLK0 … HLK) -HLK -HLK0 #H destruct + #HW0 #HX lapply (IHWV … HW0) -IHWV -HW0 #H destruct + /2 width=5 by lift_mono/ +| #a #I #G #L #V #T #U1 #l #_ #IHTU1 #X #H + elim (lstas_inv_bind1 … H) -H #U2 #HTU2 #H destruct /3 width=1 by eq_f/ +| #G #L #V #T #U1 #l #_ #IHTU1 #X #H + elim (lstas_inv_appl1 … H) -H #U2 #HTU2 #H destruct /3 width=1 by eq_f/ +| #G #L #W #T #U1 #l #_ #IHTU1 #U2 #H + lapply (lstas_inv_cast1 … H) -H /2 width=1 by/ +] +qed-. -theorem lstas_mono: ∀h,G,L,l. singlevalued … (lstas h G L l). -/3 width=7 by sta_mono, lstar_singlevalued/ qed-. +(* Advanced inversion lemmas ************************************************) + +(* Basic_1: was just: sty0_correct *) +lemma lstas_correct: ∀h,G,L,T1,T,l1. ⦃G, L⦄ ⊢ T1 •*[h, l1] T → + ∀l2. ∃T2. ⦃G, L⦄ ⊢ T •*[h, l2] T2. +#h #G #L #T1 #T #l1 #H elim H -G -L -T1 -T -l1 +[ /2 width=2 by lstas_sort, ex_intro/ +| #G #L #K #V1 #V #U #i #l #HLK #_ #HVU #IHV1 #l2 + elim (IHV1 l2) -IHV1 #V2 + elim (lift_total V2 0 (i+1)) + lapply (drop_fwd_drop2 … HLK) -HLK + /3 width=11 by ex_intro, lstas_lift/ +| #G #L #K #W1 #W #i #HLK #HW1 #IHW1 #l2 + @(nat_ind_plus … l2) -l2 /3 width=5 by lstas_zero, ex_intro/ + #l2 #_ elim (IHW1 l2) -IHW1 #W2 #HW2 + lapply (lstas_trans … HW1 … HW2) -W + elim (lift_total W2 0 (i+1)) + /3 width=7 by lstas_succ, ex_intro/ +| #G #L #K #W1 #W #U #i #l #HLK #_ #HWU #IHW1 #l2 + elim (IHW1 l2) -IHW1 #W2 + elim (lift_total W2 0 (i+1)) + lapply (drop_fwd_drop2 … HLK) -HLK + /3 width=11 by ex_intro, lstas_lift/ +| #a #I #G #L #V #T #U #l #_ #IHTU #l2 + elim (IHTU l2) -IHTU /3 width=2 by lstas_bind, ex_intro/ +| #G #L #V #T #U #l #_ #IHTU #l2 + elim (IHTU l2) -IHTU /3 width=2 by lstas_appl, ex_intro/ +| #G #L #W #T #U #l #_ #IHTU #l2 + elim (IHTU l2) -IHTU /2 width=2 by ex_intro/ +] +qed-. + +(* more main properties *****************************************************) theorem lstas_conf_le: ∀h,G,L,T,U1,l1. ⦃G, L⦄ ⊢ T •*[h, l1] U1 → ∀U2,l2. l1 ≤ l2 → ⦃G, L⦄ ⊢ T •*[h, l2] U2 → @@ -34,18 +113,12 @@ elim (lstas_split … H) -H #U #HTU >(lstas_mono … HTU … HTU1) -T // qed-. -(* Advanced properties ******************************************************) - -lemma lstas_sta_conf_pos: ∀h,G,L,T,U1. ⦃G, L⦄ ⊢ T •[h] U1 → - ∀U2,l. ⦃G, L⦄ ⊢ T •*[h, l+1] U2 → ⦃G, L⦄ ⊢ U1 •*[h, l] U2. -#h #G #L #T #U1 #HTU1 #U2 #l #HTU2 -lapply (lstas_conf_le … T U1 1 … HTU2) -HTU2 /2 width=1 by sta_lstas/ -qed-. - -lemma lstas_strip_pos: ∀h,G,L,T1,U1. ⦃G, L⦄ ⊢ T1 •[h] U1 → - ∀T2,l. ⦃G, L⦄ ⊢ T1 •*[h, l+1] T2 → - ∃∃U2. ⦃G, L⦄ ⊢ T2 •[h] U2 & ⦃G, L⦄ ⊢ U1 •*[h, l+1] U2. -#h #G #L #T1 #U1 #HTU1 #T2 #l #HT12 -elim (lstas_fwd_correct … HTU1 … HT12) -lapply (lstas_sta_conf_pos … HTU1 … HT12) -T1 /3 width=5 by lstas_step_dx, ex2_intro/ +theorem lstas_conf: ∀h,G,L,T0,T1,l1. ⦃G, L⦄ ⊢ T0 •*[h, l1] T1 → + ∀T2,l2. ⦃G, L⦄ ⊢ T0 •*[h, l2] T2 → + ∃∃T. ⦃G, L⦄ ⊢ T1 •*[h, l2] T & ⦃G, L⦄ ⊢ T2 •*[h, l1] T. +#h #G #L #T0 #T1 #l1 #HT01 #T2 #l2 #HT02 +elim (lstas_lstas … HT01 (l1+l2)) #T #HT0 +lapply (lstas_conf_le … HT01 … HT0) // -HT01