inductive at: mr2 → relation nat ≝
| at_nil: ∀i. at (◊) i i
| at_lt : ∀cs,l,m,i1,i2. i1 < l →
- at cs i1 i2 → at ({l, m};cs) i1 i2
+ at cs i1 i2 → at (❨l, m❩;cs) i1 i2
| at_ge : ∀cs,l,m,i1,i2. l ≤ i1 →
- at cs (i1 + m) i2 → at ({l, m};cs) i1 i2
+ at cs (i1 + m) i2 → at (❨l, m❩;cs) i1 i2
.
interpretation "application (multiple relocation with pairs)"
(* Basic inversion lemmas ***************************************************)
-fact at_inv_nil_aux: â\88\80cs,i1,i2. @â¦\83i1, csâ¦\84 ≘ i2 → cs = ◊ → i1 = i2.
+fact at_inv_nil_aux: â\88\80cs,i1,i2. @â\9dªi1, csâ\9d« ≘ i2 → cs = ◊ → i1 = i2.
#cs #i1 #i2 * -cs -i1 -i2
[ //
| #cs #l #m #i1 #i2 #_ #_ #H destruct
]
qed-.
-lemma at_inv_nil: â\88\80i1,i2. @â¦\83i1, â\97\8aâ¦\84 ≘ i2 → i1 = i2.
+lemma at_inv_nil: â\88\80i1,i2. @â\9dªi1, â\97\8aâ\9d« ≘ i2 → i1 = i2.
/2 width=3 by at_inv_nil_aux/ qed-.
-fact at_inv_cons_aux: â\88\80cs,i1,i2. @â¦\83i1, csâ¦\84 ≘ i2 →
- ∀l,m,cs0. cs = {l, m};cs0 →
- i1 < l â\88§ @â¦\83i1, cs0â¦\84 ≘ i2 ∨
- l â\89¤ i1 â\88§ @â¦\83i1 + m, cs0â¦\84 ≘ i2.
+fact at_inv_cons_aux: â\88\80cs,i1,i2. @â\9dªi1, csâ\9d« ≘ i2 →
+ ∀l,m,cs0. cs = ❨l, m❩;cs0 →
+ i1 < l â\88§ @â\9dªi1, cs0â\9d« ≘ i2 ∨
+ l â\89¤ i1 â\88§ @â\9dªi1 + m, cs0â\9d« ≘ i2.
#cs #i1 #i2 * -cs -i1 -i2
[ #i #l #m #cs #H destruct
| #cs1 #l1 #m1 #i1 #i2 #Hil1 #Hi12 #l2 #m2 #cs2 #H destruct /3 width=1 by or_introl, conj/
]
qed-.
-lemma at_inv_cons: â\88\80cs,l,m,i1,i2. @â¦\83i1, {l, m};csâ¦\84 ≘ i2 →
- i1 < l â\88§ @â¦\83i1, csâ¦\84 ≘ i2 ∨
- l â\89¤ i1 â\88§ @â¦\83i1 + m, csâ¦\84 ≘ i2.
+lemma at_inv_cons: â\88\80cs,l,m,i1,i2. @â\9dªi1, â\9d¨l, mâ\9d©;csâ\9d« ≘ i2 →
+ i1 < l â\88§ @â\9dªi1, csâ\9d« ≘ i2 ∨
+ l â\89¤ i1 â\88§ @â\9dªi1 + m, csâ\9d« ≘ i2.
/2 width=3 by at_inv_cons_aux/ qed-.
-lemma at_inv_cons_lt: â\88\80cs,l,m,i1,i2. @â¦\83i1, {l, m};csâ¦\84 ≘ i2 →
- i1 < l â\86\92 @â¦\83i1, csâ¦\84 ≘ i2.
+lemma at_inv_cons_lt: â\88\80cs,l,m,i1,i2. @â\9dªi1, â\9d¨l, mâ\9d©;csâ\9d« ≘ i2 →
+ i1 < l â\86\92 @â\9dªi1, csâ\9d« ≘ i2.
#cs #l #m #i1 #m2 #H
elim (at_inv_cons … H) -H * // #Hli1 #_ #Hi1l
elim (lt_le_false … Hi1l Hli1)
qed-.
-lemma at_inv_cons_ge: â\88\80cs,l,m,i1,i2. @â¦\83i1, {l, m};csâ¦\84 ≘ i2 →
- l â\89¤ i1 â\86\92 @â¦\83i1 + m, csâ¦\84 ≘ i2.
+lemma at_inv_cons_ge: â\88\80cs,l,m,i1,i2. @â\9dªi1, â\9d¨l, mâ\9d©;csâ\9d« ≘ i2 →
+ l â\89¤ i1 â\86\92 @â\9dªi1 + m, csâ\9d« ≘ i2.
#cs #l #m #i1 #m2 #H
elim (at_inv_cons … H) -H * // #Hi1l #_ #Hli1
elim (lt_le_false … Hi1l Hli1)
(* Main properties **********************************************************)
-theorem at_mono: â\88\80cs,i,i1. @â¦\83i, csâ¦\84 â\89\98 i1 â\86\92 â\88\80i2. @â¦\83i, csâ¦\84 ≘ i2 → i1 = i2.
+theorem at_mono: â\88\80cs,i,i1. @â\9dªi, csâ\9d« â\89\98 i1 â\86\92 â\88\80i2. @â\9dªi, csâ\9d« ≘ i2 → i1 = i2.
#cs #i #i1 #H elim H -cs -i -i1
[ #i #x #H <(at_inv_nil … H) -x //
| #cs #l #m #i #i1 #Hil #_ #IHi1 #x #H