matita/matita/contribs/lambdadelta/ground/ynat/ynat_minus_sn.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 "ground/ynat/ynat_plus.ma".
  16
  17 (* NATURAL NUMBERS WITH INFINITY ********************************************)
  18
  19 (* left subtraction *)
  20 definition yminus_sn (x) (y): ynat ≝ ypred^y x.
  21
  22 interpretation "ynat left minus" 'minus x y = (yminus_sn x y).
  23
  24 lemma yminus_O2: ∀m:ynat. m - 0 = m.
  25 // qed.
  26
  27 lemma yminus_S2: ∀m:ynat. ∀n:nat. m - S n = ↓(m - n).
  28 // qed.
  29
  30 (* Basic properties *********************************************************)
  31
  32 lemma yminus_inj: ∀m,n. yinj m - n = yinj (m - n).
  33 #m #n elim n -n //
  34 #n #IH >yminus_S2 >IH -IH >eq_minus_S_pred //
  35 qed.
  36
  37 lemma yminus_Y_inj: ∀n. ∞ - n = ∞.
  38 #n elim n -n //
  39 qed.
  40
  41 lemma yminus_O1: ∀x:nat. yinj 0 - x = 0.
  42 // qed.
  43
  44 lemma yminus_refl: ∀x:nat. yinj x - x = 0.
  45 // qed.
  46
  47 lemma yminus_minus_comm: ∀x:ynat. ∀y,z. x - y - z = x - z - y.
  48 * // qed.
  49
  50 (* Properties on predecessor ************************************************)
  51
  52 lemma yminus_SO2: ∀m:ynat. m - 1 = ↓m.
  53 // qed.
  54
  55 lemma yminus_pred1: ∀x,y. ↓x - y = ↓(x-y).
  56 #x * // #y elim y -y //
  57 qed.
  58
  59 lemma yminus_pred: ∀m:ynat. ∀n. 0 < m → 0 < n → ↓m - ↓n = m - n.
  60 * // #m #n >yminus_inj >yminus_inj
  61 /4 width=1 by ylt_inv_inj, minus_pred_pred, eq_f/
  62 qed-.
  63
  64 (* Properties on successor **************************************************)
  65
  66 lemma yminus_succ: ∀m:ynat. ∀n. ↑m - ↑n = m - n.
  67 * // qed.
  68
  69 lemma yminus_succ1_inj: ∀n:nat. ∀m:ynat. n ≤ m → ↑m - n = ↑(m - n).
  70 #n *
  71 [ #m #Hmn >yminus_inj >yminus_inj
  72   /4 width=1 by yle_inv_inj, plus_minus, eq_f/
  73 | >yminus_Y_inj //
  74 ]
  75 qed-.
  76
  77 lemma yminus_succ2: ∀x:ynat. ∀y. x - ↑y = ↓(x-y).
  78 * //
  79 qed.
  80
  81 (* Properties on order ******************************************************)
  82
  83 lemma yle_minus_sn: ∀m:ynat. ∀n. m - n ≤ m.
  84 * // #n /2 width=1 by yle_inj/
  85 qed.
  86
  87 lemma yle_to_minus: ∀m:ynat. ∀n:nat. m ≤ n → m - n = 0.
  88 *
  89 [ #m #n #H >yminus_inj /4 width=1 by yle_inv_inj, eq_minus_O, eq_f/
  90 | #n #H lapply (yle_inv_Y1 … H) -H #H destruct
  91 ]
  92 qed-.
  93
  94 lemma yminus_to_le: ∀m:ynat. ∀n. m - n = 0 → m ≤ n.
  95 * [2: #n >yminus_Y_inj #H destruct ]
  96 #m #n >yminus_inj #H
  97 lapply (yinj_inj … H) -H (**) (* destruct lemma needed *)
  98 /2 width=1 by yle_inj/
  99 qed.
 100
 101 lemma monotonic_yle_minus_dx: ∀x,y. x ≤ y → ∀z. x - z ≤ y - z.
 102 #x #y * /3 width=1 by yle_inj, monotonic_le_minus_l2/
 103 qed.
 104
 105 (* Properties on strict order ***********************************************)
 106
 107 lemma ylt_to_minus: ∀y:ynat. ∀x. yinj x < y → 0 < y - x.
 108 * // #y #x #H >yminus_inj
 109 /4 width=1 by ylt_inj, ylt_inv_inj, lt_plus_to_minus_r/
 110 qed.
 111
 112 lemma yminus_to_lt: ∀y:ynat. ∀x. 0 < y - x → x < y.
 113 * // #y #x >yminus_inj #H
 114 /4 width=1 by ylt_inv_inj, ylt_inj, lt_minus_to_plus_r/
 115 qed-.
 116
 117 lemma monotonic_ylt_minus_dx: ∀x,y:ynat. x < y → ∀z:nat. z ≤ x → x - z < y - z.
 118 #x #y * -x -y
 119 /4 width=1 by ylt_inj, yle_inv_inj, monotonic_lt_minus_l/
 120 qed.
 121
 122 (* Properties on minus ******************************************************)
 123
 124 lemma yplus_minus: ∀m:ynat. ∀n:nat. m + n - n = m.
 125 #m #n elim n -n //
 126 #n #IHn >(yplus_succ2 m n) >(yminus_succ … n) //
 127 qed.
 128
 129 lemma yminus_plus2: ∀x:ynat. ∀y,z. x - (y + z) = x - y - z.
 130 * // qed.
 131
 132 (* Forward lemmas on minus **************************************************)
 133
 134 lemma yle_plus1_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y.
 135 #x #z #y #H lapply (monotonic_yle_minus_dx … H y) -H //
 136 qed-.
 137
 138 lemma yle_plus1_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y.
 139 /2 width=1 by yle_plus1_to_minus_inj2/ qed-.
 140
 141 lemma yle_plus2_to_minus_inj2: ∀x,y:ynat. ∀z:nat. x ≤ y + z → x - z ≤ y.
 142 /2 width=1 by monotonic_yle_minus_dx/ qed-.
 143
 144 lemma yle_plus2_to_minus_inj1: ∀x,y:ynat. ∀z:nat. x ≤ z + y → x - z ≤ y.
 145 /2 width=1 by yle_plus2_to_minus_inj2/ qed-.
 146
 147 lemma yminus_plus (x:ynat) (y:nat): y ≤ x → x = (x-y)+y.
 148 * // #x #y #H >yminus_inj >yplus_inj
 149 /4 width=1 by yle_inv_inj, plus_minus, eq_f/
 150 qed-.
 151
 152 lemma yplus_minus_assoc_inj: ∀x:nat. ∀y,z:ynat. x ≤ y → z + (y - x) = z + y - x.
 153 #x *
 154 [ #y * // #z >yminus_inj >yplus_inj >yplus_inj
 155   /4 width=1 by yle_inv_inj, plus_minus, eq_f/
 156 | >yminus_Y_inj //
 157 ]
 158 qed-.
 159
 160 alias symbol "plus" (instance 5) = "ynat plus".
 161 alias symbol "minus" (instance 4) = "ynat left minus".
 162 alias symbol "minus" (instance 3) = "natural minus".
 163 alias symbol "minus" (instance 2) = "ynat left minus".
 164 alias symbol "leq" (instance 6) = "natural 'less or equal to'".
 165 lemma yplus_minus_assoc_comm_inj: ∀z:ynat. ∀x,y:nat. x ≤ y → z - (y - x) = z + x - y.
 166 * // #z #x #y >yminus_inj >yplus_inj >yminus_inj
 167 /4 width=1 by yle_inv_inj, minus_le_minus_minus_comm, eq_f/
 168 qed-.
 169
 170 lemma yplus_minus_comm_inj: ∀y:nat. ∀x,z:ynat. y ≤ x → x + z - y = x - y + z.
 171 #y * // #x * //
 172 #z #Hxy >yplus_inj >yminus_inj <plus_minus
 173 /2 width=1 by yle_inv_inj/
 174 qed-.
 175
 176 lemma ylt_plus1_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y < z → x < z - y.
 177 #x #z #y #H lapply (monotonic_ylt_minus_dx … H y ?) -H //
 178 qed-.
 179
 180 lemma ylt_plus1_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x < z → x < z - y.
 181 /2 width=1 by ylt_plus1_to_minus_inj2/ qed-.
 182
 183 lemma ylt_plus2_to_minus_inj2: ∀x,y:ynat. ∀z:nat. z ≤ x → x < y + z → x - z < y.
 184 /2 width=1 by monotonic_ylt_minus_dx/ qed-.
 185
 186 lemma ylt_plus2_to_minus_inj1: ∀x,y:ynat. ∀z:nat. z ≤ x → x < z + y → x - z < y.
 187 /2 width=1 by ylt_plus2_to_minus_inj2/ qed-.
 188
 189 lemma yplus_inv_Y1: ∀x,y. ∞ = x + y → ∨∨ ∞ = x | ∞ = y.
 190 * /2 width=1 by or_introl/ #x * // #y >yplus_inj #H destruct
 191 qed-.
 192
 193 lemma yplus_inv_minus:
 194       ∀x1,y2:ynat.∀y1,x2:nat.
 195       y1 ≤ x1 → x1 + x2 = y2 + y1 → ∧∧ x1 - y1 = y2 - x2 & x2 ≤ y2.
 196 *
 197 [ #x1 * [| #y1 #x2 #_ >yplus_inj >yplus_Y1 #H destruct ]
 198   #y2 #y1 #x2 #H1 >yplus_inj >yplus_inj #H2 >yminus_inj >yminus_inj
 199   lapply (yle_inv_inj … H1) -H1 #Hyx1
 200   lapply (yinj_inj … H2) -H2 #Hxy (**) (* destruct lemma needed *)
 201   /5 width=4 by yle_inj, plus2_le_sn_sn, plus_to_minus_2, conj, eq_f2/
 202 | #y2 #y1 #x2 #_ >yplus_Y1 #H
 203   elim (yplus_inv_Y1 … H) -H #H destruct /2 width=1 by conj/
 204 ]
 205 qed-.
 206
 207 (* Inversion lemmas on minus ************************************************)
 208
 209 lemma yle_inv_plus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y ∧ y ≤ z.
 210 /3 width=3 by yle_plus1_to_minus_inj2, yle_trans, conj/ qed-.
 211
 212 lemma yle_inv_plus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y ∧ y ≤ z.
 213 /2 width=1 by yle_inv_plus_inj2/ qed-.
 214
 215 lemma yle_inv_plus_inj_dx: ∀z,x:ynat. ∀y:nat. x + y ≤ z →
 216                            ∧∧ x ≤ z - y & y ≤ z.
 217 * [| /2 width=1 by conj/ ]
 218 #z * [| #y >yplus_Y1 #H >(yle_inv_Y1 … H) -z /2 width=1 by conj/ ]
 219 #x #y >yplus_inj #H >yminus_inj
 220 /5 width=2 by yle_inv_inj, yle_inj, le_plus_to_minus_r, le_plus_b, conj/
 221 qed-.