matita/matita/contribs/lambdadelta/basic_2/unfold/ltpss_dx_ltpss_dx.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/tpss_tpss.ma".
  16 include "basic_2/unfold/tpss_alt.ma".
  17 include "basic_2/unfold/ltpss_dx_tpss.ma".
  18
  19 (* DX PARTIAL UNFOLD ON LOCAL ENVIRONMENTS **********************************)
  20
  21 (* Advanced properties ******************************************************)
  22
  23 lemma ltpss_dx_tpss_conf: ∀L0,T2,U2,d2,e2. L0 ⊢ T2 ▶* [d2, e2] U2 →
  24                           ∀L1,d1,e1. L0 ▶* [d1, e1] L1 →
  25                           ∃∃T. L1 ⊢ T2 ▶* [d2, e2] T &
  26                                L1 ⊢ U2 ▶* [d1, e1] T.
  27 #L0 #T2 #U2 #d2 #e2 #H #L1 #d1 #e1 #HL01 @(tpss_ind … H) -U2 /2 width=3/
  28 #U #U2 #_ #HU2 * #X2 #HTX2 #HUX2
  29 elim (ltpss_dx_tps_conf … HU2 … HL01) -L0 #X1 #HUX1 #HU2X1
  30 elim (tpss_strip_eq … HUX2 … HUX1) -U #X #HX2 #HX1
  31 lapply (tpss_trans_eq … HU2X1 … HX1) -X1 /3 width=3/
  32 qed.
  33
  34 lemma ltpss_dx_tpss_trans_down: ∀L0,L1,T2,U2,d1,e1,d2,e2. d2 + e2 ≤ d1 →
  35                                 L1 ▶* [d1, e1] L0 → L0 ⊢ T2 ▶* [d2, e2] U2 →
  36                                 ∃∃T. L1 ⊢ T2 ▶* [d2, e2] T & L0 ⊢ T ▶* [d1, e1] U2.
  37 #L0 #L1 #T2 #U2 #d1 #e1 #d2 #e2 #Hde2d1 #HL10 #H @(tpss_ind … H) -U2
  38 [ /2 width=3/
  39 | #U #U2 #_ #HU2 * #T #HT2 #HTU
  40   elim (tpss_strap1_down … HTU … HU2 ?) -U // #U #HTU #HU2
  41   elim (ltpss_dx_tps_trans … HTU … HL10) -HTU -HL10 #X #HTX #HXU
  42   lapply (tpss_trans_eq … HXU HU2) -U /3 width=3/
  43 ]
  44 qed.
  45
  46 fact ltpss_dx_tpss_trans_eq_aux: ∀Y1,X2,L1,T2,U2,d,e.
  47                                  L1 ⊢ T2 ▶* [d, e] U2 → ∀L0. L0 ▶* [d, e] L1 →
  48                                  Y1 = L1 → X2 = T2 → L0 ⊢ T2 ▶* [d, e] U2.
  49 #Y1 #X2 @(fw_ind … Y1 X2) -Y1 -X2 #Y1 #X2 #IH
  50 #L1 #T2 #U2 #d #e #H @(tpss_ind_alt … H) -L1 -T2 -U2 -d -e
  51 [ //
  52 | #L1 #K1 #V1 #V2 #W2 #i #d #e #Hdi #Hide #HLK1 #HV12 #HVW2 #_ #L0 #HL01 #H1 #H2 destruct
  53   lapply (ldrop_fwd_lw … HLK1) #H1 normalize in H1;
  54   elim (ltpss_dx_ldrop_trans_be … HL01 … HLK1 ? ?) -HL01 -HLK1 // /2 width=2/ #X #H #HLK0
  55   elim (ltpss_dx_inv_tpss22 … H ?) -H /2 width=1/ #K0 #V0 #HK01 #HV01 #H destruct
  56   lapply (tpss_fwd_tw … HV01) #H2
  57   lapply (transitive_le (#{K1} + #{V0}) … H1) -H1 /2 width=1/ -H2 #H
  58   lapply (tpss_trans_eq … HV01 HV12) -V1 #HV02
  59   lapply (IH … HV02 … HK01 ? ?) -IH -HV02 -HK01
  60   [1,3: // |2,4: skip | normalize /2 width=1/ | /2 width=6/ ]
  61 | #L #a #I #V1 #V2 #T1 #T2 #d #e #HV12 #HT12 #_ #_ #L0 #HL0 #H1 #H2 destruct
  62   lapply (tpss_lsubs_trans … HT12 (L. ⓑ{I} V1) ?) -HT12 /2 width=1/ #HT12
  63   lapply (IH … HV12 … HL0 ? ?) -HV12 [1,3: // |2,4: skip |5: /2 width=2/ ] #HV12
  64   lapply (IH … HT12 (L0. ⓑ{I} V1) ? ? ?) -IH -HT12 [1,3,5: /2 width=2/ |2,4: skip | normalize // ] -HL0 #HT12
  65   lapply (tpss_lsubs_trans … HT12 (L0. ⓑ{I} V2) ?) -HT12 /2 width=1/
  66 | #L #I #V1 #V2 #T1 #T2 #d #e #HV12 #HT12 #_ #_ #L0 #HL0 #H1 #H2 destruct
  67   lapply (IH … HV12 … HL0 ? ?) -HV12 [1,3: // |2,4: skip |5: /2 width=3/ ]
  68   lapply (IH … HT12 … HL0 ? ?) -IH -HT12 [1,3,5: normalize // |2,4: skip ] -HL0 /2 width=1/
  69 ]
  70 qed.
  71
  72 lemma ltpss_dx_tpss_trans_eq: ∀L1,T2,U2,d,e. L1 ⊢ T2 ▶* [d, e] U2 →
  73                               ∀L0. L0 ▶* [d, e] L1 → L0 ⊢ T2 ▶* [d, e] U2.
  74 /2 width=5/ qed.
  75
  76 lemma ltpss_dx_tps_trans_eq: ∀L0,L1,T2,U2,d,e. L0 ▶* [d, e] L1 →
  77                              L1 ⊢ T2 ▶ [d, e] U2 → L0 ⊢ T2 ▶* [d, e] U2.
  78 /3 width=3/ qed.
  79
  80 (* Main properties **********************************************************)
  81
  82 fact ltpss_dx_conf_aux: ∀K,K1,L1,d1,e1. K1 ▶* [d1, e1] L1 →
  83                         ∀K2,L2,d2,e2. K2 ▶* [d2, e2] L2 → K1 = K → K2 = K →
  84                         ∃∃L. L1 ▶* [d2, e2] L & L2 ▶* [d1, e1] L.
  85 #K @(lw_ind … K) -K #K #IH #K1 #L1 #d1 #e1 * -K1 -L1 -d1 -e1
  86 [ -IH /2 width=3/
  87 | -IH #K1 #I1 #V1 #K2 #L2 #d2 #e2 * -K2 -L2 -d2 -e2
  88   [ /2 width=3/
  89   | #K2 #I2 #V2 #H1 #H2 destruct /2 width=3/
  90   | #K2 #L2 #I2 #W2 #V2 #e2 #HKL2 #HWV2 #H1 #H2 destruct /3 width=3/
  91   | #K2 #L2 #I2 #W2 #V2 #d2 #e2 #HKL2 #HWV2 #H1 #H2 destruct /3 width=3/
  92   ]
  93 | #K1 #L1 #I1 #W1 #V1 #e1 #HKL1 #HWV1 #K2 #L2 #d2 #e2 * -K2 -L2 -d2 -e2
  94   [ -IH #d2 #e2 #H1 #H2 destruct
  95   | -IH #K2 #I2 #V2 #H1 #H2 destruct /3 width=5/
  96   | #K2 #L2 #I2 #W2 #V2 #e2 #HKL2 #HWV2 #H1 #H2 destruct
  97     elim (IH … HKL1 … HKL2 ? ?) -IH [2,4: // |3: skip |5: /2 width=1/ ] -K1 #L #HL1 #HL2
  98     elim (ltpss_dx_tpss_conf … HWV1 … HL1) #U1 #HWU1 #HVU1
  99     elim (ltpss_dx_tpss_conf … HWV2 … HL2) #U2 #HWU2 #HVU2
 100     elim (tpss_conf_eq … HWU1 … HWU2) -W1 #W #HU1W #HU2W
 101     lapply (tpss_trans_eq … HVU1 HU1W) -U1
 102     lapply (tpss_trans_eq … HVU2 HU2W) -U2 /3 width=5/
 103   | #K2 #L2 #I2 #W2 #V2 #d2 #e2 #HKL2 #HWV2 #H1 #H2 destruct
 104     elim (IH … HKL1 … HKL2 ? ?) -IH [2,4: // |3: skip |5: /2 width=1/ ] -K1 #L #HL1 #HL2
 105     elim (ltpss_dx_tpss_conf … HWV1 … HL1) #U1 #HWU1 #HVU1
 106     elim (ltpss_dx_tpss_conf … HWV2 … HL2) #U2 #HWU2 #HVU2
 107     elim (tpss_conf_eq … HWU1 … HWU2) -W1 #W #HU1W #HU2W
 108     lapply (tpss_trans_eq … HVU1 HU1W) -U1
 109     lapply (tpss_trans_eq … HVU2 HU2W) -U2 /3 width=5/
 110   ]
 111 | #K1 #L1 #I1 #W1 #V1 #d1 #e1 #HKL1 #HWV1 #K2 #L2 #d2 #e2 * -K2 -L2 -d2 -e2
 112   [ -IH #d2 #e2 #H1 #H2 destruct
 113   | -IH #K2 #I2 #V2 #H1 #H2 destruct /3 width=5/
 114   | #K2 #L2 #I2 #W2 #V2 #e2 #HKL2 #HWV2 #H1 #H2 destruct
 115     elim (IH … HKL1 … HKL2 ? ?) -IH [2,4: // |3: skip |5: /2 width=1/ ] -K1 #L #HL1 #HL2
 116     elim (ltpss_dx_tpss_conf … HWV1 … HL1) #U1 #HWU1 #HVU1
 117     elim (ltpss_dx_tpss_conf … HWV2 … HL2) #U2 #HWU2 #HVU2
 118     elim (tpss_conf_eq … HWU1 … HWU2) -W1 #W #HU1W #HU2W
 119     lapply (tpss_trans_eq … HVU1 HU1W) -U1
 120     lapply (tpss_trans_eq … HVU2 HU2W) -U2 /3 width=5/
 121   | #K2 #L2 #I2 #W2 #V2 #d2 #e2 #HKL2 #HWV2 #H1 #H2 destruct
 122     elim (IH … HKL1 … HKL2 ? ?) -IH [2,4: // |3: skip |5: /2 width=1/ ] -K1 #L #HL1 #HL2
 123     elim (ltpss_dx_tpss_conf … HWV1 … HL1) #U1 #HWU1 #HVU1
 124     elim (ltpss_dx_tpss_conf … HWV2 … HL2) #U2 #HWU2 #HVU2
 125     elim (tpss_conf_eq … HWU1 … HWU2) -W1 #W #HU1W #HU2W
 126     lapply (tpss_trans_eq … HVU1 HU1W) -U1
 127     lapply (tpss_trans_eq … HVU2 HU2W) -U2 /3 width=5/
 128   ]
 129 ]
 130 qed.
 131
 132 theorem ltpss_dx_conf: ∀L0,L1,d1,e1. L0 ▶* [d1, e1] L1 →
 133                        ∀L2,d2,e2. L0 ▶* [d2, e2] L2 →
 134                        ∃∃L. L1 ▶* [d2, e2] L & L2 ▶* [d1, e1] L.
 135 /2 width=7/ qed.