(* *)
(**************************************************************************)
+include "ground_2/ynat/ynat_minus.ma".
include "basic_2/notation/relations/rminus_3.ma".
include "basic_2/multiple/mr2.ma".
(* MULTIPLE RELOCATION WITH PAIRS *******************************************)
-inductive minuss: nat → relation (list2 nat nat) ≝
-| minuss_nil: â\88\80i. minuss i (â\9f ) (â\9f )
-| minuss_lt : ∀des1,des2,d,e,i. i < d → minuss i des1 des2 →
- minuss i ({d, e} @ des1) ({d - i, e} @ des2)
-| minuss_ge : ∀des1,des2,d,e,i. d ≤ i → minuss (e + i) des1 des2 →
- minuss i ({d, e} @ des1) des2
+inductive minuss: nat → relation (list2 ynat nat) ≝
+| minuss_nil: â\88\80i. minuss i (â\97\8a) (â\97\8a)
+| minuss_lt : ∀cs1,cs2,l,m,i. yinj i < l → minuss i cs1 cs2 →
+ minuss i ({l, m} @ cs1) ({l - i, m} @ cs2)
+| minuss_ge : ∀cs1,cs2,l,m,i. l ≤ yinj i → minuss (m + i) cs1 cs2 →
+ minuss i ({l, m} @ cs1) cs2
.
interpretation "minus (multiple relocation with pairs)"
- 'RMinus des1 i des2 = (minuss i des1 des2).
+ 'RMinus cs1 i cs2 = (minuss i cs1 cs2).
(* Basic inversion lemmas ***************************************************)
-fact minuss_inv_nil1_aux: ∀des1,des2,i. des1 ▭ i ≡ des2 → des1 = ⟠ → des2 = ⟠.
-#des1 #des2 #i * -des1 -des2 -i
+fact minuss_inv_nil1_aux: ∀cs1,cs2,i. cs1 ▭ i ≡ cs2 → cs1 = ◊ → cs2 = ◊.
+#cs1 #cs2 #i * -cs1 -cs2 -i
[ //
-| #des1 #des2 #d #e #i #_ #_ #H destruct
-| #des1 #des2 #d #e #i #_ #_ #H destruct
+| #cs1 #cs2 #l #m #i #_ #_ #H destruct
+| #cs1 #cs2 #l #m #i #_ #_ #H destruct
]
qed-.
-lemma minuss_inv_nil1: ∀des2,i. ⟠ ▭ i ≡ des2 → des2 = ⟠.
+lemma minuss_inv_nil1: ∀cs2,i. ◊ ▭ i ≡ cs2 → cs2 = ◊.
/2 width=4 by minuss_inv_nil1_aux/ qed-.
-fact minuss_inv_cons1_aux: ∀des1,des2,i. des1 ▭ i ≡ des2 →
- ∀d,e,des. des1 = {d, e} @ des →
- d ≤ i ∧ des ▭ e + i ≡ des2 ∨
- ∃∃des0. i < d & des ▭ i ≡ des0 &
- des2 = {d - i, e} @ des0.
-#des1 #des2 #i * -des1 -des2 -i
-[ #i #d #e #des #H destruct
-| #des1 #des #d1 #e1 #i1 #Hid1 #Hdes #d2 #e2 #des2 #H destruct /3 width=3 by ex3_intro, or_intror/
-| #des1 #des #d1 #e1 #i1 #Hdi1 #Hdes #d2 #e2 #des2 #H destruct /3 width=1 by or_introl, conj/
+fact minuss_inv_cons1_aux: ∀cs1,cs2,i. cs1 ▭ i ≡ cs2 →
+ ∀l,m,cs. cs1 = {l, m} @ cs →
+ l ≤ i ∧ cs ▭ m + i ≡ cs2 ∨
+ ∃∃cs0. i < l & cs ▭ i ≡ cs0 &
+ cs2 = {l - i, m} @ cs0.
+#cs1 #cs2 #i * -cs1 -cs2 -i
+[ #i #l #m #cs #H destruct
+| #cs1 #cs #l1 #m1 #i1 #Hil1 #Hcs #l2 #m2 #cs2 #H destruct /3 width=3 by ex3_intro, or_intror/
+| #cs1 #cs #l1 #m1 #i1 #Hli1 #Hcs #l2 #m2 #cs2 #H destruct /3 width=1 by or_introl, conj/
]
qed-.
-lemma minuss_inv_cons1: ∀des1,des2,d,e,i. {d, e} @ des1 ▭ i ≡ des2 →
- d ≤ i ∧ des1 ▭ e + i ≡ des2 ∨
- ∃∃des. i < d & des1 ▭ i ≡ des &
- des2 = {d - i, e} @ des.
+lemma minuss_inv_cons1: ∀cs1,cs2,l,m,i. {l, m} @ cs1 ▭ i ≡ cs2 →
+ l ≤ i ∧ cs1 ▭ m + i ≡ cs2 ∨
+ ∃∃cs. i < l & cs1 ▭ i ≡ cs &
+ cs2 = {l - i, m} @ cs.
/2 width=3 by minuss_inv_cons1_aux/ qed-.
-lemma minuss_inv_cons1_ge: ∀des1,des2,d,e,i. {d, e} @ des1 ▭ i ≡ des2 →
- d ≤ i → des1 ▭ e + i ≡ des2.
-#des1 #des2 #d #e #i #H
-elim (minuss_inv_cons1 … H) -H * // #des #Hid #_ #_ #Hdi
-lapply (lt_to_le_to_lt … Hid Hdi) -Hid -Hdi #Hi
-elim (lt_refl_false … Hi)
+lemma minuss_inv_cons1_ge: ∀cs1,cs2,l,m,i. {l, m} @ cs1 ▭ i ≡ cs2 →
+ l ≤ i → cs1 ▭ m + i ≡ cs2.
+#cs1 #cs2 #l #m #i #H
+elim (minuss_inv_cons1 … H) -H * // #cs #Hil #_ #_ #Hli
+elim (ylt_yle_false … Hil Hli)
qed-.
-lemma minuss_inv_cons1_lt: ∀des1,des2,d,e,i. {d, e} @ des1 ▭ i ≡ des2 →
- i < d →
- ∃∃des. des1 ▭ i ≡ des & des2 = {d - i, e} @ des.
-#des1 #des2 #d #e #i #H elim (minuss_inv_cons1 … H) -H * /2 width=3 by ex2_intro/
-#Hdi #_ #Hid lapply (lt_to_le_to_lt … Hid Hdi) -Hid -Hdi
-#Hi elim (lt_refl_false … Hi)
+lemma minuss_inv_cons1_lt: ∀cs1,cs2,l,m,i. {l, m} @ cs1 ▭ i ≡ cs2 →
+ i < l →
+ ∃∃cs. cs1 ▭ i ≡ cs & cs2 = {l - i, m} @ cs.
+#cs1 #cs2 #l #m #i #H elim (minuss_inv_cons1 … H) -H * /2 width=3 by ex2_intro/
+#Hli #_ #Hil elim (ylt_yle_false … Hil Hli)
qed-.