9548
|
1 |
(* Title: ZF/ArithSimp.ML
|
|
2 |
ID: $Id$
|
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory
|
|
4 |
Copyright 2000 University of Cambridge
|
|
5 |
|
|
6 |
*)
|
|
7 |
|
13328
|
8 |
header{*Arithmetic with simplification*}
|
|
9 |
|
9548
|
10 |
theory ArithSimp = Arith
|
|
11 |
files "arith_data.ML":
|
13259
|
12 |
|
13356
|
13 |
subsection{*Difference*}
|
13259
|
14 |
|
|
15 |
lemma diff_self_eq_0: "m #- m = 0"
|
|
16 |
apply (subgoal_tac "natify (m) #- natify (m) = 0")
|
|
17 |
apply (rule_tac [2] natify_in_nat [THEN nat_induct], auto)
|
|
18 |
done
|
|
19 |
|
|
20 |
(**Addition is the inverse of subtraction**)
|
|
21 |
|
|
22 |
(*We need m:nat even if we replace the RHS by natify(m), for consider e.g.
|
|
23 |
n=2, m=omega; then n + (m-n) = 2 + (0-2) = 2 ~= 0 = natify(m).*)
|
|
24 |
lemma add_diff_inverse: "[| n le m; m:nat |] ==> n #+ (m#-n) = m"
|
|
25 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
26 |
apply (erule rev_mp)
|
|
27 |
apply (rule_tac m = "m" and n = "n" in diff_induct, auto)
|
|
28 |
done
|
|
29 |
|
|
30 |
lemma add_diff_inverse2: "[| n le m; m:nat |] ==> (m#-n) #+ n = m"
|
|
31 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
32 |
apply (simp (no_asm_simp) add: add_commute add_diff_inverse)
|
|
33 |
done
|
|
34 |
|
|
35 |
(*Proof is IDENTICAL to that of add_diff_inverse*)
|
|
36 |
lemma diff_succ: "[| n le m; m:nat |] ==> succ(m) #- n = succ(m#-n)"
|
|
37 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
38 |
apply (erule rev_mp)
|
|
39 |
apply (rule_tac m = "m" and n = "n" in diff_induct)
|
|
40 |
apply (simp_all (no_asm_simp))
|
|
41 |
done
|
|
42 |
|
|
43 |
lemma zero_less_diff [simp]:
|
|
44 |
"[| m: nat; n: nat |] ==> 0 < (n #- m) <-> m<n"
|
|
45 |
apply (rule_tac m = "m" and n = "n" in diff_induct)
|
|
46 |
apply (simp_all (no_asm_simp))
|
|
47 |
done
|
|
48 |
|
|
49 |
|
|
50 |
(** Difference distributes over multiplication **)
|
|
51 |
|
|
52 |
lemma diff_mult_distrib: "(m #- n) #* k = (m #* k) #- (n #* k)"
|
|
53 |
apply (subgoal_tac " (natify (m) #- natify (n)) #* natify (k) = (natify (m) #* natify (k)) #- (natify (n) #* natify (k))")
|
|
54 |
apply (rule_tac [2] m = "natify (m) " and n = "natify (n) " in diff_induct)
|
|
55 |
apply (simp_all add: diff_cancel)
|
|
56 |
done
|
|
57 |
|
|
58 |
lemma diff_mult_distrib2: "k #* (m #- n) = (k #* m) #- (k #* n)"
|
|
59 |
apply (simp (no_asm) add: mult_commute [of k] diff_mult_distrib)
|
|
60 |
done
|
|
61 |
|
|
62 |
|
13356
|
63 |
subsection{*Remainder*}
|
13259
|
64 |
|
|
65 |
(*We need m:nat even with natify*)
|
|
66 |
lemma div_termination: "[| 0<n; n le m; m:nat |] ==> m #- n < m"
|
|
67 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
68 |
apply (erule rev_mp)
|
|
69 |
apply (erule rev_mp)
|
|
70 |
apply (rule_tac m = "m" and n = "n" in diff_induct)
|
|
71 |
apply (simp_all (no_asm_simp) add: diff_le_self)
|
|
72 |
done
|
|
73 |
|
|
74 |
(*for mod and div*)
|
|
75 |
lemmas div_rls =
|
|
76 |
nat_typechecks Ord_transrec_type apply_funtype
|
|
77 |
div_termination [THEN ltD]
|
|
78 |
nat_into_Ord not_lt_iff_le [THEN iffD1]
|
|
79 |
|
|
80 |
lemma raw_mod_type: "[| m:nat; n:nat |] ==> raw_mod (m, n) : nat"
|
|
81 |
apply (unfold raw_mod_def)
|
|
82 |
apply (rule Ord_transrec_type)
|
|
83 |
apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff])
|
|
84 |
apply (blast intro: div_rls)
|
|
85 |
done
|
|
86 |
|
|
87 |
lemma mod_type [TC,iff]: "m mod n : nat"
|
|
88 |
apply (unfold mod_def)
|
|
89 |
apply (simp (no_asm) add: mod_def raw_mod_type)
|
|
90 |
done
|
|
91 |
|
|
92 |
|
|
93 |
(** Aribtrary definitions for division by zero. Useful to simplify
|
|
94 |
certain equations **)
|
|
95 |
|
|
96 |
lemma DIVISION_BY_ZERO_DIV: "a div 0 = 0"
|
|
97 |
apply (unfold div_def)
|
|
98 |
apply (rule raw_div_def [THEN def_transrec, THEN trans])
|
|
99 |
apply (simp (no_asm_simp))
|
|
100 |
done (*NOT for adding to default simpset*)
|
|
101 |
|
|
102 |
lemma DIVISION_BY_ZERO_MOD: "a mod 0 = natify(a)"
|
|
103 |
apply (unfold mod_def)
|
|
104 |
apply (rule raw_mod_def [THEN def_transrec, THEN trans])
|
|
105 |
apply (simp (no_asm_simp))
|
|
106 |
done (*NOT for adding to default simpset*)
|
|
107 |
|
|
108 |
lemma raw_mod_less: "m<n ==> raw_mod (m,n) = m"
|
|
109 |
apply (rule raw_mod_def [THEN def_transrec, THEN trans])
|
|
110 |
apply (simp (no_asm_simp) add: div_termination [THEN ltD])
|
|
111 |
done
|
|
112 |
|
|
113 |
lemma mod_less [simp]: "[| m<n; n : nat |] ==> m mod n = m"
|
|
114 |
apply (frule lt_nat_in_nat, assumption)
|
|
115 |
apply (simp (no_asm_simp) add: mod_def raw_mod_less)
|
|
116 |
done
|
|
117 |
|
|
118 |
lemma raw_mod_geq:
|
|
119 |
"[| 0<n; n le m; m:nat |] ==> raw_mod (m, n) = raw_mod (m#-n, n)"
|
|
120 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
121 |
apply (rule raw_mod_def [THEN def_transrec, THEN trans])
|
13611
|
122 |
apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2], blast)
|
13259
|
123 |
done
|
|
124 |
|
|
125 |
|
|
126 |
lemma mod_geq: "[| n le m; m:nat |] ==> m mod n = (m#-n) mod n"
|
|
127 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
128 |
apply (case_tac "n=0")
|
|
129 |
apply (simp add: DIVISION_BY_ZERO_MOD)
|
|
130 |
apply (simp add: mod_def raw_mod_geq nat_into_Ord [THEN Ord_0_lt_iff])
|
|
131 |
done
|
|
132 |
|
|
133 |
|
13356
|
134 |
subsection{*Division*}
|
13259
|
135 |
|
|
136 |
lemma raw_div_type: "[| m:nat; n:nat |] ==> raw_div (m, n) : nat"
|
|
137 |
apply (unfold raw_div_def)
|
|
138 |
apply (rule Ord_transrec_type)
|
|
139 |
apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff])
|
|
140 |
apply (blast intro: div_rls)
|
|
141 |
done
|
|
142 |
|
|
143 |
lemma div_type [TC,iff]: "m div n : nat"
|
|
144 |
apply (unfold div_def)
|
|
145 |
apply (simp (no_asm) add: div_def raw_div_type)
|
|
146 |
done
|
|
147 |
|
|
148 |
lemma raw_div_less: "m<n ==> raw_div (m,n) = 0"
|
|
149 |
apply (rule raw_div_def [THEN def_transrec, THEN trans])
|
|
150 |
apply (simp (no_asm_simp) add: div_termination [THEN ltD])
|
|
151 |
done
|
|
152 |
|
|
153 |
lemma div_less [simp]: "[| m<n; n : nat |] ==> m div n = 0"
|
|
154 |
apply (frule lt_nat_in_nat, assumption)
|
|
155 |
apply (simp (no_asm_simp) add: div_def raw_div_less)
|
|
156 |
done
|
|
157 |
|
|
158 |
lemma raw_div_geq: "[| 0<n; n le m; m:nat |] ==> raw_div(m,n) = succ(raw_div(m#-n, n))"
|
|
159 |
apply (subgoal_tac "n ~= 0")
|
|
160 |
prefer 2 apply blast
|
|
161 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
162 |
apply (rule raw_div_def [THEN def_transrec, THEN trans])
|
13611
|
163 |
apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2] )
|
13259
|
164 |
done
|
|
165 |
|
|
166 |
lemma div_geq [simp]:
|
|
167 |
"[| 0<n; n le m; m:nat |] ==> m div n = succ ((m#-n) div n)"
|
|
168 |
apply (frule lt_nat_in_nat, erule nat_succI)
|
|
169 |
apply (simp (no_asm_simp) add: div_def raw_div_geq)
|
|
170 |
done
|
|
171 |
|
|
172 |
declare div_less [simp] div_geq [simp]
|
|
173 |
|
|
174 |
|
|
175 |
(*A key result*)
|
|
176 |
lemma mod_div_lemma: "[| m: nat; n: nat |] ==> (m div n)#*n #+ m mod n = m"
|
|
177 |
apply (case_tac "n=0")
|
|
178 |
apply (simp add: DIVISION_BY_ZERO_MOD)
|
|
179 |
apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff])
|
|
180 |
apply (erule complete_induct)
|
|
181 |
apply (case_tac "x<n")
|
|
182 |
txt{*case x<n*}
|
|
183 |
apply (simp (no_asm_simp))
|
|
184 |
txt{*case n le x*}
|
|
185 |
apply (simp add: not_lt_iff_le add_assoc mod_geq div_termination [THEN ltD] add_diff_inverse)
|
|
186 |
done
|
|
187 |
|
|
188 |
lemma mod_div_equality_natify: "(m div n)#*n #+ m mod n = natify(m)"
|
|
189 |
apply (subgoal_tac " (natify (m) div natify (n))#*natify (n) #+ natify (m) mod natify (n) = natify (m) ")
|
|
190 |
apply force
|
|
191 |
apply (subst mod_div_lemma, auto)
|
|
192 |
done
|
|
193 |
|
|
194 |
lemma mod_div_equality: "m: nat ==> (m div n)#*n #+ m mod n = m"
|
|
195 |
apply (simp (no_asm_simp) add: mod_div_equality_natify)
|
|
196 |
done
|
|
197 |
|
|
198 |
|
13356
|
199 |
subsection{*Further Facts about Remainder*}
|
|
200 |
|
|
201 |
text{*(mainly for mutilated chess board)*}
|
13259
|
202 |
|
|
203 |
lemma mod_succ_lemma:
|
|
204 |
"[| 0<n; m:nat; n:nat |]
|
|
205 |
==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))"
|
|
206 |
apply (erule complete_induct)
|
|
207 |
apply (case_tac "succ (x) <n")
|
|
208 |
txt{* case succ(x) < n *}
|
|
209 |
apply (simp (no_asm_simp) add: nat_le_refl [THEN lt_trans] succ_neq_self)
|
|
210 |
apply (simp add: ltD [THEN mem_imp_not_eq])
|
|
211 |
txt{* case n le succ(x) *}
|
|
212 |
apply (simp add: mod_geq not_lt_iff_le)
|
|
213 |
apply (erule leE)
|
|
214 |
apply (simp (no_asm_simp) add: mod_geq div_termination [THEN ltD] diff_succ)
|
|
215 |
txt{*equality case*}
|
|
216 |
apply (simp add: diff_self_eq_0)
|
|
217 |
done
|
|
218 |
|
|
219 |
lemma mod_succ:
|
|
220 |
"n:nat ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))"
|
|
221 |
apply (case_tac "n=0")
|
|
222 |
apply (simp (no_asm_simp) add: natify_succ DIVISION_BY_ZERO_MOD)
|
|
223 |
apply (subgoal_tac "natify (succ (m)) mod n = (if succ (natify (m) mod n) = n then 0 else succ (natify (m) mod n))")
|
|
224 |
prefer 2
|
|
225 |
apply (subst natify_succ)
|
|
226 |
apply (rule mod_succ_lemma)
|
|
227 |
apply (auto simp del: natify_succ simp add: nat_into_Ord [THEN Ord_0_lt_iff])
|
|
228 |
done
|
|
229 |
|
|
230 |
lemma mod_less_divisor: "[| 0<n; n:nat |] ==> m mod n < n"
|
|
231 |
apply (subgoal_tac "natify (m) mod n < n")
|
|
232 |
apply (rule_tac [2] i = "natify (m) " in complete_induct)
|
|
233 |
apply (case_tac [3] "x<n", auto)
|
|
234 |
txt{* case n le x*}
|
|
235 |
apply (simp add: mod_geq not_lt_iff_le div_termination [THEN ltD])
|
|
236 |
done
|
|
237 |
|
|
238 |
lemma mod_1_eq [simp]: "m mod 1 = 0"
|
|
239 |
by (cut_tac n = "1" in mod_less_divisor, auto)
|
|
240 |
|
|
241 |
lemma mod2_cases: "b<2 ==> k mod 2 = b | k mod 2 = (if b=1 then 0 else 1)"
|
|
242 |
apply (subgoal_tac "k mod 2: 2")
|
|
243 |
prefer 2 apply (simp add: mod_less_divisor [THEN ltD])
|
|
244 |
apply (drule ltD, auto)
|
|
245 |
done
|
|
246 |
|
|
247 |
lemma mod2_succ_succ [simp]: "succ(succ(m)) mod 2 = m mod 2"
|
|
248 |
apply (subgoal_tac "m mod 2: 2")
|
|
249 |
prefer 2 apply (simp add: mod_less_divisor [THEN ltD])
|
|
250 |
apply (auto simp add: mod_succ)
|
|
251 |
done
|
|
252 |
|
|
253 |
lemma mod2_add_more [simp]: "(m#+m#+n) mod 2 = n mod 2"
|
|
254 |
apply (subgoal_tac " (natify (m) #+natify (m) #+n) mod 2 = n mod 2")
|
|
255 |
apply (rule_tac [2] n = "natify (m) " in nat_induct)
|
|
256 |
apply auto
|
|
257 |
done
|
|
258 |
|
|
259 |
lemma mod2_add_self [simp]: "(m#+m) mod 2 = 0"
|
|
260 |
by (cut_tac n = "0" in mod2_add_more, auto)
|
|
261 |
|
|
262 |
|
13356
|
263 |
subsection{*Additional theorems about @{text "\<le>"}*}
|
13259
|
264 |
|
|
265 |
lemma add_le_self: "m:nat ==> m le (m #+ n)"
|
|
266 |
apply (simp (no_asm_simp))
|
|
267 |
done
|
|
268 |
|
|
269 |
lemma add_le_self2: "m:nat ==> m le (n #+ m)"
|
|
270 |
apply (simp (no_asm_simp))
|
|
271 |
done
|
|
272 |
|
|
273 |
(*** Monotonicity of Multiplication ***)
|
|
274 |
|
|
275 |
lemma mult_le_mono1: "[| i le j; j:nat |] ==> (i#*k) le (j#*k)"
|
|
276 |
apply (subgoal_tac "natify (i) #*natify (k) le j#*natify (k) ")
|
|
277 |
apply (frule_tac [2] lt_nat_in_nat)
|
|
278 |
apply (rule_tac [3] n = "natify (k) " in nat_induct)
|
|
279 |
apply (simp_all add: add_le_mono)
|
|
280 |
done
|
|
281 |
|
|
282 |
(* le monotonicity, BOTH arguments*)
|
|
283 |
lemma mult_le_mono: "[| i le j; k le l; j:nat; l:nat |] ==> i#*k le j#*l"
|
|
284 |
apply (rule mult_le_mono1 [THEN le_trans], assumption+)
|
|
285 |
apply (subst mult_commute, subst mult_commute, rule mult_le_mono1, assumption+)
|
|
286 |
done
|
|
287 |
|
|
288 |
(*strict, in 1st argument; proof is by induction on k>0.
|
|
289 |
I can't see how to relax the typing conditions.*)
|
|
290 |
lemma mult_lt_mono2: "[| i<j; 0<k; j:nat; k:nat |] ==> k#*i < k#*j"
|
|
291 |
apply (erule zero_lt_natE)
|
|
292 |
apply (frule_tac [2] lt_nat_in_nat)
|
|
293 |
apply (simp_all (no_asm_simp))
|
|
294 |
apply (induct_tac "x")
|
|
295 |
apply (simp_all (no_asm_simp) add: add_lt_mono)
|
|
296 |
done
|
|
297 |
|
|
298 |
lemma mult_lt_mono1: "[| i<j; 0<k; j:nat; k:nat |] ==> i#*k < j#*k"
|
|
299 |
apply (simp (no_asm_simp) add: mult_lt_mono2 mult_commute [of _ k])
|
|
300 |
done
|
|
301 |
|
|
302 |
lemma add_eq_0_iff [iff]: "m#+n = 0 <-> natify(m)=0 & natify(n)=0"
|
|
303 |
apply (subgoal_tac "natify (m) #+ natify (n) = 0 <-> natify (m) =0 & natify (n) =0")
|
|
304 |
apply (rule_tac [2] n = "natify (m) " in natE)
|
|
305 |
apply (rule_tac [4] n = "natify (n) " in natE)
|
|
306 |
apply auto
|
|
307 |
done
|
|
308 |
|
|
309 |
lemma zero_lt_mult_iff [iff]: "0 < m#*n <-> 0 < natify(m) & 0 < natify(n)"
|
|
310 |
apply (subgoal_tac "0 < natify (m) #*natify (n) <-> 0 < natify (m) & 0 < natify (n) ")
|
|
311 |
apply (rule_tac [2] n = "natify (m) " in natE)
|
|
312 |
apply (rule_tac [4] n = "natify (n) " in natE)
|
|
313 |
apply (rule_tac [3] n = "natify (n) " in natE)
|
|
314 |
apply auto
|
|
315 |
done
|
|
316 |
|
|
317 |
lemma mult_eq_1_iff [iff]: "m#*n = 1 <-> natify(m)=1 & natify(n)=1"
|
|
318 |
apply (subgoal_tac "natify (m) #* natify (n) = 1 <-> natify (m) =1 & natify (n) =1")
|
|
319 |
apply (rule_tac [2] n = "natify (m) " in natE)
|
|
320 |
apply (rule_tac [4] n = "natify (n) " in natE)
|
|
321 |
apply auto
|
|
322 |
done
|
|
323 |
|
|
324 |
|
|
325 |
lemma mult_is_zero: "[|m: nat; n: nat|] ==> (m #* n = 0) <-> (m = 0 | n = 0)"
|
|
326 |
apply auto
|
|
327 |
apply (erule natE)
|
|
328 |
apply (erule_tac [2] natE, auto)
|
|
329 |
done
|
|
330 |
|
|
331 |
lemma mult_is_zero_natify [iff]:
|
|
332 |
"(m #* n = 0) <-> (natify(m) = 0 | natify(n) = 0)"
|
|
333 |
apply (cut_tac m = "natify (m) " and n = "natify (n) " in mult_is_zero)
|
|
334 |
apply auto
|
|
335 |
done
|
|
336 |
|
|
337 |
|
13356
|
338 |
subsection{*Cancellation Laws for Common Factors in Comparisons*}
|
13259
|
339 |
|
|
340 |
lemma mult_less_cancel_lemma:
|
|
341 |
"[| k: nat; m: nat; n: nat |] ==> (m#*k < n#*k) <-> (0<k & m<n)"
|
|
342 |
apply (safe intro!: mult_lt_mono1)
|
|
343 |
apply (erule natE, auto)
|
|
344 |
apply (rule not_le_iff_lt [THEN iffD1])
|
|
345 |
apply (drule_tac [3] not_le_iff_lt [THEN [2] rev_iffD2])
|
|
346 |
prefer 5 apply (blast intro: mult_le_mono1, auto)
|
|
347 |
done
|
|
348 |
|
|
349 |
lemma mult_less_cancel2 [simp]:
|
|
350 |
"(m#*k < n#*k) <-> (0 < natify(k) & natify(m) < natify(n))"
|
|
351 |
apply (rule iff_trans)
|
|
352 |
apply (rule_tac [2] mult_less_cancel_lemma, auto)
|
|
353 |
done
|
|
354 |
|
|
355 |
lemma mult_less_cancel1 [simp]:
|
|
356 |
"(k#*m < k#*n) <-> (0 < natify(k) & natify(m) < natify(n))"
|
|
357 |
apply (simp (no_asm) add: mult_less_cancel2 mult_commute [of k])
|
|
358 |
done
|
|
359 |
|
|
360 |
lemma mult_le_cancel2 [simp]: "(m#*k le n#*k) <-> (0 < natify(k) --> natify(m) le natify(n))"
|
|
361 |
apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym])
|
|
362 |
apply auto
|
|
363 |
done
|
|
364 |
|
|
365 |
lemma mult_le_cancel1 [simp]: "(k#*m le k#*n) <-> (0 < natify(k) --> natify(m) le natify(n))"
|
|
366 |
apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym])
|
|
367 |
apply auto
|
|
368 |
done
|
|
369 |
|
|
370 |
lemma mult_le_cancel_le1: "k : nat ==> k #* m le k \<longleftrightarrow> (0 < k \<longrightarrow> natify(m) le 1)"
|
|
371 |
by (cut_tac k = "k" and m = "m" and n = "1" in mult_le_cancel1, auto)
|
|
372 |
|
|
373 |
lemma Ord_eq_iff_le: "[| Ord(m); Ord(n) |] ==> m=n <-> (m le n & n le m)"
|
|
374 |
by (blast intro: le_anti_sym)
|
|
375 |
|
|
376 |
lemma mult_cancel2_lemma:
|
|
377 |
"[| k: nat; m: nat; n: nat |] ==> (m#*k = n#*k) <-> (m=n | k=0)"
|
|
378 |
apply (simp (no_asm_simp) add: Ord_eq_iff_le [of "m#*k"] Ord_eq_iff_le [of m])
|
|
379 |
apply (auto simp add: Ord_0_lt_iff)
|
|
380 |
done
|
|
381 |
|
|
382 |
lemma mult_cancel2 [simp]:
|
|
383 |
"(m#*k = n#*k) <-> (natify(m) = natify(n) | natify(k) = 0)"
|
|
384 |
apply (rule iff_trans)
|
|
385 |
apply (rule_tac [2] mult_cancel2_lemma, auto)
|
|
386 |
done
|
|
387 |
|
|
388 |
lemma mult_cancel1 [simp]:
|
|
389 |
"(k#*m = k#*n) <-> (natify(m) = natify(n) | natify(k) = 0)"
|
|
390 |
apply (simp (no_asm) add: mult_cancel2 mult_commute [of k])
|
|
391 |
done
|
|
392 |
|
|
393 |
|
|
394 |
(** Cancellation law for division **)
|
|
395 |
|
|
396 |
lemma div_cancel_raw:
|
|
397 |
"[| 0<n; 0<k; k:nat; m:nat; n:nat |] ==> (k#*m) div (k#*n) = m div n"
|
|
398 |
apply (erule_tac i = "m" in complete_induct)
|
|
399 |
apply (case_tac "x<n")
|
|
400 |
apply (simp add: div_less zero_lt_mult_iff mult_lt_mono2)
|
|
401 |
apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono]
|
|
402 |
div_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD])
|
|
403 |
done
|
|
404 |
|
|
405 |
lemma div_cancel:
|
|
406 |
"[| 0 < natify(n); 0 < natify(k) |] ==> (k#*m) div (k#*n) = m div n"
|
|
407 |
apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)"
|
|
408 |
in div_cancel_raw)
|
|
409 |
apply auto
|
|
410 |
done
|
|
411 |
|
|
412 |
|
13356
|
413 |
subsection{*More Lemmas about Remainder*}
|
13259
|
414 |
|
|
415 |
lemma mult_mod_distrib_raw:
|
|
416 |
"[| k:nat; m:nat; n:nat |] ==> (k#*m) mod (k#*n) = k #* (m mod n)"
|
|
417 |
apply (case_tac "k=0")
|
|
418 |
apply (simp add: DIVISION_BY_ZERO_MOD)
|
|
419 |
apply (case_tac "n=0")
|
|
420 |
apply (simp add: DIVISION_BY_ZERO_MOD)
|
|
421 |
apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff])
|
|
422 |
apply (erule_tac i = "m" in complete_induct)
|
|
423 |
apply (case_tac "x<n")
|
|
424 |
apply (simp (no_asm_simp) add: mod_less zero_lt_mult_iff mult_lt_mono2)
|
|
425 |
apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono]
|
|
426 |
mod_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD])
|
|
427 |
done
|
|
428 |
|
|
429 |
lemma mod_mult_distrib2: "k #* (m mod n) = (k#*m) mod (k#*n)"
|
|
430 |
apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)"
|
|
431 |
in mult_mod_distrib_raw)
|
|
432 |
apply auto
|
|
433 |
done
|
|
434 |
|
|
435 |
lemma mult_mod_distrib: "(m mod n) #* k = (m#*k) mod (n#*k)"
|
|
436 |
apply (simp (no_asm) add: mult_commute mod_mult_distrib2)
|
|
437 |
done
|
|
438 |
|
|
439 |
lemma mod_add_self2_raw: "n \<in> nat ==> (m #+ n) mod n = m mod n"
|
|
440 |
apply (subgoal_tac " (n #+ m) mod n = (n #+ m #- n) mod n")
|
|
441 |
apply (simp add: add_commute)
|
|
442 |
apply (subst mod_geq [symmetric], auto)
|
|
443 |
done
|
|
444 |
|
|
445 |
lemma mod_add_self2 [simp]: "(m #+ n) mod n = m mod n"
|
|
446 |
apply (cut_tac n = "natify (n) " in mod_add_self2_raw)
|
|
447 |
apply auto
|
|
448 |
done
|
|
449 |
|
|
450 |
lemma mod_add_self1 [simp]: "(n#+m) mod n = m mod n"
|
|
451 |
apply (simp (no_asm_simp) add: add_commute mod_add_self2)
|
|
452 |
done
|
|
453 |
|
|
454 |
lemma mod_mult_self1_raw: "k \<in> nat ==> (m #+ k#*n) mod n = m mod n"
|
|
455 |
apply (erule nat_induct)
|
|
456 |
apply (simp_all (no_asm_simp) add: add_left_commute [of _ n])
|
|
457 |
done
|
|
458 |
|
|
459 |
lemma mod_mult_self1 [simp]: "(m #+ k#*n) mod n = m mod n"
|
|
460 |
apply (cut_tac k = "natify (k) " in mod_mult_self1_raw)
|
|
461 |
apply auto
|
|
462 |
done
|
|
463 |
|
|
464 |
lemma mod_mult_self2 [simp]: "(m #+ n#*k) mod n = m mod n"
|
|
465 |
apply (simp (no_asm) add: mult_commute mod_mult_self1)
|
|
466 |
done
|
|
467 |
|
|
468 |
(*Lemma for gcd*)
|
|
469 |
lemma mult_eq_self_implies_10: "m = m#*n ==> natify(n)=1 | m=0"
|
|
470 |
apply (subgoal_tac "m: nat")
|
|
471 |
prefer 2
|
|
472 |
apply (erule ssubst)
|
|
473 |
apply simp
|
|
474 |
apply (rule disjCI)
|
|
475 |
apply (drule sym)
|
|
476 |
apply (rule Ord_linear_lt [of "natify(n)" 1])
|
|
477 |
apply simp_all
|
|
478 |
apply (subgoal_tac "m #* n = 0", simp)
|
|
479 |
apply (subst mult_natify2 [symmetric])
|
|
480 |
apply (simp del: mult_natify2)
|
|
481 |
apply (drule nat_into_Ord [THEN Ord_0_lt, THEN [2] mult_lt_mono2], auto)
|
|
482 |
done
|
|
483 |
|
|
484 |
lemma less_imp_succ_add [rule_format]:
|
|
485 |
"[| m<n; n: nat |] ==> EX k: nat. n = succ(m#+k)"
|
|
486 |
apply (frule lt_nat_in_nat, assumption)
|
|
487 |
apply (erule rev_mp)
|
|
488 |
apply (induct_tac "n")
|
|
489 |
apply (simp_all (no_asm) add: le_iff)
|
|
490 |
apply (blast elim!: leE intro!: add_0_right [symmetric] add_succ_right [symmetric])
|
|
491 |
done
|
|
492 |
|
|
493 |
lemma less_iff_succ_add:
|
|
494 |
"[| m: nat; n: nat |] ==> (m<n) <-> (EX k: nat. n = succ(m#+k))"
|
|
495 |
by (auto intro: less_imp_succ_add)
|
|
496 |
|
13356
|
497 |
|
|
498 |
subsubsection{*More Lemmas About Difference*}
|
13259
|
499 |
|
|
500 |
lemma diff_is_0_lemma:
|
|
501 |
"[| m: nat; n: nat |] ==> m #- n = 0 <-> m le n"
|
|
502 |
apply (rule_tac m = "m" and n = "n" in diff_induct, simp_all)
|
|
503 |
done
|
|
504 |
|
|
505 |
lemma diff_is_0_iff: "m #- n = 0 <-> natify(m) le natify(n)"
|
|
506 |
by (simp add: diff_is_0_lemma [symmetric])
|
|
507 |
|
|
508 |
lemma nat_lt_imp_diff_eq_0:
|
|
509 |
"[| a:nat; b:nat; a<b |] ==> a #- b = 0"
|
|
510 |
by (simp add: diff_is_0_iff le_iff)
|
|
511 |
|
|
512 |
lemma nat_diff_split:
|
|
513 |
"[| a:nat; b:nat |] ==>
|
|
514 |
(P(a #- b)) <-> ((a < b -->P(0)) & (ALL d:nat. a = b #+ d --> P(d)))"
|
|
515 |
apply (case_tac "a < b")
|
|
516 |
apply (force simp add: nat_lt_imp_diff_eq_0)
|
|
517 |
apply (rule iffI, simp_all)
|
|
518 |
apply clarify
|
|
519 |
apply (rotate_tac -1)
|
|
520 |
apply simp
|
|
521 |
apply (drule_tac x="a#-b" in bspec)
|
|
522 |
apply (simp_all add: Ordinal.not_lt_iff_le add_diff_inverse)
|
|
523 |
done
|
|
524 |
|
|
525 |
ML
|
|
526 |
{*
|
|
527 |
val diff_self_eq_0 = thm "diff_self_eq_0";
|
|
528 |
val add_diff_inverse = thm "add_diff_inverse";
|
|
529 |
val add_diff_inverse2 = thm "add_diff_inverse2";
|
|
530 |
val diff_succ = thm "diff_succ";
|
|
531 |
val zero_less_diff = thm "zero_less_diff";
|
|
532 |
val diff_mult_distrib = thm "diff_mult_distrib";
|
|
533 |
val diff_mult_distrib2 = thm "diff_mult_distrib2";
|
|
534 |
val div_termination = thm "div_termination";
|
|
535 |
val raw_mod_type = thm "raw_mod_type";
|
|
536 |
val mod_type = thm "mod_type";
|
|
537 |
val DIVISION_BY_ZERO_DIV = thm "DIVISION_BY_ZERO_DIV";
|
|
538 |
val DIVISION_BY_ZERO_MOD = thm "DIVISION_BY_ZERO_MOD";
|
|
539 |
val raw_mod_less = thm "raw_mod_less";
|
|
540 |
val mod_less = thm "mod_less";
|
|
541 |
val raw_mod_geq = thm "raw_mod_geq";
|
|
542 |
val mod_geq = thm "mod_geq";
|
|
543 |
val raw_div_type = thm "raw_div_type";
|
|
544 |
val div_type = thm "div_type";
|
|
545 |
val raw_div_less = thm "raw_div_less";
|
|
546 |
val div_less = thm "div_less";
|
|
547 |
val raw_div_geq = thm "raw_div_geq";
|
|
548 |
val div_geq = thm "div_geq";
|
|
549 |
val mod_div_equality_natify = thm "mod_div_equality_natify";
|
|
550 |
val mod_div_equality = thm "mod_div_equality";
|
|
551 |
val mod_succ = thm "mod_succ";
|
|
552 |
val mod_less_divisor = thm "mod_less_divisor";
|
|
553 |
val mod_1_eq = thm "mod_1_eq";
|
|
554 |
val mod2_cases = thm "mod2_cases";
|
|
555 |
val mod2_succ_succ = thm "mod2_succ_succ";
|
|
556 |
val mod2_add_more = thm "mod2_add_more";
|
|
557 |
val mod2_add_self = thm "mod2_add_self";
|
|
558 |
val add_le_self = thm "add_le_self";
|
|
559 |
val add_le_self2 = thm "add_le_self2";
|
|
560 |
val mult_le_mono1 = thm "mult_le_mono1";
|
|
561 |
val mult_le_mono = thm "mult_le_mono";
|
|
562 |
val mult_lt_mono2 = thm "mult_lt_mono2";
|
|
563 |
val mult_lt_mono1 = thm "mult_lt_mono1";
|
|
564 |
val add_eq_0_iff = thm "add_eq_0_iff";
|
|
565 |
val zero_lt_mult_iff = thm "zero_lt_mult_iff";
|
|
566 |
val mult_eq_1_iff = thm "mult_eq_1_iff";
|
|
567 |
val mult_is_zero = thm "mult_is_zero";
|
|
568 |
val mult_is_zero_natify = thm "mult_is_zero_natify";
|
|
569 |
val mult_less_cancel2 = thm "mult_less_cancel2";
|
|
570 |
val mult_less_cancel1 = thm "mult_less_cancel1";
|
|
571 |
val mult_le_cancel2 = thm "mult_le_cancel2";
|
|
572 |
val mult_le_cancel1 = thm "mult_le_cancel1";
|
|
573 |
val mult_le_cancel_le1 = thm "mult_le_cancel_le1";
|
|
574 |
val Ord_eq_iff_le = thm "Ord_eq_iff_le";
|
|
575 |
val mult_cancel2 = thm "mult_cancel2";
|
|
576 |
val mult_cancel1 = thm "mult_cancel1";
|
|
577 |
val div_cancel_raw = thm "div_cancel_raw";
|
|
578 |
val div_cancel = thm "div_cancel";
|
|
579 |
val mult_mod_distrib_raw = thm "mult_mod_distrib_raw";
|
|
580 |
val mod_mult_distrib2 = thm "mod_mult_distrib2";
|
|
581 |
val mult_mod_distrib = thm "mult_mod_distrib";
|
|
582 |
val mod_add_self2_raw = thm "mod_add_self2_raw";
|
|
583 |
val mod_add_self2 = thm "mod_add_self2";
|
|
584 |
val mod_add_self1 = thm "mod_add_self1";
|
|
585 |
val mod_mult_self1_raw = thm "mod_mult_self1_raw";
|
|
586 |
val mod_mult_self1 = thm "mod_mult_self1";
|
|
587 |
val mod_mult_self2 = thm "mod_mult_self2";
|
|
588 |
val mult_eq_self_implies_10 = thm "mult_eq_self_implies_10";
|
|
589 |
val less_imp_succ_add = thm "less_imp_succ_add";
|
|
590 |
val less_iff_succ_add = thm "less_iff_succ_add";
|
|
591 |
val diff_is_0_iff = thm "diff_is_0_iff";
|
|
592 |
val nat_lt_imp_diff_eq_0 = thm "nat_lt_imp_diff_eq_0";
|
|
593 |
val nat_diff_split = thm "nat_diff_split";
|
|
594 |
*}
|
|
595 |
|
9548
|
596 |
end
|