matita/matita/contribs/lambdadelta/ground_2/etc/ynat/ynat_minus_dx.etc

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