1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "ground_2/ynat/ynat_lt.ma".
17 (* NATURAL NUMBERS WITH INFINITY ********************************************)
20 definition yminus: ynat → ynat → ynat ≝ λx,y. match y with
25 interpretation "ynat minus" 'minus x y = (yminus x y).
27 lemma yminus_O2: ∀m:ynat. m - 0 = m.
30 lemma yminus_S2: ∀m:ynat. ∀n:nat. m - S n = ⫰(m - n).
33 lemma yminus_Y2: ∀m. m - (∞) = 0.
36 (* Basic properties *********************************************************)
38 lemma yminus_inj: ∀m,n. yinj m - yinj n = yinj (m - n).
40 #n #IH >yminus_S2 >IH -IH >eq_minus_S_pred //
43 lemma yminus_Y_inj: ∀n. ∞ - yinj n = ∞.
47 lemma yminus_O1: ∀x:ynat. 0 - x = 0.
50 lemma yminus_refl: ∀x:ynat. x - x = 0.
53 lemma yminus_minus_comm: ∀y,z,x. x - y - z = x - z - y.
54 * #y [ * #z [ * // ] ] >yminus_O1 //
57 (* Properties on predecessor ************************************************)
59 lemma yminus_SO2: ∀m. m - 1 = ⫰m.
63 lemma yminus_pred1: ∀x,y. ⫰x - y = ⫰(x-y).
64 #x * // #y elim y -y //
67 lemma yminus_pred: ∀n,m. 0 < m → 0 < n → ⫰m - ⫰n = m - n.
69 [ #m #Hm #Hn >yminus_inj >yminus_inj
70 /4 width=1 by ylt_inv_inj, minus_pred_pred, eq_f/
75 (* Properties on successor **************************************************)
77 lemma yminus_succ: ∀n,m. ⫯m - ⫯n = m - n.
80 lemma yminus_succ1_inj: ∀n:nat. ∀m:ynat. n ≤ m → ⫯m - n = ⫯(m - n).
82 [ #m #Hmn >yminus_inj >yminus_inj
83 /4 width=1 by yle_inv_inj, plus_minus, eq_f/
88 lemma yminus_succ2: ∀y,x. x - ⫯y = ⫰(x-y).
92 (* Properties on order ******************************************************)
94 lemma yle_minus_sn: ∀n,m. m - n ≤ m.
95 * // #n * /2 width=1 by yle_inj/
98 lemma yle_to_minus: ∀m:ynat. ∀n:ynat. m ≤ n → m - n = 0.
99 #m #n * -m -n /3 width=3 by eq_minus_O, eq_f/
102 lemma yminus_to_le: ∀n:ynat. ∀m:ynat. m - n = 0 → m ≤ n.
104 [ #m >yminus_inj #H lapply (yinj_inj … H) -H (**) (* destruct lemma needed *)
105 /2 width=1 by yle_inj/
106 | >yminus_Y_inj #H destruct
110 lemma monotonic_yle_minus_dx: ∀x,y. x ≤ y → ∀z. x - z ≤ y - z.
112 #z elim z -z /3 width=1 by yle_pred/
115 (* Properties on strict order ***********************************************)
117 lemma ylt_to_minus: ∀x,y:ynat. x < y → 0 < y - x.
118 #x #y #H elim H -x -y /3 width=1 by ylt_inj, lt_plus_to_minus_r/
121 lemma yminus_to_lt: ∀x,y:ynat. 0 < y - x → x < y.
122 * [2: #y #H elim (ylt_yle_false … H) // ]
123 #m * /4 width=1 by ylt_inv_inj, ylt_inj, lt_minus_to_plus_r/
126 lemma monotonic_ylt_minus_dx: ∀x,y:ynat. x < y → ∀z:nat. z ≤ x → x - z < y - z.
128 /4 width=1 by ylt_inj, yle_inv_inj, monotonic_lt_minus_l/