From b1868c5a258a6bf7fc983d63f3c417f00185e7b6 Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Sat, 13 Jan 2018 22:24:16 +0100 Subject: [PATCH] update in ground_2 and basic_2 - new version of lveq completed: allows to prove all six main properties of fle, but lfxs_fle fails :( - voids parked for now - more ignores for the web site --- .gitignore | 6 + .../contribs/lambdadelta/basic_2/etc/lveq.etc | 36 ++++ .../voids/lveq_voids.etc} | 3 +- .../{syntax/voids.ma => etc/voids/voids.etc} | 0 .../voids/voids_length.etc} | 0 .../voids/voidstar_2.etc} | 0 .../lambdadelta/basic_2/static/fle.ma | 8 +- .../lambdadelta/basic_2/static/fle_drops.ma | 8 +- .../lambdadelta/basic_2/static/fle_fle.ma | 61 +++--- .../lambdadelta/basic_2/static/fle_fqup.ma | 6 +- .../lambdadelta/basic_2/static/lfxs_fle.ma | 20 +- .../lambdadelta/basic_2/syntax/lveq.ma | 62 +++++- .../lambdadelta/basic_2/syntax/lveq_length.ma | 27 ++- .../lambdadelta/basic_2/syntax/lveq_lveq.ma | 191 ++++++++++-------- matita/matita/contribs/lambdadelta/etc2ma.sh | 2 +- .../ground_2/relocation/rtmap_sle.ma | 6 + .../lambdadelta/ground_2/xoa2.conf.xml | 1 - matita/matita/contribs/lambdadelta/ma2etc.sh | 2 +- 18 files changed, 297 insertions(+), 142 deletions(-) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/lveq.etc rename matita/matita/contribs/lambdadelta/basic_2/{syntax/lveq_voids.ma => etc/voids/lveq_voids.etc} (99%) rename matita/matita/contribs/lambdadelta/basic_2/{syntax/voids.ma => etc/voids/voids.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{syntax/voids_length.ma => etc/voids/voids_length.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{notation/functions/voidstar_2.ma => etc/voids/voidstar_2.etc} (100%) diff --git a/.gitignore b/.gitignore index 29933ad99..7ab34bb92 100644 --- a/.gitignore +++ b/.gitignore @@ -45,14 +45,18 @@ helm/www/lambdadelta/etc/BTM helm/www/lambdadelta/etc/lambdadelta helm/www/lambdadelta/etc/coq-contribs helm/www/lambdadelta/xslt/apps_2_src.xsl +helm/www/lambdadelta/xslt/apps_2_sum.xsl helm/www/lambdadelta/xslt/basic_2_blk.xsl helm/www/lambdadelta/xslt/basic_2_src.xsl +helm/www/lambdadelta/xslt/basic_2_sum.xsl helm/www/lambdadelta/xslt/ground_2_src.xsl +helm/www/lambdadelta/xslt/ground_2_sum.xsl helm/www/lambdadelta/xslt/basic_1_blk.xsl helm/www/lambdadelta/xslt/basic_1_src.xsl helm/www/lambdadelta/xslt/basic_1_sum.xsl helm/www/lambdadelta/xslt/ground_1_src.xsl helm/www/lambdadelta/xslt/ground_1_sum.xsl +helm/www/lambdadelta/xslt/alpha_1_sum.xsl helm/www/lambdadelta/xslt/documentation_1.xsl helm/www/lambdadelta/xslt/documentation_2.xsl helm/www/lambdadelta/xslt/documentation_3.xsl @@ -68,3 +72,5 @@ matita/matita/contribs/lambdadelta/apps_2/notation matita/matita/contribs/lambdadelta/apps_2/models matita/matita/contribs/lambdadelta/ground_2/xoa/xoa2.ma matita/matita/contribs/lambdadelta/ground_2/notation/xoa/notation2.ma +matita/matita/contribs/lambdadelta/*/*_probe.txt +matita/matita/contribs/lambdadelta/*/web/*_sum.tbl diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/lveq.etc b/matita/matita/contribs/lambdadelta/basic_2/etc/lveq.etc new file mode 100644 index 000000000..e355449ef --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/lveq.etc @@ -0,0 +1,36 @@ +fact lveq_inv_pair_bind_aux: ∀L1,L2,n1,n2. L1 ≋ ⓧ*[n1, n2] L2 → + ∀I1,I2,K1,K2,V1. K1.ⓑ{I1}V1 = L1 → K2.ⓘ{I2} = L2 → + ∨∨ ∃∃m. K1 ≋ ⓧ*[m, m] K2 & 0 = n1 & 0 = n2 + | ∃∃m1,m2. K1 ≋ ⓧ*[m1, m2] K2 & + BUnit Void = I2 & ⫯m2 = n2. +#L1 #L2 #n1 #n2 #H elim H -L1 -L2 -n1 -n2 +[ #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct +|2,3: #I1 #I2 #K1 #K2 #V #n #HK #_ #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct /3 width=2 by or_introl, ex3_intro/ +|4,5: #K1 #K2 #n1 #n2 #HK #IH #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct + /3 width=4 by _/ +] +qed-. + +lemma voids_inv_pair_bind: ∀I1,I2,K1,K2,V1,n1,n2. ⓧ*[n1]K1.ⓑ{I1}V1 ≋ ⓧ*[n2]K2.ⓘ{I2} → + ∨∨ ∃∃n. ⓧ*[n]K1 ≋ ⓧ*[n]K2 & 0 = n1 & 0 = n2 + | ∃∃m2. ⓧ*[n1]K1.ⓑ{I1}V1 ≋ ⓧ*[m2]K2 & + BUnit Void = I2 & ⫯m2 = n2. +/2 width=5 by voids_inv_pair_bind_aux/ qed-. + +fact voids_inv_bind_pair_aux: ∀L1,L2,n1,n2. ⓧ*[n1]L1 ≋ ⓧ*[n2]L2 → + ∀I1,I2,K1,K2,V2. K1.ⓘ{I1} = L1 → K2.ⓑ{I2}V2 = L2 → + ∨∨ ∃∃n. ⓧ*[n]K1 ≋ ⓧ*[n]K2 & 0 = n1 & 0 = n2 + | ∃∃m1. ⓧ*[m1]K1 ≋ ⓧ*[n2]K2.ⓑ{I2}V2 & + BUnit Void = I1 & ⫯m1 = n1. +#L1 #L2 #n1 #n2 * -L1 -L2 -n1 -n2 +[ #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct +|2,3: #I1 #I2 #K1 #K2 #V #n #HK #J1 #J2 #L1 #L2 #V2 #H1 #H2 destruct /3 width=2 by or_introl, ex3_intro/ +|4,5: #K1 #K2 #n1 #n2 #HK #J1 #J2 #L1 #L2 #V2 #H1 #H2 destruct /3 width=3 by or_intror, ex3_intro/ +] +qed-. + +lemma voids_inv_bind_pair: ∀I1,I2,K1,K2,V2,n1,n2. ⓧ*[n1]K1.ⓘ{I1} ≋ ⓧ*[n2]K2.ⓑ{I2}V2 → + ∨∨ ∃∃n. ⓧ*[n]K1 ≋ ⓧ*[n]K2 & 0 = n1 & 0 = n2 + | ∃∃m1. ⓧ*[m1]K1 ≋ ⓧ*[n2]K2.ⓑ{I2}V2 & + BUnit Void = I1 & ⫯m1 = n1. +/2 width=5 by voids_inv_bind_pair_aux/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_voids.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/voids/lveq_voids.etc similarity index 99% rename from matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_voids.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/voids/lveq_voids.etc index 88b7f77aa..38b2076a6 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_voids.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/voids/lveq_voids.etc @@ -12,6 +12,7 @@ (* *) (**************************************************************************) +(* requires 3 6 *) include "ground_2/xoa/xoa2.ma". include "basic_2/syntax/voids_length.ma". include "basic_2/syntax/lveq.ma". @@ -95,4 +96,4 @@ lemma lveq_inv_voids_zero: ∀L1,L2,n1,n2. ⓧ*[n1]L1 ≋ⓧ*[n1, n2] ⓧ*[n2]L2 L1 ≋ⓧ*[0, 0] L2. /2 width=3 by lveq_inv_voids/ qed-. -*) \ No newline at end of file +*) diff --git a/matita/matita/contribs/lambdadelta/basic_2/syntax/voids.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/voids/voids.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/syntax/voids.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/voids/voids.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/syntax/voids_length.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/voids/voids_length.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/syntax/voids_length.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/voids/voids_length.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/functions/voidstar_2.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/voids/voidstar_2.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/notation/functions/voidstar_2.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/voids/voidstar_2.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/fle.ma b/matita/matita/contribs/lambdadelta/basic_2/static/fle.ma index 02d3ecdb1..fdc03a5e2 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/static/fle.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/static/fle.ma @@ -14,14 +14,14 @@ include "ground_2/relocation/rtmap_id.ma". include "basic_2/notation/relations/subseteq_4.ma". -include "basic_2/syntax/voids.ma". +include "basic_2/syntax/lveq.ma". include "basic_2/static/frees.ma". (* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************) definition fle: bi_relation lenv term ≝ λL1,T1,L2,T2. ∃∃n1,n2,f1,f2. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 & L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 & - ⓧ*[n1]L1 ≋ ⓧ*[n2]L2 & ⫱*[n1]f1 ⊆ ⫱*[n2]f2. + L1 ≋ⓧ*[n1, n2] L2 & ⫱*[n1]f1 ⊆ ⫱*[n2]f2. interpretation "free variables inclusion (restricted closure)" 'SubSetEq L1 T1 L2 T2 = (fle L1 T1 L2 T2). @@ -29,12 +29,12 @@ interpretation "free variables inclusion (restricted closure)" (* Basic properties *********************************************************) lemma fle_sort: ∀L,s1,s2. ⦃L, ⋆s1⦄ ⊆ ⦃L, ⋆s2⦄. -#L elim (voids_refl L) +#L elim (lveq_refl L) /3 width=8 by frees_sort, sle_refl, ex4_4_intro/ qed. lemma fle_gref: ∀L,l1,l2. ⦃L, §l1⦄ ⊆ ⦃L, §l2⦄. -#L elim (voids_refl L) +#L elim (lveq_refl L) /3 width=8 by frees_gref, sle_refl, ex4_4_intro/ qed. diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/fle_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/static/fle_drops.ma index ca9549a06..ff0b8872d 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/static/fle_drops.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/static/fle_drops.ma @@ -24,8 +24,8 @@ lemma fle_bind_dx: ∀T,U. ⬆*[1] T ≡ U → #T #U #HTU #p #I #L #V elim (frees_total L V) #f1 #Hf1 elim (frees_total L T) #f2 #Hf2 -elim (sor_isfin_ex f1 f2) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #H #_ -lapply (sor_inv_sle_dx … H) #Hf0 ->(tl_push_rew f) in H; #Hf -/6 width=6 by frees_lifts_SO, frees_bind, drops_refl, drops_drop, ex3_2_intro/ +elim (sor_isfin_ex f1 f2) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #Hf #_ +lapply (sor_inv_sle_dx … Hf) #Hf0 +elim (lveq_refl L) #n #HL +/6 width=8 by frees_lifts_SO, frees_bind, drops_refl, drops_drop, sle_tls, ex4_4_intro/ qed. diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/fle_fle.ma b/matita/matita/contribs/lambdadelta/basic_2/static/fle_fle.ma index e756b43f7..42c403412 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/static/fle_fle.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/static/fle_fle.ma @@ -12,6 +12,7 @@ (* *) (**************************************************************************) +include "basic_2/syntax/lveq_lveq.ma". include "basic_2/static/frees_frees.ma". include "basic_2/static/fle_fqup.ma". @@ -19,14 +20,15 @@ include "basic_2/static/fle_fqup.ma". (* Advanced inversion lemmas ************************************************) -lemma fle_inv_voids_sn_frees_dx: ∀L1,L2,T1,T2,n. ⦃ⓧ*[n]L1, T1⦄ ⊆ ⦃L2, T2⦄ → - |L1| = |L2| → ∀f2. L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 → - ∃∃f1. ⓧ*[n]L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 & ⫱*[n]f1 ⊆ f2. -#L1 #L2 #T1 #T2 #n #H #HL12 #f2 #Hf2 -elim (fle_inv_voids_sn … H HL12) -H -HL12 #f1 #g2 #Hf1 #Hg2 #Hfg -lapply (frees_mono … Hg2 … Hf2) -Hg2 -Hf2 #Hfg2 -lapply (sle_eq_repl_back2 … Hfg … Hfg2) -g2 -/2 width=3 by ex2_intro/ +lemma fle_frees_trans: ∀L1,L2,T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ → + ∀f2. L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 → + ∃∃n1,n2,f1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 & + L1 ≋ⓧ*[n1, n2] L2 & ⫱*[n1]f1 ⊆ ⫱*[n2]f2. +#L1 #L2 #T1 #T2 * #n1 #n2 #f1 #g2 #Hf1 #Hg2 #HL #Hn #f2 #Hf2 +lapply (frees_mono … Hg2 … Hf2) -Hg2 -Hf2 #Hgf2 +lapply (tls_eq_repl n2 … Hgf2) -Hgf2 #Hgf2 +lapply (sle_eq_repl_back2 … Hn … Hgf2) -g2 +/2 width=6 by ex3_3_intro/ qed-. (* Main properties **********************************************************) @@ -38,37 +40,38 @@ qed-. *) theorem fle_bind_sn: ∀L1,L2,V1,T1,T. ⦃L1, V1⦄ ⊆ ⦃L2, T⦄ → ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2, T⦄ → ∀p,I. ⦃L1, ⓑ{p,I}V1.T1⦄ ⊆ ⦃L2, T⦄. -#L1 #L2 #V1 #T1 #T * -L1 #f1 #x #L1 #n1 #Hf1 #Hx #HL12 #Hf1x ->voids_succ #H #p #I -elim (fle_inv_voids_sn_frees_dx … H … Hx) -H // #f2 #Hf2 -length_bind >length_bind #H +/2 width=1 by monotonic_pred/ +qed-. + +lemma lveq_fwd_bind_abst_length_le: ∀I1,I2,L1,L2,V2,n1,n2. + L1.ⓘ{I1} ≋ⓧ*[n1, n2] L2.ⓑ{I2}V2 → |L2| ≤ |L1|. +/3 width=6 by lveq_fwd_abst_bind_length_le, lveq_sym/ qed-. + (* Inversion lemmas with length for local environments **********************) - + lemma lveq_inv_void_dx_length: ∀L1,L2,n1,n2. L1 ≋ⓧ*[n1, n2] L2.ⓧ → |L1| ≤ |L2| → ∃∃m2. L1 ≋ ⓧ*[n1, m2] L2 & n2 = ⫯m2 & n1 ≤ m2. #L1 #L2 #n1 #n2 #H #HL12 lapply (lveq_fwd_length … H) normalize >plus_n_Sm #H0 lapply (plus2_inv_le_sn … H0 HL12) -H0 -HL12 #H0 elim (le_inv_S1 … H0) -H0 #m2 #Hm2 #H0 destruct -/3 width=4 by lveq_inv_void_dx, ex3_intro/ +/3 width=4 by lveq_inv_void_succ_dx, ex3_intro/ +qed-. + +lemma lveq_inv_void_sn_length: ∀L1,L2,n1,n2. L1.ⓧ ≋ⓧ*[n1, n2] L2 → |L2| ≤ |L1| → + ∃∃m1. L1 ≋ ⓧ*[m1, n2] L2 & n1 = ⫯m1 & n2 ≤ m1. +#L1 #L2 #n1 #n2 #H #HL +lapply (lveq_sym … H) -H #H +elim (lveq_inv_void_dx_length … H HL) -H -HL +/3 width=4 by lveq_sym, ex3_intro/ qed-. -*) \ No newline at end of file diff --git a/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma b/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma index 12b6f0cb6..3f64c33b0 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma @@ -16,6 +16,33 @@ include "basic_2/syntax/lveq_length.ma". (* EQUIVALENCE FOR LOCAL ENVIRONMENTS UP TO EXCLUSION BINDERS ***************) +(* Main forward lemmas ******************************************************) + +theorem lveq_fwd_inj_succ_zero: ∀L1,L2,n1. L1 ≋ⓧ*[⫯n1, 0] L2 → + ∀m1,m2. L1 ≋ⓧ*[m1, m2] L2 → ∃x1. ⫯x1 = m1. +#L1 #L2 #n1 #Hn #m1 #m2 #Hm +lapply (lveq_fwd_length … Hn) -Hn Hn >associative_plus -Hn #Hm +lapply (injective_plus_r … Hm) -Hm +ground_2/xoa/xoa2 ground_2/notation/xoa/notation2 basics/pts.ma - 3 6 diff --git a/matita/matita/contribs/lambdadelta/ma2etc.sh b/matita/matita/contribs/lambdadelta/ma2etc.sh index e546af776..b135f45b4 100644 --- a/matita/matita/contribs/lambdadelta/ma2etc.sh +++ b/matita/matita/contribs/lambdadelta/ma2etc.sh @@ -1 +1 @@ -for FILE in `find $1 -name "*.ma"`; do svn mv $FILE ${FILE/%.ma/.etc} ; done +for FILE in `find $1 -name "*.ma"`; do git mv $FILE ${FILE/%.ma/.etc} ; done -- 2.39.2