matita/matita/contribs/lambdadelta/basic_2A/multiple/mr2_minus.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_2A/notation/relations/rminus_3.ma".
  16 include "basic_2A/multiple/mr2.ma".
  17
  18 (* MULTIPLE RELOCATION WITH PAIRS *******************************************)
  19
  20 inductive minuss: nat → relation (list2 nat nat) ≝
  21 | minuss_nil: ∀i. minuss i (◊) (◊)
  22 | minuss_lt : ∀cs1,cs2,l,m,i. i < l → minuss i cs1 cs2 →
  23               minuss i ({l, m} @ cs1) ({l - i, m} @ cs2)
  24 | minuss_ge : ∀cs1,cs2,l,m,i. l ≤ i → minuss (m + i) cs1 cs2 →
  25               minuss i ({l, m} @ cs1) cs2
  26 .
  27
  28 interpretation "minus (multiple relocation with pairs)"
  29    'RMinus cs1 i cs2 = (minuss i cs1 cs2).
  30
  31 (* Basic inversion lemmas ***************************************************)
  32
  33 fact minuss_inv_nil1_aux: ∀cs1,cs2,i. cs1 ▭ i ≡ cs2 → cs1 = ◊ → cs2 = ◊.
  34 #cs1 #cs2 #i * -cs1 -cs2 -i
  35 [ //
  36 | #cs1 #cs2 #l #m #i #_ #_ #H destruct
  37 | #cs1 #cs2 #l #m #i #_ #_ #H destruct
  38 ]
  39 qed-.
  40
  41 lemma minuss_inv_nil1: ∀cs2,i. ◊ ▭ i ≡ cs2 → cs2 = ◊.
  42 /2 width=4 by minuss_inv_nil1_aux/ qed-.
  43
  44 fact minuss_inv_cons1_aux: ∀cs1,cs2,i. cs1 ▭ i ≡ cs2 →
  45                            ∀l,m,cs. cs1 = {l, m} @ cs →
  46                            l ≤ i ∧ cs ▭ m + i ≡ cs2 ∨
  47                            ∃∃cs0. i < l & cs ▭ i ≡ cs0 &
  48                                    cs2 = {l - i, m} @ cs0.
  49 #cs1 #cs2 #i * -cs1 -cs2 -i
  50 [ #i #l #m #cs #H destruct
  51 | #cs1 #cs #l1 #m1 #i1 #Hil1 #Hcs #l2 #m2 #cs2 #H destruct /3 width=3 by ex3_intro, or_intror/
  52 | #cs1 #cs #l1 #m1 #i1 #Hli1 #Hcs #l2 #m2 #cs2 #H destruct /3 width=1 by or_introl, conj/
  53 ]
  54 qed-.
  55
  56 lemma minuss_inv_cons1: ∀cs1,cs2,l,m,i. {l, m} @ cs1 ▭ i ≡ cs2 →
  57                         l ≤ i ∧ cs1 ▭ m + i ≡ cs2 ∨
  58                         ∃∃cs. i < l & cs1 ▭ i ≡ cs &
  59                                cs2 = {l - i, m} @ cs.
  60 /2 width=3 by minuss_inv_cons1_aux/ qed-.
  61
  62 lemma minuss_inv_cons1_ge: ∀cs1,cs2,l,m,i. {l, m} @ cs1 ▭ i ≡ cs2 →
  63                            l ≤ i → cs1 ▭ m + i ≡ cs2.
  64 #cs1 #cs2 #l #m #i #H
  65 elim (minuss_inv_cons1 … H) -H * // #cs #Hil #_ #_ #Hli
  66 lapply (lt_to_le_to_lt … Hil Hli) -Hil -Hli #Hi
  67 elim (lt_refl_false … Hi)
  68 qed-.
  69
  70 lemma minuss_inv_cons1_lt: ∀cs1,cs2,l,m,i. {l, m} @ cs1 ▭ i ≡ cs2 →
  71                            i < l →
  72                            ∃∃cs. cs1 ▭ i ≡ cs & cs2 = {l - i, m} @ cs.
  73 #cs1 #cs2 #l #m #i #H elim (minuss_inv_cons1 … H) -H * /2 width=3 by ex2_intro/
  74 #Hli #_ #Hil lapply (lt_to_le_to_lt … Hil Hli) -Hil -Hli
  75 #Hi elim (lt_refl_false … Hi)
  76 qed-.