matita/matita/contribs/lambda_delta/basic_2/substitution/ltps_ldrop.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_ldrop_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 -L0 -L1 -d1 -e1
  23 [ #d1 #e1 #L2 #e2 #H >(ldrop_inv_atom1 … H) -H //
  24 | //
  25 | normalize #K0 #K1 #I #V0 #V1 #e1 #_ #_ #IHK01 #L2 #e2 #H #He12
  26   elim (le_inv_plus_l … He12) #_ #He2
  27   lapply (ldrop_inv_ldrop1 … H ?) -H // #HK0L2
  28   lapply (IHK01 … HK0L2 ?) -K0 /2 width=1/
  29 | #K0 #K1 #I #V0 #V1 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK01 #L2 #e2 #H #Hd1e2
  30   elim (le_inv_plus_l … Hd1e2) #_ #He2
  31   lapply (ldrop_inv_ldrop1 … H ?) -H // #HK0L2
  32   lapply (IHK01 … HK0L2 ?) -K0 /2 width=1/
  33 ]
  34 qed.
  35
  36 lemma ltps_ldrop_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 -L1 -L0 -d1 -e1
  40 [ #d1 #e1 #L2 #e2 #H >(ldrop_inv_atom1 … H) -H //
  41 | //
  42 | normalize #K1 #K0 #I #V1 #V0 #e1 #_ #_ #IHK10 #L2 #e2 #H #He12
  43   elim (le_inv_plus_l … He12) #_ #He2
  44   lapply (ldrop_inv_ldrop1 … H ?) -H // #HK0L2
  45   lapply (IHK10 … HK0L2 ?) -K0 /2 width=1/
  46 | #K0 #K1 #I #V1 #V0 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK10 #L2 #e2 #H #Hd1e2
  47   elim (le_inv_plus_l … Hd1e2) #_ #He2
  48   lapply (ldrop_inv_ldrop1 … H ?) -H // #HK0L2
  49   lapply (IHK10 … HK0L2 ?) -IHK10 -HK0L2 /2 width=1/
  50 ]
  51 qed.
  52
  53 lemma ltps_ldrop_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 -L0 -L1 -d1 -e1
  57 [ #d1 #e1 #L2 #e2 #H >(ldrop_inv_atom1 … H) -H /2 width=3/
  58 | normalize #L #I #V #L2 #e2 #HL2 #_ #He2
  59   lapply (le_n_O_to_eq … He2) -He2 #H destruct
  60   lapply (ldrop_inv_refl … HL2) -HL2 #H destruct /2 width=3/
  61 | normalize #K0 #K1 #I #V0 #V1 #e1 #HK01 #HV01 #IHK01 #L2 #e2 #H #_ #He21
  62   lapply (ldrop_inv_O1 … H) -H * * #He2 #HK0L2
  63   [ -IHK01 -He21 destruct <minus_n_O /3 width=3/
  64   | -HK01 -HV01 <minus_le_minus_minus_comm //
  65     elim (IHK01 … HK0L2 ? ?) -K0 // /2 width=1/ /3 width=3/
  66   ]
  67 | #K0 #K1 #I #V0 #V1 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK01 #L2 #e2 #H #Hd1e2 #He2de1
  68   elim (le_inv_plus_l … Hd1e2) #_ #He2
  69   <minus_le_minus_minus_comm //
  70   lapply (ldrop_inv_ldrop1 … H ?) -H // #HK0L2
  71   elim (IHK01 … HK0L2 ? ?) -K0 /2 width=1/ /3 width=3/
  72 ]
  73 qed.
  74
  75 lemma ltps_ldrop_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 -L1 -L0 -d1 -e1
  79 [ #d1 #e1 #L2 #e2 #H >(ldrop_inv_atom1 … H) -H /2 width=3/
  80 | normalize #L #I #V #L2 #e2 #HL2 #_ #He2
  81   lapply (le_n_O_to_eq … He2) -He2 #H destruct
  82   lapply (ldrop_inv_refl … HL2) -HL2 #H destruct /2 width=3/
  83 | normalize #K1 #K0 #I #V1 #V0 #e1 #HK10 #HV10 #IHK10 #L2 #e2 #H #_ #He21
  84   lapply (ldrop_inv_O1 … H) -H * * #He2 #HK0L2
  85   [ -IHK10 -He21 destruct <minus_n_O /3 width=3/
  86   | -HK10 -HV10 <minus_le_minus_minus_comm //
  87     elim (IHK10 … HK0L2 ? ?) -K0 // /2 width=1/ /3 width=3/
  88   ]
  89 | #K1 #K0 #I #V1 #V0 #d1 #e1 >plus_plus_comm_23 #_ #_ #IHK10 #L2 #e2 #H #Hd1e2 #He2de1
  90   elim (le_inv_plus_l … Hd1e2) #_ #He2
  91   <minus_le_minus_minus_comm //
  92   lapply (ldrop_inv_ldrop1 … H ?) -H // #HK0L2
  93   elim (IHK10 … HK0L2 ? ?) -K0 /2 width=1/ /3 width=3/
  94 ]
  95 qed.
  96
  97 lemma ltps_ldrop_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 -L0 -L1 -d1 -e1
 101 [ #d1 #e1 #L2 #e2 #H >(ldrop_inv_atom1 … H) -H /2 width=3/
 102 | /2 width=3/
 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
 105   lapply (ldrop_inv_refl … H) -H #H destruct /3 width=3/
 106 | #K0 #K1 #I #V0 #V1 #d1 #e1 #HK01 #HV01 #IHK01 #L2 #e2 #H #He2d1
 107   lapply (ldrop_inv_O1 … H) -H * * #He2 #HK0L2
 108   [ -IHK01 -He2d1 destruct <minus_n_O /3 width=3/
 109   | -HK01 -HV01 <minus_le_minus_minus_comm //
 110     elim (IHK01 … HK0L2 ?) -K0 /2 width=1/ /3 width=3/
 111   ]
 112 ]
 113 qed.
 114
 115 lemma ltps_ldrop_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 -L1 -L0 -d1 -e1
 119 [ #d1 #e1 #L2 #e2 #H >(ldrop_inv_atom1 … H) -H /2 width=3/
 120 | /2 width=3/
 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
 123   lapply (ldrop_inv_refl … H) -H #H destruct /3 width=3/
 124 | #K1 #K0 #I #V1 #V0 #d1 #e1 #HK10 #HV10 #IHK10 #L2 #e2 #H #He2d1
 125   lapply (ldrop_inv_O1 … H) -H * * #He2 #HK0L2
 126   [ -IHK10 -He2d1 destruct <minus_n_O /3 width=3/
 127   | -HK10 -HV10 <minus_le_minus_minus_comm //
 128     elim (IHK10 … HK0L2 ?) -K0 /2 width=1/ /3 width=3/
 129   ]
 130 ]
 131 qed.