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/xoa/ex_3_2.ma".
  16 include "ground_2/ynat/ynat_lt.ma".
  17
  18 (* NATURAL NUMBERS WITH INFINITY ********************************************)
  19
  20 (* addition *)
  21 definition yplus: ynat → ynat → ynat ≝ λx,y. match y with
  22 [ yinj n ⇒ ysucc^n x
  23 | Y      ⇒ Y
  24 ].
  25
  26 interpretation "ynat plus" 'plus x y = (yplus x y).
  27
  28 lemma yplus_O2: ∀m:ynat. m + 0 = m.
  29 // qed.
  30
  31 lemma yplus_S2: ∀m:ynat. ∀n. m + S n = ↑(m + n).
  32 // qed.
  33
  34 lemma yplus_Y2: ∀m:ynat. m + (∞) = ∞.
  35 // qed.
  36
  37 (* Properties on successor **************************************************)
  38
  39 lemma yplus_succ2: ∀m,n. m + ↑n = ↑(m + n).
  40 #m * //
  41 qed.
  42
  43 lemma yplus_succ1: ∀m,n. ↑m + n = ↑(m + n).
  44 #m * // #n elim n -n //
  45 qed.
  46
  47 lemma yplus_succ_swap: ∀m,n. m + ↑n = ↑m + n.
  48 // qed.
  49
  50 lemma yplus_SO2: ∀m. m + 1 = ↑m.
  51 * //
  52 qed.
  53
  54 (* Basic properties *********************************************************)
  55
  56 lemma yplus_inj: ∀n,m. yinj m + yinj n = yinj (m + n).
  57 #n elim n -n //
  58 #n #IHn #m >(yplus_succ2 ? n) >IHn -IHn
  59 <plus_n_Sm //
  60 qed.
  61
  62 lemma yplus_Y1: ∀m. ∞ + m = ∞.
  63 * // #m elim m -m //
  64 qed.
  65
  66 lemma yplus_comm: commutative … yplus.
  67 * [ #m ] * [1,3: #n ] //
  68 qed.
  69
  70 lemma yplus_assoc: associative … yplus.
  71 #x #y * // #z cases y -y
  72 [ #y >yplus_inj whd in ⊢ (??%%); <iter_plus //
  73 | >yplus_Y1 //
  74 ]
  75 qed.
  76
  77 lemma yplus_O1: ∀n:ynat. 0 + n = n.
  78 #n >yplus_comm // qed.
  79
  80 lemma yplus_comm_23: ∀x,y,z. x + z + y = x + y + z.
  81 #x #y #z >yplus_assoc //
  82 qed.
  83
  84 lemma yplus_comm_24: ∀x1,x2,x3,x4. x1 + x4 + x3 + x2 = x1 + x2 + x3 + x4.
  85 #x1 #x2 #x3 #x4
  86 >yplus_assoc >yplus_assoc >yplus_assoc >yplus_assoc
  87 /2 width=1 by eq_f2/
  88 qed.
  89
  90 lemma yplus_assoc_23: ∀x1,x2,x3,x4. x1 + x2 + (x3 + x4) = x1 + (x2 + x3) + x4.
  91 #x1 #x2 #x3 #x4 >yplus_assoc >yplus_assoc
  92 /2 width=1 by eq_f2/
  93 qed.
  94
  95 (* Inversion lemmas on successor *********************************************)
  96
  97 lemma yplus_inv_succ_lt_dx: ∀x,y,z:ynat. 0 < y → x + y = ↑z → x + ↓y = z.
  98 #x #y #z #H <(ylt_inv_O1 y) // >yplus_succ2
  99 /2 width=1 by ysucc_inv_inj/
 100 qed-.
 101
 102 lemma yplus_inv_succ_lt_sn: ∀x,y,z:ynat. 0 < x → x + y = ↑z → ↓x + y = z.
 103 #x #y #z #H <(ylt_inv_O1 x) // >yplus_succ1
 104 /2 width=1 by ysucc_inv_inj/
 105
 106 qed-.
 107
 108 (* Inversion lemmas on order ************************************************)
 109
 110 lemma yle_inv_plus_dx: ∀x,y. x ≤ y → ∃z. x + z = y.
 111 #x #y #H elim H -x -y /2 width=2 by ex_intro/
 112 #m #n #H @(ex_intro … (yinj (n-m))) (**) (* explicit constructor *)
 113 /3 width=1 by plus_minus, eq_f/
 114 qed-.
 115
 116 lemma yle_inv_plus_sn: ∀x,y. x ≤ y → ∃z. z + x = y.
 117 #x #y #H elim (yle_inv_plus_dx … H) -H
 118 /2 width=2 by ex_intro/
 119 qed-.
 120
 121 (* Basic inversion lemmas ***************************************************)
 122
 123 lemma yplus_inv_inj: ∀z,y,x. x + y = yinj z →
 124                      ∃∃m,n. m + n = z & x = yinj m & y = yinj n.
 125 #z * [2: normalize #x #H destruct ]
 126 #y * [2: >yplus_Y1 #H destruct ]
 127 /3 width=5 by yinj_inj, ex3_2_intro/
 128 qed-.
 129
 130 lemma yplus_inv_O: ∀x,y:ynat. x + y = 0 → x = 0 ∧ y = 0.
 131 #x #y #H elim (yplus_inv_inj … H) -H
 132 #m * /2 width=1 by conj/ #n <plus_n_Sm #H destruct
 133 qed-.
 134
 135 lemma discr_yplus_xy_x: ∀x,y. x + y = x → x = ∞ ∨ y = 0.
 136 * /2 width=1 by or_introl/
 137 #x elim x -x /2 width=1 by or_intror/
 138 #x #IHx * [2: >yplus_Y2 #H destruct ]
 139 #y <ysucc_inj >yplus_succ1 #H
 140 lapply (ysucc_inv_inj … H) -H #H
 141 elim (IHx … H) -IHx -H /2 width=1 by or_introl, or_intror/
 142 qed-.
 143
 144 lemma discr_yplus_x_xy: ∀x,y. x = x + y → x = ∞ ∨ y = 0.
 145 /2 width=1 by discr_yplus_xy_x/ qed-.
 146
 147 lemma yplus_inv_monotonic_dx_inj: ∀z,x,y. x + yinj z = y + yinj z → x = y.
 148 #z @(nat_ind_plus … z) -z /3 width=2 by ysucc_inv_inj/
 149 qed-.
 150
 151 lemma yplus_inv_monotonic_dx: ∀z,x,y. z < ∞ → x + z = y + z → x = y.
 152 #z #x #y #H elim (ylt_inv_Y2 … H) -H /2 width=2 by yplus_inv_monotonic_dx_inj/
 153 qed-.
 154
 155 lemma yplus_inv_Y2: ∀x,y. x + y = ∞ → x = ∞ ∨ y = ∞.
 156 * /2 width=1 by or_introl/ #x * // #y >yplus_inj #H destruct
 157 qed-.
 158
 159 lemma yplus_inv_monotonic_23: ∀z,x1,x2,y1,y2. z < ∞ →
 160                               x1 + z + y1 = x2 + z + y2 → x1 + y1 = x2 + y2.
 161 #z #x1 #x2 #y1 #y2 #Hz #H @(yplus_inv_monotonic_dx z) //
 162 >yplus_comm_23 >H -H //
 163 qed-.
 164
 165 (* Inversion lemmas on strict_order *****************************************)
 166
 167 lemma ylt_inv_plus_Y: ∀x,y. x + y < ∞ → x < ∞ ∧ y < ∞.
 168 #x #y #H elim (ylt_inv_Y2 … H) -H
 169 #z #H elim (yplus_inv_inj … H) -H /2 width=1 by conj/
 170 qed-.
 171
 172 lemma ylt_inv_plus_sn: ∀x,y. x < y → ∃∃z. ↑z + x = y & x < ∞.
 173 #x #y #H elim (ylt_inv_le … H) -H
 174 #Hx #H elim (yle_inv_plus_sn … H) -H
 175 /2 width=2 by ex2_intro/
 176 qed-.
 177
 178 lemma ylt_inv_plus_dx: ∀x,y. x < y → ∃∃z. x + ↑z = y & x < ∞.
 179 #x #y #H elim (ylt_inv_plus_sn … H) -H
 180 #z >yplus_comm /2 width=2 by ex2_intro/
 181 qed-.
 182
 183 (* Properties on order ******************************************************)
 184
 185 lemma yle_plus_dx2: ∀n,m. n ≤ m + n.
 186 * //
 187 #n elim n -n //
 188 #n #IHn #m >(yplus_succ2 ? n) @(yle_succ n) // (**) (* full auto fails *)
 189 qed.
 190
 191 lemma yle_plus_dx1: ∀n,m. m ≤ m + n.
 192 // qed.
 193
 194 lemma yle_plus_dx1_trans: ∀x,z. z ≤ x → ∀y. z ≤ x + y.
 195 /2 width=3 by yle_trans/ qed.
 196
 197 lemma yle_plus_dx2_trans: ∀y,z. z ≤ y → ∀x. z ≤ x + y.
 198 /2 width=3 by yle_trans/ qed.
 199
 200 lemma monotonic_yle_plus_dx: ∀x,y. x ≤ y → ∀z. x + z ≤ y + z.
 201 #x #y #Hxy * //
 202 #z elim z -z /3 width=1 by yle_succ/
 203 qed.
 204
 205 lemma monotonic_yle_plus_sn: ∀x,y. x ≤ y → ∀z. z + x ≤ z + y.
 206 /2 width=1 by monotonic_yle_plus_dx/ qed.
 207
 208 lemma monotonic_yle_plus: ∀x1,y1. x1 ≤ y1 → ∀x2,y2. x2 ≤ y2 →
 209                           x1 + x2 ≤ y1 + y2.
 210 /3 width=3 by monotonic_yle_plus_dx, monotonic_yle_plus_sn, yle_trans/ qed.
 211
 212 lemma ylt_plus_Y: ∀x,y. x < ∞ → y < ∞ → x + y < ∞.
 213 #x #y #Hx elim (ylt_inv_Y2 … Hx) -Hx
 214 #m #Hm #Hy elim (ylt_inv_Y2 … Hy) -Hy //
 215 qed.
 216
 217 (* Forward lemmas on order **************************************************)
 218
 219 lemma yle_fwd_plus_sn2: ∀x,y,z. x + y ≤ z → y ≤ z.
 220 /2 width=3 by yle_trans/ qed-.
 221
 222 lemma yle_fwd_plus_sn1: ∀x,y,z. x + y ≤ z → x ≤ z.
 223 /2 width=3 by yle_trans/ qed-.
 224
 225 lemma yle_inv_monotonic_plus_dx_inj: ∀x,y:ynat.∀z:nat. x + z ≤ y + z → x ≤ y.
 226 #x #y #z elim z -z /3 width=1 by yle_inv_succ/
 227 qed-.
 228
 229 lemma yle_inv_monotonic_plus_sn_inj: ∀x,y:ynat.∀z:nat. z + x ≤ z + y → x ≤ y.
 230 /2 width=2 by yle_inv_monotonic_plus_dx_inj/ qed-.
 231
 232 lemma yle_inv_monotonic_plus_dx: ∀x,y,z. z < ∞ → x + z ≤ y + z → x ≤ y.
 233 #x #y #z #Hz elim (ylt_inv_Y2 … Hz) -Hz #m #H destruct
 234 /2 width=2 by yle_inv_monotonic_plus_sn_inj/
 235 qed-.
 236
 237 lemma yle_inv_monotonic_plus_sn: ∀x,y,z. z < ∞ → z + x ≤ z + y → x ≤ y.
 238 /2 width=3 by yle_inv_monotonic_plus_dx/ qed-.
 239
 240 lemma yle_fwd_plus_ge: ∀m1,m2:nat. m2 ≤ m1 → ∀n1,n2:ynat. m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
 241 #m1 #m2 #Hm12 #n1 #n2 #H
 242 lapply (monotonic_yle_plus … Hm12 … H) -Hm12 -H
 243 /2 width=2 by yle_inv_monotonic_plus_sn_inj/
 244 qed-.
 245
 246 lemma yle_fwd_plus_ge_inj: ∀m1:nat. ∀m2,n1,n2:ynat. m2 ≤ m1 → m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
 247 #m2 #m1 #n1 #n2 #H elim (yle_inv_inj2 … H) -H
 248 #x #H0 #H destruct /3 width=4 by yle_fwd_plus_ge, yle_inj/
 249 qed-.
 250
 251 lemma yle_fwd_plus_yge: ∀n2,m1:ynat. ∀n1,m2:nat. m2 ≤ m1 → m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
 252 * // #n2 * /2 width=4 by yle_fwd_plus_ge_inj/
 253 qed-.
 254
 255 (* Properties on strict order ***********************************************)
 256
 257 lemma ylt_plus_dx1_trans: ∀x,z. z < x → ∀y. z < x + y.
 258 /2 width=3 by ylt_yle_trans/ qed.
 259
 260 lemma ylt_plus_dx2_trans: ∀y,z. z < y → ∀x. z < x + y.
 261 /2 width=3 by ylt_yle_trans/ qed.
 262
 263 lemma monotonic_ylt_plus_dx_inj: ∀x,y. x < y → ∀z:nat. x + yinj z < y + yinj z.
 264 #x #y #Hxy #z elim z -z /3 width=1 by ylt_succ/
 265 qed.
 266
 267 lemma monotonic_ylt_plus_sn_inj: ∀x,y. x < y → ∀z:nat. yinj z + x < yinj z + y.
 268 /2 width=1 by monotonic_ylt_plus_dx_inj/ qed.
 269
 270 lemma monotonic_ylt_plus_dx: ∀x,y. x < y → ∀z. z < ∞ → x + z < y + z.
 271 #x #y #Hxy #z #Hz elim (ylt_inv_Y2 … Hz) -Hz
 272 #m #H destruct /2 width=1 by monotonic_ylt_plus_dx_inj/
 273 qed.
 274
 275 lemma monotonic_ylt_plus_sn: ∀x,y. x < y → ∀z. z < ∞ → z + x < z + y.
 276 /2 width=1 by monotonic_ylt_plus_dx/ qed.
 277
 278 lemma monotonic_ylt_plus_inj: ∀m1,m2. m1 < m2 → ∀n1,n2. yinj n1 ≤ n2 → m1 + n1 < m2 + n2.
 279 /3 width=3 by monotonic_ylt_plus_sn_inj, monotonic_yle_plus_sn, ylt_yle_trans/
 280 qed.
 281
 282 lemma monotonic_ylt_plus: ∀m1,m2. m1 < m2 → ∀n1. n1 < ∞ → ∀n2. n1 ≤ n2 → m1 + n1 < m2 + n2.
 283 #m1 #m2 #Hm12 #n1 #H elim (ylt_inv_Y2 … H) -H #m #H destruct /2 width=1 by monotonic_ylt_plus_inj/
 284 qed.
 285
 286 (* Forward lemmas on strict order *******************************************)
 287
 288 lemma ylt_inv_monotonic_plus_dx: ∀x,y,z. x + z < y + z → x < y.
 289 * [2: #y #z >yplus_comm #H elim (ylt_inv_Y1 … H) ]
 290 #x * // #y * [2: #H elim (ylt_inv_Y1 … H) ]
 291 /4 width=3 by ylt_inv_inj, ylt_inj, lt_plus_to_lt_l/
 292 qed-.
 293
 294 lemma ylt_fwd_plus_ge: ∀m1,m2. m2 ≤ m1 → ∀n1,n2. m1 + n1 < m2 + n2 → n1 < n2.
 295 #m1 #m2 #Hm12 #n1 #n2 #H elim (ylt_fwd_gen … H)
 296 #x #H0 elim (yplus_inv_inj … H0) -H0
 297 #y #z #_ #H2 #H3 destruct -x
 298 elim (yle_inv_inj2 … Hm12)
 299 #x #_ #H0 destruct
 300 lapply (monotonic_ylt_plus … H … Hm12) -H -Hm12
 301 /2 width=2 by ylt_inv_monotonic_plus_dx/
 302 qed-.
 303
 304 (* Properties on predeccessor ***********************************************)
 305
 306 lemma yplus_pred1: ∀x,y:ynat. 0 < x → ↓x + y = ↓(x+y).
 307 #x * // #y elim y -y // #y #IH #Hx
 308 >yplus_S2 >yplus_S2 >IH -IH // >ylt_inv_O1
 309 /2 width=1 by ylt_plus_dx1_trans/
 310 qed-.
 311
 312 lemma yplus_pred2: ∀x,y:ynat. 0 < y → x + ↓y = ↓(x+y).
 313 /2 width=1 by yplus_pred1/ qed-.