]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambdadelta/ground_2/etc/ynat/ynat_minus.etc
updated probe and matitadep
[helm.git] / matita / matita / contribs / lambdadelta / ground_2 / etc / ynat / ynat_minus.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_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 lemma yminus_O2: ∀m:ynat. m - 0 = m.
28 // qed.
29
30 lemma yminus_S2: ∀m:ynat. ∀n:nat. m - S n = ⫰(m - n).
31 // qed.
32
33 lemma yminus_Y2: ∀m. m - (∞) = 0.
34 // qed.
35
36 (* Basic properties *********************************************************)
37
38 lemma yminus_inj: ∀m,n. yinj m - yinj n = yinj (m - n).
39 #m #n elim n -n //
40 #n #IH >yminus_S2 >IH -IH >eq_minus_S_pred //
41 qed.
42
43 lemma yminus_Y_inj: ∀n. ∞ - yinj n = ∞.
44 #n elim n -n //
45 qed.
46
47 lemma yminus_O1: ∀x:ynat. 0 - x = 0.
48 * // qed.
49
50 lemma yminus_refl: ∀x:ynat. x - x = 0.
51 * // qed.
52
53 lemma yminus_minus_comm: ∀y,z,x. x - y - z = x - z - y.
54 * #y [ * #z [ * // ] ] >yminus_O1 //
55 qed.
56
57 (* Properties on predecessor ************************************************)
58
59 lemma yminus_SO2: ∀m. m - 1 = ⫰m.
60 * //
61 qed.
62
63 lemma yminus_pred1: ∀x,y. ⫰x - y = ⫰(x-y).
64 #x * // #y elim y -y //
65 qed.
66
67 lemma yminus_pred: ∀n,m. 0 < m → 0 < n → ⫰m - ⫰n = m - n.
68 * // #n *
69 [ #m #Hm #Hn >yminus_inj >yminus_inj
70   /4 width=1 by ylt_inv_inj, minus_pred_pred, eq_f/
71 | >yminus_Y_inj //
72 ]
73 qed-.
74
75 (* Properties on successor **************************************************)
76
77 lemma yminus_succ: ∀n,m. ⫯m - ⫯n = m - n.
78 * // qed.
79
80 lemma yminus_succ1_inj: ∀n:nat. ∀m:ynat. n ≤ m → ⫯m - n = ⫯(m - n).
81 #n *
82 [ #m #Hmn >yminus_inj >yminus_inj
83   /4 width=1 by yle_inv_inj, plus_minus, eq_f/
84 | >yminus_Y_inj //
85 ]
86 qed-.
87
88 lemma yminus_succ2: ∀y,x. x - ⫯y = ⫰(x-y).
89 * //
90 qed.
91
92 (* Properties on order ******************************************************)
93
94 lemma yle_minus_sn: ∀n,m. m - n ≤ m.
95 * // #n * /2 width=1 by yle_inj/
96 qed.
97
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/
100 qed-.
101
102 lemma yminus_to_le: ∀n:ynat. ∀m:ynat. m - n = 0 → m ≤ n.
103 * // #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
107 ]
108 qed.
109
110 lemma monotonic_yle_minus_dx: ∀x,y. x ≤ y → ∀z. x - z ≤ y - z.
111 #x #y #Hxy * //
112 #z elim z -z /3 width=1 by yle_pred/
113 qed.
114
115 (* Properties on strict order ***********************************************)
116
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/
119 qed.
120
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/
124 qed-.
125
126 lemma monotonic_ylt_minus_dx: ∀x,y:ynat. x < y → ∀z:nat. z ≤ x → x - z < y - z.
127 #x #y * -x -y
128 /4 width=1 by ylt_inj, yle_inv_inj, monotonic_lt_minus_l/
129 qed.
130
131 (* Properties on minus ******************************************************)
132
133 lemma yplus_minus_inj: ∀m:ynat. ∀n:nat. m + n - n = m.
134 #m #n elim n -n //
135 #n #IHn >(yplus_succ2 m n) >(yminus_succ … n) //
136 qed.
137
138 lemma yplus_minus: ∀m,n. m + n - n ≤ m.
139 #m * //
140 qed.
141
142 lemma yminus_plus2: ∀z,y,x:ynat. x - (y + z) = x - y - z.
143 * // #z * [2: >yplus_Y1 >yminus_O1 // ] #y *
144 [ #x >yplus_inj >yminus_inj >yminus_inj >yminus_inj /2 width=1 by eq_f/
145 | >yplus_inj >yminus_Y_inj //
146 ]
147 qed.
148
149 (* Forward lemmas on minus **************************************************)
150
151 lemma yle_plus1_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y.
152 #x #z #y #H lapply (monotonic_yle_minus_dx … H y) -H //
153 qed-.
154
155 lemma yle_plus1_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y.
156 /2 width=1 by yle_plus1_to_minus_inj2/ qed-.
157
158 lemma yle_plus2_to_minus_inj2: ∀x,y:ynat. ∀z:nat. x ≤ y + z → x - z ≤ y.
159 /2 width=1 by monotonic_yle_minus_dx/ qed-.
160
161 lemma yle_plus2_to_minus_inj1: ∀x,y:ynat. ∀z:nat. x ≤ z + y → x - z ≤ y.
162 /2 width=1 by yle_plus2_to_minus_inj2/ qed-.
163
164 lemma yplus_minus_assoc_inj: ∀x:nat. ∀y,z:ynat. x ≤ y → z + (y - x) = z + y - x.
165 #x *
166 [ #y * // #z >yminus_inj >yplus_inj >yplus_inj
167   /4 width=1 by yle_inv_inj, plus_minus, eq_f/
168 | >yminus_Y_inj //
169 ]
170 qed-.
171
172 lemma yplus_minus_assoc_comm_inj: ∀x:nat. ∀y,z:ynat. x ≤ y → z - (y - x) = z + x - y.
173 #x *
174 [ #y *
175   [ #z >yminus_inj >yminus_inj >yplus_inj >yminus_inj
176     /4 width=1 by yle_inv_inj, minus_le_minus_minus_comm, eq_f/
177   | >yminus_inj >yminus_Y_inj //
178   ]
179 | >yminus_Y_inj //
180 ]
181 qed-.
182
183 lemma yplus_minus_comm_inj: ∀y:nat. ∀x,z:ynat. y ≤ x → x + z - y = x - y + z.
184 #y * // #x * //
185 #z #Hxy >yplus_inj >yminus_inj <plus_minus
186 /2 width=1 by yle_inv_inj/
187 qed-.
188
189 lemma ylt_plus1_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y < z → x < z - y.
190 #x #z #y #H lapply (monotonic_ylt_minus_dx … H y ?) -H //
191 qed-.
192
193 lemma ylt_plus1_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x < z → x < z - y.
194 /2 width=1 by ylt_plus1_to_minus_inj2/ qed-.
195
196 lemma ylt_plus2_to_minus_inj2: ∀x,y:ynat. ∀z:nat. z ≤ x → x < y + z → x - z < y.
197 /2 width=1 by monotonic_ylt_minus_dx/ qed-.
198
199 lemma ylt_plus2_to_minus_inj1: ∀x,y:ynat. ∀z:nat. z ≤ x → x < z + y → x - z < y.
200 /2 width=1 by ylt_plus2_to_minus_inj2/ qed-.
201
202 lemma yplus_inv_minus: ∀x1,y1. y1 ≤ yinj x1 →
203                        ∀x2,y2. yinj x1 + x2 = yinj y2 + y1 →
204                        yinj x1 - y1 = yinj y2 - x2 ∧ x2 ≤ yinj y2.
205 #x1 #y1 #Hyx1 #x2 #y2 #H0
206 lapply (yle_fwd_plus_ge_inj … x2 y2 Hyx1 ?) // #Hxy2
207 elim (yle_inv_inj2 … Hyx1) -Hyx1 #m #Hyx1 #H destruct
208 elim (yle_inv_inj2 … Hxy2) #n #H1 #H destruct
209 >yplus_inj in H0; >yplus_inj >yminus_inj >yminus_inj #H0
210 @conj // lapply (yinj_inj … H0) -H0 /3 width=1 by arith_b1, eq_f/
211 qed-.
212
213 (* Inversion lemmas on minus ************************************************)
214
215 lemma yle_inv_plus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y ∧ y ≤ z.
216 /3 width=3 by yle_plus1_to_minus_inj2, yle_trans, conj/ qed-.
217
218 lemma yle_inv_plus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y ∧ y ≤ z.
219 /2 width=1 by yle_inv_plus_inj2/ qed-.
220
221 lemma yle_inv_plus_inj_dx: ∀x,y:ynat. ∀z:nat. x + y ≤ z →
222                            ∃∃m,n. x = yinj m & y = yinj n & x ≤ z - y & y ≤ z.
223 #x #y #z #Hz elim (yle_inv_inj2 … Hz)
224 #z0 #_ #H elim (yplus_inv_inj … H) -H
225 #m #n #H1 #H2 #H3 destruct
226 elim (yle_inv_plus_inj2 … Hz) -Hz /2 width=2 by ex4_2_intro/
227 qed-.