matita/matita/contribs/lambdadelta/basic_2/substitution/lleq.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/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 #H1VW #H1WV
  54 elim (IHT U) -IHT #H1TU #H1UT
  55 @cpys_bind /2 width=1 by/ -HVW -H1VW -H1WV
  56 [ @(lsuby_cpys_trans … (L2.ⓑ{I}V))
  57 | @(lsuby_cpys_trans … (L1.ⓑ{I}V))
  58 ] /4 width=5 by lsuby_cpys_trans, lsuby_succ/ (**) (* full auto too slow *)
  59 qed.
  60
  61 lemma lleq_flat: ∀I,L1,L2,V,T,d.
  62                  L1 ⋕[V, d] L2 → L1 ⋕[T, d] L2 → L1 ⋕[ⓕ{I}V.T, d] L2.
  63 #I #L1 #L2 #V #T #d * #HL12 #IHV * #_ #IHT @conj // -HL12
  64 #X @conj #H elim (cpys_inv_flat1 … H) -H
  65 #W #U #HVW #HTU #H destruct
  66 elim (IHV W) -IHV elim (IHT U) -IHT
  67 /3 width=1 by cpys_flat/
  68 qed.
  69
  70 lemma lleq_be: ∀L1,L2,U,dt. L1 ⋕[U, dt] L2 → ∀T,d,e. ⇧[d, e] T ≡ U →
  71                d ≤ dt → dt ≤ d + e → L1 ⋕[U, d] L2.
  72 #L1 #L2 #U #dt * #HL12 #IH #T #d #e #HTU #Hddt #Hdtde @conj // -HL12
  73 #U0 elim (IH U0) -IH #H12 #H21 @conj
  74 #HU0 elim (cpys_up … HU0 … HTU) // -HU0 /4 width=5 by cpys_weak/
  75 qed-.
  76
  77 (* Basic forward lemmas *****************************************************)
  78
  79 lemma lleq_fwd_length: ∀L1,L2,T,d. L1 ⋕[T, d] L2 → |L1| = |L2|.
  80 #L1 #L2 #T #d * //
  81 qed-.
  82
  83 lemma lleq_fwd_ldrop_sn: ∀L1,L2,T,d. L1 ⋕[d, T] L2 → ∀K1,i. ⇩[0, i] L1 ≡ K1 →
  84                          ∃K2. ⇩[0, i] L2 ≡ K2.
  85 #L1 #L2 #T #d #H #K1 #i #HLK1 lapply (lleq_fwd_length … H) -H
  86 #HL12 lapply (ldrop_fwd_length_le2 … HLK1) -HLK1 /2 width=1 by ldrop_O1_le/
  87 qed-.
  88
  89 lemma lleq_fwd_ldrop_dx: ∀L1,L2,T,d. L1 ⋕[d, T] L2 → ∀K2,i. ⇩[0, i] L2 ≡ K2 →
  90                          ∃K1. ⇩[0, i] L1 ≡ K1.
  91 /3 width=6 by lleq_fwd_ldrop_sn, lleq_sym/ qed-.
  92
  93 lemma lleq_fwd_bind_sn: ∀a,I,L1,L2,V,T,d.
  94                         L1 ⋕[ⓑ{a,I}V.T, d] L2 → L1 ⋕[V, d] L2.
  95 #a #I #L1 #L2 #V #T #d * #HL12 #H @conj // -HL12
  96 #U elim (H (ⓑ{a,I}U.T)) -H
  97 #H1 #H2 @conj
  98 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
  99 /2 width=1 by cpys_bind/ -H
 100 #H elim (cpys_inv_bind1 … H) -H
 101 #X #Y #H1 #H2 #H destruct //
 102 qed-.
 103
 104 lemma lleq_fwd_bind_dx: ∀a,I,L1,L2,V,T,d.
 105                         L1 ⋕[ⓑ{a,I}V.T, d] L2 → L1.ⓑ{I}V ⋕[T, ⫯d] L2.ⓑ{I}V.
 106 #a #I #L1 #L2 #V #T #d * #HL12 #H @conj [ normalize // ] -HL12
 107 #U elim (H (ⓑ{a,I}V.U)) -H
 108 #H1 #H2 @conj
 109 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
 110 /2 width=1 by cpys_bind/ -H
 111 #H elim (cpys_inv_bind1 … H) -H
 112 #X #Y #H1 #H2 #H destruct //
 113 qed-.
 114
 115 lemma lleq_fwd_flat_sn: ∀I,L1,L2,V,T,d.
 116                         L1 ⋕[ⓕ{I}V.T, d] L2 → L1 ⋕[V, d] L2.
 117 #I #L1 #L2 #V #T #d * #HL12 #H @conj // -HL12
 118 #U elim (H (ⓕ{I}U.T)) -H
 119 #H1 #H2 @conj
 120 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
 121 /2 width=1 by cpys_flat/ -H
 122 #H elim (cpys_inv_flat1 … H) -H
 123 #X #Y #H1 #H2 #H destruct //
 124 qed-.
 125
 126 lemma lleq_fwd_flat_dx: ∀I,L1,L2,V,T,d.
 127                         L1 ⋕[ⓕ{I}V.T, d] L2 → L1 ⋕[T, d] L2.
 128 #I #L1 #L2 #V #T #d * #HL12 #H @conj // -HL12
 129 #U elim (H (ⓕ{I}V.U)) -H
 130 #H1 #H2 @conj
 131 #H [ lapply (H1 ?) | lapply (H2 ?) ] -H1 -H2
 132 /2 width=1 by cpys_flat/ -H
 133 #H elim (cpys_inv_flat1 … H) -H
 134 #X #Y #H1 #H2 #H destruct //
 135 qed-.
 136
 137 (* Basic inversion lemmas ***************************************************)
 138
 139 lemma lleq_inv_bind: ∀a,I,L1,L2,V,T,d. L1 ⋕[ⓑ{a,I}V.T, d] L2 →
 140                      L1 ⋕[V, d] L2 ∧ L1.ⓑ{I}V ⋕[T, ⫯d] L2.ⓑ{I}V.
 141 /3 width=4 by lleq_fwd_bind_sn, lleq_fwd_bind_dx, conj/ qed-.
 142
 143 lemma lleq_inv_flat: ∀I,L1,L2,V,T,d. L1 ⋕[ⓕ{I}V.T, d] L2 →
 144                      L1 ⋕[V, d] L2 ∧ L1 ⋕[T, d] L2.
 145 /3 width=3 by lleq_fwd_flat_sn, lleq_fwd_flat_dx, conj/ qed-.