X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;ds=sidebyside;f=matita%2Fmatita%2Flib%2Flambda-delta%2Fsubstitution%2Flift_main.ma;h=a41e49c5b86eea11ab3d1d0929b7445de2f31678;hb=6f29b61aeae23efb412ac48ab747d63bcedcacd6;hp=2f588c1a6fcf48c8bd7118da260016bfc4263c07;hpb=13935d33cc0899b9555648a4d49586e17274c748;p=helm.git diff --git a/matita/matita/lib/lambda-delta/substitution/lift_main.ma b/matita/matita/lib/lambda-delta/substitution/lift_main.ma index 2f588c1a6..a41e49c5b 100644 --- a/matita/matita/lib/lambda-delta/substitution/lift_main.ma +++ b/matita/matita/lib/lambda-delta/substitution/lift_main.ma @@ -18,21 +18,18 @@ include "lambda-delta/substitution/lift_defs.ma". (* the main properies *******************************************************) -theorem lift_conf_rev: ∀d1,e1,T1,T. ↑[d1,e1] T1 ≡ T → - ∀d2,e2,T2. ↑[d2 + e1, e2] T2 ≡ T → - d1 ≤ d2 → - ∃∃T0. ↑[d1, e1] T0 ≡ T2 & ↑[d2, e2] T0 ≡ T1. +lemma lift_div_le: ∀d1,e1,T1,T. ↑[d1, e1] T1 ≡ T → + ∀d2,e2,T2. ↑[d2 + e1, e2] T2 ≡ T → + d1 ≤ d2 → + ∃∃T0. ↑[d1, e1] T0 ≡ T2 & ↑[d2, e2] T0 ≡ T1. #d1 #e1 #T1 #T #H elim H -H d1 e1 T1 T [ #k #d1 #e1 #d2 #e2 #T2 #Hk #Hd12 lapply (lift_inv_sort2 … Hk) -Hk #Hk destruct -T2 /3/ | #i #d1 #e1 #Hid1 #d2 #e2 #T2 #Hi #Hd12 - lapply (lift_inv_lref2 … Hi) -Hi * * #Hid2 #H destruct -T2 - [ -Hid2 /4/ - | elim (lt_false d1 ?) - @(le_to_lt_to_lt … Hd12) -Hd12 @(le_to_lt_to_lt … Hid1) -Hid1 /2/ - ] + lapply (lt_to_le_to_lt … Hid1 Hd12) -Hd12 #Hid2 + lapply (lift_inv_lref2_lt … Hi ?) -Hi /3/ | #i #d1 #e1 #Hid1 #d2 #e2 #T2 #Hi #Hd12 - lapply (lift_inv_lref2 … Hi) -Hi * * #Hid2 #H destruct -T2 + elim (lift_inv_lref2 … Hi) -Hi * #Hid2 #H destruct -T2 [ -Hd12; lapply (lt_plus_to_lt_l … Hid2) -Hid2 #Hid2 /3/ | -Hid1; lapply (arith1 … Hid2) -Hid2 #Hid2 @(ex2_1_intro … #(i - e2)) @@ -51,9 +48,9 @@ theorem lift_conf_rev: ∀d1,e1,T1,T. ↑[d1,e1] T1 ≡ T → ] qed. -theorem lift_free: ∀d1,e2,T1,T2. ↑[d1, e2] T1 ≡ T2 → ∀d2,e1. - d1 ≤ d2 → d2 ≤ d1 + e1 → e1 ≤ e2 → - ∃∃T. ↑[d1, e1] T1 ≡ T & ↑[d2, e2 - e1] T ≡ T2. +lemma lift_free: ∀d1,e2,T1,T2. ↑[d1, e2] T1 ≡ T2 → ∀d2,e1. + d1 ≤ d2 → d2 ≤ d1 + e1 → e1 ≤ e2 → + ∃∃T. ↑[d1, e1] T1 ≡ T & ↑[d2, e2 - e1] T ≡ T2. #d1 #e2 #T1 #T2 #H elim H -H d1 e2 T1 T2 [ /3/ | #i #d1 #e2 #Hid1 #d2 #e1 #Hd12 #_ #_ @@ -70,42 +67,77 @@ theorem lift_free: ∀d1,e2,T1,T2. ↑[d1, e2] T1 ≡ T2 → ∀d2,e1. ] qed. -theorem lift_trans: ∀d1,e1,T1,T. ↑[d1, e1] T1 ≡ T → - ∀d2,e2,T2. ↑[d2, e2] T ≡ T2 → - d1 ≤ d2 → d2 ≤ d1 + e1 → ↑[d1, e1 + e2] T1 ≡ T2. -#d1 #e1 #T1 #T #H elim H -d1 e1 T1 T +lemma lift_trans_be: ∀d1,e1,T1,T. ↑[d1, e1] T1 ≡ T → + ∀d2,e2,T2. ↑[d2, e2] T ≡ T2 → + d1 ≤ d2 → d2 ≤ d1 + e1 → ↑[d1, e1 + e2] T1 ≡ T2. +#d1 #e1 #T1 #T #H elim H -H d1 e1 T1 T [ #k #d1 #e1 #d2 #e2 #T2 #HT2 #_ #_ >(lift_inv_sort1 … HT2) -HT2 // | #i #d1 #e1 #Hid1 #d2 #e2 #T2 #HT2 #Hd12 #_ - lapply (lift_inv_lref1 … HT2) -HT2 * * #Hid2 #H destruct -T2 - [ -Hd12 Hid2 /2/ - | lapply (le_to_lt_to_lt … d1 Hid2 ?) // -Hid1 Hid2 #Hd21 - lapply (le_to_lt_to_lt … d1 Hd12 ?) // -Hd12 Hd21 #Hd11 - elim (lt_false … Hd11) - ] + lapply (lt_to_le_to_lt … Hid1 Hd12) -Hd12 #Hid2 + lapply (lift_inv_lref1_lt … HT2 Hid2) /2/ | #i #d1 #e1 #Hid1 #d2 #e2 #T2 #HT2 #_ #Hd21 - lapply (lift_inv_lref1 … HT2) -HT2 * * #Hid2 #H destruct -T2 - [ lapply (lt_to_le_to_lt … (d1+e1) Hid2 ?) // -Hid2 Hd21 #H - lapply (lt_plus_to_lt_l … H) -H #H - lapply (le_to_lt_to_lt … d1 Hid1 ?) // -Hid1 H #Hd11 - elim (lt_false … Hd11) - | -Hd21 Hid2 /2/ + lapply (lift_inv_lref1_ge … HT2 ?) -HT2 + [ @(transitive_le … Hd21 ?) -Hd21 /2/ + | -Hd21 /2/ ] | #I #V1 #V2 #T1 #T2 #d1 #e1 #_ #_ #IHV12 #IHT12 #d2 #e2 #X #HX #Hd12 #Hd21 - lapply (lift_inv_bind1 … HX) -HX * #V0 #T0 #HV20 #HT20 #HX destruct -X; + elim (lift_inv_bind1 … HX) -HX #V0 #T0 #HV20 #HT20 #HX destruct -X; lapply (IHV12 … HV20 ? ?) // -IHV12 HV20 #HV10 lapply (IHT12 … HT20 ? ?) /2/ | #I #V1 #V2 #T1 #T2 #d1 #e1 #_ #_ #IHV12 #IHT12 #d2 #e2 #X #HX #Hd12 #Hd21 - lapply (lift_inv_flat1 … HX) -HX * #V0 #T0 #HV20 #HT20 #HX destruct -X; + elim (lift_inv_flat1 … HX) -HX #V0 #T0 #HV20 #HT20 #HX destruct -X; lapply (IHV12 … HV20 ? ?) // -IHV12 HV20 #HV10 lapply (IHT12 … HT20 ? ?) /2/ ] qed. -axiom lift_trans_le: ∀d1,e1,T1,T. ↑[d1, e1] T1 ≡ T → +lemma lift_trans_le: ∀d1,e1,T1,T. ↑[d1, e1] T1 ≡ T → ∀d2,e2,T2. ↑[d2, e2] T ≡ T2 → d2 ≤ d1 → ∃∃T0. ↑[d2, e2] T1 ≡ T0 & ↑[d1 + e2, e1] T0 ≡ T2. +#d1 #e1 #T1 #T #H elim H -H d1 e1 T1 T +[ #k #d1 #e1 #d2 #e2 #X #HX #_ + >(lift_inv_sort1 … HX) -HX /2/ +| #i #d1 #e1 #Hid1 #d2 #e2 #X #HX #_ + lapply (lt_to_le_to_lt … (d1+e2) Hid1 ?) // #Hie2 + elim (lift_inv_lref1 … HX) -HX * #Hid2 #HX destruct -X /4/ +| #i #d1 #e1 #Hid1 #d2 #e2 #X #HX #Hd21 + lapply (transitive_le … Hd21 Hid1) -Hd21 #Hid2 + lapply (lift_inv_lref1_ge … HX ?) -HX /2/ #HX destruct -X; + >plus_plus_comm_23 /4/ +| #I #V1 #V2 #T1 #T2 #d1 #e1 #_ #_ #IHV12 #IHT12 #d2 #e2 #X #HX #Hd21 + elim (lift_inv_bind1 … HX) -HX #V0 #T0 #HV20 #HT20 #HX destruct -X; + elim (IHV12 … HV20 ?) -IHV12 HV20 // + elim (IHT12 … HT20 ?) -IHT12 HT20 /3 width=5/ +| #I #V1 #V2 #T1 #T2 #d1 #e1 #_ #_ #IHV12 #IHT12 #d2 #e2 #X #HX #Hd21 + elim (lift_inv_flat1 … HX) -HX #V0 #T0 #HV20 #HT20 #HX destruct -X; + elim (IHV12 … HV20 ?) -IHV12 HV20 // + elim (IHT12 … HT20 ?) -IHT12 HT20 /3 width=5/ +] +qed. -axiom lift_trans_ge: ∀d1,e1,T1,T. ↑[d1, e1] T1 ≡ T → +lemma lift_trans_ge: ∀d1,e1,T1,T. ↑[d1, e1] T1 ≡ T → ∀d2,e2,T2. ↑[d2, e2] T ≡ T2 → d1 + e1 ≤ d2 → ∃∃T0. ↑[d2 - e1, e2] T1 ≡ T0 & ↑[d1, e1] T0 ≡ T2. +#d1 #e1 #T1 #T #H elim H -H d1 e1 T1 T +[ #k #d1 #e1 #d2 #e2 #X #HX #_ + >(lift_inv_sort1 … HX) -HX /2/ +| #i #d1 #e1 #Hid1 #d2 #e2 #X #HX #Hded + lapply (lt_to_le_to_lt … (d1+e1) Hid1 ?) // #Hid1e + lapply (lt_to_le_to_lt … (d2-e1) Hid1 ?) /2/ #Hid2e + lapply (lt_to_le_to_lt … Hid1e Hded) -Hid1e Hded #Hid2 + lapply (lift_inv_lref1_lt … HX ?) -HX // #HX destruct -X /3/ +| #i #d1 #e1 #Hid1 #d2 #e2 #X #HX #_ + elim (lift_inv_lref1 … HX) -HX * #Hied #HX destruct -X; + [2: >plus_plus_comm_23] /4/ +| #I #V1 #V2 #T1 #T2 #d1 #e1 #_ #_ #IHV12 #IHT12 #d2 #e2 #X #HX #Hded + elim (lift_inv_bind1 … HX) -HX #V0 #T0 #HV20 #HT20 #HX destruct -X; + elim (IHV12 … HV20 ?) -IHV12 HV20 // + elim (IHT12 … HT20 ?) -IHT12 HT20 /2/ #T +