matita/matita/contribs/lambdadelta/ground_2A/ynat/ynat_minus.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_2A/ynat/ynat_lt.ma".
  16
  17 (* NATURAL NUMBERS WITH INFINITY ********************************************)
  18
  19 (* subtraction *)
  20 definition yminus: ynat → ynat → ynat ≝ λx,y. match y with
  21 [ yinj n ⇒ ypred^n x
  22 | Y      ⇒ yinj 0
  23 ].
  24
  25 interpretation "ynat minus" 'minus x y = (yminus x y).
  26
  27 (* Basic properties *********************************************************)
  28
  29 lemma yminus_inj: ∀n,m. yinj m - yinj n = yinj (m - n).
  30 #n elim n -n /2 width=3 by trans_eq/
  31 qed.
  32
  33 lemma yminus_Y_inj: ∀n. ∞ - yinj n = ∞.
  34 #n elim n -n // normalize
  35 #n #IHn >IHn //
  36 qed.
  37
  38 lemma yminus_O1: ∀x:ynat. 0 - x = 0.
  39 * // qed.
  40
  41 lemma yminus_refl: ∀x:ynat. x - x = 0.
  42 * // qed.
  43
  44 lemma yminus_minus_comm: ∀y,z,x. x - y - z = x - z - y.
  45 * #y [ * #z [ * // ] ] >yminus_O1 //
  46 qed.
  47
  48 (* Properties on predecessor ************************************************)
  49
  50 lemma yminus_SO2: ∀m. m - 1 = ⫰m.
  51 * //
  52 qed.
  53
  54 lemma yminus_pred: ∀n,m. 0 < m → 0 < n → ⫰m - ⫰n = m - n.
  55 * // #n *
  56 [ #m #Hm #Hn >yminus_inj >yminus_inj
  57   /4 width=1 by ylt_inv_inj, minus_pred_pred, eq_f/
  58 | >yminus_Y_inj //
  59 ]
  60 qed-.
  61
  62 (* Properties on successor **************************************************)
  63
  64 lemma yminus_succ: ∀n,m. ⫯m - ⫯n = m - n.
  65 * // #n * [2: >yminus_Y_inj // ]
  66 #m >yminus_inj //
  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: ∀y,x. x - ⫯y = ⫰(x-y).
  78 * //
  79 qed.
  80
  81 (* Properties on order ******************************************************)
  82
  83 lemma yle_minus_sn: ∀n,m. m - n ≤ m.
  84 * // #n * /2 width=1 by yle_inj/
  85 qed.
  86
  87 lemma yle_to_minus: ∀m:ynat. ∀n:ynat. m ≤ n → m - n = 0.
  88 #m #n * -m -n /3 width=3 by eq_minus_O, eq_f/
  89 qed-.
  90
  91 lemma yminus_to_le: ∀n:ynat. ∀m:ynat. m - n = 0 → m ≤ n.
  92 * // #n *
  93 [ #m >yminus_inj #H lapply (yinj_inj … H) -H (**) (* destruct lemma needed *)
  94   /2 width=1 by yle_inj/
  95 | >yminus_Y_inj #H destruct
  96 ]
  97 qed.
  98
  99 lemma monotonic_yle_minus_dx: ∀x,y. x ≤ y → ∀z. x - z ≤ y - z.
 100 #x #y #Hxy * //
 101 #z elim z -z /3 width=1 by yle_pred/
 102 qed.
 103
 104 (* Properties on strict order ***********************************************)
 105
 106 lemma monotonic_ylt_minus_dx: ∀x,y:ynat. x < y → ∀z:nat. z ≤ x → x - z < y - z.
 107 #x #y * -x -y
 108 /4 width=1 by ylt_inj, yle_inv_inj, monotonic_lt_minus_l/
 109 qed.