matita/matita/contribs/lambda_delta/basic_2/unfold/gr2.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/grammar/term_vector.ma".
  16
  17 (* GENERIC RELOCATION WITH PAIRS ********************************************)
  18
  19 inductive at: list2 nat nat → relation nat ≝
  20 | at_nil: ∀i. at ⟠ i i
  21 | at_lt : ∀des,d,e,i1,i2. i1 < d →
  22           at des i1 i2 → at ({d, e} @ des) i1 i2
  23 | at_ge : ∀des,d,e,i1,i2. d ≤ i1 →
  24           at des (i1 + e) i2 → at ({d, e} @ des) i1 i2
  25 .
  26
  27 interpretation "application (generic relocation with pairs)"
  28    'RAt i1 des i2 = (at des i1 i2).
  29
  30 (* Basic inversion lemmas ***************************************************)
  31
  32 fact at_inv_nil_aux: ∀des,i1,i2. @⦃i1, des⦄ ≡ i2 → des = ⟠ → i1 = i2.
  33 #des #i1 #i2 * -des -i1 -i2
  34 [ //
  35 | #des #d #e #i1 #i2 #_ #_ #H destruct
  36 | #des #d #e #i1 #i2 #_ #_ #H destruct
  37 ]
  38 qed.
  39
  40 lemma at_inv_nil: ∀i1,i2. @⦃i1, ⟠⦄ ≡ i2 → i1 = i2.
  41 /2 width=3/ qed-.
  42
  43 fact at_inv_cons_aux: ∀des,i1,i2. @⦃i1, des⦄ ≡ i2 →
  44                       ∀d,e,des0. des = {d, e} @ des0 →
  45                       i1 < d ∧ @⦃i1, des0⦄ ≡ i2 ∨
  46                       d ≤ i1 ∧ @⦃i1 + e, des0⦄ ≡ i2.
  47 #des #i1 #i2 * -des -i1 -i2
  48 [ #i #d #e #des #H destruct
  49 | #des1 #d1 #e1 #i1 #i2 #Hid1 #Hi12 #d2 #e2 #des2 #H destruct /3 width=1/
  50 | #des1 #d1 #e1 #i1 #i2 #Hdi1 #Hi12 #d2 #e2 #des2 #H destruct /3 width=1/
  51 ]
  52 qed.
  53
  54 lemma at_inv_cons: ∀des,d,e,i1,i2. @⦃i1, {d, e} @ des⦄ ≡ i2 →
  55                    i1 < d ∧ @⦃i1, des⦄ ≡ i2 ∨
  56                    d ≤ i1 ∧ @⦃i1 + e, des⦄ ≡ i2.
  57 /2 width=3/ qed-.
  58
  59 lemma at_inv_cons_lt: ∀des,d,e,i1,i2. @⦃i1, {d, e} @ des⦄ ≡ i2 →
  60                       i1 < d → @⦃i1, des⦄ ≡ i2.
  61 #des #d #e #i1 #e2 #H
  62 elim (at_inv_cons … H) -H * // #Hdi1 #_ #Hi1d
  63 lapply (le_to_lt_to_lt … Hdi1 Hi1d) -Hdi1 -Hi1d #Hd
  64 elim (lt_refl_false … Hd)
  65 qed-.
  66
  67 lemma at_inv_cons_ge: ∀des,d,e,i1,i2. @⦃i1, {d, e} @ des⦄ ≡ i2 →
  68                       d ≤ i1 → @⦃i1 + e, des⦄ ≡ i2.
  69 #des #d #e #i1 #e2 #H
  70 elim (at_inv_cons … H) -H * // #Hi1d #_ #Hdi1
  71 lapply (le_to_lt_to_lt … Hdi1 Hi1d) -Hdi1 -Hi1d #Hd
  72 elim (lt_refl_false … Hd)
  73 qed-.