1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "basic_2/notation/relations/rminus_3.ma".
16 include "basic_2/multiple/mr2.ma".
18 (* MULTIPLE RELOCATION WITH PAIRS *******************************************)
20 inductive minuss: nat → relation (list2 nat nat) ≝
21 | minuss_nil: ∀i. minuss i (◊) (◊)
22 | minuss_lt : ∀des1,des2,l,m,i. i < l → minuss i des1 des2 →
23 minuss i ({l, m} @ des1) ({l - i, m} @ des2)
24 | minuss_ge : ∀des1,des2,l,m,i. l ≤ i → minuss (m + i) des1 des2 →
25 minuss i ({l, m} @ des1) des2
28 interpretation "minus (multiple relocation with pairs)"
29 'RMinus des1 i des2 = (minuss i des1 des2).
31 (* Basic inversion lemmas ***************************************************)
33 fact minuss_inv_nil1_aux: ∀des1,des2,i. des1 ▭ i ≡ des2 → des1 = ◊ → des2 = ◊.
34 #des1 #des2 #i * -des1 -des2 -i
36 | #des1 #des2 #l #m #i #_ #_ #H destruct
37 | #des1 #des2 #l #m #i #_ #_ #H destruct
41 lemma minuss_inv_nil1: ∀des2,i. ◊ ▭ i ≡ des2 → des2 = ◊.
42 /2 width=4 by minuss_inv_nil1_aux/ qed-.
44 fact minuss_inv_cons1_aux: ∀des1,des2,i. des1 ▭ i ≡ des2 →
45 ∀l,m,des. des1 = {l, m} @ des →
46 l ≤ i ∧ des ▭ m + i ≡ des2 ∨
47 ∃∃des0. i < l & des ▭ i ≡ des0 &
48 des2 = {l - i, m} @ des0.
49 #des1 #des2 #i * -des1 -des2 -i
50 [ #i #l #m #des #H destruct
51 | #des1 #des #l1 #m1 #i1 #Hil1 #Hcs #l2 #m2 #des2 #H destruct /3 width=3 by ex3_intro, or_intror/
52 | #des1 #des #l1 #m1 #i1 #Hli1 #Hcs #l2 #m2 #des2 #H destruct /3 width=1 by or_introl, conj/
56 lemma minuss_inv_cons1: ∀des1,des2,l,m,i. {l, m} @ des1 ▭ i ≡ des2 →
57 l ≤ i ∧ des1 ▭ m + i ≡ des2 ∨
58 ∃∃des. i < l & des1 ▭ i ≡ des &
59 des2 = {l - i, m} @ des.
60 /2 width=3 by minuss_inv_cons1_aux/ qed-.
62 lemma minuss_inv_cons1_ge: ∀des1,des2,l,m,i. {l, m} @ des1 ▭ i ≡ des2 →
63 l ≤ i → des1 ▭ m + i ≡ des2.
64 #des1 #des2 #l #m #i #H
65 elim (minuss_inv_cons1 … H) -H * // #des #Hil #_ #_ #Hli
66 lapply (lt_to_le_to_lt … Hil Hli) -Hil -Hli #Hi
67 elim (lt_refl_false … Hi)
70 lemma minuss_inv_cons1_lt: ∀des1,des2,l,m,i. {l, m} @ des1 ▭ i ≡ des2 →
72 ∃∃des. des1 ▭ i ≡ des & des2 = {l - i, m} @ des.
73 #des1 #des2 #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)