From 32bdf7f107be22a121fab8225c5fae4eb6b33633 Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Fri, 3 Jan 2014 17:31:49 +0000 Subject: [PATCH] - extended multiple substitutions now uses bounds in ynat (ie. they can be infinite) for use in lleq - ground_2: additions in ynat --- .../{lazyeqalt_3.ma => lazyeqalt_4.ma} | 4 +- .../lambdadelta/basic_2/relocation/cpy.ma | 104 ++++++------- .../lambdadelta/basic_2/relocation/cpy_cpy.ma | 31 ++-- .../basic_2/relocation/cpy_lift.ma | 140 +++++++++--------- .../basic_2/relocation/ldrop_leq.ma | 4 +- .../lambdadelta/basic_2/relocation/lsuby.ma | 105 ++++++------- .../lambdadelta/basic_2/substitution/cpys.ma | 2 +- .../basic_2/substitution/cpys_alt.ma | 11 +- .../basic_2/substitution/cpys_cpys.ma | 11 +- .../basic_2/substitution/cpys_lift.ma | 44 +++--- .../lambdadelta/ground_2/ynat/ynat_lt.ma | 8 +- .../lambdadelta/ground_2/ynat/ynat_minus.ma | 6 +- 12 files changed, 237 insertions(+), 233 deletions(-) rename matita/matita/contribs/lambdadelta/basic_2/notation/relations/{lazyeqalt_3.ma => lazyeqalt_4.ma} (90%) diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyeqalt_3.ma b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyeqalt_4.ma similarity index 90% rename from matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyeqalt_3.ma rename to matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyeqalt_4.ma index a4d786052..9cd39df3e 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyeqalt_3.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyeqalt_4.ma @@ -14,6 +14,6 @@ (* NOTATION FOR THE FORMAL SYSTEM λδ ****************************************) -notation "hvbox( L1 ⋕ ⋕ break [ term 46 T ] break term 46 L2 )" +notation "hvbox( L1 ⋕ ⋕ break [ term 46 d , break term 46 T ] break term 46 L2 )" non associative with precedence 45 - for @{ 'LazyEqAlt $T $L1 $L2 }. + for @{ 'LazyEqAlt $d $T $L1 $L2 }. diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy.ma index 900bf7d73..41971c43e 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy.ma @@ -12,6 +12,7 @@ (* *) (**************************************************************************) +include "ground_2/ynat/ynat_max.ma". include "basic_2/notation/relations/extpsubst_6.ma". include "basic_2/grammar/genv.ma". include "basic_2/grammar/cl_shift.ma". @@ -21,12 +22,12 @@ include "basic_2/relocation/lsuby.ma". (* CONTEXT-SENSITIVE EXTENDED ORDINARY SUBSTITUTION FOR TERMS ***************) (* activate genv *) -inductive cpy: nat → nat → relation4 genv lenv term term ≝ +inductive cpy: ynat → ynat → relation4 genv lenv term term ≝ | cpy_atom : ∀I,G,L,d,e. cpy d e G L (⓪{I}) (⓪{I}) -| cpy_subst: ∀I,G,L,K,V,W,i,d,e. d ≤ i → i < d + e → - ⇩[0, i] L ≡ K.ⓑ{I}V → ⇧[0, i + 1] V ≡ W → cpy d e G L (#i) W +| cpy_subst: ∀I,G,L,K,V,W,i,d,e. d ≤ yinj i → i < d+e → + ⇩[0, i] L ≡ K.ⓑ{I}V → ⇧[0, i+1] V ≡ W → cpy d e G L (#i) W | cpy_bind : ∀a,I,G,L,V1,V2,T1,T2,d,e. - cpy d e G L V1 V2 → cpy (d + 1) e G (L.ⓑ{I}V2) T1 T2 → + cpy d e G L V1 V2 → cpy (⫯d) e G (L.ⓑ{I}V2) T1 T2 → cpy d e G L (ⓑ{a,I}V1.T1) (ⓑ{a,I}V2.T2) | cpy_flat : ∀I,G,L,V1,V2,T1,T2,d,e. cpy d e G L V1 V2 → cpy d e G L T1 T2 → @@ -62,7 +63,7 @@ lemma cpy_full: ∀I,G,K,V,T1,L,d. ⇩[0, d] L ≡ K.ⓑ{I}V → destruct elim (lift_total V 0 (i+1)) #W #HVW elim (lift_split … HVW i i) - /3 width=5 by cpy_subst, le_n, ex2_2_intro/ + /4 width=5 by cpy_subst, ylt_inj, ex2_2_intro/ | * [ #a ] #J #W1 #U1 #IHW1 #IHU1 #L #d #HLK elim (IHW1 … HLK) -IHW1 #W2 #W #HW12 #HW2 [ elim (IHU1 (L.ⓑ{J}W2) (d+1)) -IHU1 @@ -76,22 +77,21 @@ qed-. lemma cpy_weak: ∀G,L,T1,T2,d1,e1. ⦃G, L⦄ ⊢ T1 ▶×[d1, e1] T2 → ∀d2,e2. d2 ≤ d1 → d1 + e1 ≤ d2 + e2 → ⦃G, L⦄ ⊢ T1 ▶×[d2, e2] T2. -#G #L #T1 #T2 #d1 #e1 #H elim H -G -L -T1 -T2 -d1 -e1 -[ // -| /3 width=5 by cpy_subst, transitive_le/ -| /4 width=3 by cpy_bind, le_to_lt_to_lt, le_S_S/ +#G #L #T1 #T2 #d1 #e1 #H elim H -G -L -T1 -T2 -d1 -e1 // +[ /3 width=5 by cpy_subst, ylt_yle_trans, yle_trans/ +| /4 width=3 by cpy_bind, ylt_yle_trans, yle_succ/ | /3 width=1 by cpy_flat/ ] qed-. lemma cpy_weak_top: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T2 → ⦃G, L⦄ ⊢ T1 ▶×[d, |L| - d] T2. -#G #L #T1 #T2 #d #e #H elim H -G -L -T1 -T2 -d -e -[ // -| #I #G #L #K #V #W #i #d #e #Hdi #_ #HLK #HVW +#G #L #T1 #T2 #d #e #H elim H -G -L -T1 -T2 -d -e // +[ #I #G #L #K #V #W #i #d #e #Hdi #_ #HLK #HVW lapply (ldrop_fwd_length_lt2 … HLK) - /3 width=5 by cpy_subst, lt_to_le_to_lt/ -| normalize /2 width=1 by cpy_bind/ + /4 width=5 by cpy_subst, ylt_yle_trans, ylt_inj/ +| #a #I #G #L #V1 #V2 normalize in match (|L.ⓑ{I}V2|); (**) (* |?| does not work *) + /2 width=1 by cpy_bind/ | /2 width=1 by cpy_flat/ ] qed-. @@ -103,53 +103,46 @@ lapply (cpy_weak … HT12 0 (d + e) ? ?) -HT12 /2 width=2 by cpy_weak_top/ qed-. -lemma cpy_split_up: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T2 → ∀i. d ≤ i → i ≤ d + e → - ∃∃T. ⦃G, L⦄ ⊢ T1 ▶×[d, i - d] T & ⦃G, L⦄ ⊢ T ▶×[i, d + e - i] T2. +lemma cpy_split_up: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T2 → ∀i. i ≤ d + e → + ∃∃T. ⦃G, L⦄ ⊢ T1 ▶×[d, i-d] T & ⦃G, L⦄ ⊢ T ▶×[i, d+e-i] T2. #G #L #T1 #T2 #d #e #H elim H -G -L -T1 -T2 -d -e [ /2 width=3 by ex2_intro/ -| #I #G #L #K #V #W #i #d #e #Hdi #Hide #HLK #HVW #j #Hdj #Hjde - elim (lt_or_ge i j) [ -Hide -Hjde | -Hdi -Hdj ] - [ >(plus_minus_m_m j d) in ⊢ (%→?); - /3 width=5 by cpy_subst, ex2_intro/ - | #Hij lapply (plus_minus_m_m … Hjde) -Hjde - /3 width=9 by cpy_atom, cpy_subst, ex2_intro/ - ] -| #a #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hdi #Hide - elim (IHV12 i) -IHV12 // #V #HV1 #HV2 - elim (IHT12 (i + 1)) -IHT12 /2 width=1 by le_S_S/ - -Hdi -Hide >arith_c1x #T #HT1 #HT2 - lapply (lsuby_cpy_trans … HT1 (L.ⓑ{I} V) ?) -HT1 /3 width=5 by lsuby_succ, ex2_intro, cpy_bind/ -| #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hdi #Hide - elim (IHV12 i) -IHV12 // elim (IHT12 i) -IHT12 // - -Hdi -Hide /3 width=5 by ex2_intro, cpy_flat/ +| #I #G #L #K #V #W #i #d #e #Hdi #Hide #HLK #HVW #j #Hjde + elim (ylt_split i j) [ -Hide -Hjde | -Hdi ] + /4 width=9 by cpy_subst, ylt_yle_trans, ex2_intro/ +| #a #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hide + elim (IHV12 i) -IHV12 // #V + elim (IHT12 (i+1)) -IHT12 /2 width=1 by yle_succ/ -Hide + >yplus_SO2 >yplus_succ1 #T #HT1 #HT2 + lapply (lsuby_cpy_trans … HT1 (L.ⓑ{I}V) ?) -HT1 + /3 width=5 by lsuby_succ, ex2_intro, cpy_bind/ +| #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hide + elim (IHV12 i) -IHV12 // elim (IHT12 i) -IHT12 // -Hide + /3 width=5 by ex2_intro, cpy_flat/ ] qed-. -lemma cpy_split_down: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T2 → - ∀i. d ≤ i → i ≤ d + e → - ∃∃T. ⦃G, L⦄ ⊢ T1 ▶×[i, d + e - i] T & - ⦃G, L⦄ ⊢ T ▶×[d, i - d] T2. +lemma cpy_split_down: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T2 → ∀i. i ≤ d + e → + ∃∃T. ⦃G, L⦄ ⊢ T1 ▶×[i, d+e-i] T & ⦃G, L⦄ ⊢ T ▶×[d, i-d] T2. #G #L #T1 #T2 #d #e #H elim H -G -L -T1 -T2 -d -e [ /2 width=3 by ex2_intro/ -| #I #G #L #K #V #W #i #d #e #Hdi #Hide #HLK #HVW #j #Hdj #Hjde - elim (lt_or_ge i j) - [ -Hide -Hjde >(plus_minus_m_m j d) in ⊢ (% → ?); // -Hdj /3 width=9 by ex2_intro, cpy_atom, cpy_subst/ - | -Hdi -Hdj - >(plus_minus_m_m (d+e) j) in Hide; // -Hjde /3 width=5 by ex2_intro, cpy_subst/ - ] -| #a #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hdi #Hide +| #I #G #L #K #V #W #i #d #e #Hdi #Hide #HLK #HVW #j #Hjde + elim (ylt_split i j) [ -Hide -Hjde | -Hdi ] + /4 width=9 by cpy_subst, ylt_yle_trans, ex2_intro/ +| #a #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hide elim (IHV12 i) -IHV12 // #V - elim (IHT12 (i + 1)) -IHT12 /2 width=1 by le_S_S/ - -Hdi -Hide >arith_c1x #T #HT1 #HT2 - lapply (lsuby_cpy_trans … HT1 (L. ⓑ{I} V) ?) -HT1 /3 width=5 by lsuby_succ, ex2_intro, cpy_bind/ -| #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hdi #Hide - elim (IHV12 i) -IHV12 // elim (IHT12 i) -IHT12 // - -Hdi -Hide /3 width=5 by ex2_intro, cpy_flat/ + elim (IHT12 (i+1)) -IHT12 /2 width=1 by yle_succ/ -Hide + >yplus_SO2 >yplus_succ1 #T #HT1 #HT2 + lapply (lsuby_cpy_trans … HT1 (L. ⓑ{I} V) ?) -HT1 + /3 width=5 by lsuby_succ, ex2_intro, cpy_bind/ +| #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #i #Hide + elim (IHV12 i) -IHV12 // elim (IHT12 i) -IHT12 // -Hide + /3 width=5 by ex2_intro, cpy_flat/ ] qed-. lemma cpy_append: ∀G,d,e. l_appendable_sn … (cpy d e G). -#G #d #e #K #T1 #T2 #H elim H -K -T1 -T2 -d -e +#G #d #e #K #T1 #T2 #H elim H -G -K -T1 -T2 -d -e /2 width=1 by cpy_atom, cpy_bind, cpy_flat/ #I #G #K #K0 #V #W #i #d #e #Hdi #Hide #HK0 #HVW #L lapply (ldrop_fwd_length_lt2 … HK0) #H @@ -161,7 +154,7 @@ qed-. fact cpy_inv_atom1_aux: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T2 → ∀J. T1 = ⓪{J} → T2 = ⓪{J} ∨ - ∃∃I,K,V,i. d ≤ i & i < d + e & + ∃∃I,K,V,i. d ≤ yinj i & i < d + e & ⇩[O, i] L ≡ K.ⓑ{I}V & ⇧[O, i + 1] V ≡ T2 & J = LRef i. @@ -175,7 +168,7 @@ qed-. lemma cpy_inv_atom1: ∀I,G,L,T2,d,e. ⦃G, L⦄ ⊢ ⓪{I} ▶×[d, e] T2 → T2 = ⓪{I} ∨ - ∃∃J,K,V,i. d ≤ i & i < d + e & + ∃∃J,K,V,i. d ≤ yinj i & i < d + e & ⇩[O, i] L ≡ K.ⓑ{J}V & ⇧[O, i + 1] V ≡ T2 & I = LRef i. @@ -206,7 +199,7 @@ qed-. fact cpy_inv_bind1_aux: ∀G,L,U1,U2,d,e. ⦃G, L⦄ ⊢ U1 ▶×[d, e] U2 → ∀a,I,V1,T1. U1 = ⓑ{a,I}V1.T1 → ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ▶×[d, e] V2 & - ⦃G, L. ⓑ{I}V2⦄ ⊢ T1 ▶×[d + 1, e] T2 & + ⦃G, L. ⓑ{I}V2⦄ ⊢ T1 ▶×[⫯d, e] T2 & U2 = ⓑ{a,I}V2.T2. #G #L #U1 #U2 #d #e * -G -L -U1 -U2 -d -e [ #I #G #L #d #e #b #J #W1 #U1 #H destruct @@ -218,7 +211,7 @@ qed-. lemma cpy_inv_bind1: ∀a,I,G,L,V1,T1,U2,d,e. ⦃G, L⦄ ⊢ ⓑ{a,I} V1. T1 ▶×[d, e] U2 → ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ▶×[d, e] V2 & - ⦃G, L.ⓑ{I}V2⦄ ⊢ T1 ▶×[d + 1, e] T2 & + ⦃G, L.ⓑ{I}V2⦄ ⊢ T1 ▶×[⫯d, e] T2 & U2 = ⓑ{a,I}V2.T2. /2 width=3 by cpy_inv_bind1_aux/ qed-. @@ -246,8 +239,7 @@ fact cpy_inv_refl_O2_aux: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T2 → #G #L #T1 #T2 #d #e #H elim H -G -L -T1 -T2 -d -e [ // | #I #G #L #K #V #W #i #d #e #Hdi #Hide #_ #_ #H destruct - lapply (le_to_lt_to_lt … Hdi … Hide) -Hdi -Hide append_length >HL12 -HL12 @(ex2_2_intro … (⋆.ⓑ{I}V0@@L2) T2) [ >append_length ] (**) (* explicit constructor *) - /2 width=3 by trans_eq/ + /2 width=3 by trans_eq/ ] qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_cpy.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_cpy.ma index f876a53d7..2acd3705c 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_cpy.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_cpy.ma @@ -53,15 +53,9 @@ theorem cpy_conf_neq: ∀G,L1,T0,T1,d1,e1. ⦃G, L1⦄ ⊢ T0 ▶×[d1, e1] T1 | #I1 #G #L1 #K1 #V1 #T1 #i0 #d1 #e1 #Hd1 #Hde1 #HLK1 #HVT1 #L2 #T2 #d2 #e2 #H1 #H2 elim (cpy_inv_lref1 … H1) -H1 [ #H destruct /3 width=7 by cpy_subst, ex2_intro/ - | -HLK1 -HVT1 * #I2 #K2 #V2 #Hd2 #Hde2 #_ #_ elim H2 -H2 #Hded - [ -Hd1 -Hde2 - lapply (transitive_le … Hded Hd2) -Hded -Hd2 #H - lapply (lt_to_le_to_lt … Hde1 H) -Hde1 -H #H - elim (lt_refl_false … H) - | -Hd2 -Hde1 - lapply (transitive_le … Hded Hd1) -Hded -Hd1 #H - lapply (lt_to_le_to_lt … Hde2 H) -Hde2 -H #H - elim (lt_refl_false … H) + | -HLK1 -HVT1 * #I2 #K2 #V2 #Hd2 #Hde2 #_ #_ elim H2 -H2 #Hded [ -Hd1 -Hde2 | -Hd2 -Hde1 ] + [ elim (ylt_yle_false … Hde1) -Hde1 /2 width=3 by yle_trans/ + | elim (ylt_yle_false … Hde2) -Hde2 /2 width=3 by yle_trans/ ] ] | #a #I #G #L1 #V0 #V1 #T0 #T1 #d1 #e1 #_ #_ #IHV01 #IHT01 #L2 #X #d2 #e2 #HX #H @@ -71,8 +65,7 @@ theorem cpy_conf_neq: ∀G,L1,T0,T1,d1,e1. ⦃G, L1⦄ ⊢ T0 ▶×[d1, e1] T1 [ -H #T #HT1 #HT2 lapply (lsuby_cpy_trans … HT1 (L2.ⓑ{I}V) ?) -HT1 /2 width=1 by lsuby_succ/ lapply (lsuby_cpy_trans … HT2 (L1.ⓑ{I}V) ?) -HT2 /3 width=5 by cpy_bind, lsuby_succ, ex2_intro/ - | -HV1 -HV2 >plus_plus_comm_23 >plus_plus_comm_23 in ⊢ (? ? %); elim H -H - /3 width=1 by monotonic_le_plus_l, or_intror, or_introl/ + | -HV1 -HV2 elim H -H /3 width=1 by yle_succ, or_introl, or_intror/ ] | #I #G #L1 #V0 #V1 #T0 #T1 #d1 #e1 #_ #_ #IHV01 #IHT01 #L2 #X #d2 #e2 #HX #H elim (cpy_inv_flat1 … HX) -HX #V2 #T2 #HV02 #HT02 #HX destruct @@ -89,11 +82,11 @@ theorem cpy_trans_ge: ∀G,L,T1,T0,d,e. ⦃G, L⦄ ⊢ T1 ▶×[d, e] T0 → elim (cpy_inv_atom1 … H) -H [ #H destruct // | * #J #K #V #i #Hd2i #Hide2 #HLK #HVT2 #H destruct - lapply (lt_to_le_to_lt … (d+e) Hide2 ?) /2 width=5 by cpy_subst, monotonic_lt_plus_r/ + lapply (ylt_yle_trans … (d+e) … Hide2) /2 width=5 by cpy_subst, monotonic_yle_plus_dx/ ] | #I #G #L #K #V #V2 #i #d #e #Hdi #Hide #HLK #HVW #T2 #HVT2 #He - lapply (cpy_weak … HVT2 0 (i +1) ? ?) -HVT2 /2 width=1 by le_S_S/ #HVT2 - <(cpy_inv_lift1_eq … HVT2 … HVW) -HVT2 /2 width=5 by cpy_subst/ + lapply (cpy_weak … HVT2 0 (i+1) ? ?) -HVT2 /3 width=1 by yle_plus_dx2_trans, yle_succ/ + >yplus_inj #HVT2 <(cpy_inv_lift1_eq … HVW … HVT2) -HVT2 /2 width=5 by cpy_subst/ | #a #I #G #L #V1 #V0 #T1 #T0 #d #e #_ #_ #IHV10 #IHT10 #X #H #He elim (cpy_inv_bind1 … H) -H #V2 #T2 #HV02 #HT02 #H destruct lapply (lsuby_cpy_trans … HT02 (L.ⓑ{I}V0) ?) -HT02 /2 width=1 by lsuby_succ/ #HT02 @@ -110,14 +103,14 @@ theorem cpy_trans_down: ∀G,L,T1,T0,d1,e1. ⦃G, L⦄ ⊢ T1 ▶×[d1, e1] T0 #G #L #T1 #T0 #d1 #e1 #H elim H -G -L -T1 -T0 -d1 -e1 [ /2 width=3 by ex2_intro/ | #I #G #L #K #V #W #i1 #d1 #e1 #Hdi1 #Hide1 #HLK #HVW #T2 #d2 #e2 #HWT2 #Hde2d1 - lapply (transitive_le … Hde2d1 Hdi1) -Hde2d1 #Hde2i1 - lapply (cpy_weak … HWT2 0 (i1 + 1) ? ?) -HWT2 normalize /2 width=1 by le_S/ -Hde2i1 #HWT2 - <(cpy_inv_lift1_eq … HWT2 … HVW) -HWT2 /3 width=9 by cpy_subst, ex2_intro/ + lapply (yle_trans … Hde2d1 … Hdi1) -Hde2d1 #Hde2i1 + lapply (cpy_weak … HWT2 0 (i1+1) ? ?) -HWT2 /3 width=1 by yle_succ, yle_pred_sn/ -Hde2i1 + >yplus_inj #HWT2 <(cpy_inv_lift1_eq … HVW … HWT2) -HWT2 /3 width=9 by cpy_subst, ex2_intro/ | #a #I #G #L #V1 #V0 #T1 #T0 #d1 #e1 #_ #_ #IHV10 #IHT10 #X #d2 #e2 #HX #de2d1 elim (cpy_inv_bind1 … HX) -HX #V2 #T2 #HV02 #HT02 #HX destruct lapply (lsuby_cpy_trans … HT02 (L. ⓑ{I} V0) ?) -HT02 /2 width=1 by lsuby_succ/ #HT02 - elim (IHV10 … HV02 ?) -IHV10 -HV02 // #V - elim (IHT10 … HT02 ?) -T0 /2 width=1 by le_S_S/ #T #HT1 #HT2 + elim (IHV10 … HV02) -IHV10 -HV02 // #V + elim (IHT10 … HT02) -T0 /2 width=1 by yle_succ/ #T #HT1 #HT2 lapply (lsuby_cpy_trans … HT1 (L. ⓑ{I} V) ?) -HT1 /2 width=1 by lsuby_succ/ lapply (lsuby_cpy_trans … HT2 (L. ⓑ{I} V2) ?) -HT2 /3 width=6 by cpy_bind, lsuby_succ, ex2_intro/ | #I #G #L #V1 #V0 #T1 #T0 #d1 #e1 #_ #_ #IHV10 #IHT10 #X #d2 #e2 #HX #de2d1 diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_lift.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_lift.ma index ebb7c9df2..7cb26f477 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_lift.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/cpy_lift.ma @@ -27,7 +27,8 @@ lemma cpy_lift_le: ∀G,K,T1,T2,dt,et. ⦃G, K⦄ ⊢ T1 ▶×[dt, et] T2 → [ #I #G #K #dt #et #L #U1 #U2 #d #e #_ #H1 #H2 #_ >(lift_mono … H1 … H2) -H1 -H2 // | #I #G #K #KV #V #W #i #dt #et #Hdti #Hidet #HKV #HVW #L #U1 #U2 #d #e #HLK #H #HWU2 #Hdetd - lapply (lt_to_le_to_lt … Hidet … Hdetd) -Hdetd #Hid + lapply (ylt_yle_trans … Hdetd … Hidet) -Hdetd #Hid + lapply (ylt_inv_inj … Hid) -Hid #Hid lapply (lift_inv_lref1_lt … H … Hid) -H #H destruct elim (lift_trans_ge … HVW … HWU2) -W // (lift_mono … HVY … HVW) -V #H destruct /2 width=5 by cpy_subst/ | -Hdti + elim (yle_inv_inj2 … Hdtd) -Hdtd #dtt #Hdtd #H destruct lapply (transitive_le … Hdtd Hid) -Hdtd #Hdti lapply (lift_trans_be … HVW … HWU2 ? ?) -W /2 width=1 by le_S/ >plus_plus_comm_23 #HVU2 - lapply (ldrop_trans_ge_comm … HLK … HKV ?) -K // -Hid /3 width=5 by cpy_subst, lt_minus_to_plus_r, transitive_le/ + lapply (ldrop_trans_ge_comm … HLK … HKV ?) -K // -Hid + /4 width=5 by cpy_subst, monotonic_ylt_plus_dx, yle_plus_dx1_trans, yle_inj/ ] | #a #I #G #K #V1 #V2 #T1 #T2 #dt #et #_ #_ #IHV12 #IHT12 #L #U1 #U2 #d #e #HLK #H1 #H2 #Hdtd #Hddet elim (lift_inv_bind1 … H1) -H1 #VV1 #TT1 #HVV1 #HTT1 #H1 elim (lift_inv_bind1 … H2) -H2 #VV2 #TT2 #HVV2 #HTT2 #H2 destruct - /4 width=6 by cpy_bind, ldrop_skip, le_S_S/ (**) (* auto a bit slow *) + /4 width=6 by cpy_bind, ldrop_skip, yle_succ/ | #I #G #K #V1 #V2 #T1 #T2 #dt #et #_ #_ #IHV12 #IHT12 #L #U1 #U2 #d #e #HLK #H1 #H2 #Hdetd elim (lift_inv_flat1 … H1) -H1 #VV1 #TT1 #HVV1 #HTT1 #H1 elim (lift_inv_flat1 … H2) -H2 #VV2 #TT2 #HVV2 #HTT2 #H2 destruct @@ -78,19 +81,21 @@ qed-. lemma cpy_lift_ge: ∀G,K,T1,T2,dt,et. ⦃G, K⦄ ⊢ T1 ▶×[dt, et] T2 → ∀L,U1,U2,d,e. ⇩[d, e] L ≡ K → ⇧[d, e] T1 ≡ U1 → ⇧[d, e] T2 ≡ U2 → - d ≤ dt → ⦃G, L⦄ ⊢ U1 ▶×[dt + e, et] U2. + d ≤ dt → ⦃G, L⦄ ⊢ U1 ▶×[dt+e, et] U2. #G #K #T1 #T2 #dt #et #H elim H -G -K -T1 -T2 -dt -et [ #I #G #K #dt #et #L #U1 #U2 #d #e #_ #H1 #H2 #_ >(lift_mono … H1 … H2) -H1 -H2 // | #I #G #K #KV #V #W #i #dt #et #Hdti #Hidet #HKV #HVW #L #U1 #U2 #d #e #HLK #H #HWU2 #Hddt - lapply (transitive_le … Hddt … Hdti) -Hddt #Hid - lapply (lift_inv_lref1_ge … H … Hid) -H #H destruct + lapply (yle_trans … Hddt … Hdti) -Hddt #Hid + elim (yle_inv_inj2 … Hid) -Hid #dd #Hddi #H0 destruct + lapply (lift_inv_lref1_ge … H … Hddi) -H #H destruct lapply (lift_trans_be … HVW … HWU2 ? ?) -W /2 width=1 by le_S/ >plus_plus_comm_23 #HVU2 - lapply (ldrop_trans_ge_comm … HLK … HKV ?) -K // -Hid /3 width=5 by cpy_subst, lt_minus_to_plus_r, monotonic_le_plus_l/ + lapply (ldrop_trans_ge_comm … HLK … HKV ?) -K // -Hddi + /3 width=5 by cpy_subst, monotonic_ylt_plus_dx, monotonic_yle_plus_dx/ | #a #I #G #K #V1 #V2 #T1 #T2 #dt #et #_ #_ #IHV12 #IHT12 #L #U1 #U2 #d #e #HLK #H1 #H2 #Hddt elim (lift_inv_bind1 … H1) -H1 #VV1 #TT1 #HVV1 #HTT1 #H1 elim (lift_inv_bind1 … H2) -H2 #VV2 #TT2 #HVV2 #HTT2 #H2 destruct - /4 width=5 by cpy_bind, ldrop_skip, le_minus_to_plus/ + /4 width=5 by cpy_bind, ldrop_skip, yle_succ/ | #I #G #K #V1 #V2 #T1 #T2 #dt #et #_ #_ #IHV12 #IHT12 #L #U1 #U2 #d #e #HLK #H1 #H2 #Hddt elim (lift_inv_flat1 … H1) -H1 #VV1 #TT1 #HVV1 #HTT1 #H1 elim (lift_inv_flat1 … H2) -H2 #VV2 #TT2 #HVV2 #HTT2 #H2 destruct @@ -109,15 +114,16 @@ lemma cpy_inv_lift1_le: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶×[dt, et] U2 | lapply (lift_inv_gref2 … H) -H #H destruct /2 width=3 by cpy_atom, lift_gref, ex2_intro/ ] | #I #G #L #KV #V #W #i #dt #et #Hdti #Hidet #HLKV #HVW #K #d #e #HLK #T1 #H #Hdetd - lapply (lt_to_le_to_lt … Hidet … Hdetd) -Hdetd #Hid + lapply (ylt_yle_trans … Hdetd … Hidet) -Hdetd #Hid + lapply (ylt_inv_inj … Hid) -Hid #Hid lapply (lift_inv_lref2_lt … H … Hid) -H #H destruct - elim (ldrop_conf_lt … HLK … HLKV ?) -L // #L #U #HKL #_ #HUV - elim (lift_trans_le … HUV … HVW ?) -V // >minus_plus minus_plus yplus_minus_assoc_inj /2 width=1 by yle_plus_to_minus_inj2/ ] -Hdedet #Hidete elim (ldrop_conf_lt … HLK … HLKV) -L // #L #U #HKL #_ #HUV - elim (lift_trans_le … HUV … HVW) -V // >minus_plus minus_plus plus_minus // commutative_plus >plus_minus /2 width=1 by monotonic_lt_minus_l/ + @(ex2_intro … H) @(cpy_subst … HKV HV1) // (**) (* explicit constructor *) + >yplus_minus_assoc_inj /3 width=1 by monotonic_ylt_minus_dx, yle_inj/ ] | #a #I #G #L #V1 #V2 #U1 #U2 #dt #et #_ #_ #IHV12 #IHU12 #K #d #e #HLK #X #H #Hdtd #Hdedet elim (lift_inv_bind2 … H) -H #W1 #T1 #HWV1 #HTU1 #H destruct elim (IHV12 … HLK … HWV1) -V1 // #W2 #HW12 #HWV2 elim (IHU12 … HTU1) -U1 - [5: /2 width=2 by ldrop_skip/ |2: skip - |3: >plus_plus_comm_23 >(plus_plus_comm_23 dt) /2 width=1 by le_S_S/ - |4: /2 width=1 by le_S_S/ - ] - /3 width=5 by cpy_bind, lift_bind, ex2_intro/ + /3 width=5 by cpy_bind, ldrop_skip, lift_bind, yle_succ, ex2_intro/ | #I #G #L #V1 #V2 #U1 #U2 #dt #et #_ #_ #IHV12 #IHU12 #K #d #e #HLK #X #H #Hdtd #Hdedet elim (lift_inv_flat2 … H) -H #W1 #T1 #HWV1 #HTU1 #H destruct elim (IHV12 … HLK … HWV1) -V1 // @@ -172,7 +174,7 @@ qed-. lemma cpy_inv_lift1_ge: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶×[dt, et] U2 → ∀K,d,e. ⇩[d, e] L ≡ K → ∀T1. ⇧[d, e] T1 ≡ U1 → d + e ≤ dt → - ∃∃T2. ⦃G, K⦄ ⊢ T1 ▶×[dt - e, et] T2 & ⇧[d, e] T2 ≡ U2. + ∃∃T2. ⦃G, K⦄ ⊢ T1 ▶×[dt-e, et] T2 & ⇧[d, e] T2 ≡ U2. #G #L #U1 #U2 #dt #et #H elim H -G -L -U1 -U2 -dt -et [ * #G #L #i #dt #et #K #d #e #_ #T1 #H #_ [ lapply (lift_inv_sort2 … H) -H #H destruct /2 width=3 by cpy_atom, lift_sort, ex2_intro/ @@ -180,21 +182,23 @@ lemma cpy_inv_lift1_ge: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶×[dt, et] U2 | lapply (lift_inv_gref2 … H) -H #H destruct /2 width=3 by cpy_atom, lift_gref, ex2_intro/ ] | #I #G #L #KV #V #W #i #dt #et #Hdti #Hidet #HLKV #HVW #K #d #e #HLK #T1 #H #Hdedt - lapply (transitive_le … Hdedt … Hdti) #Hdei - elim (le_inv_plus_l … Hdedt) -Hdedt #_ #Hedt - elim (le_inv_plus_l … Hdei) #Hdie #Hei - lapply (lift_inv_lref2_ge … H … Hdei) -H #H destruct - lapply (ldrop_conf_ge … HLK … HLKV ?) -L // #HKV - elim (lift_split … HVW d (i-e+1)) -HVW [2,3,4: /2 width=1 by le_S_S, le_S/ ] -Hdei -Hdie - #V0 #HV10 >plus_minus // plus_minus /2 width=1 by monotonic_lt_minus_l/ + lapply (yle_trans … Hdedt … Hdti) #Hdei + elim (yle_inv_plus_inj2 … Hdedt) -Hdedt #_ #Hedt + elim (yle_inv_plus_inj2 … Hdei) #Hdie #Hei + lapply (lift_inv_lref2_ge … H ?) -H /2 width=1 by yle_inv_inj/ #H destruct + lapply (ldrop_conf_ge … HLK … HLKV ?) -L /2 width=1 by yle_inv_inj/ #HKV + elim (lift_split … HVW d (i-e+1)) -HVW [2,3,4: /3 width=1 by yle_inv_inj, le_S_S, le_S/ ] -Hdei -Hdie + #V0 #HV10 >plus_minus /2 width=1 by yle_inv_inj/ yminus_succ1_inj /3 width=5 by cpy_bind, lift_bind, ex2_intro/ | #I #G #L #V1 #V2 #U1 #U2 #dt #et #_ #_ #IHV12 #IHU12 #K #d #e #HLK #X #H #Hdetd elim (lift_inv_flat2 … H) -H #W1 #T1 #HWV1 #HTU1 #H destruct elim (IHV12 … HLK … HWV1) -V1 // @@ -202,23 +206,20 @@ lemma cpy_inv_lift1_ge: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶×[dt, et] U2 ] qed-. -lemma cpy_inv_lift1_eq: ∀G,L,U1,U2,d,e. - ⦃G, L⦄ ⊢ U1 ▶×[d, e] U2 → ∀T1. ⇧[d, e] T1 ≡ U1 → U1 = U2. -#G #L #U1 #U2 #d #e #H elim H -G -L -U1 -U2 -d -e -[ // -| #I #G #L #K #V #W #i #d #e #Hdi #Hide #_ #_ #T1 #H - elim (lift_inv_lref2 … H) -H * #H - [ lapply (le_to_lt_to_lt … Hdi … H) -Hdi -H #H - elim (lt_refl_false … H) - | lapply (lt_to_le_to_lt … Hide … H) -Hide -H #H - elim (lt_refl_false … H) - ] -| #a #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #X #HX - elim (lift_inv_bind2 … HX) -HX #V #T #HV1 #HT1 #H destruct - >IHV12 // >IHT12 // -| #I #G #L #V1 #V2 #T1 #T2 #d #e #_ #_ #IHV12 #IHT12 #X #HX - elim (lift_inv_flat2 … HX) -HX #V #T #HV1 #HT1 #H destruct - >IHV12 // >IHT12 // +lemma cpy_inv_lift1_eq: ∀G,T1,U1,d,e. ⇧[d, e] T1 ≡ U1 → + ∀L,U2. ⦃G, L⦄ ⊢ U1 ▶×[d, e] U2 → U1 = U2. +#G #T1 #U1 #d #e #H elim H -T1 -U1 -d -e +[ #k #d #e #L #X #H >(cpy_inv_sort1 … H) -H // +| #i #d #e #Hid #L #X #H elim (cpy_inv_lref1 … H) -H // + * #I #K #V #H elim (ylt_yle_false … H) -H /2 width=1 by ylt_inj/ +| #i #d #e #Hdi #L #X #H elim (cpy_inv_lref1 … H) -H // + * #I #K #V #_ #H elim (ylt_yle_false i d) + /2 width=2 by ylt_inv_monotonic_plus_dx, yle_inj/ +| #p #d #e #L #X #H >(cpy_inv_gref1 … H) -H // +| #a #I #V1 #W1 #T1 #U1 #d #e #_ #_ #IHVW1 #IHTU1 #L #X #H elim (cpy_inv_bind1 … H) -H + #W2 #U2 #HW12 #HU12 #H destruct /3 width=2 by eq_f2/ +| #I #V1 #W1 #T1 #U1 #d #e #_ #_ #IHVW1 #IHTU1 #L #X #H elim (cpy_inv_flat1 … H) -H + #W2 #U2 #HW12 #HU12 #H destruct /3 width=2 by eq_f2/ ] qed-. @@ -228,17 +229,18 @@ lemma cpy_inv_lift1_ge_up: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶×[dt, et] U ∃∃T2. ⦃G, K⦄ ⊢ T1 ▶×[d, dt + et - (d + e)] T2 & ⇧[d, e] T2 ≡ U2. #G #L #U1 #U2 #dt #et #HU12 #K #d #e #HLK #T1 #HTU1 #Hddt #Hdtde #Hdedet elim (cpy_split_up … HU12 (d + e)) -HU12 // -Hdedet #U #HU1 #HU2 -lapply (cpy_weak … HU1 d e ? ?) -HU1 // [ >commutative_plus /2 width=1 by le_minus_to_plus_r/ ] -Hddt -Hdtde #HU1 -lapply (cpy_inv_lift1_eq … HU1 … HTU1) -HU1 #HU1 destruct -elim (cpy_inv_lift1_ge … HU2 … HLK … HTU1) -U -L // ymax_pre_sn_comm // ] -Hddt -Hdtde #HU1 +lapply (cpy_inv_lift1_eq … HTU1 … HU1) -HU1 #HU1 destruct +elim (cpy_inv_lift1_ge … HU2 … HLK … HTU1) -U -L /2 width=3 by ex2_intro/ qed-. lemma cpy_inv_lift1_be_up: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶×[dt, et] U2 → ∀K,d,e. ⇩[d, e] L ≡ K → ∀T1. ⇧[d, e] T1 ≡ U1 → dt ≤ d → dt + et ≤ d + e → - ∃∃T2. ⦃G, K⦄ ⊢ T1 ▶×[dt, d - dt] T2 & ⇧[d, e] T2 ≡ U2. + ∃∃T2. ⦃G, K⦄ ⊢ T1 ▶×[dt, d-dt] T2 & ⇧[d, e] T2 ≡ U2. #G #L #U1 #U2 #dt #et #HU12 #K #d #e #HLK #T1 #HTU1 #Hdtd #Hdetde -lapply (cpy_weak … HU12 dt (d + e - dt) ? ?) -HU12 /2 width=3 by transitive_le, le_n/ -Hdetde #HU12 +lapply (cpy_weak … HU12 dt (d+e-dt) ? ?) -HU12 // +[ >ymax_pre_sn_comm /2 width=1 by yle_plus_dx1_trans/ ] -Hdetde #HU12 elim (cpy_inv_lift1_be … HU12 … HLK … HTU1) -U1 -L /2 width=3 by ex2_intro/ qed-. @@ -248,7 +250,9 @@ lemma cpy_inv_lift1_le_up: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶×[dt, et] U ∃∃T2. ⦃G, K⦄ ⊢ T1 ▶×[dt, d - dt] T2 & ⇧[d, e] T2 ≡ U2. #G #L #U1 #U2 #dt #et #HU12 #K #d #e #HLK #T1 #HTU1 #Hdtd #Hddet #Hdetde elim (cpy_split_up … HU12 d) -HU12 // #U #HU1 #HU2 -elim (cpy_inv_lift1_le … HU1 … HLK … HTU1) -U1 [2: >commutative_plus /2 width=1 by le_minus_to_plus_r/ ] -Hdtd #T #HT1 #HTU -lapply (cpy_weak … HU2 d e ? ?) -HU2 // [ >commutative_plus ymax_pre_sn_comm // ] -Hdtd #T #HT1 #HTU +lapply (cpy_weak … HU2 d e ? ?) -HU2 // +[ >ymax_pre_sn_comm // ] -Hddet -Hdetde #HU2 +lapply (cpy_inv_lift1_eq … HTU … HU2) -L #H destruct /2 width=3 by ex2_intro/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/ldrop_leq.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/ldrop_leq.ma index 2c58473a3..47ac4653d 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/ldrop_leq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/ldrop_leq.ma @@ -66,8 +66,8 @@ lemma ldrop_leq_conf_be: ∀L1,L2,d,e. L1 ≃[d, e] L2 → >yminus_succ /3 width=5 by ldrop_ldrop_lt, ex2_3_intro/ ] | #I #L1 #L2 #V #d #e #_ #IHL12 #J1 #K1 #W1 #i #H #Hdi lapply (ylt_yle_trans 0 … Hdi ?) // - #Hi <(ylt_inv_O1 … Hi) >yplus_succ1 >yminus_succ lapply (yle_fwd_succ1 … Hdi) -Hdi - #Hdi #Hide lapply (ylt_inv_succ … Hide) + #Hi <(ylt_inv_O1 … Hi) >yplus_succ1 >yminus_succ elim (yle_inv_succ1 … Hdi) -Hdi + #Hdi #_ #Hide lapply (ylt_inv_succ … Hide) #Hide lapply (ylt_inv_inj … Hi) -Hi #Hi lapply (ldrop_inv_ldrop1_lt … H ?) -H // #H elim (IHL12 … H) -IHL12 -H diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/lsuby.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/lsuby.ma index 3c89103c3..a8567a4b2 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/lsuby.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/lsuby.ma @@ -12,19 +12,20 @@ (* *) (**************************************************************************) +include "ground_2/ynat/ynat_plus.ma". include "basic_2/notation/relations/extlrsubeq_4.ma". include "basic_2/relocation/ldrop.ma". (* LOCAL ENVIRONMENT REFINEMENT FOR EXTENDED SUBSTITUTION *******************) -inductive lsuby: relation4 nat nat lenv lenv ≝ +inductive lsuby: relation4 ynat ynat lenv lenv ≝ | lsuby_atom: ∀L,d,e. lsuby d e L (⋆) | lsuby_zero: ∀I1,I2,L1,L2,V1,V2. lsuby 0 0 L1 L2 → lsuby 0 0 (L1.ⓑ{I1}V1) (L2.ⓑ{I2}V2) | lsuby_pair: ∀I1,I2,L1,L2,V,e. lsuby 0 e L1 L2 → - lsuby 0 (e + 1) (L1.ⓑ{I1}V) (L2.ⓑ{I2}V) + lsuby 0 (⫯e) (L1.ⓑ{I1}V) (L2.ⓑ{I2}V) | lsuby_succ: ∀I1,I2,L1,L2,V1,V2,d,e. - lsuby d e L1 L2 → lsuby (d + 1) e (L1. ⓑ{I1}V1) (L2. ⓑ{I2} V2) + lsuby d e L1 L2 → lsuby (⫯d) e (L1. ⓑ{I1}V1) (L2. ⓑ{I2} V2) . interpretation @@ -33,23 +34,25 @@ interpretation (* Basic properties *********************************************************) -lemma lsuby_pair_lt: ∀I1,I2,L1,L2,V,e. L1 ⊑×[0, e-1] L2 → 0 < e → +lemma lsuby_pair_lt: ∀I1,I2,L1,L2,V,e. L1 ⊑×[0, ⫰e] L2 → 0 < e → L1.ⓑ{I1}V ⊑×[0, e] L2.ⓑ{I2}V. -#I1 #I2 #L1 #L2 #V #e #HL12 #He >(plus_minus_m_m e 1) /2 width=1 by lsuby_pair/ +#I1 #I2 #L1 #L2 #V #e #HL12 #He <(ylt_inv_O1 … He) /2 width=1 by lsuby_pair/ qed. -lemma lsuby_succ_lt: ∀I1,I2,L1,L2,V1,V2,d,e. L1 ⊑×[d-1, e] L2 → 0 < d → +lemma lsuby_succ_lt: ∀I1,I2,L1,L2,V1,V2,d,e. L1 ⊑×[⫰d, e] L2 → 0 < d → L1.ⓑ{I1}V1 ⊑×[d, e] L2. ⓑ{I2}V2. -#I1 #I2 #L1 #L2 #V1 #V2 #d #e #HL12 #Hd >(plus_minus_m_m d 1) /2 width=1 by lsuby_succ/ +#I1 #I2 #L1 #L2 #V1 #V2 #d #e #HL12 #Hd <(ylt_inv_O1 … Hd) /2 width=1 by lsuby_succ/ qed. lemma lsuby_refl: ∀L,d,e. L ⊑×[d, e] L. #L elim L -L // -#L #I #V #IHL #d @(nat_ind_plus … d) -d /2 width=1 by lsuby_succ/ -#e @(nat_ind_plus … e) -e /2 width=2 by lsuby_pair, lsuby_zero/ +#L #I #V #IHL #d elim (ynat_cases … d) [| * #x ] +#Hd destruct /2 width=1 by lsuby_succ/ +#e elim (ynat_cases … e) [| * #x ] +#He destruct /2 width=1 by lsuby_zero, lsuby_pair/ qed. -lemma lsuby_length: ∀L1,L2. |L2| ≤ |L1| → L1 ⊑×[0, 0] L2. +lemma lsuby_length: ∀L1,L2. |L2| ≤ |L1| → L1 ⊑×[yinj 0, yinj 0] L2. #L1 elim L1 -L1 [ #X #H lapply (le_n_O_to_eq … H) -H #H lapply (length_inv_zero_sn … H) #H destruct /2 width=1 by lsuby_atom/ @@ -78,10 +81,10 @@ fact lsuby_inv_zero1_aux: ∀L1,L2,d,e. L1 ⊑×[d, e] L2 → #L1 #L2 #d #e * -L1 -L2 -d -e /2 width=1 by or_introl/ [ #I1 #I2 #L1 #L2 #V1 #V2 #HL12 #J1 #K1 #W1 #H #_ #_ destruct /3 width=5 by ex2_3_intro, or_intror/ -| #I1 #I2 #L1 #L2 #V #e #_ #J1 #K1 #W1 #_ #_ - minus_minus_comm >arith_b1 /3 width=4 by ldrop_ldrop_lt, ex2_2_intro/ + elim (ylt_yle_false … H) // +| #I1 #I2 #L1 #L2 #V #e #HL12 #IHL12 #J2 #K2 #W #i #H #_ >yplus_O_sn + elim (ldrop_inv_O1_pair1 … H) -H * #Hi #HLK1 [ -IHL12 | -HL12 ] + [ #_ destruct -I2 >ypred_succ + /2 width=4 by ldrop_pair, ex2_2_intro/ + | lapply (ylt_inv_O1 i ?) /2 width=1 by ylt_inj/ + #H yminus_succ plus_plus_comm_23 #Hide - elim (le_inv_plus_l … Hdi) #_ #Hi - lapply (ldrop_inv_ldrop1_lt … H ?) -H // #HLK1 - elim (IHL12 … HLK1) -IHL12 -HLK1 - [2,3: /2 width=1 by lt_plus_to_minus, monotonic_pred/ ] -Hdi -Hide - >minus_minus_comm >arith_b1 /3 width=4 by ldrop_ldrop_lt, ex2_2_intro/ +| #I1 #I2 #L1 #L2 #V1 #V2 #d #e #_ #IHL12 #J2 #K2 #W #i #HLK2 #Hdi + elim (yle_inv_succ1 … Hdi) -Hdi + #Hdi #Hi yplus_succ1 #H lapply (ylt_inv_succ … H) -H + #Hide lapply (ldrop_inv_ldrop1_lt … HLK2 ?) -HLK2 /2 width=1 by ylt_O/ + #HLK1 elim (IHL12 … HLK1) -IHL12 -HLK1 yminus_SO2 + /4 width=4 by ylt_O, ldrop_ldrop_lt, ex2_2_intro/ ] qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys.ma b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys.ma index 91f9f35aa..033034d53 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys.ma @@ -17,7 +17,7 @@ include "basic_2/relocation/cpy.ma". (* CONTEXT-SENSITIVE EXTENDED MULTIPLE SUBSTITUTION FOR TERMS ***************) -definition cpys: nat → nat → relation4 genv lenv term term ≝ +definition cpys: ynat → ynat → relation4 genv lenv term term ≝ λd,e,G. LTC … (cpy d e G). interpretation "context-sensitive extended multiple substritution (term)" diff --git a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_alt.ma b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_alt.ma index cf0b10e76..045aa4490 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_alt.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_alt.ma @@ -18,9 +18,9 @@ include "basic_2/substitution/cpys_lift.ma". (* CONTEXT-SENSITIVE EXTENDED MULTIPLE SUBSTITUTION FOR TERMS ***************) (* alternative definition of cpys *) -inductive cpysa: nat → nat → relation4 genv lenv term term ≝ +inductive cpysa: ynat → ynat → relation4 genv lenv term term ≝ | cpysa_atom : ∀I,G,L,d,e. cpysa d e G L (⓪{I}) (⓪{I}) -| cpysa_subst: ∀I,G,L,K,V1,V2,W2,i,d,e. d ≤ i → i < d + e → +| cpysa_subst: ∀I,G,L,K,V1,V2,W2,i,d,e. d ≤ yinj i → i < d+e → ⇩[0, i] L ≡ K.ⓑ{I}V1 → cpysa 0 (d+e-i-1) G K V1 V2 → ⇧[0, i+1] V2 ≡ W2 → cpysa d e G L (#i) W2 | cpysa_bind : ∀a,I,G,L,V1,V2,T1,T2,d,e. @@ -60,7 +60,8 @@ lemma cpysa_cpy_trans: ∀G,L,T1,T,d,e. ⦃G, L⦄ ⊢ T1 ▶▶*×[d, e] T → | #I #G #L #K #V1 #V2 #W2 #i #d #e #Hdi #Hide #HLK #_ #HVW2 #IHV12 #T2 #H lapply (ldrop_fwd_ldrop2 … HLK) #H0LK lapply (cpy_weak … H 0 (d+e) ? ?) -H // #H - elim (cpy_inv_lift1_be … H … H0LK … HVW2) -H -H0LK -HVW2 /3 width=7 by cpysa_subst/ + elim (cpy_inv_lift1_be … H … H0LK … HVW2) -H -H0LK -HVW2 + /3 width=7 by cpysa_subst, ylt_fwd_le_succ/ | #a #I #G #L #V1 #V #T1 #T #d #e #_ #_ #IHV1 #IHT1 #X #H elim (cpy_inv_bind1 … H) -H #V2 #T2 #HV2 #HT2 #H destruct lapply (lsuby_cpy_trans … HT2 (L.ⓑ{I}V) ?) -HT2 /2 width=1 by lsuby_succ/ #HT2 @@ -82,9 +83,9 @@ lemma cpysa_cpys: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶▶*×[d, e] T2 → ⦃ /2 width=7 by cpys_subst, cpys_flat, cpys_bind, cpy_cpys/ qed-. -lemma cpys_ind_alt: ∀R:nat→nat→relation4 genv lenv term term. +lemma cpys_ind_alt: ∀R:ynat→ynat→relation4 genv lenv term term. (∀I,G,L,d,e. R d e G L (⓪{I}) (⓪{I})) → - (∀I,G,L,K,V1,V2,W2,i,d,e. d ≤ i → i < d + e → + (∀I,G,L,K,V1,V2,W2,i,d,e. d ≤ yinj i → i < d + e → ⇩[O, i] L ≡ K.ⓑ{I}V1 → ⦃G, K⦄ ⊢ V1 ▶*×[O, d+e-i-1] V2 → ⇧[O, i + 1] V2 ≡ W2 → R O (d+e-i-1) G K V1 V2 → R d e G L (#i) W2 ) → diff --git a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_cpys.ma b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_cpys.ma index f84916b9b..41ab4081d 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_cpys.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_cpys.ma @@ -52,9 +52,9 @@ lemma cpys_split_up: ∀G,L,T1,T2,d,e. ⦃G, L⦄ ⊢ T1 ▶*×[d, e] T2 → #G #L #T1 #T2 #d #e #H #i #Hdi #Hide @(cpys_ind … H) -T2 [ /2 width=3 by ex2_intro/ | #T #T2 #_ #HT12 * #T3 #HT13 #HT3 - elim (cpy_split_up … HT12 … Hdi Hide) -HT12 -Hide #T0 #HT0 #HT02 - elim (cpys_strap1_down … HT3 … HT0 ?) -T /3 width=5 by cpys_strap1, ex2_intro/ - >commutative_plus /2 width=1 by le_minus_to_plus_r/ + elim (cpy_split_up … HT12 … Hide) -HT12 -Hide #T0 #HT0 #HT02 + elim (cpys_strap1_down … HT3 … HT0) -T /3 width=5 by cpys_strap1, ex2_intro/ + >ymax_pre_sn_comm // ] qed-. @@ -65,9 +65,10 @@ lemma cpys_inv_lift1_up: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶*×[dt, et] U2 ⇧[d, e] T2 ≡ U2. #G #L #U1 #U2 #dt #et #HU12 #K #d #e #HLK #T1 #HTU1 #Hddt #Hdtde #Hdedet elim (cpys_split_up … HU12 (d + e)) -HU12 // -Hdedet #U #HU1 #HU2 -lapply (cpys_weak … HU1 d e ? ?) -HU1 // [ >commutative_plus /2 width=1 by le_minus_to_plus_r/ ] -Hddt -Hdtde #HU1 +lapply (cpys_weak … HU1 d e ? ?) -HU1 // [ >ymax_pre_sn_comm // ] -Hddt -Hdtde #HU1 lapply (cpys_inv_lift1_eq … HU1 … HTU1) -HU1 #HU1 destruct -elim (cpys_inv_lift1_ge … HU2 … HLK … HTU1) -HU2 -HLK -HTU1 // yplus_minus_inj /2 width=3 by ex2_intro/ qed-. (* Main properties **********************************************************) diff --git a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_lift.ma b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_lift.ma index 631ab202d..3cf6f8b31 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_lift.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/substitution/cpys_lift.ma @@ -20,39 +20,41 @@ include "basic_2/substitution/cpys.ma". (* Advanced properties ******************************************************) lemma cpys_subst: ∀I,G,L,K,V,U1,i,d,e. - d ≤ i → i < d + e → - ⇩[0, i] L ≡ K.ⓑ{I}V → ⦃G, K⦄ ⊢ V ▶*×[0, d+e-i-1] U1 → - ∀U2. ⇧[0, i + 1] U1 ≡ U2 → ⦃G, L⦄ ⊢ #i ▶*×[d, e] U2. + d ≤ yinj i → i < d + e → + ⇩[0, i] L ≡ K.ⓑ{I}V → ⦃G, K⦄ ⊢ V ▶*×[0, ⫰(d+e-i)] U1 → + ∀U2. ⇧[0, i+1] U1 ≡ U2 → ⦃G, L⦄ ⊢ #i ▶*×[d, e] U2. #I #G #L #K #V #U1 #i #d #e #Hdi #Hide #HLK #H @(cpys_ind … H) -U1 [ /3 width=5 by cpy_cpys, cpy_subst/ | #U #U1 #_ #HU1 #IHU #U2 #HU12 elim (lift_total U 0 (i+1)) #U0 #HU0 lapply (IHU … HU0) -IHU #H lapply (ldrop_fwd_ldrop2 … HLK) -HLK #HLK - lapply (cpy_lift_ge … HU1 … HLK HU0 HU12 ?) -HU1 -HLK -HU0 -HU12 // normalize #HU02 - lapply (cpy_weak … HU02 d e ? ?) -HU02 [2,3: /2 width=3 by cpys_strap1, le_S/ ] - >minus_plus >commutative_plus /2 width=1 by le_minus_to_plus_r/ + lapply (cpy_lift_ge … HU1 … HLK HU0 HU12 ?) -HU1 -HLK -HU0 -HU12 // #HU02 + lapply (cpy_weak … HU02 d e ? ?) -HU02 + [2,3: /2 width=3 by cpys_strap1, yle_succ_dx/ ] + >yplus_O_sn ymax_pre_sn_comm /2 width=1 by ylt_fwd_le_succ/ ] qed. (* Advanced inverion lemmas *************************************************) -lemma cpys_inv_atom1: ∀G,L,T2,I,d,e. ⦃G, L⦄ ⊢ ⓪{I} ▶*×[d, e] T2 → +lemma cpys_inv_atom1: ∀I,G,L,T2,d,e. ⦃G, L⦄ ⊢ ⓪{I} ▶*×[d, e] T2 → T2 = ⓪{I} ∨ - ∃∃J,K,V1,V2,i. d ≤ i & i < d + e & + ∃∃J,K,V1,V2,i. d ≤ yinj i & i < d + e & ⇩[O, i] L ≡ K.ⓑ{J}V1 & ⦃G, K⦄ ⊢ V1 ▶*×[0, d+e-i-1] V2 & - ⇧[O, i + 1] V2 ≡ T2 & + ⇧[O, i+1] V2 ≡ T2 & I = LRef i. -#G #L #T2 #I #d #e #H @(cpys_ind … H) -T2 +#I #G #L #T2 #d #e #H @(cpys_ind … H) -T2 [ /2 width=1 by or_introl/ | #T #T2 #_ #HT2 * [ #H destruct elim (cpy_inv_atom1 … HT2) -HT2 [ /2 width=1 by or_introl/ | * /3 width=11 by ex6_5_intro, or_intror/ ] | * #J #K #V1 #V #i #Hdi #Hide #HLK #HV1 #HVT #HI lapply (ldrop_fwd_ldrop2 … HLK) #H - elim (cpy_inv_lift1_ge_up … HT2 … H … HVT) normalize -HT2 -H -HVT [2,3,4: /2 width=1 by le_S/ ] - (lift_mono … HTU1 … H) -H // | -HTU1 #T #T2 #_ #HT2 #IHT #U2 #HTU2 @@ -137,15 +139,15 @@ lemma cpys_inv_lift1_ge: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶*×[dt, et] U2 #G #L #U1 #U2 #dt #et #H #K #d #e #HLK #T1 #HTU1 #Hdedt @(cpys_ind … H) -U2 [ /2 width=3 by ex2_intro/ | -HTU1 #U #U2 #_ #HU2 * #T #HT1 #HTU - elim (cpy_inv_lift1_ge … HU2 … HLK … HTU ?) -HU2 -HLK -HTU /3 width=3 by cpys_strap1, ex2_intro/ + elim (cpy_inv_lift1_ge … HU2 … HLK … HTU) -HU2 -HLK -HTU /3 width=3 by cpys_strap1, ex2_intro/ ] qed-. -lemma cpys_inv_lift1_eq: ∀G,L,U1,U2,d,e. +lemma cpys_inv_lift1_eq: ∀G,L,U1,U2. ∀d,e:nat. ⦃G, L⦄ ⊢ U1 ▶*×[d, e] U2 → ∀T1. ⇧[d, e] T1 ≡ U1 → U1 = U2. #G #L #U1 #U2 #d #e #H #T1 #HTU1 @(cpys_ind … H) -U2 // #U #U2 #_ #HU2 #IHU destruct -<(cpy_inv_lift1_eq … HU2 … HTU1) -HU2 -HTU1 // +<(cpy_inv_lift1_eq … HTU1 … HU2) -HU2 -HTU1 // qed-. lemma cpys_inv_lift1_ge_up: ∀G,L,U1,U2,dt,et. ⦃G, L⦄ ⊢ U1 ▶*×[dt, et] U2 → diff --git a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma index 265572bae..6cc21d5bc 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma @@ -26,10 +26,14 @@ interpretation "ynat 'less than'" 'lt x y = (ylt x y). (* Basic forward lemmas *****************************************************) -lemma ylt_inv_gen: ∀x,y. x < y → ∃m. x = yinj m. +lemma ylt_fwd_gen: ∀x,y. x < y → ∃m. x = yinj m. #x #y * -x -y /2 width=2 by ex_intro/ qed-. +lemma ylt_fwd_le_succ: ∀x,y. x < y → ⫯x ≤ y. +#x #y * -x -y /2 width=1 by yle_inj/ +qed-. + (* Basic inversion lemmas ***************************************************) fact ylt_inv_inj2_aux: ∀x,y. x < y → ∀n. y = yinj n → @@ -51,7 +55,7 @@ lemma ylt_inv_inj: ∀m,n. yinj m < yinj n → m < n. qed-. lemma ylt_inv_Y1: ∀n. ∞ < n → ⊥. -#n #H elim (ylt_inv_gen … H) -H +#n #H elim (ylt_fwd_gen … H) -H #y #H destruct qed-. diff --git a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma index a8ede2637..10a841cbd 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma @@ -55,7 +55,7 @@ lemma yminus_succ: ∀n,m. ⫯m - ⫯n = m - n. #m >yminus_inj // qed. -lemma yminus_succ1_inj: ∀n:nat. ∀m:ynat. n ≤ m → ⫯m - n = ⫯(m - n). +lemma yminus_succ1_inj: ∀n:nat. ∀m:ynat. n ≤ m → ⫯m - n = ⫯(m - n). #n * [ #m #Hmn >yminus_inj >yminus_inj /4 width=1 by yle_inv_inj, plus_minus, eq_f/ @@ -63,6 +63,10 @@ lemma yminus_succ1_inj: ∀n:nat. ∀m:ynat. n ≤ m → ⫯m - n = ⫯(m - n). ] qed-. +lemma yminus_succ2: ∀y,x. x - ⫯y = ⫰(x-y). +* // +qed. + (* Properties on order ******************************************************) lemma yle_minus_sn: ∀n,m. m - n ≤ m. -- 2.39.2