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_minus.ma".
17 (* NATURAL NUMBERS WITH INFINITY ********************************************)
20 definition yplus: ynat → ynat → ynat ≝ λx,y. match y with
25 interpretation "ynat plus" 'plus x y = (yplus x y).
27 (* Properties on successor **************************************************)
29 lemma yplus_succ2: ∀m,n. m + ⫯n = ⫯(m + n).
33 lemma yplus_succ1: ∀m,n. ⫯m + n = ⫯(m + n).
37 lemma yplus_succ_swap: ∀m,n. m + ⫯n = ⫯m + n.
40 lemma yplus_SO2: ∀m. m + 1 = ⫯m.
44 (* Basic properties *********************************************************)
46 lemma yplus_inj: ∀n,m. yinj m + yinj n = yinj (m + n).
47 #n elim n -n [ normalize // ]
48 #n #IHn #m >(yplus_succ2 ? n) >IHn -IHn
52 lemma yplus_Y1: ∀m. ∞ + m = ∞.
56 lemma yplus_comm: commutative … yplus.
57 * [ #m ] * [1,3: #n ] //
58 normalize >ysucc_iter_Y //
61 lemma yplus_assoc: associative … yplus.
62 #x #y * // #z cases y -y
63 [ #y >yplus_inj whd in ⊢ (??%%); <iter_plus //
68 lemma yplus_O1: ∀n:ynat. 0 + n = n.
69 #n >yplus_comm // qed.
71 (* Basic inversion lemmas ***************************************************)
73 lemma yplus_inv_inj: ∀z,y,x. x + y = yinj z →
74 ∃∃m,n. m + n = z & x = yinj m & y = yinj n.
75 #z * [2: normalize #x #H destruct ]
76 #y * [2: >yplus_Y1 #H destruct ]
77 /3 width=5 by yinj_inj, ex3_2_intro/
80 (* Properties on order ******************************************************)
82 lemma yle_plus_dx2: ∀n,m. n ≤ m + n.
85 #n #IHn #m >(yplus_succ2 ? n) @(yle_succ n) // (**) (* full auto fails *)
88 lemma yle_plus_dx1: ∀n,m. m ≤ m + n.
91 lemma yle_plus_dx1_trans: ∀x,z. z ≤ x → ∀y. z ≤ x + y.
92 /2 width=3 by yle_trans/ qed.
94 lemma yle_plus_dx2_trans: ∀y,z. z ≤ y → ∀x. z ≤ x + y.
95 /2 width=3 by yle_trans/ qed.
97 lemma monotonic_yle_plus_dx: ∀x,y. x ≤ y → ∀z. x + z ≤ y + z.
99 #z elim z -z /3 width=1 by yle_succ/
102 lemma monotonic_yle_plus_sn: ∀x,y. x ≤ y → ∀z. z + x ≤ z + y.
103 /2 width=1 by monotonic_yle_plus_dx/ qed.
105 lemma monotonic_yle_plus: ∀x1,y1. x1 ≤ y1 → ∀x2,y2. x2 ≤ y2 →
107 /3 width=3 by monotonic_yle_plus_dx, yle_trans/ qed.
109 (* Forward lemmas on order **************************************************)
111 lemma yle_fwd_plus_sn2: ∀x,y,z. x + y ≤ z → y ≤ z.
112 /2 width=3 by yle_trans/ qed-.
114 lemma yle_fwd_plus_sn1: ∀x,y,z. x + y ≤ z → x ≤ z.
115 /2 width=3 by yle_trans/ qed-.
117 lemma yle_inv_monotonic_plus_dx: ∀x,y:ynat.∀z:nat. x + z ≤ y + z → x ≤ y.
118 #x #y #z elim z -z /3 width=1 by yle_inv_succ/
121 lemma yle_inv_monotonic_plus_sn: ∀x,y:ynat.∀z:nat. z + x ≤ z + y → x ≤ y.
122 /2 width=2 by yle_inv_monotonic_plus_dx/ qed-.
124 lemma yle_fwd_plus_ge: ∀m1,m2:nat. m2 ≤ m1 → ∀n1,n2:ynat. m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
125 #m1 #m2 #Hm12 #n1 #n2 #H
126 lapply (monotonic_yle_plus … Hm12 … H) -Hm12 -H
127 /2 width=2 by yle_inv_monotonic_plus_sn/
130 lemma yle_fwd_plus_ge_inj: ∀m1:nat. ∀m2,n1,n2:ynat. m2 ≤ m1 → m1 + n1 ≤ m2 + n2 → n1 ≤ n2.
131 #m2 #m1 #n1 #n2 #H elim (yle_inv_inj2 … H) -H
132 #x #H0 #H destruct /3 width=4 by yle_fwd_plus_ge, yle_inj/
135 (* Forward lemmas on strict_order *******************************************)
137 lemma ylt_inv_monotonic_plus_dx: ∀x,y,z. x + z < y + z → x < y.
138 * [2: #y #z >yplus_comm #H elim (ylt_inv_Y1 … H) ]
139 #x * // #y * [2: #H elim (ylt_inv_Y1 … H) ]
140 /4 width=3 by ylt_inv_inj, ylt_inj, lt_plus_to_lt_l/
143 (* Properties on strict order ***********************************************)
145 lemma monotonic_ylt_plus_dx: ∀x,y. x < y → ∀z:nat. x + yinj z < y + yinj z.
146 #x #y #Hxy #z elim z -z /3 width=1 by ylt_succ/
149 lemma monotonic_ylt_plus_sn: ∀x,y. x < y → ∀z:nat. yinj z + x < yinj z + y.
150 /2 width=1 by monotonic_ylt_plus_dx/ qed.
152 (* Properties on minus ******************************************************)
154 lemma yplus_minus_inj: ∀m:ynat. ∀n:nat. m + n - n = m.
156 #n #IHn >(yplus_succ2 m n) >(yminus_succ … n) //
159 lemma yplus_minus: ∀m,n. m + n - n ≤ m.
163 (* Forward lemmas on minus **************************************************)
165 lemma yle_plus_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y.
166 /2 width=1 by monotonic_yle_minus_dx/ qed-.
168 lemma yle_plus_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y.
169 /2 width=1 by yle_plus_to_minus_inj2/ qed-.
171 lemma yplus_minus_assoc_inj: ∀x:nat. ∀y,z:ynat. x ≤ y → z + (y - x) = z + y - x.
173 [ #y * // #z >yminus_inj >yplus_inj >yplus_inj
174 /4 width=1 by yle_inv_inj, plus_minus, eq_f/
179 lemma yplus_minus_comm_inj: ∀y:nat. ∀x,z:ynat. y ≤ x → x + z - y = x - y + z.
181 #z #Hxy >yplus_inj >yminus_inj <plus_minus
182 /2 width=1 by yle_inv_inj/
185 (* Inversion lemmas on minus ************************************************)
187 lemma yle_inv_plus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y ∧ y ≤ z.
188 /3 width=3 by yle_plus_to_minus_inj2, yle_trans, conj/ qed-.
190 lemma yle_inv_plus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y ∧ y ≤ z.
191 /2 width=1 by yle_inv_plus_inj2/ qed-.