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 -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 ?) -HL01 HLK0 /2/
  28 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL01 #Hde1d2
  29   @tps_bind [ /2/ | @IHTU2 [3: /2/ |1,2: skip | /2/ ] ] (**) (* /3/ is too slow *)
  30 | /3/
  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 -H L0 T2 U2 d2 e2
  40 [ /2/
  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 ?) -HL01 HLK0 /2/ #X #H #HLK1
  44     elim (ltps_inv_tps11 … H ?) -H [2: /2/ ] #K1 #V1 #_ #HV01 #H destruct -X;
  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 ?) -H HV01 HVW0 // >arith_a2 /3/
  48   | elim (lt_or_ge i2 (d1 + e1)) #Hde1i2
  49     [ elim (ltps_ldrop_conf_be … HL01 … HLK0 ? ?) -HL01 HLK0 [2,3: /2/ ] #X #H #HLK1
  50       elim (ltps_inv_tps21 … H ?) -H [2: /2/ ] #K1 #V1 #_ #HV01 #H destruct -X;
  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 ?) -H HV01 HVW0 // normalize #HW01
  54       lapply (tps_weak … HW01 d1 e1 ? ?) [2,3: /3/ ] >arith_i2 //
  55     | lapply (ltps_ldrop_conf_ge … HL01 … HLK0 ?) -HL01 HLK0 /3/
  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: /2/ ] -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 -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 ?) -HL10 HLK0 /2/
  75 | #L0 #I #V2 #W2 #T2 #U2 #d2 #e2 #_ #_ #IHVW2 #IHTU2 #L1 #d1 #e1 #HL10 #Hde1d2
  76   @tps_bind [ /2/ | @IHTU2 [3: /2/ |1,2: skip | /2/ ] ] (**) (* /3/ is too slow *)
  77 | /3/
  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 -H L0 T2 U2 d2 e2
  87 [ /2/
  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/ #X #H #HLK1
  91     elim (ltps_inv_tps12 … H ?) -H [2: /2/ ] #K1 #V1 #_ #HV01 #H destruct -X;
  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 ?) -H HV01 HVW0 // >arith_a2 /3/
  95   | elim (lt_or_ge i2 (d1 + e1)) #Hde1i2
  96     [ elim (ltps_ldrop_trans_be … HL10 … HLK0 ? ?) -HL10 [2,3: /2/ ] #X #H #HLK1
  97       elim (ltps_inv_tps22 … H ?) -H [2: /2/ ] #K1 #V1 #_ #HV01 #H destruct -X;
  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 ?) -H HV01 HVW0 // normalize #HW01
 101       lapply (tps_weak … HW01 d1 e1 ? ?) [2,3: /3/ ] >arith_i2 //
 102     | lapply (ltps_ldrop_trans_ge … HL10 … HLK0 ?) -HL10 HLK0 /3/
 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: /2/ ] -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.