matita/matita/contribs/lambdadelta/basic_2/etc/llor.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 "ground_2/xoa/xoa2.ma".
  16 include "basic_2/notation/relations/lazyor_4.ma".
  17 include "basic_2/relocation/lpx_sn_alt.ma".
  18 include "basic_2/substitution/cofrees.ma".
  19
  20 (* POINTWISE UNION FOR LOCAL ENVIRONMENTS ***********************************)
  21
  22 inductive clor (T) (L2) (I) (K1) (V1): predicate term ≝
  23 | clor_sn: |K1| < |L2| → |L2|-|K1|-1 ~ϵ 𝐅*⦃K1, T⦄ → clor T L2 I K1 V1 V1
  24 | clor_dx: ∀K2,V2. |K1| < |L2| → (|L2|-|K1|-1 ~ϵ 𝐅*⦃K1, T⦄ → ⊥) →
  25            ⇩[|L2|-|K1|-1] L2 ≡ K2.ⓑ{I}V2 → clor T L2 I K1 V1 V2
  26 .
  27
  28 definition llor: relation4 term lenv lenv lenv ≝
  29                  λT,L2. lpx_sn (clor T L2).
  30
  31 interpretation
  32    "lazy union (local environment)"
  33    'LazyOr L1 T L2 L = (llor T L2 L1 L).
  34
  35 (* Basic properties *********************************************************)
  36
  37 lemma llor_pair_sn: ∀I,L1,L2,L,V,T. L1 ⩖[T] L2 ≡ L →
  38                     |L1| < |L2| → |L2|-|L1|-1 ~ϵ 𝐅*⦃L1, T⦄ →
  39                     L1.ⓑ{I}V ⩖[T] L2 ≡ L.ⓑ{I}V.
  40 /3 width=2 by clor_sn, lpx_sn_pair/ qed.
  41
  42 lemma llor_pair_dx: ∀I,L1,L2,L,K2,V1,V2,T. L1 ⩖[T] L2 ≡ L →
  43                     |L1| < |L2| → (|L2|-|L1|-1 ~ϵ 𝐅*⦃L1, T⦄ → ⊥) →
  44                     ⇩[|L2|-|L1|-1] L2 ≡ K2.ⓑ{I}V2 →
  45                     L1.ⓑ{I}V1 ⩖[T] L2 ≡ L.ⓑ{I}V2.
  46 /4 width=3 by clor_dx, lpx_sn_pair/ qed.
  47 (*
  48 lemma llor_total: ∀T,L2,L1. |L1| ≤ |L2| → ∃L. L1 ⩖[T] L2 ≡ L.
  49 #T #L2 #L1 elim L1 -L1 /2 width=2 by ex_intro/
  50 #L1 #I1 #V1 #IHL1 normalize
  51 #H elim IHL1 -IHL1 /2 width=3 by transitive_le/
  52 #L #HT elim (cofrees_dec L1 T (|L2|-|L1|-1))
  53 [ /3 width=2 by llor_pair_sn, ex_intro/
  54 | elim (ldrop_O1_lt L2 (|L2|-|L1|-1))
  55   /5 width=4 by llor_pair_dx, monotonic_lt_minus_l, ex_intro/
  56 |
  57 ]
  58 qed-.
  59 *)
  60 (* Alternative definition ***************************************************)
  61
  62 (* Note: uses minus_minus_comm, minus_plus_m_m, commutative_plus, plus_minus *)
  63 lemma plus_minus_minus_be: ∀x,y,z:nat. y ≤ z → z ≤ x → (x - z) + (z - y) = x - y.
  64 #x #z #y #Hzy #Hyx >plus_minus // >commutative_plus >plus_minus //
  65 qed-.
  66
  67 fact plus_minus_minus_be_aux: ∀i,x,y,z:nat. y ≤ z → z ≤ x → i = z - y → x - z + i = x - y.
  68 /2 width=1 by plus_minus_minus_be/ qed-.
  69
  70 lemma llor_intro_alt: ∀T,L2,L1,L. |L1| ≤ |L2| → |L1| = |L| →
  71                       (∀I1,I,K1,K,V1,V,i. ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L ≡ K.ⓑ{I}V →
  72                          (|L2|-|L1|+i ~ϵ 𝐅*⦃K1, T⦄ → I1 = I ∧ V1 = V) ∧
  73                          (∀I2,K2,V2. (|L2|-|L1|+i ~ϵ 𝐅*⦃K1, T⦄  → ⊥) →
  74                                      ⇩[|L2|-|L1|+i] L2 ≡ K2.ⓑ{I2}V2 →
  75                                      ∧∧ I1 = I & I2 = I & V2 = V
  76                          )
  77                       ) → L1 ⩖[T] L2 ≡ L.
  78 #T #L2 #L1 #L #HL12 #HL1 #IH @lpx_sn_intro_alt // -HL1
  79 #I1 #I #K1 #K #V1 #V #i #HLK1 #HLK
  80 lapply (ldrop_fwd_length_minus4 … HLK1)
  81 lapply (ldrop_fwd_length_le4 … HLK1)
  82 normalize #HKL1 #H1i lapply (plus_minus_minus_be_aux … HL12 H1i) // #H2i
  83 lapply (transitive_le … HKL1 HL12) -HKL1 -HL12 #HKL1
  84 elim (IH … HLK1 HLK) -IH -HLK1 -HLK #IH1 #IH2
  85 elim (cofrees_dec K1 T (|L2|-|L1|+i))
  86 [ -IH2 #HT elim (IH1 … HT) -IH1
  87   /3 width=2 by clor_sn, conj/
  88 | -IH1 #H elim (ldrop_O1_lt L2 (|L2|-|L1|+i)) /2 width=1 by monotonic_lt_minus_l/
  89   #I2 #K2 #V2 #HLK2 elim (IH2 … HLK2) -IH2
  90   /5 width=3 by clor_dx, ex_intro, and3_intro/
  91 ]
  92 qed.
  93
  94 lemma llor_inv_alt: ∀T,L2,L1,L. L1 ⩖[T] L2 ≡ L → |L1| ≤ |L2| →
  95                     |L1| = |L| ∧
  96                     (∀I1,I,K1,K,V1,V,i.
  97                        ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L ≡ K.ⓑ{I}V →
  98                        (∃∃U. ⇧[|L2|-|L1|+i, 1] U ≡ T &
  99                              I1 = I & V1 = V & K1 ⩖[T] L2 ≡ K
 100                        ) ∨
 101                        (∃∃I2,K2,V2. (∀U. ⇧[|L2|-|L1|+i, 1] U ≡ T → ⊥) &
 102                                     ⇩[|L2|-|L1|+i] L2 ≡ K2.ⓑ{I2}V2 &
 103                                     I1 = I & V2 = V & K1 ⩖[T] L2 ≡ K
 104                        )
 105                     ).
 106 #T #L2 #L1 #L #H #HL12 elim (lpx_sn_inv_alt … H) -H
 107 #HL1 #IH @conj // -HL1
 108 #I1 #I #K1 #K #V1 #V #i #HLK1 #HLK
 109 lapply (ldrop_fwd_length_minus4 … HLK1)
 110 lapply (ldrop_fwd_length_le4 … HLK1)
 111 normalize #HKL1 #H1i lapply (plus_minus_minus_be_aux … HL12 H1i) //
 112 lapply (transitive_le … HKL1 HL12) -HKL1 -HL12
 113 elim (IH … HLK1 HLK) -IH #H *
 114 /4 width=5 by ex5_3_intro, ex4_intro, or_intror, or_introl/
 115 qed-.