matita/matita/contribs/lambda_delta/basic_2/substitution/lift_vector.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/grammar/term_vector.ma".
  16 include "basic_2/substitution/lift.ma".
  17
  18 (* BASIC TERM VECTOR RELOCATION *********************************************)
  19
  20 inductive liftv (d,e:nat) : relation (list term) ≝
  21 | liftv_nil : liftv d e ◊ ◊
  22 | liftv_cons: ∀T1s,T2s,T1,T2.
  23               ⇧[d, e] T1 ≡ T2 → liftv d e T1s T2s →
  24               liftv d e (T1 @ T1s) (T2 @ T2s)
  25 .
  26
  27 interpretation "relocation (vector)" 'RLift d e T1s T2s = (liftv d e T1s T2s).
  28
  29 (* Basic inversion lemmas ***************************************************)
  30
  31 fact liftv_inv_nil1_aux: ∀T1s,T2s,d,e. ⇧[d, e] T1s ≡ T2s → T1s = ◊ → T2s = ◊.
  32 #T1s #T2s #d #e * -T1s -T2s //
  33 #T1s #T2s #T1 #T2 #_ #_ #H destruct
  34 qed.
  35
  36 lemma liftv_inv_nil1: ∀T2s,d,e. ⇧[d, e] ◊ ≡ T2s → T2s = ◊.
  37 /2 width=5/ qed-.
  38
  39 fact liftv_inv_cons1_aux: ∀T1s,T2s,d,e. ⇧[d, e] T1s ≡ T2s →
  40                           ∀U1,U1s. T1s = U1 @ U1s →
  41                           ∃∃U2,U2s. ⇧[d, e] U1 ≡ U2 & ⇧[d, e] U1s ≡ U2s &
  42                                     T2s = U2 @ U2s.
  43 #T1s #T2s #d #e * -T1s -T2s
  44 [ #U1 #U1s #H destruct
  45 | #T1s #T2s #T1 #T2 #HT12 #HT12s #U1 #U1s #H destruct /2 width=5/
  46 ]
  47 qed.
  48
  49 lemma liftv_inv_cons1: ∀U1,U1s,T2s,d,e. ⇧[d, e] U1 @ U1s ≡ T2s →
  50                        ∃∃U2,U2s. ⇧[d, e] U1 ≡ U2 & ⇧[d, e] U1s ≡ U2s &
  51                                  T2s = U2 @ U2s.
  52 /2 width=3/ qed-.
  53
  54 (* Basic properties *********************************************************)
  55
  56 lemma liftv_total: ∀d,e. ∀T1s:list term. ∃T2s. ⇧[d, e] T1s ≡ T2s.
  57 #d #e #T1s elim T1s -T1s
  58 [ /2 width=2/
  59 | #T1 #T1s * #T2s #HT12s
  60   elim (lift_total T1 d e) /3 width=2/
  61 ]
  62 qed-.