matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_plus.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_2/ynat/ynat_minus.ma".
  16
  17 (* NATURAL NUMBERS WITH INFINITY ********************************************)
  18
  19 (* addition *)
  20 definition yplus: ynat → ynat → ynat ≝ λx,y. match y with
  21 [ yinj n ⇒ ysucc^n x
  22 | Y      ⇒ Y
  23 ].
  24
  25 interpretation "ynat plus" 'plus x y = (yplus x y).
  26
  27 lemma yplus_O2: ∀m:ynat. m + 0 = m.
  28 // qed.
  29
  30 lemma yplus_S2: ∀m:ynat. ∀n. m + S n = ⫯(m + n).
  31 // qed.
  32
  33 lemma yplus_Y2: ∀m:ynat. m + (∞) = ∞.
  34 // qed.
  35
  36 (* Properties on successor **************************************************)
  37
  38 lemma yplus_succ2: ∀m,n. m + ⫯n = ⫯(m + n).
  39 #m * //
  40 qed.
  41
  42 lemma yplus_succ1: ∀m,n. ⫯m + n = ⫯(m + n).
  43 #m * // #n elim n -n //
  44 qed.
  45
  46 lemma yplus_succ_swap: ∀m,n. m + ⫯n = ⫯m + n.
  47 // qed.
  48
  49 lemma yplus_SO2: ∀m. m + 1 = ⫯m.
  50 * //
  51 qed.
  52
  53 (* Basic properties *********************************************************)
  54
  55 lemma yplus_inj: ∀n,m. yinj m + yinj n = yinj (m + n).
  56 #n elim n -n //
  57 #n #IHn #m >(yplus_succ2 ? n) >IHn -IHn
  58 <plus_n_Sm //
  59 qed.
  60
  61 lemma yplus_Y1: ∀m. ∞ + m = ∞.
  62 * // #m elim m -m //
  63 qed.
  64
  65 lemma yplus_comm: commutative … yplus.
  66 * [ #m ] * [1,3: #n ] //
  67 qed.
  68
  69 lemma yplus_assoc: associative … yplus.
  70 #x #y * // #z cases y -y
  71 [ #y >yplus_inj whd in ⊢ (??%%); <iter_plus //
  72 | >yplus_Y1 //
  73 ]
  74 qed.
  75
  76 lemma yplus_O1: ∀n:ynat. 0 + n = n.
  77 #n >yplus_comm // qed.
  78
  79 lemma yplus_comm_23: ∀x,y,z. x + z + y = x + y + z.
  80 #x #y #z >yplus_assoc //
  81 qed.
  82
  83 (* Basic inversion lemmas ***************************************************)
  84
  85 lemma yplus_inv_inj: ∀z,y,x. x + y = yinj z →
  86                      ∃∃m,n. m + n = z & x = yinj m & y = yinj n.
  87 #z * [2: normalize #x #H destruct ]
  88 #y * [2: >yplus_Y1 #H destruct ]
  89 /3 width=5 by yinj_inj, ex3_2_intro/
  90 qed-.
  91
  92 (* Properties on order ******************************************************)
  93
  94 lemma yle_plus_dx2: ∀n,m. n ≤ m + n.
  95 * //
  96 #n elim n -n //
  97 #n #IHn #m >(yplus_succ2 ? n) @(yle_succ n) // (**) (* full auto fails *)
  98 qed.
  99
 100 lemma yle_plus_dx1: ∀n,m. m ≤ m + n.
 101 // qed.
 102
 103 lemma yle_plus_dx1_trans: ∀x,z. z ≤ x → ∀y. z ≤ x + y.
 104 /2 width=3 by yle_trans/ qed.
 105
 106 lemma yle_plus_dx2_trans: ∀y,z. z ≤ y → ∀x. z ≤ x + y.
 107 /2 width=3 by yle_trans/ qed.
 108
 109 lemma monotonic_yle_plus_dx: ∀x,y. x ≤ y → ∀z. x + z ≤ y + z.
 110 #x #y #Hxy * //
 111 #z elim z -z /3 width=1 by yle_succ/
 112 qed.
 113
 114 lemma monotonic_yle_plus_sn: ∀x,y. x ≤ y → ∀z. z + x ≤ z + y.
 115 /2 width=1 by monotonic_yle_plus_dx/ qed.
 116
 117 lemma monotonic_yle_plus: ∀x1,y1. x1 ≤ y1 → ∀x2,y2. x2 ≤ y2 →
 118                           x1 + x2 ≤ y1 + y2.
 119 /3 width=3 by monotonic_yle_plus_dx, monotonic_yle_plus_sn, yle_trans/ qed.
 120
 121 (* Forward lemmas on order **************************************************)
 122
 123 lemma yle_fwd_plus_sn2: ∀x,y,z. x + y ≤ z → y ≤ z.
 124 /2 width=3 by yle_trans/ qed-.
 125
 126 lemma yle_fwd_plus_sn1: ∀x,y,z. x + y ≤ z → x ≤ z.
 127 /2 width=3 by yle_trans/ qed-.
 128
 129 lemma yle_inv_monotonic_plus_dx: ∀x,y:ynat.∀z:nat. x + z ≤ y + z → x ≤ y.
 130 #x #y #z elim z -z /3 width=1 by yle_inv_succ/
 131 qed-.
 132
 133 lemma yle_inv_monotonic_plus_sn: ∀x,y:ynat.∀z:nat. z + x ≤ z + y → x ≤ y.
 134 /2 width=2 by yle_inv_monotonic_plus_dx/ qed-.
 135
 136 lemma yle_fwd_plus_ge: ∀m1,m2:nat. m2 ≤ m1 → ∀n1,n2:ynat. m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
 137 #m1 #m2 #Hm12 #n1 #n2 #H
 138 lapply (monotonic_yle_plus … Hm12 … H) -Hm12 -H
 139 /2 width=2 by yle_inv_monotonic_plus_sn/
 140 qed-.
 141
 142 lemma yle_fwd_plus_ge_inj: ∀m1:nat. ∀m2,n1,n2:ynat. m2 ≤ m1 → m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
 143 #m2 #m1 #n1 #n2 #H elim (yle_inv_inj2 … H) -H
 144 #x #H0 #H destruct /3 width=4 by yle_fwd_plus_ge, yle_inj/
 145 qed-.
 146
 147 lemma yle_fwd_plus_yge: ∀n2,m1:ynat. ∀n1,m2:nat. m2 ≤ m1 → m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
 148 * // #n2 * /2 width=4 by yle_fwd_plus_ge_inj/
 149 qed-.
 150
 151 (* Forward lemmas on strict order *******************************************)
 152
 153 lemma ylt_inv_monotonic_plus_dx: ∀x,y,z. x + z < y + z → x < y.
 154 * [2: #y #z >yplus_comm #H elim (ylt_inv_Y1 … H) ]
 155 #x * // #y * [2: #H elim (ylt_inv_Y1 … H) ]
 156 /4 width=3 by ylt_inv_inj, ylt_inj, lt_plus_to_lt_l/
 157 qed-.
 158
 159 (* Properties on strict order ***********************************************)
 160
 161 lemma ylt_plus_dx1_trans: ∀x,z. z < x → ∀y. z < x + yinj y.
 162 /2 width=3 by ylt_yle_trans/ qed.
 163
 164 lemma ylt_plus_dx2_trans: ∀y,z. z < y → ∀x. z < yinj x + y.
 165 /2 width=3 by ylt_yle_trans/ qed.
 166
 167 lemma monotonic_ylt_plus_dx: ∀x,y. x < y → ∀z:nat. x + yinj z < y + yinj z.
 168 #x #y #Hxy #z elim z -z /3 width=1 by ylt_succ/
 169 qed.
 170
 171 lemma monotonic_ylt_plus_sn: ∀x,y. x < y → ∀z:nat. yinj z + x < yinj z + y.
 172 /2 width=1 by monotonic_ylt_plus_dx/ qed.
 173
 174 (* Properties on predeccessor ***********************************************)
 175
 176 lemma yplus_pred1: ∀x,y:ynat. 0 < x → ⫰x + y = ⫰(x+y).
 177 #x * // #y elim y -y // #y #IH #Hx
 178 >yplus_S2 >yplus_S2 >IH -IH // >ylt_inv_O1
 179 /2 width=1 by ylt_plus_dx1_trans/
 180 qed-.
 181
 182 lemma yplus_pred2: ∀x,y:ynat. 0 < y → x + ⫰y = ⫰(x+y).
 183 /2 width=1 by yplus_pred1/ qed-.
 184
 185 (* Properties on minus ******************************************************)
 186
 187 lemma yplus_minus_inj: ∀m:ynat. ∀n:nat. m + n - n = m.
 188 #m #n elim n -n //
 189 #n #IHn >(yplus_succ2 m n) >(yminus_succ … n) //
 190 qed.
 191
 192 lemma yplus_minus: ∀m,n. m + n - n ≤ m.
 193 #m * //
 194 qed.
 195
 196 lemma yminus_plus2: ∀z,y,x:ynat. x - (y + z) = x - y - z.
 197 * // #z * [2: >yplus_Y1 >yminus_O1 // ] #y *
 198 [ #x >yplus_inj >yminus_inj >yminus_inj >yminus_inj /2 width=1 by eq_f/
 199 | >yplus_inj >yminus_Y_inj //
 200 ]
 201 qed.
 202
 203 (* Forward lemmas on minus **************************************************)
 204
 205 lemma yle_plus1_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y.
 206 #x #z #y #H lapply (monotonic_yle_minus_dx … H y) -H //
 207 qed-.
 208
 209 lemma yle_plus1_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y.
 210 /2 width=1 by yle_plus1_to_minus_inj2/ qed-.
 211
 212 lemma yle_plus2_to_minus_inj2: ∀x,y:ynat. ∀z:nat. x ≤ y + z → x - z ≤ y.
 213 /2 width=1 by monotonic_yle_minus_dx/ qed-.
 214
 215 lemma yle_plus2_to_minus_inj1: ∀x,y:ynat. ∀z:nat. x ≤ z + y → x - z ≤ y.
 216 /2 width=1 by yle_plus2_to_minus_inj2/ qed-.
 217
 218 lemma yplus_minus_assoc_inj: ∀x:nat. ∀y,z:ynat. x ≤ y → z + (y - x) = z + y - x.
 219 #x *
 220 [ #y * // #z >yminus_inj >yplus_inj >yplus_inj
 221   /4 width=1 by yle_inv_inj, plus_minus, eq_f/
 222 | >yminus_Y_inj //
 223 ]
 224 qed-.
 225
 226 lemma yplus_minus_assoc_comm_inj: ∀x:nat. ∀y,z:ynat. x ≤ y → z - (y - x) = z + x - y.
 227 #x *
 228 [ #y *
 229   [ #z >yminus_inj >yminus_inj >yplus_inj >yminus_inj
 230     /4 width=1 by yle_inv_inj, minus_le_minus_minus_comm, eq_f/
 231   | >yminus_inj >yminus_Y_inj //
 232   ]
 233 | >yminus_Y_inj //
 234 ]
 235 qed-.
 236
 237 lemma yplus_minus_comm_inj: ∀y:nat. ∀x,z:ynat. y ≤ x → x + z - y = x - y + z.
 238 #y * // #x * //
 239 #z #Hxy >yplus_inj >yminus_inj <plus_minus
 240 /2 width=1 by yle_inv_inj/
 241 qed-.
 242
 243 lemma ylt_plus1_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y < z → x < z - y.
 244 #x #z #y #H lapply (monotonic_ylt_minus_dx … H y ?) -H //
 245 qed-.
 246
 247 lemma ylt_plus1_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x < z → x < z - y.
 248 /2 width=1 by ylt_plus1_to_minus_inj2/ qed-.
 249
 250 lemma ylt_plus2_to_minus_inj2: ∀x,y:ynat. ∀z:nat. z ≤ x → x < y + z → x - z < y.
 251 /2 width=1 by monotonic_ylt_minus_dx/ qed-.
 252
 253 lemma ylt_plus2_to_minus_inj1: ∀x,y:ynat. ∀z:nat. z ≤ x → x < z + y → x - z < y.
 254 /2 width=1 by ylt_plus2_to_minus_inj2/ qed-.
 255
 256 (* Inversion lemmas on minus ************************************************)
 257
 258 lemma yle_inv_plus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y ∧ y ≤ z.
 259 /3 width=3 by yle_plus1_to_minus_inj2, yle_trans, conj/ qed-.
 260
 261 lemma yle_inv_plus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y ∧ y ≤ z.
 262 /2 width=1 by yle_inv_plus_inj2/ qed-.