matita/matita/contribs/lambdadelta/basic_2A/multiple/lifts_lift.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 "ground/relocation/mr2_minus.ma".
  16 include "basic_2A/substitution/lift_lift.ma".
  17 include "basic_2A/multiple/lifts.ma".
  18
  19 (* GENERIC TERM RELOCATION **************************************************)
  20
  21 (* Properties concerning basic term relocation ******************************)
  22
  23 lemma lifts_lift_trans_le: ∀T1,T,cs. ⬆*[cs] T1 ≡ T → ∀T2. ⬆[0, 1] T ≡ T2 →
  24                            ∃∃T0. ⬆[0, 1] T1 ≡ T0 & ⬆*[cs + 1] T0 ≡ T2.
  25 #T1 #T #cs #H elim H -T1 -T -cs
  26 [ /2 width=3 by lifts_nil, ex2_intro/
  27 | #T1 #T3 #T #cs #l #m #HT13 #_ #IHT13 #T2 #HT2
  28   elim (IHT13 … HT2) -T #T #HT3 #HT2
  29   elim (lift_trans_le … HT13 … HT3) -T3 /3 width=5 by lifts_cons, ex2_intro/
  30 ]
  31 qed-.
  32
  33 lemma lifts_lift_trans: ∀cs,i,i0. @❪i, cs❫ ≘ i0 →
  34                         ∀cs0. cs + 1 ▭ i + 1 ≘ cs0 + 1 →
  35                         ∀T1,T0. ⬆*[cs0] T1 ≡ T0 →
  36                         ∀T2. ⬆[O, i0 + 1] T0 ≡ T2 →
  37                         ∃∃T. ⬆[0, i + 1] T1 ≡ T & ⬆*[cs] T ≡ T2.
  38 #cs elim cs -cs normalize
  39 [ #i #x #H1 #cs0 #H2 #T1 #T0 #HT10 #T2
  40   <(at_inv_nil … H1) -x #HT02
  41   lapply (minuss_inv_nil1 … H2) -H2 #H
  42   >(pluss_inv_nil2 … H) in HT10; -cs0 #H
  43   >(lifts_inv_nil … H) -T1 /2 width=3 by lifts_nil, ex2_intro/
  44 | #l #m #cs #IHcs #i #i0 #H1 #cs0 #H2 #T1 #T0 #HT10 #T2 #HT02
  45   elim (at_inv_cons … H1) -H1 * #Hil #Hi0
  46   [ elim (minuss_inv_cons1_lt … H2) -H2 [2: /2 width=1 by lt_minus_to_plus/ ] #cs1 #Hcs1 <minus_le_minus_minus_comm // <minus_plus_m_m #H
  47     elim (pluss_inv_cons2 … H) -H #cs2 #H1 #H2 destruct
  48     elim (lifts_inv_cons … HT10) -HT10 #T >minus_plus #HT1 #HT0
  49     elim (IHcs … Hi0 … Hcs1 … HT0 … HT02) -IHcs -Hi0 -Hcs1 -T0 #T0 #HT0 #HT02
  50     elim (lift_trans_le … HT1 … HT0) -T /2 width=1 by/ #T #HT1 <plus_minus_m_m /3 width=5 by lifts_cons, ex2_intro/
  51   | >commutative_plus in Hi0; #Hi0
  52     lapply (minuss_inv_cons1_ge … H2 ?) -H2 [ /2 width=1 by le_S_S/ ] <associative_plus #Hcs0
  53     elim (IHcs … Hi0 … Hcs0 … HT10 … HT02) -IHcs -Hi0 -Hcs0 -T0 #T0 #HT0 #HT02
  54     elim (lift_split … HT0 l (i+1)) -HT0 /3 width=5 by lifts_cons, le_S, ex2_intro/
  55   ]
  56 ]
  57 qed-.