matita/matita/contribs/lambdadelta/basic_2/relocation/llor.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/notation/relations/lazyor_4.ma".
  16 include "basic_2/relocation/lpx_sn_alt.ma".
  17
  18 (* POINTWISE UNION FOR LOCAL ENVIRONMENTS ***********************************)
  19
  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
  24 .
  25
  26 definition llor: relation4 term lenv lenv lenv ≝
  27                  λT,L2. lpx_sn (clor T L2).
  28
  29 interpretation
  30    "lazy union (local environment)"
  31    'LazyOr L1 T L2 L = (llor T L2 L1 L).
  32
  33 (* Basic properties *********************************************************)
  34
  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.
  39
  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.
  45
  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/
  54 ]
  55 qed-.
  56
  57 (* Alternative definition ***************************************************)
  58
  59 lemma llor_intro_alt_eq: ∀T,L2,L1,L. |L1| = |L2| → |L1| = |L| →
  60                          (∀I1,I,K1,K,V1,V,U,i. ⇧[i, 1] U ≡ T →
  61                             ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L ≡ K.ⓑ{I}V →
  62                             ∧∧ I1 = I & V1 = V & K1 ⩖[T] L2 ≡ K
  63                          ) →
  64                          (∀I1,I2,I,K1,K2,K,V1,V2,V,i. (∀U. ⇧[i, 1] U ≡ T → ⊥) →
  65                             ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L2 ≡ K2.ⓑ{I2}V2 →
  66                             ⇩[i] L ≡ K.ⓑ{I}V → ∧∧ I1 = I & V2 = V & K1 ⩖[T] L2 ≡ K
  67                          ) → L1 ⩖[T] L2 ≡ L.
  68 #T #L2 #L1 #L #HL12 #HL1 #IH1 #IH2 @lpx_sn_intro_alt // -HL1
  69 #I1 #I #K1 #K #V1 #V #i #HLK1 #HLK
  70 lapply (ldrop_fwd_length_minus4 … HLK1)
  71 lapply (ldrop_fwd_length_le4 … HLK1)
  72 normalize >HL12 <minus_plus #HKL1 #Hi elim (is_lift_dec T i 1) -HL12
  73 [ * #U #HUT elim (IH1 … HUT HLK1 HLK) -IH1 -HLK1 -HLK #H1 #H2 #HT destruct
  74   /3 width=2 by clor_sn, and3_intro/
  75 | #H elim (ldrop_O1_lt L2 i) destruct /2 width=1 by monotonic_lt_minus_l/
  76   #I2 #K2 #V2 #HLK2 elim (IH2 … HLK1 HLK2 HLK) -HLK1 -HLK
  77   /5 width=3 by clor_dx, ex_intro, and3_intro/
  78 ]
  79 qed.
  80
  81 lemma llor_inv_gen_eq: ∀T,L2,L1,L. L1 ⩖[T] L2 ≡ L → |L1| = |L2| →
  82                        |L1| = |L| ∧
  83                        (∀I1,I,K1,K,V1,V,i.
  84                           ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L ≡ K.ⓑ{I}V →
  85                           (∃∃U. ⇧[i, 1] U ≡ T &
  86                                 I1 = I & V1 = V & K1 ⩖[T] L2 ≡ K
  87                           ) ∨
  88                           (∃∃I2,K2,V2. (∀U. ⇧[i, 1] U ≡ T → ⊥) &
  89                                        ⇩[i] L2 ≡ K2.ⓑ{I2}V2 &
  90                                        I1 = I & V2 = V & K1 ⩖[T] L2 ≡ K
  91                           )
  92                        ).
  93 #T #L2 #L1 #L #H #HL12 elim (lpx_sn_inv_gen … H) -H
  94 #HL1 #IH @conj //
  95 #I1 #I #K1 #K #V1 #V #i #HLK1 #HLK
  96 lapply (ldrop_fwd_length_minus4 … HLK1)
  97 lapply (ldrop_fwd_length_le4 … HLK1)
  98 normalize >HL12 <minus_plus #HKL1 #Hi elim (IH … HLK1 HLK) -IH #H *
  99 /4 width=5 by ex5_3_intro, ex4_intro, or_intror, or_introl/
 100 qed-.