]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambda_delta/Basic_2/substitution/ltps_drop.ma
6c3288358344e43ed6610aa203cb2af2497ec113
[helm.git] / matita / matita / contribs / lambda_delta / Basic_2 / substitution / ltps_drop.ma
1 (**************************************************************************)
2 (*       ___                                                              *)
3 (*      ||M||                                                             *)
4 (*      ||A||       A project by Andrea Asperti                           *)
5 (*      ||T||                                                             *)
6 (*      ||I||       Developers:                                           *)
7 (*      ||T||         The HELM team.                                      *)
8 (*      ||A||         http://helm.cs.unibo.it                             *)
9 (*      \   /                                                             *)
10 (*       \ /        This file is distributed under the terms of the       *)
11 (*        v         GNU General Public License Version 2                  *)
12 (*                                                                        *)
13 (**************************************************************************)
14
15 include "Basic_2/substitution/ltps.ma".
16
17 (* PARALLEL SUBSTITUTION ON LOCAL ENVIRONMENTS ******************************)
18
19 lemma ltps_drop_conf_ge: ∀L0,L1,d1,e1. L0 [d1, e1] ≫ L1 →
20                          ∀L2,e2. ↓[0, e2] L0 ≡ L2 →
21                          d1 + e1 ≤ e2 → ↓[0, e2] L1 ≡ L2.
22 #L0 #L1 #d1 #e1 #H elim H -H L0 L1 d1 e1
23 [ #d1 #e1 #L2 #e2 #H >(drop_inv_atom1 … H) -H //
24 | //
25 | normalize #K0 #K1 #I #V0 #V1 #e1 #_ #_ #IHK01 #L2 #e2 #H #He12
26   lapply (plus_le_weak … He12) #He2
27   lapply (drop_inv_drop1 … H ?) -H // #HK0L2
28   lapply (IHK01 … HK0L2 ?) -IHK01 HK0L2 /2/
29 | #K0 #K1 #I #V0 #V1 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK01 #L2 #e2 #H #Hd1e2
30   lapply (plus_le_weak … Hd1e2) #He2
31   lapply (drop_inv_drop1 … H ?) -H // #HK0L2
32   lapply (IHK01 … HK0L2 ?) -IHK01 HK0L2 /2/
33 ]
34 qed.
35
36 lemma ltps_drop_trans_ge: ∀L1,L0,d1,e1. L1 [d1, e1] ≫ L0 →
37                           ∀L2,e2. ↓[0, e2] L0 ≡ L2 →
38                           d1 + e1 ≤ e2 → ↓[0, e2] L1 ≡ L2.
39 #L1 #L0 #d1 #e1 #H elim H -H L1 L0 d1 e1
40 [ #d1 #e1 #L2 #e2 #H >(drop_inv_atom1 … H) -H //
41 | //
42 | normalize #K1 #K0 #I #V1 #V0 #e1 #_ #_ #IHK10 #L2 #e2 #H #He12
43   lapply (plus_le_weak … He12) #He2
44   lapply (drop_inv_drop1 … H ?) -H // #HK0L2
45   lapply (IHK10 … HK0L2 ?) -IHK10 HK0L2 /2/
46 | #K0 #K1 #I #V1 #V0 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK10 #L2 #e2 #H #Hd1e2
47   lapply (plus_le_weak … Hd1e2) #He2
48   lapply (drop_inv_drop1 … H ?) -H // #HK0L2
49   lapply (IHK10 … HK0L2 ?) -IHK10 HK0L2 /2/
50 ]
51 qed.
52
53 lemma ltps_drop_conf_be: ∀L0,L1,d1,e1. L0 [d1, e1] ≫ L1 →
54                          ∀L2,e2. ↓[0, e2] L0 ≡ L2 → d1 ≤ e2 → e2 ≤ d1 + e1 →
55                          ∃∃L. L2 [0, d1 + e1 - e2] ≫ L & ↓[0, e2] L1 ≡ L.
56 #L0 #L1 #d1 #e1 #H elim H -H L0 L1 d1 e1
57 [ #d1 #e1 #L2 #e2 #H >(drop_inv_atom1 … H) -H /2/
58 | normalize #L #I #V #L2 #e2 #HL2 #_ #He2
59   lapply (le_n_O_to_eq … He2) -He2 #H destruct -e2;
60   lapply (drop_inv_refl … HL2) -HL2 #H destruct -L2 /2/
61 | normalize #K0 #K1 #I #V0 #V1 #e1 #HK01 #HV01 #IHK01 #L2 #e2 #H #_ #He21
62   lapply (drop_inv_O1 … H) -H * * #He2 #HK0L2
63   [ destruct -IHK01 He21 e2 L2 <minus_n_O /3/
64   | -HK01 HV01 <minus_le_minus_minus_comm //
65     elim (IHK01 … HK0L2 ? ?) -IHK01 HK0L2 /3/
66   ]
67 | #K0 #K1 #I #V0 #V1 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK01 #L2 #e2 #H #Hd1e2 #He2de1
68   lapply (plus_le_weak … Hd1e2) #He2
69   <minus_le_minus_minus_comm //
70   lapply (drop_inv_drop1 … H ?) -H // #HK0L2
71   elim (IHK01 … HK0L2 ? ?) -IHK01 HK0L2 /3/
72 ]
73 qed.
74
75 lemma ltps_drop_trans_be: ∀L1,L0,d1,e1. L1 [d1, e1] ≫ L0 →
76                           ∀L2,e2. ↓[0, e2] L0 ≡ L2 → d1 ≤ e2 → e2 ≤ d1 + e1 →
77                           ∃∃L. L [0, d1 + e1 - e2] ≫ L2 & ↓[0, e2] L1 ≡ L.
78 #L1 #L0 #d1 #e1 #H elim H -H L1 L0 d1 e1
79 [ #d1 #e1 #L2 #e2 #H >(drop_inv_atom1 … H) -H /2/
80 | normalize #L #I #V #L2 #e2 #HL2 #_ #He2
81   lapply (le_n_O_to_eq … He2) -He2 #H destruct -e2;
82   lapply (drop_inv_refl … HL2) -HL2 #H destruct -L2 /2/
83 | normalize #K1 #K0 #I #V1 #V0 #e1 #HK10 #HV10 #IHK10 #L2 #e2 #H #_ #He21
84   lapply (drop_inv_O1 … H) -H * * #He2 #HK0L2
85   [ destruct -IHK10 He21 e2 L2 <minus_n_O /3/
86   | -HK10 HV10 <minus_le_minus_minus_comm //
87     elim (IHK10 … HK0L2 ? ?) -IHK10 HK0L2 /3/
88   ]
89 | #K1 #K0 #I #V1 #V0 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK10 #L2 #e2 #H #Hd1e2 #He2de1
90   lapply (plus_le_weak … Hd1e2) #He2
91   <minus_le_minus_minus_comm //
92   lapply (drop_inv_drop1 … H ?) -H // #HK0L2
93   elim (IHK10 … HK0L2 ? ?) -IHK10 HK0L2 /3/
94 ]
95 qed.
96
97 lemma ltps_drop_conf_le: ∀L0,L1,d1,e1. L0 [d1, e1] ≫ L1 →
98                          ∀L2,e2. ↓[0, e2] L0 ≡ L2 → e2 ≤ d1 →
99                          ∃∃L. L2 [d1 - e2, e1] ≫ L & ↓[0, e2] L1 ≡ L.
100 #L0 #L1 #d1 #e1 #H elim H -H L0 L1 d1 e1
101 [ #d1 #e1 #L2 #e2 #H >(drop_inv_atom1 … H) -H /2/
102 | /2/
103 | normalize #K0 #K1 #I #V0 #V1 #e1 #HK01 #HV01 #_ #L2 #e2 #H #He2
104   lapply (le_n_O_to_eq … He2) -He2 #He2 destruct -e2;
105   lapply (drop_inv_refl … H) -H #H destruct -L2 /3/
106 | #K0 #K1 #I #V0 #V1 #d1 #e1 #HK01 #HV01 #IHK01 #L2 #e2 #H #He2d1
107   lapply (drop_inv_O1 … H) -H * * #He2 #HK0L2
108   [ destruct -IHK01 He2d1 e2 L2 <minus_n_O /3/
109   | -HK01 HV01 <minus_le_minus_minus_comm //
110     elim (IHK01 … HK0L2 ?) -IHK01 HK0L2 /3/
111   ]
112 ]
113 qed.
114
115 lemma ltps_drop_trans_le: ∀L1,L0,d1,e1. L1 [d1, e1] ≫ L0 →
116                           ∀L2,e2. ↓[0, e2] L0 ≡ L2 → e2 ≤ d1 →
117                           ∃∃L. L [d1 - e2, e1] ≫ L2 & ↓[0, e2] L1 ≡ L.
118 #L1 #L0 #d1 #e1 #H elim H -H L1 L0 d1 e1
119 [ #d1 #e1 #L2 #e2 #H >(drop_inv_atom1 … H) -H /2/
120 | /2/
121 | normalize #K1 #K0 #I #V1 #V0 #e1 #HK10 #HV10 #_ #L2 #e2 #H #He2
122   lapply (le_n_O_to_eq … He2) -He2 #He2 destruct -e2;
123   lapply (drop_inv_refl … H) -H #H destruct -L2 /3/
124 | #K1 #K0 #I #V1 #V0 #d1 #e1 #HK10 #HV10 #IHK10 #L2 #e2 #H #He2d1
125   lapply (drop_inv_O1 … H) -H * * #He2 #HK0L2
126   [ destruct -IHK10 He2d1 e2 L2 <minus_n_O /3/
127   | -HK10 HV10 <minus_le_minus_minus_comm //
128     elim (IHK10 … HK0L2 ?) -IHK10 HK0L2 /3/
129   ]
130 ]
131 qed.