]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambda_delta/Basic_2/substitution/ltps_tps.ma
- support for candidates of reducibility continues ...
[helm.git] / matita / matita / contribs / lambda_delta / Basic_2 / substitution / ltps_tps.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/tps_lift.ma".
16 include "Basic_2/substitution/ltps_ldrop.ma".
17
18 (* PARALLEL SUBSTITUTION ON LOCAL ENVIRONMENTS ******************************)
19
20 lemma ltps_tps_conf_ge: ∀L0,T2,U2,d2,e2. L0 ⊢ T2 [d2, e2] ≫ U2 →
21                         ∀L1,d1,e1. L0 [d1, e1] ≫ L1 → d1 + e1 ≤ d2 →
22                         L1 ⊢ T2 [d2, e2] ≫ U2.
23 #L0 #T2 #U2 #d2 #e2 #H elim H -L0 -T2 -U2 -d2 -e2
24 [ //
25 | #L0 #K0 #V0 #W0 #i2 #d2 #e2 #Hdi2 #Hide2 #HLK0 #HVW0 #L1 #d1 #e1 #HL01 #Hde1d2
26   lapply (transitive_le … Hde1d2 Hdi2) -Hde1d2 #Hde1i2
27   lapply (ltps_ldrop_conf_ge … HL01 … HLK0 ?) -L0 // /2 width=4/
28 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL01 #Hde1d2
29   @tps_bind [ /2 width=4/ | @IHTU2 -IHTU2 -IHVW2 [3: /2 by ltps_tps1/ |1,2: skip | /2 width=1/ ] ] (**) (* explicit constructor *)
30 | /3 width=4/
31 ]
32 qed.
33
34 (* Basic_1: was: subst1_subst1_back *)
35 lemma ltps_tps_conf: ∀L0,T2,U2,d2,e2. L0 ⊢ T2 [d2, e2] ≫ U2 →
36                      ∀L1,d1,e1. L0 [d1, e1] ≫ L1 →
37                      ∃∃T. L1 ⊢ T2 [d2, e2] ≫ T &
38                           L1 ⊢ U2 [d1, e1] ≫ T.
39 #L0 #T2 #U2 #d2 #e2 #H elim H -L0 -T2 -U2 -d2 -e2
40 [ /2 width=3/
41 | #L0 #K0 #V0 #W0 #i2 #d2 #e2 #Hdi2 #Hide2 #HLK0 #HVW0 #L1 #d1 #e1 #HL01
42   elim (lt_or_ge i2 d1) #Hi2d1
43   [ elim (ltps_ldrop_conf_le … HL01 … HLK0 ?) -L0 /2 width=2/ #X #H #HLK1
44     elim (ltps_inv_tps11 … H ?) -H /2 width=1/ #K1 #V1 #_ #HV01 #H destruct
45     lapply (ldrop_fwd_ldrop2 … HLK1) #H
46     elim (lift_total V1 0 (i2 + 1)) #W1 #HVW1
47     lapply (tps_lift_ge … HV01 … H HVW0 HVW1 ?) -V0 -H // >minus_plus <plus_minus_m_m // /3 width=4/
48   | elim (lt_or_ge i2 (d1 + e1)) #Hde1i2
49     [ elim (ltps_ldrop_conf_be … HL01 … HLK0 ? ?) -L0 // /2 width=2/ #X #H #HLK1
50       elim (ltps_inv_tps21 … H ?) -H /2 width=1/ #K1 #V1 #_ #HV01 #H destruct
51       lapply (ldrop_fwd_ldrop2 … HLK1) #H
52       elim (lift_total V1 0 (i2 + 1)) #W1 #HVW1
53       lapply (tps_lift_ge … HV01 … H HVW0 HVW1 ?) -V0 -H // normalize #HW01
54       lapply (tps_weak … HW01 d1 e1 ? ?) [2: /2 width=1/ |3: /3 width=4/ ] >minus_plus >commutative_plus /2 width=1/
55     | lapply (ltps_ldrop_conf_ge … HL01 … HLK0 ?) -L0 // /3 width=4/
56     ]
57   ]
58 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL01
59   elim (IHVW2 … HL01) -IHVW2 #V #HV2 #HVW2
60   elim (IHTU2 (L1. 𝕓{I} V) (d1 + 1) e1 ?) -IHTU2 /2 width=1/ -HL01 /3 width=5/
61 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL01
62   elim (IHVW2 … HL01) -IHVW2
63   elim (IHTU2 … HL01) -IHTU2 -HL01 /3 width=5/
64 ]
65 qed.
66
67 lemma ltps_tps_trans_ge: ∀L0,T2,U2,d2,e2. L0 ⊢ T2 [d2, e2] ≫ U2 →
68                          ∀L1,d1,e1. L1 [d1, e1] ≫ L0 → d1 + e1 ≤ d2 →
69                          L1 ⊢ T2 [d2, e2] ≫ U2.
70 #L0 #T2 #U2 #d2 #e2 #H elim H -L0 -T2 -U2 -d2 -e2
71 [ //
72 | #L0 #K0 #V0 #W0 #i2 #d2 #e2 #Hdi2 #Hide2 #HLK0 #HVW0 #L1 #d1 #e1 #HL10 #Hde1d2
73   lapply (transitive_le … Hde1d2 Hdi2) -Hde1d2 #Hde1i2
74   lapply (ltps_ldrop_trans_ge … HL10 … HLK0 ?) -L0 // /2 width=4/
75 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL10 #Hde1d2
76   @tps_bind [ /2 width=4/ | @IHTU2 -IHTU2 -IHVW2 [3: /2 by ltps_tps1/ |1,2: skip | /2 width=1/ ] ] (**) (* explicit constructor *)
77 | /3 width=4/
78 ]
79 qed.
80
81 (* Basic_1: was: subst1_subst1 *)
82 lemma ltps_tps_trans: ∀L0,T2,U2,d2,e2. L0 ⊢ T2 [d2, e2] ≫ U2 →
83                       ∀L1,d1,e1. L1 [d1, e1] ≫ L0 →
84                       ∃∃T. L1 ⊢ T2 [d2, e2] ≫ T &
85                            L0 ⊢ T [d1, e1] ≫ U2.
86 #L0 #T2 #U2 #d2 #e2 #H elim H -L0 -T2 -U2 -d2 -e2
87 [ /2 width=3/
88 | #L0 #K0 #V0 #W0 #i2 #d2 #e2 #Hdi2 #Hide2 #HLK0 #HVW0 #L1 #d1 #e1 #HL10
89   elim (lt_or_ge i2 d1) #Hi2d1
90   [ elim (ltps_ldrop_trans_le … HL10 … HLK0 ?) -HL10 /2 width=2/ #X #H #HLK1
91     elim (ltps_inv_tps12 … H ?) -H /2 width=1/ #K1 #V1 #_ #HV01 #H destruct
92     lapply (ldrop_fwd_ldrop2 … HLK0) -HLK0 #H
93     elim (lift_total V1 0 (i2 + 1)) #W1 #HVW1
94     lapply (tps_lift_ge … HV01 … H HVW1 HVW0 ?) -V0 -H // >minus_plus <plus_minus_m_m /2 width=1/ /3 width=4/
95   | elim (lt_or_ge i2 (d1 + e1)) #Hde1i2
96     [ elim (ltps_ldrop_trans_be … HL10 … HLK0 ? ?) -HL10 // /2 width=2/ #X #H #HLK1
97       elim (ltps_inv_tps22 … H ?) -H /2 width=1/ #K1 #V1 #_ #HV01 #H destruct
98       lapply (ldrop_fwd_ldrop2 … HLK0) -HLK0 #H
99       elim (lift_total V1 0 (i2 + 1)) #W1 #HVW1
100       lapply (tps_lift_ge … HV01 … H HVW1 HVW0 ?) -V0 -H // normalize #HW01
101       lapply (tps_weak … HW01 d1 e1 ? ?) [2: /3 width=1/ |3: /3 width=4/ ] >minus_plus >commutative_plus /2 width=1/
102     | lapply (ltps_ldrop_trans_ge … HL10 … HLK0 ?) -HL10 -HLK0 // /3 width=4/
103     ]
104   ]
105 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL10
106   elim (IHVW2 … HL10) -IHVW2 #V #HV2 #HVW2
107   elim (IHTU2 (L1. 𝕓{I} V) (d1 + 1) e1 ?) -IHTU2 /2 width=1/ -HL10 /3 width=5/
108 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL10
109   elim (IHVW2 … HL10) -IHVW2
110   elim (IHTU2 … HL10) -IHTU2 -HL10 /3 width=5/
111 ]
112 qed.