]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambdadelta/basic_2/etc/lleq_alt/lleq.etc
components: arity, csuba
[helm.git] / matita / matita / contribs / lambdadelta / basic_2 / etc / lleq_alt / lleq.etc
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/notation/relations/lazyeq_4.ma".
16 include "basic_2/substitution/cpys.ma".
17
18 (* LAZY EQUIVALENCE FOR LOCAL ENVIRONMENTS **********************************)
19
20 definition lleq: relation4 ynat term lenv lenv ≝
21                  λd,T,L1,L2. |L1| = |L2| ∧
22                              (∀U. ⦃⋆, L1⦄ ⊢ T ▶*[d, ∞] U ↔ ⦃⋆, L2⦄ ⊢ T ▶*[d, ∞] U).
23
24 interpretation
25    "lazy equivalence (local environment)"
26    'LazyEq T d L1 L2 = (lleq d T L1 L2).
27
28 (* Basic properties *********************************************************)
29
30 lemma lleq_refl: ∀d,T. reflexive … (lleq d T).
31 /3 width=1 by conj/ qed.
32
33 lemma lleq_sym: ∀d,T. symmetric … (lleq d T).
34 #d #T #L1 #L2 * /3 width=1 by iff_sym, conj/
35 qed-.
36
37 lemma lleq_sort: ∀L1,L2,d,k. |L1| = |L2| → L1 ⋕[⋆k, d] L2.
38 #L1 #L2 #d #k #HL12 @conj // -HL12
39 #U @conj #H >(cpys_inv_sort1 … H) -H //
40 qed.
41
42 lemma lleq_gref: ∀L1,L2,d,p. |L1| = |L2| → L1 ⋕[§p, d] L2.
43 #L1 #L2 #d #k #HL12 @conj // -HL12
44 #U @conj #H >(cpys_inv_gref1 … H) -H //
45 qed.
46
47 lemma lleq_bind: ∀a,I,L1,L2,V,T,d.
48                  L1 ⋕[V, d] L2 → L1.ⓑ{I}V ⋕[T, ⫯d] L2.ⓑ{I}V →
49                  L1 ⋕[ⓑ{a,I}V.T, d] L2.
50 #a #I #L1 #L2 #V #T #d * #HL12 #IHV * #_ #IHT @conj // -HL12
51 #X @conj #H elim (cpys_inv_bind1 … H) -H
52 #W #U #HVW #HTU #H destruct
53 elim (IHV W) -IHV elim (IHT U) -IHT /3 width=1 by cpys_bind/
54 qed.
55
56 lemma lleq_flat: ∀I,L1,L2,V,T,d.
57                  L1 ⋕[V, d] L2 → L1 ⋕[T, d] L2 → L1 ⋕[ⓕ{I}V.T, d] L2.
58 #I #L1 #L2 #V #T #d * #HL12 #IHV * #_ #IHT @conj // -HL12
59 #X @conj #H elim (cpys_inv_flat1 … H) -H
60 #W #U #HVW #HTU #H destruct
61 elim (IHV W) -IHV elim (IHT U) -IHT
62 /3 width=1 by cpys_flat/
63 qed.
64
65 lemma lleq_be: ∀L1,L2,U,dt. L1 ⋕[U, dt] L2 → ∀T,d,e. ⇧[d, e] T ≡ U →
66                d ≤ dt → dt ≤ d + e → L1 ⋕[U, d] L2.
67 #L1 #L2 #U #dt * #HL12 #IH #T #d #e #HTU #Hddt #Hdtde @conj // -HL12
68 #U0 elim (IH U0) -IH #H12 #H21 @conj
69 #HU0 elim (cpys_fwd_up … HU0 … HTU) // -HU0 /4 width=5 by cpys_weak/
70 qed-.
71
72 lemma lsuby_lleq_trans: ∀L2,L,T,d. L2 ⋕[T, d] L →
73                         ∀L1. L1 ⊑×[d, ∞] L2 → |L1| = |L2| → L1 ⋕[T, d] L.
74 #L2 #L #T #d * #HL2 #IH #L1 #HL12 #H @conj // -HL2
75 #U elim (IH U) -IH #Hdx #Hsn @conj #HTU
76 [ @Hdx -Hdx -Hsn @(lsuby_cpys_trans … HTU) -HTU
77   /2 width=1 by lsuby_sym/ (**) (* full auto does not work *)
78 | -H -Hdx /3 width=3 by lsuby_cpys_trans/
79 ]
80 qed-.
81
82 lemma lleq_lsuby_trans: ∀L,L1,T,d. L ⋕[T, d] L1 →
83                         ∀L2. L1 ⊑×[d, ∞] L2 → |L1| = |L2| → L ⋕[T, d] L2.
84 /5 width=4 by lsuby_lleq_trans, lleq_sym, lsuby_sym/ qed-.
85
86 lemma lleq_lsuby_repl: ∀L1,L2,T,d. L1 ⋕[T, d] L2 →
87                        ∀K1. K1 ⊑×[d, ∞] L1 → |K1| = |L1| →
88                        ∀K2. L2 ⊑×[d, ∞] K2 → |L2| = |K2| →
89                        K1 ⋕[T, d] K2.
90 /3 width=4 by lleq_lsuby_trans, lsuby_lleq_trans/ qed-.
91
92 (* Basic forward lemmas *****************************************************)
93
94 lemma lleq_fwd_length: ∀L1,L2,T,d. L1 ⋕[T, d] L2 → |L1| = |L2|.
95 #L1 #L2 #T #d * //
96 qed-.
97
98 lemma lleq_fwd_ldrop_sn: ∀L1,L2,T,d. L1 ⋕[d, T] L2 → ∀K1,i. ⇩[i] L1 ≡ K1 →
99                          ∃K2. ⇩[i] L2 ≡ K2.
100 #L1 #L2 #T #d #H #K1 #i #HLK1 lapply (lleq_fwd_length … H) -H
101 #HL12 lapply (ldrop_fwd_length_le2 … HLK1) -HLK1 /2 width=1 by ldrop_O1_le/
102 qed-.
103
104 lemma lleq_fwd_ldrop_dx: ∀L1,L2,T,d. L1 ⋕[d, T] L2 → ∀K2,i. ⇩[i] L2 ≡ K2 →
105                          ∃K1. ⇩[i] L1 ≡ K1.
106 /3 width=6 by lleq_fwd_ldrop_sn, lleq_sym/ qed-.
107
108 lemma lleq_fwd_bind_sn: ∀a,I,L1,L2,V,T,d.
109                         L1 ⋕[ⓑ{a,I}V.T, d] L2 → L1 ⋕[V, d] L2.
110 #a #I #L1 #L2 #V #T #d * #HL12 #H @conj // -HL12
111 #U elim (H (ⓑ{a,I}U.T)) -H
112 #H1 #H2 @conj
113 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
114 /2 width=1 by cpys_bind/ -H
115 #H elim (cpys_inv_bind1 … H) -H
116 #X #Y #H1 #H2 #H destruct //
117 qed-.
118
119 lemma lleq_fwd_bind_dx: ∀a,I,L1,L2,V,T,d.
120                         L1 ⋕[ⓑ{a,I}V.T, d] L2 → L1.ⓑ{I}V ⋕[T, ⫯d] L2.ⓑ{I}V.
121 #a #I #L1 #L2 #V #T #d * #HL12 #H @conj [ normalize // ] -HL12
122 #U elim (H (ⓑ{a,I}V.U)) -H
123 #H1 #H2 @conj
124 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
125 /2 width=1 by cpys_bind/ -H
126 #H elim (cpys_inv_bind1 … H) -H
127 #X #Y #H1 #H2 #H destruct //
128 qed-.
129
130 lemma lleq_fwd_flat_sn: ∀I,L1,L2,V,T,d.
131                         L1 ⋕[ⓕ{I}V.T, d] L2 → L1 ⋕[V, d] L2.
132 #I #L1 #L2 #V #T #d * #HL12 #H @conj // -HL12
133 #U elim (H (ⓕ{I}U.T)) -H
134 #H1 #H2 @conj
135 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
136 /2 width=1 by cpys_flat/ -H
137 #H elim (cpys_inv_flat1 … H) -H
138 #X #Y #H1 #H2 #H destruct //
139 qed-.
140
141 lemma lleq_fwd_flat_dx: ∀I,L1,L2,V,T,d.
142                         L1 ⋕[ⓕ{I}V.T, d] L2 → L1 ⋕[T, d] L2.
143 #I #L1 #L2 #V #T #d * #HL12 #H @conj // -HL12
144 #U elim (H (ⓕ{I}V.U)) -H
145 #H1 #H2 @conj
146 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
147 /2 width=1 by cpys_flat/ -H
148 #H elim (cpys_inv_flat1 … H) -H
149 #X #Y #H1 #H2 #H destruct //
150 qed-.
151
152 (* Basic inversion lemmas ***************************************************)
153
154 lemma lleq_inv_bind: ∀a,I,L1,L2,V,T,d. L1 ⋕[ⓑ{a,I}V.T, d] L2 →
155                      L1 ⋕[V, d] L2 ∧ L1.ⓑ{I}V ⋕[T, ⫯d] L2.ⓑ{I}V.
156 /3 width=4 by lleq_fwd_bind_sn, lleq_fwd_bind_dx, conj/ qed-.
157
158 lemma lleq_inv_flat: ∀I,L1,L2,V,T,d. L1 ⋕[ⓕ{I}V.T, d] L2 →
159                      L1 ⋕[V, d] L2 ∧ L1 ⋕[T, d] L2.
160 /3 width=3 by lleq_fwd_flat_sn, lleq_fwd_flat_dx, conj/ qed-.