]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambda_delta/basic_2/substitution/lift_vector.ma
- lib: some additions
[helm.git] / 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-.