matita/matita/contribs/lambda_delta/basic_2/unfold/thin_delift.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/unfold/delift_tpss.ma".
  16 include "basic_2/unfold/delift_ltpss.ma".
  17 include "basic_2/unfold/thin.ma".
  18
  19 (* BASIC DELIFT ON LOCAL ENVIRONMENTS ***************************************)
  20
  21 (* Inversion lemmas on inverse basic term relocation ************************)
  22
  23 lemma thin_inv_delift1: ∀I,K1,V1,L2,d,e. K1. ⓑ{I} V1 [d, e] ≡ L2 → 0 < d →
  24                         ∃∃K2,V2. K1 [d - 1, e] ≡ K2 &
  25                                  K1 ⊢ V1 [d - 1, e] ≡ V2 &
  26                                  L2 = K2. ⓑ{I} V2.
  27 #I #K1 #V1 #L2 #d #e * #X #HK1 #HL2 #e
  28 elim (ltpss_inv_tpss11 … HK1 ?) -HK1 // #K #V #HK1 #HV1 #H destruct
  29 elim (ldrop_inv_skip1 … HL2 ?) -HL2 // #K2 #V2 #HK2 #HV2 #H destruct
  30 lapply (ltpss_tpss_trans_eq … HV1 … HK1) -HV1 /3 width=5/
  31 qed-.
  32
  33 (* Properties on inverse basic term relocation ******************************)
  34
  35 lemma thin_delift1: ∀L1,L2,d,e. L1 [d, e] ≡ L2 → ∀V1,V2. L1 ⊢ V1 [d, e] ≡ V2 →
  36                     ∀I. L1.ⓑ{I}V1 [d + 1, e] ≡ L2.ⓑ{I}V2.
  37 #L1 #L2 #d #e * #L #HL1 #HL2 #V1 #V2 * #V #HV1 #HV2 #I
  38 elim (ltpss_tpss_conf … HV1 … HL1) -HV1 #V0 #HV10 #HV0
  39 elim (tpss_inv_lift1_be … HV0 … HL2 … HV2 ? ?) -HV0 // <minus_n_n #X #H1 #H2
  40 lapply (tpss_inv_refl_O2 … H1) -H1 #H destruct
  41 lapply (lift_mono … H2 … HV2) -H2 #H destruct /3 width=5/
  42 qed.
  43
  44 lemma thin_delift_tpss_conf_le: ∀L,U1,U2,d,e. L ⊢ U1 ▶* [d, e] U2 →
  45                                 ∀T1,dd,ee. L ⊢ U1 [dd, ee] ≡ T1 →
  46                                 ∀K. L [dd, ee] ≡ K → d + e ≤ dd →
  47                                 ∃∃T2. K ⊢ T1 ▶* [d, e] T2 &
  48                                       L ⊢ U2 [dd, ee] ≡ T2.
  49 #L #U1 #U2 #d #e #HU12 #T1 #dd #ee #HUT1 #K * #Y #HLY #HYK #Hdedd
  50 lapply (delift_ltpss_conf_eq … HUT1 … HLY) -HUT1 #HUT1
  51 elim (ltpss_tpss_conf … HU12 … HLY) -HU12 #U #HU1 #HU2
  52 elim (delift_tpss_conf_le … HU1 … HUT1 … HYK ?) -HU1 -HUT1 // -Hdedd #T #HT1 #HUT
  53 lapply (tpss_delift_trans_eq … HU2 … HUT) -U #HU2T
  54 lapply (ltpss_delift_trans_eq … HLY … HU2T) -Y /2 width=3/
  55 qed.
  56
  57 lemma thin_delift_tps_conf_le: ∀L,U1,U2,d,e. L ⊢ U1 ▶ [d, e] U2 →
  58                                ∀T1,dd,ee. L ⊢ U1 [dd, ee] ≡ T1 →
  59                                ∀K. L [dd, ee] ≡ K → d + e ≤ dd →
  60                                ∃∃T2. K ⊢ T1 ▶* [d, e] T2 &
  61                                      L ⊢ U2 [dd, ee] ≡ T2.
  62 /3 width=3/ qed.
  63
  64 lemma thin_delift_tpss_conf_le_up: ∀L,U1,U2,d,e. L ⊢ U1 ▶* [d, e] U2 →
  65                                    ∀T1,dd,ee. L ⊢ U1 [dd, ee] ≡ T1 →
  66                                    ∀K. L [dd, ee] ≡ K →
  67                                    d ≤ dd → dd ≤ d + e → d + e ≤ dd + ee →
  68                                    ∃∃T2. K ⊢ T1 ▶* [d, dd - d] T2 &
  69                                          L ⊢ U2 [dd, ee] ≡ T2.
  70 #L #U1 #U2 #d #e #HU12 #T1 #dd #ee #HUT1 #K * #Y #HLY #HYK #Hdd #Hdde #Hddee
  71 lapply (delift_ltpss_conf_eq … HUT1 … HLY) -HUT1 #HUT1
  72 elim (ltpss_tpss_conf … HU12 … HLY) -HU12 #U #HU1 #HU2
  73 elim (delift_tpss_conf_le_up … HU1 … HUT1 … HYK ? ? ?) -HU1 -HUT1 // -Hdd -Hdde -Hddee #T #HT1 #HUT
  74 lapply (tpss_delift_trans_eq … HU2 … HUT) -U #HU2T
  75 lapply (ltpss_delift_trans_eq … HLY … HU2T) -Y /2 width=3/
  76 qed.
  77
  78 lemma thin_delift_tps_conf_le_up: ∀L,U1,U2,d,e. L ⊢ U1 ▶ [d, e] U2 →
  79                                   ∀T1,dd,ee. L ⊢ U1 [dd, ee] ≡ T1 →
  80                                   ∀K. L [dd, ee] ≡ K →
  81                                   d ≤ dd → dd ≤ d + e → d + e ≤ dd + ee →
  82                                   ∃∃T2. K ⊢ T1 ▶* [d, dd - d] T2 &
  83                                         L ⊢ U2 [dd, ee] ≡ T2.
  84 /3 width=6 by thin_delift_tpss_conf_le_up, tpss_strap/ qed. (**) (* too slow without trace *)
  85
  86 lemma thin_delift_tpss_conf_be: ∀L,U1,U2,d,e. L ⊢ U1 ▶* [d, e] U2 →
  87                                 ∀T1,dd,ee. L ⊢ U1 [dd, ee] ≡ T1 →
  88                                 ∀K. L [dd, ee] ≡ K → d ≤ dd → dd + ee ≤ d + e →
  89                                 ∃∃T2. K ⊢ T1 ▶* [d, e - ee] T2 &
  90                                       L ⊢ U2 [dd, ee] ≡ T2.
  91 #L #U1 #U2 #d #e #HU12 #T1 #dd #ee #HUT1 #K * #Y #HLY #HYK #Hdd #Hddee
  92 lapply (delift_ltpss_conf_eq … HUT1 … HLY) -HUT1 #HUT1
  93 elim (ltpss_tpss_conf … HU12 … HLY) -HU12 #U #HU1 #HU2
  94 elim (delift_tpss_conf_be … HU1 … HUT1 … HYK ? ?) -HU1 -HUT1 // -Hdd -Hddee #T #HT1 #HUT
  95 lapply (tpss_delift_trans_eq … HU2 … HUT) -U #HU2T
  96 lapply (ltpss_delift_trans_eq … HLY … HU2T) -Y /2 width=3/
  97 qed.
  98
  99 lemma thin_delift_tps_conf_be: ∀L,U1,U2,d,e. L ⊢ U1 ▶ [d, e] U2 →
 100                                ∀T1,dd,ee. L ⊢ U1 [dd, ee] ≡ T1 →
 101                                ∀K. L [dd, ee] ≡ K → d ≤ dd → dd + ee ≤ d + e →
 102                                ∃∃T2. K ⊢ T1 ▶* [d, e - ee] T2 &
 103                                      L ⊢ U2 [dd, ee] ≡ T2.
 104 /3 width=3/ qed.