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