]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambdadelta/basic_2/relocation/lifts_vector.ma
basic_2: stronger supclosure allows better inversion lemmas
[helm.git] / matita / matita / contribs / lambdadelta / basic_2 / relocation / lifts_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/relocation/lifts.ma".
17
18 (* GENERIC RELOCATION FOR TERM VECTORS *************************************)
19
20 (* Basic_2A1: includes: liftv_nil liftv_cons *)
21 inductive liftsv (f:rtmap): relation (list term) ≝
22 | liftsv_nil : liftsv f (◊) (◊)
23 | liftsv_cons: ∀T1s,T2s,T1,T2.
24                ⬆*[f] T1 ≡ T2 → liftsv f T1s T2s →
25                liftsv f (T1 @ T1s) (T2 @ T2s)
26 .
27
28 interpretation "uniform relocation (vector)"
29    'RLiftStar i T1s T2s = (liftsv (uni i) T1s T2s).
30
31 interpretation "generic relocation (vector)"
32    'RLiftStar f T1s T2s = (liftsv f T1s T2s).
33
34 (* Basic inversion lemmas ***************************************************)
35
36 fact liftsv_inv_nil1_aux: ∀f,X,Y. ⬆*[f] X ≡ Y → X = ◊ → Y = ◊.
37 #f #X #Y * -X -Y //
38 #T1s #T2s #T1 #T2 #_ #_ #H destruct
39 qed-.
40
41 (* Basic_2A1: includes: liftv_inv_nil1 *)
42 lemma liftsv_inv_nil1: ∀f,Y. ⬆*[f] ◊ ≡ Y → Y = ◊.
43 /2 width=5 by liftsv_inv_nil1_aux/ qed-.
44
45 fact liftsv_inv_cons1_aux: ∀f:rtmap. ∀X,Y. ⬆*[f] X ≡ Y →
46                            ∀T1,T1s. X = T1 @ T1s →
47                            ∃∃T2,T2s. ⬆*[f] T1 ≡ T2 & ⬆*[f] T1s ≡ T2s &
48                                      Y = T2 @ T2s.
49 #f #X #Y * -X -Y
50 [ #U1 #U1s #H destruct
51 | #T1s #T2s #T1 #T2 #HT12 #HT12s #U1 #U1s #H destruct /2 width=5 by ex3_2_intro/
52 ]
53 qed-.
54
55 (* Basic_2A1: includes: liftv_inv_cons1 *)
56 lemma liftsv_inv_cons1: ∀f:rtmap. ∀T1,T1s,Y. ⬆*[f] T1 @ T1s ≡ Y →
57                         ∃∃T2,T2s. ⬆*[f] T1 ≡ T2 & ⬆*[f] T1s ≡ T2s &
58                                   Y = T2 @ T2s.
59 /2 width=3 by liftsv_inv_cons1_aux/ qed-.
60
61 fact liftsv_inv_nil2_aux: ∀f,X,Y. ⬆*[f] X ≡ Y → Y = ◊ → X = ◊.
62 #f #X #Y * -X -Y //
63 #T1s #T2s #T1 #T2 #_ #_ #H destruct
64 qed-.
65
66 lemma liftsv_inv_nil2: ∀f,X. ⬆*[f] X ≡ ◊ → X = ◊.
67 /2 width=5 by liftsv_inv_nil2_aux/ qed-.
68
69 fact liftsv_inv_cons2_aux: ∀f:rtmap. ∀X,Y. ⬆*[f] X ≡ Y →
70                            ∀T2,T2s. Y = T2 @ T2s →
71                            ∃∃T1,T1s. ⬆*[f] T1 ≡ T2 & ⬆*[f] T1s ≡ T2s &
72                                      X = T1 @ T1s.
73 #f #X #Y * -X -Y
74 [ #U2 #U2s #H destruct
75 | #T1s #T2s #T1 #T2 #HT12 #HT12s #U2 #U2s #H destruct /2 width=5 by ex3_2_intro/
76 ]
77 qed-.
78
79 lemma liftsv_inv_cons2: ∀f:rtmap. ∀X,T2,T2s. ⬆*[f] X ≡ T2 @ T2s →
80                         ∃∃T1,T1s. ⬆*[f] T1 ≡ T2 & ⬆*[f] T1s ≡ T2s &
81                                   X = T1 @ T1s.
82 /2 width=3 by liftsv_inv_cons2_aux/ qed-.
83
84 (* Basic_1: was: lifts1_flat (left to right) *)
85 lemma lifts_inv_applv1: ∀f:rtmap. ∀V1s,U1,T2. ⬆*[f] Ⓐ V1s.U1 ≡ T2 →
86                         ∃∃V2s,U2. ⬆*[f] V1s ≡ V2s & ⬆*[f] U1 ≡ U2 &
87                                   T2 = Ⓐ V2s.U2.
88 #f #V1s elim V1s -V1s
89 [ /3 width=5 by ex3_2_intro, liftsv_nil/
90 | #V1 #V1s #IHV1s #T1 #X #H elim (lifts_inv_flat1 … H) -H
91   #V2 #Y #HV12 #HY #H destruct elim (IHV1s … HY) -IHV1s -HY
92   #V2s #T2 #HV12s #HT12 #H destruct /3 width=5 by ex3_2_intro, liftsv_cons/
93 ]
94 qed-.
95
96 lemma lifts_inv_applv2: ∀f:rtmap. ∀V2s,U2,T1. ⬆*[f] T1 ≡ Ⓐ V2s.U2 →
97                         ∃∃V1s,U1. ⬆*[f] V1s ≡ V2s & ⬆*[f] U1 ≡ U2 &
98                                   T1 = Ⓐ V1s.U1.
99 #f #V2s elim V2s -V2s
100 [ /3 width=5 by ex3_2_intro, liftsv_nil/
101 | #V2 #V2s #IHV2s #T2 #X #H elim (lifts_inv_flat2 … H) -H
102   #V1 #Y #HV12 #HY #H destruct elim (IHV2s … HY) -IHV2s -HY
103   #V1s #T1 #HV12s #HT12 #H destruct /3 width=5 by ex3_2_intro, liftsv_cons/
104 ]
105 qed-.
106
107 (* Basic properties *********************************************************)
108
109 (* Basic_2A1: includes: liftv_total *)
110 lemma liftsv_total: ∀f. ∀T1s:list term. ∃T2s. ⬆*[f] T1s ≡ T2s.
111 #f #T1s elim T1s -T1s
112 [ /2 width=2 by liftsv_nil, ex_intro/
113 | #T1 #T1s * #T2s #HT12s
114   elim (lifts_total T1 f) /3 width=2 by liftsv_cons, ex_intro/
115 ]
116 qed-.
117
118 (* Basic_1: was: lifts1_flat (right to left) *)
119 lemma lifts_applv: ∀f:rtmap. ∀V1s,V2s. ⬆*[f] V1s ≡ V2s →
120                    ∀T1,T2. ⬆*[f] T1 ≡ T2 →
121                    ⬆*[f] Ⓐ V1s.T1 ≡ Ⓐ V2s.T2.
122 #f #V1s #V2s #H elim H -V1s -V2s /3 width=1 by lifts_flat/
123 qed.
124
125 (* Basic_1: removed theorems 2: lifts1_nil lifts1_cons *)