1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "basic_2/notation/relations/lazyor_4.ma".
16 include "basic_2/relocation/lpx_sn_alt.ma".
18 (* LAZY UNION FOR LOCAL ENVIRONMENTS ****************************************)
20 inductive clor (T) (L2) (K1) (V1): predicate term ≝
21 | clor_sn: ∀U. |K1| < |L2| → ⇧[|L2|-|K1|-1, 1] U ≡ T → clor T L2 K1 V1 V1
22 | clor_dx: ∀I,K2,V2. |K1| < |L2| → (∀U. ⇧[|L2|-|K1|-1, 1] U ≡ T → ⊥) →
23 ⇩[|L2|-|K1|-1] L2 ≡ K2.ⓑ{I}V2 → clor T L2 K1 V1 V2
26 definition llor: relation4 term lenv lenv lenv ≝
27 λT,L2. lpx_sn (clor T L2).
30 "lazy union (local environment)"
31 'LazyOr L1 T L2 L = (llor T L2 L1 L).
33 (* Basic properties *********************************************************)
35 lemma llor_pair_sn: ∀I,L1,L2,L,V,T,U. L1 ⩖[T] L2 ≡ L →
36 |L1| < |L2| → ⇧[|L2|-|L1|-1, 1] U ≡ T →
37 L1.ⓑ{I}V ⩖[T] L2 ≡ L.ⓑ{I}V.
38 /3 width=2 by clor_sn, lpx_sn_pair/ qed.
40 lemma llor_pair_dx: ∀I,J,L1,L2,L,K2,V1,V2,T. L1 ⩖[T] L2 ≡ L →
41 |L1| < |L2| → (∀U. ⇧[|L2|-|L1|-1, 1] U ≡ T → ⊥) →
42 ⇩[|L2|-|L1|-1] L2 ≡ K2.ⓑ{J}V2 →
43 L1.ⓑ{I}V1 ⩖[T] L2 ≡ L.ⓑ{I}V2.
44 /4 width=3 by clor_dx, lpx_sn_pair/ qed.
46 lemma llor_total: ∀T,L2,L1. |L1| ≤ |L2| → ∃L. L1 ⩖[T] L2 ≡ L.
47 #T #L2 #L1 elim L1 -L1 /2 width=2 by ex_intro/
48 #L1 #I1 #V1 #IHL1 normalize
49 #H elim IHL1 -IHL1 /2 width=3 by transitive_le/
50 #L #HT elim (is_lift_dec T (|L2|-|L1|-1) 1)
51 [ * /3 width=2 by llor_pair_sn, ex_intro/
52 | elim (ldrop_O1_lt L2 (|L2|-|L1|-1))
53 /5 width=4 by llor_pair_dx, monotonic_lt_minus_l, ex_intro/