1.1 --- a/src/HOL/Divides.thy Mon Apr 16 16:11:03 2007 +0200
1.2 +++ b/src/HOL/Divides.thy Tue Apr 17 00:30:44 2007 +0200
1.3 @@ -34,7 +34,7 @@
1.4 instance nat :: "Divides.div"
1.5 mod_def: "m mod n == wfrec (pred_nat^+)
1.6 (%f j. if j<n | n=0 then j else f (j-n)) m"
1.7 - div_def: "m div n == wfrec (pred_nat^+)
1.8 + div_def: "m div n == wfrec (pred_nat^+)
1.9 (%f j. if j<n | n=0 then 0 else Suc (f (j-n))) m" ..
1.10
1.11 definition
1.12 @@ -42,13 +42,11 @@
1.13 dvd :: "'a::times \<Rightarrow> 'a \<Rightarrow> bool" (infixl "dvd" 50) where
1.14 dvd_def: "m dvd n \<longleftrightarrow> (\<exists>k. n = m*k)"
1.15
1.16 -consts
1.17 - quorem :: "(nat*nat) * (nat*nat) => bool"
1.18 -
1.19 -defs
1.20 +definition
1.21 + quorem :: "(nat*nat) * (nat*nat) => bool" where
1.22 (*This definition helps prove the harder properties of div and mod.
1.23 It is copied from IntDiv.thy; should it be overloaded?*)
1.24 - quorem_def: "quorem \<equiv> (%((a,b), (q,r)).
1.25 + "quorem = (%((a,b), (q,r)).
1.26 a = b*q + r &
1.27 (if 0<b then 0\<le>r & r<b else b<r & r \<le>0))"
1.28
1.29 @@ -56,161 +54,150 @@
1.30
1.31 subsection{*Initial Lemmas*}
1.32
1.33 -lemmas wf_less_trans =
1.34 +lemmas wf_less_trans =
1.35 def_wfrec [THEN trans, OF eq_reflection wf_pred_nat [THEN wf_trancl],
1.36 standard]
1.37
1.38 -lemma mod_eq: "(%m. m mod n) =
1.39 +lemma mod_eq: "(%m. m mod n) =
1.40 wfrec (pred_nat^+) (%f j. if j<n | n=0 then j else f (j-n))"
1.41 by (simp add: mod_def)
1.42
1.43 -lemma div_eq: "(%m. m div n) = wfrec (pred_nat^+)
1.44 +lemma div_eq: "(%m. m div n) = wfrec (pred_nat^+)
1.45 (%f j. if j<n | n=0 then 0 else Suc (f (j-n)))"
1.46 by (simp add: div_def)
1.47
1.48
1.49 -(** Aribtrary definitions for division by zero. Useful to simplify
1.50 +(** Aribtrary definitions for division by zero. Useful to simplify
1.51 certain equations **)
1.52
1.53 lemma DIVISION_BY_ZERO_DIV [simp]: "a div 0 = (0::nat)"
1.54 -by (rule div_eq [THEN wf_less_trans], simp)
1.55 + by (rule div_eq [THEN wf_less_trans], simp)
1.56
1.57 lemma DIVISION_BY_ZERO_MOD [simp]: "a mod 0 = (a::nat)"
1.58 -by (rule mod_eq [THEN wf_less_trans], simp)
1.59 + by (rule mod_eq [THEN wf_less_trans], simp)
1.60
1.61
1.62 subsection{*Remainder*}
1.63
1.64 lemma mod_less [simp]: "m<n ==> m mod n = (m::nat)"
1.65 -by (rule mod_eq [THEN wf_less_trans], simp)
1.66 + by (rule mod_eq [THEN wf_less_trans]) simp
1.67
1.68 lemma mod_geq: "~ m < (n::nat) ==> m mod n = (m-n) mod n"
1.69 -apply (case_tac "n=0", simp)
1.70 -apply (rule mod_eq [THEN wf_less_trans])
1.71 -apply (simp add: cut_apply less_eq)
1.72 -done
1.73 + apply (cases "n=0")
1.74 + apply simp
1.75 + apply (rule mod_eq [THEN wf_less_trans])
1.76 + apply (simp add: cut_apply less_eq)
1.77 + done
1.78
1.79 (*Avoids the ugly ~m<n above*)
1.80 lemma le_mod_geq: "(n::nat) \<le> m ==> m mod n = (m-n) mod n"
1.81 -by (simp add: mod_geq linorder_not_less)
1.82 + by (simp add: mod_geq linorder_not_less)
1.83
1.84 lemma mod_if: "m mod (n::nat) = (if m<n then m else (m-n) mod n)"
1.85 -by (simp add: mod_geq)
1.86 + by (simp add: mod_geq)
1.87
1.88 lemma mod_1 [simp]: "m mod Suc 0 = 0"
1.89 -apply (induct "m")
1.90 -apply (simp_all (no_asm_simp) add: mod_geq)
1.91 -done
1.92 + by (induct m) (simp_all add: mod_geq)
1.93
1.94 lemma mod_self [simp]: "n mod n = (0::nat)"
1.95 -apply (case_tac "n=0")
1.96 -apply (simp_all add: mod_geq)
1.97 -done
1.98 + by (cases "n = 0") (simp_all add: mod_geq)
1.99
1.100 lemma mod_add_self2 [simp]: "(m+n) mod n = m mod (n::nat)"
1.101 -apply (subgoal_tac "(n + m) mod n = (n+m-n) mod n")
1.102 -apply (simp add: add_commute)
1.103 -apply (subst mod_geq [symmetric], simp_all)
1.104 -done
1.105 + apply (subgoal_tac "(n + m) mod n = (n+m-n) mod n")
1.106 + apply (simp add: add_commute)
1.107 + apply (subst mod_geq [symmetric], simp_all)
1.108 + done
1.109
1.110 lemma mod_add_self1 [simp]: "(n+m) mod n = m mod (n::nat)"
1.111 -by (simp add: add_commute mod_add_self2)
1.112 + by (simp add: add_commute mod_add_self2)
1.113
1.114 lemma mod_mult_self1 [simp]: "(m + k*n) mod n = m mod (n::nat)"
1.115 -apply (induct "k")
1.116 -apply (simp_all add: add_left_commute [of _ n])
1.117 -done
1.118 + by (induct k) (simp_all add: add_left_commute [of _ n])
1.119
1.120 lemma mod_mult_self2 [simp]: "(m + n*k) mod n = m mod (n::nat)"
1.121 -by (simp add: mult_commute mod_mult_self1)
1.122 + by (simp add: mult_commute mod_mult_self1)
1.123
1.124 lemma mod_mult_distrib: "(m mod n) * (k::nat) = (m*k) mod (n*k)"
1.125 -apply (case_tac "n=0", simp)
1.126 -apply (case_tac "k=0", simp)
1.127 -apply (induct "m" rule: nat_less_induct)
1.128 -apply (subst mod_if, simp)
1.129 -apply (simp add: mod_geq diff_mult_distrib)
1.130 -done
1.131 + apply (cases "n = 0", simp)
1.132 + apply (cases "k = 0", simp)
1.133 + apply (induct m rule: nat_less_induct)
1.134 + apply (subst mod_if, simp)
1.135 + apply (simp add: mod_geq diff_mult_distrib)
1.136 + done
1.137
1.138 lemma mod_mult_distrib2: "(k::nat) * (m mod n) = (k*m) mod (k*n)"
1.139 -by (simp add: mult_commute [of k] mod_mult_distrib)
1.140 + by (simp add: mult_commute [of k] mod_mult_distrib)
1.141
1.142 lemma mod_mult_self_is_0 [simp]: "(m*n) mod n = (0::nat)"
1.143 -apply (case_tac "n=0", simp)
1.144 -apply (induct "m", simp)
1.145 -apply (rename_tac "k")
1.146 -apply (cut_tac m = "k*n" and n = n in mod_add_self2)
1.147 -apply (simp add: add_commute)
1.148 -done
1.149 + apply (cases "n = 0", simp)
1.150 + apply (induct m, simp)
1.151 + apply (rename_tac k)
1.152 + apply (cut_tac m = "k * n" and n = n in mod_add_self2)
1.153 + apply (simp add: add_commute)
1.154 + done
1.155
1.156 lemma mod_mult_self1_is_0 [simp]: "(n*m) mod n = (0::nat)"
1.157 -by (simp add: mult_commute mod_mult_self_is_0)
1.158 + by (simp add: mult_commute mod_mult_self_is_0)
1.159
1.160
1.161 subsection{*Quotient*}
1.162
1.163 lemma div_less [simp]: "m<n ==> m div n = (0::nat)"
1.164 -by (rule div_eq [THEN wf_less_trans], simp)
1.165 + by (rule div_eq [THEN wf_less_trans], simp)
1.166
1.167 lemma div_geq: "[| 0<n; ~m<n |] ==> m div n = Suc((m-n) div n)"
1.168 -apply (rule div_eq [THEN wf_less_trans])
1.169 -apply (simp add: cut_apply less_eq)
1.170 -done
1.171 + apply (rule div_eq [THEN wf_less_trans])
1.172 + apply (simp add: cut_apply less_eq)
1.173 + done
1.174
1.175 (*Avoids the ugly ~m<n above*)
1.176 lemma le_div_geq: "[| 0<n; n\<le>m |] ==> m div n = Suc((m-n) div n)"
1.177 -by (simp add: div_geq linorder_not_less)
1.178 + by (simp add: div_geq linorder_not_less)
1.179
1.180 lemma div_if: "0<n ==> m div n = (if m<n then 0 else Suc((m-n) div n))"
1.181 -by (simp add: div_geq)
1.182 + by (simp add: div_geq)
1.183
1.184
1.185 (*Main Result about quotient and remainder.*)
1.186 lemma mod_div_equality: "(m div n)*n + m mod n = (m::nat)"
1.187 -apply (case_tac "n=0", simp)
1.188 -apply (induct "m" rule: nat_less_induct)
1.189 -apply (subst mod_if)
1.190 -apply (simp_all (no_asm_simp) add: add_assoc div_geq add_diff_inverse)
1.191 -done
1.192 + apply (cases "n = 0", simp)
1.193 + apply (induct m rule: nat_less_induct)
1.194 + apply (subst mod_if)
1.195 + apply (simp_all add: add_assoc div_geq add_diff_inverse)
1.196 + done
1.197
1.198 lemma mod_div_equality2: "n * (m div n) + m mod n = (m::nat)"
1.199 -apply(cut_tac m = m and n = n in mod_div_equality)
1.200 -apply(simp add: mult_commute)
1.201 -done
1.202 + apply (cut_tac m = m and n = n in mod_div_equality)
1.203 + apply (simp add: mult_commute)
1.204 + done
1.205
1.206 subsection{*Simproc for Cancelling Div and Mod*}
1.207
1.208 lemma div_mod_equality: "((m div n)*n + m mod n) + k = (m::nat) + k"
1.209 -apply(simp add: mod_div_equality)
1.210 -done
1.211 + by (simp add: mod_div_equality)
1.212
1.213 lemma div_mod_equality2: "(n*(m div n) + m mod n) + k = (m::nat) + k"
1.214 -apply(simp add: mod_div_equality2)
1.215 -done
1.216 + by (simp add: mod_div_equality2)
1.217
1.218 ML
1.219 {*
1.220 -val div_mod_equality = thm "div_mod_equality";
1.221 -val div_mod_equality2 = thm "div_mod_equality2";
1.222 -
1.223 -
1.224 structure CancelDivModData =
1.225 struct
1.226
1.227 -val div_name = "Divides.div";
1.228 -val mod_name = "Divides.mod";
1.229 +val div_name = @{const_name Divides.div};
1.230 +val mod_name = @{const_name Divides.mod};
1.231 val mk_binop = HOLogic.mk_binop;
1.232 val mk_sum = NatArithUtils.mk_sum;
1.233 val dest_sum = NatArithUtils.dest_sum;
1.234
1.235 (*logic*)
1.236
1.237 -val div_mod_eqs = map mk_meta_eq [div_mod_equality,div_mod_equality2]
1.238 +val div_mod_eqs = map mk_meta_eq [@{thm div_mod_equality}, @{thm div_mod_equality2}]
1.239
1.240 val trans = trans
1.241
1.242 val prove_eq_sums =
1.243 - let val simps = add_0 :: add_0_right :: add_ac
1.244 + let val simps = @{thm add_0} :: @{thm add_0_right} :: @{thms add_ac}
1.245 in NatArithUtils.prove_conv all_tac (NatArithUtils.simp_all_tac simps) end;
1.246
1.247 end;
1.248 @@ -226,25 +213,26 @@
1.249
1.250 (* a simple rearrangement of mod_div_equality: *)
1.251 lemma mult_div_cancel: "(n::nat) * (m div n) = m - (m mod n)"
1.252 -by (cut_tac m = m and n = n in mod_div_equality2, arith)
1.253 + by (cut_tac m = m and n = n in mod_div_equality2, arith)
1.254
1.255 lemma mod_less_divisor [simp]: "0<n ==> m mod n < (n::nat)"
1.256 -apply (induct "m" rule: nat_less_induct)
1.257 -apply (case_tac "na<n", simp)
1.258 -txt{*case @{term "n \<le> na"}*}
1.259 -apply (simp add: mod_geq)
1.260 -done
1.261 + apply (induct m rule: nat_less_induct)
1.262 + apply (rename_tac m)
1.263 + apply (case_tac "m<n", simp)
1.264 + txt{*case @{term "n \<le> m"}*}
1.265 + apply (simp add: mod_geq)
1.266 + done
1.267
1.268 lemma mod_le_divisor[simp]: "0 < n \<Longrightarrow> m mod n \<le> (n::nat)"
1.269 -apply(drule mod_less_divisor[where m = m])
1.270 -apply simp
1.271 -done
1.272 + apply (drule mod_less_divisor [where m = m])
1.273 + apply simp
1.274 + done
1.275
1.276 lemma div_mult_self_is_m [simp]: "0<n ==> (m*n) div n = (m::nat)"
1.277 -by (cut_tac m = "m*n" and n = n in mod_div_equality, auto)
1.278 + by (cut_tac m = "m*n" and n = n in mod_div_equality, auto)
1.279
1.280 lemma div_mult_self1_is_m [simp]: "0<n ==> (n*m) div n = (m::nat)"
1.281 -by (simp add: mult_commute div_mult_self_is_m)
1.282 + by (simp add: mult_commute div_mult_self_is_m)
1.283
1.284 (*mod_mult_distrib2 above is the counterpart for remainder*)
1.285
1.286 @@ -252,95 +240,93 @@
1.287 subsection{*Proving facts about Quotient and Remainder*}
1.288
1.289 lemma unique_quotient_lemma:
1.290 - "[| b*q' + r' \<le> b*q + r; x < b; r < b |]
1.291 + "[| b*q' + r' \<le> b*q + r; x < b; r < b |]
1.292 ==> q' \<le> (q::nat)"
1.293 -apply (rule leI)
1.294 -apply (subst less_iff_Suc_add)
1.295 -apply (auto simp add: add_mult_distrib2)
1.296 -done
1.297 + apply (rule leI)
1.298 + apply (subst less_iff_Suc_add)
1.299 + apply (auto simp add: add_mult_distrib2)
1.300 + done
1.301
1.302 lemma unique_quotient:
1.303 - "[| quorem ((a,b), (q,r)); quorem ((a,b), (q',r')); 0 < b |]
1.304 + "[| quorem ((a,b), (q,r)); quorem ((a,b), (q',r')); 0 < b |]
1.305 ==> q = q'"
1.306 -apply (simp add: split_ifs quorem_def)
1.307 -apply (blast intro: order_antisym
1.308 - dest: order_eq_refl [THEN unique_quotient_lemma] sym)
1.309 -done
1.310 + apply (simp add: split_ifs quorem_def)
1.311 + apply (blast intro: order_antisym
1.312 + dest: order_eq_refl [THEN unique_quotient_lemma] sym)
1.313 + done
1.314
1.315 lemma unique_remainder:
1.316 - "[| quorem ((a,b), (q,r)); quorem ((a,b), (q',r')); 0 < b |]
1.317 + "[| quorem ((a,b), (q,r)); quorem ((a,b), (q',r')); 0 < b |]
1.318 ==> r = r'"
1.319 -apply (subgoal_tac "q = q'")
1.320 -prefer 2 apply (blast intro: unique_quotient)
1.321 -apply (simp add: quorem_def)
1.322 -done
1.323 + apply (subgoal_tac "q = q'")
1.324 + prefer 2 apply (blast intro: unique_quotient)
1.325 + apply (simp add: quorem_def)
1.326 + done
1.327
1.328 lemma quorem_div_mod: "0 < b ==> quorem ((a, b), (a div b, a mod b))"
1.329 - unfolding quorem_def by simp
1.330 + unfolding quorem_def by simp
1.331
1.332 lemma quorem_div: "[| quorem((a,b),(q,r)); 0 < b |] ==> a div b = q"
1.333 -by (simp add: quorem_div_mod [THEN unique_quotient])
1.334 + by (simp add: quorem_div_mod [THEN unique_quotient])
1.335
1.336 lemma quorem_mod: "[| quorem((a,b),(q,r)); 0 < b |] ==> a mod b = r"
1.337 -by (simp add: quorem_div_mod [THEN unique_remainder])
1.338 + by (simp add: quorem_div_mod [THEN unique_remainder])
1.339
1.340 (** A dividend of zero **)
1.341
1.342 lemma div_0 [simp]: "0 div m = (0::nat)"
1.343 -by (case_tac "m=0", simp_all)
1.344 + by (cases "m = 0") simp_all
1.345
1.346 lemma mod_0 [simp]: "0 mod m = (0::nat)"
1.347 -by (case_tac "m=0", simp_all)
1.348 + by (cases "m = 0") simp_all
1.349
1.350 (** proving (a*b) div c = a * (b div c) + a * (b mod c) **)
1.351
1.352 lemma quorem_mult1_eq:
1.353 - "[| quorem((b,c),(q,r)); 0 < c |]
1.354 + "[| quorem((b,c),(q,r)); 0 < c |]
1.355 ==> quorem ((a*b, c), (a*q + a*r div c, a*r mod c))"
1.356 -apply (auto simp add: split_ifs mult_ac quorem_def add_mult_distrib2)
1.357 -done
1.358 + by (auto simp add: split_ifs mult_ac quorem_def add_mult_distrib2)
1.359
1.360 lemma div_mult1_eq: "(a*b) div c = a*(b div c) + a*(b mod c) div (c::nat)"
1.361 -apply (case_tac "c = 0", simp)
1.362 -apply (blast intro: quorem_div_mod [THEN quorem_mult1_eq, THEN quorem_div])
1.363 -done
1.364 + apply (cases "c = 0", simp)
1.365 + apply (blast intro: quorem_div_mod [THEN quorem_mult1_eq, THEN quorem_div])
1.366 + done
1.367
1.368 lemma mod_mult1_eq: "(a*b) mod c = a*(b mod c) mod (c::nat)"
1.369 -apply (case_tac "c = 0", simp)
1.370 -apply (blast intro: quorem_div_mod [THEN quorem_mult1_eq, THEN quorem_mod])
1.371 -done
1.372 + apply (cases "c = 0", simp)
1.373 + apply (blast intro: quorem_div_mod [THEN quorem_mult1_eq, THEN quorem_mod])
1.374 + done
1.375
1.376 lemma mod_mult1_eq': "(a*b) mod (c::nat) = ((a mod c) * b) mod c"
1.377 -apply (rule trans)
1.378 -apply (rule_tac s = "b*a mod c" in trans)
1.379 -apply (rule_tac [2] mod_mult1_eq)
1.380 -apply (simp_all (no_asm) add: mult_commute)
1.381 -done
1.382 + apply (rule trans)
1.383 + apply (rule_tac s = "b*a mod c" in trans)
1.384 + apply (rule_tac [2] mod_mult1_eq)
1.385 + apply (simp_all add: mult_commute)
1.386 + done
1.387
1.388 lemma mod_mult_distrib_mod: "(a*b) mod (c::nat) = ((a mod c) * (b mod c)) mod c"
1.389 -apply (rule mod_mult1_eq' [THEN trans])
1.390 -apply (rule mod_mult1_eq)
1.391 -done
1.392 + apply (rule mod_mult1_eq' [THEN trans])
1.393 + apply (rule mod_mult1_eq)
1.394 + done
1.395
1.396 (** proving (a+b) div c = a div c + b div c + ((a mod c + b mod c) div c) **)
1.397
1.398 lemma quorem_add1_eq:
1.399 - "[| quorem((a,c),(aq,ar)); quorem((b,c),(bq,br)); 0 < c |]
1.400 + "[| quorem((a,c),(aq,ar)); quorem((b,c),(bq,br)); 0 < c |]
1.401 ==> quorem ((a+b, c), (aq + bq + (ar+br) div c, (ar+br) mod c))"
1.402 -by (auto simp add: split_ifs mult_ac quorem_def add_mult_distrib2)
1.403 + by (auto simp add: split_ifs mult_ac quorem_def add_mult_distrib2)
1.404
1.405 (*NOT suitable for rewriting: the RHS has an instance of the LHS*)
1.406 lemma div_add1_eq:
1.407 "(a+b) div (c::nat) = a div c + b div c + ((a mod c + b mod c) div c)"
1.408 -apply (case_tac "c = 0", simp)
1.409 -apply (blast intro: quorem_add1_eq [THEN quorem_div] quorem_div_mod quorem_div_mod)
1.410 -done
1.411 + apply (cases "c = 0", simp)
1.412 + apply (blast intro: quorem_add1_eq [THEN quorem_div] quorem_div_mod quorem_div_mod)
1.413 + done
1.414
1.415 lemma mod_add1_eq: "(a+b) mod (c::nat) = (a mod c + b mod c) mod c"
1.416 -apply (case_tac "c = 0", simp)
1.417 -apply (blast intro: quorem_div_mod quorem_div_mod
1.418 - quorem_add1_eq [THEN quorem_mod])
1.419 -done
1.420 + apply (cases "c = 0", simp)
1.421 + apply (blast intro: quorem_div_mod quorem_div_mod quorem_add1_eq [THEN quorem_mod])
1.422 + done
1.423
1.424
1.425 subsection{*Proving @{term "a div (b*c) = (a div b) div c"}*}
1.426 @@ -348,45 +334,44 @@
1.427 (** first, a lemma to bound the remainder **)
1.428
1.429 lemma mod_lemma: "[| (0::nat) < c; r < b |] ==> b * (q mod c) + r < b * c"
1.430 -apply (cut_tac m = q and n = c in mod_less_divisor)
1.431 -apply (drule_tac [2] m = "q mod c" in less_imp_Suc_add, auto)
1.432 -apply (erule_tac P = "%x. ?lhs < ?rhs x" in ssubst)
1.433 -apply (simp add: add_mult_distrib2)
1.434 -done
1.435 + apply (cut_tac m = q and n = c in mod_less_divisor)
1.436 + apply (drule_tac [2] m = "q mod c" in less_imp_Suc_add, auto)
1.437 + apply (erule_tac P = "%x. ?lhs < ?rhs x" in ssubst)
1.438 + apply (simp add: add_mult_distrib2)
1.439 + done
1.440
1.441 -lemma quorem_mult2_eq: "[| quorem ((a,b), (q,r)); 0 < b; 0 < c |]
1.442 +lemma quorem_mult2_eq: "[| quorem ((a,b), (q,r)); 0 < b; 0 < c |]
1.443 ==> quorem ((a, b*c), (q div c, b*(q mod c) + r))"
1.444 -apply (auto simp add: mult_ac quorem_def add_mult_distrib2 [symmetric] mod_lemma)
1.445 -done
1.446 + by (auto simp add: mult_ac quorem_def add_mult_distrib2 [symmetric] mod_lemma)
1.447
1.448 lemma div_mult2_eq: "a div (b*c) = (a div b) div (c::nat)"
1.449 -apply (case_tac "b=0", simp)
1.450 -apply (case_tac "c=0", simp)
1.451 -apply (force simp add: quorem_div_mod [THEN quorem_mult2_eq, THEN quorem_div])
1.452 -done
1.453 + apply (cases "b = 0", simp)
1.454 + apply (cases "c = 0", simp)
1.455 + apply (force simp add: quorem_div_mod [THEN quorem_mult2_eq, THEN quorem_div])
1.456 + done
1.457
1.458 lemma mod_mult2_eq: "a mod (b*c) = b*(a div b mod c) + a mod (b::nat)"
1.459 -apply (case_tac "b=0", simp)
1.460 -apply (case_tac "c=0", simp)
1.461 -apply (auto simp add: mult_commute quorem_div_mod [THEN quorem_mult2_eq, THEN quorem_mod])
1.462 -done
1.463 + apply (cases "b = 0", simp)
1.464 + apply (cases "c = 0", simp)
1.465 + apply (auto simp add: mult_commute quorem_div_mod [THEN quorem_mult2_eq, THEN quorem_mod])
1.466 + done
1.467
1.468
1.469 subsection{*Cancellation of Common Factors in Division*}
1.470
1.471 lemma div_mult_mult_lemma:
1.472 - "[| (0::nat) < b; 0 < c |] ==> (c*a) div (c*b) = a div b"
1.473 -by (auto simp add: div_mult2_eq)
1.474 + "[| (0::nat) < b; 0 < c |] ==> (c*a) div (c*b) = a div b"
1.475 + by (auto simp add: div_mult2_eq)
1.476
1.477 lemma div_mult_mult1 [simp]: "(0::nat) < c ==> (c*a) div (c*b) = a div b"
1.478 -apply (case_tac "b = 0")
1.479 -apply (auto simp add: linorder_neq_iff [of b] div_mult_mult_lemma)
1.480 -done
1.481 + apply (cases "b = 0")
1.482 + apply (auto simp add: linorder_neq_iff [of b] div_mult_mult_lemma)
1.483 + done
1.484
1.485 lemma div_mult_mult2 [simp]: "(0::nat) < c ==> (a*c) div (b*c) = a div b"
1.486 -apply (drule div_mult_mult1)
1.487 -apply (auto simp add: mult_commute)
1.488 -done
1.489 + apply (drule div_mult_mult1)
1.490 + apply (auto simp add: mult_commute)
1.491 + done
1.492
1.493
1.494 (*Distribution of Factors over Remainders:
1.495 @@ -404,34 +389,32 @@
1.496 subsection{*Further Facts about Quotient and Remainder*}
1.497
1.498 lemma div_1 [simp]: "m div Suc 0 = m"
1.499 -apply (induct "m")
1.500 -apply (simp_all (no_asm_simp) add: div_geq)
1.501 -done
1.502 + by (induct m) (simp_all add: div_geq)
1.503
1.504 lemma div_self [simp]: "0<n ==> n div n = (1::nat)"
1.505 -by (simp add: div_geq)
1.506 + by (simp add: div_geq)
1.507
1.508 lemma div_add_self2: "0<n ==> (m+n) div n = Suc (m div n)"
1.509 -apply (subgoal_tac "(n + m) div n = Suc ((n+m-n) div n) ")
1.510 -apply (simp add: add_commute)
1.511 -apply (subst div_geq [symmetric], simp_all)
1.512 -done
1.513 + apply (subgoal_tac "(n + m) div n = Suc ((n+m-n) div n) ")
1.514 + apply (simp add: add_commute)
1.515 + apply (subst div_geq [symmetric], simp_all)
1.516 + done
1.517
1.518 lemma div_add_self1: "0<n ==> (n+m) div n = Suc (m div n)"
1.519 -by (simp add: add_commute div_add_self2)
1.520 + by (simp add: add_commute div_add_self2)
1.521
1.522 lemma div_mult_self1 [simp]: "!!n::nat. 0<n ==> (m + k*n) div n = k + m div n"
1.523 -apply (subst div_add1_eq)
1.524 -apply (subst div_mult1_eq, simp)
1.525 -done
1.526 + apply (subst div_add1_eq)
1.527 + apply (subst div_mult1_eq, simp)
1.528 + done
1.529
1.530 lemma div_mult_self2 [simp]: "0<n ==> (m + n*k) div n = k + m div (n::nat)"
1.531 -by (simp add: mult_commute div_mult_self1)
1.532 + by (simp add: mult_commute div_mult_self1)
1.533
1.534
1.535 (* Monotonicity of div in first argument *)
1.536 lemma div_le_mono [rule_format (no_asm)]:
1.537 - "\<forall>m::nat. m \<le> n --> (m div k) \<le> (n div k)"
1.538 + "\<forall>m::nat. m \<le> n --> (m div k) \<le> (n div k)"
1.539 apply (case_tac "k=0", simp)
1.540 apply (induct "n" rule: nat_less_induct, clarify)
1.541 apply (case_tac "n<k")
1.542 @@ -448,12 +431,12 @@
1.543 (* Antimonotonicity of div in second argument *)
1.544 lemma div_le_mono2: "!!m::nat. [| 0<m; m\<le>n |] ==> (k div n) \<le> (k div m)"
1.545 apply (subgoal_tac "0<n")
1.546 - prefer 2 apply simp
1.547 + prefer 2 apply simp
1.548 apply (induct_tac k rule: nat_less_induct)
1.549 apply (rename_tac "k")
1.550 apply (case_tac "k<n", simp)
1.551 apply (subgoal_tac "~ (k<m) ")
1.552 - prefer 2 apply simp
1.553 + prefer 2 apply simp
1.554 apply (simp add: div_geq)
1.555 apply (subgoal_tac "(k-n) div n \<le> (k-m) div n")
1.556 prefer 2
1.557 @@ -469,14 +452,14 @@
1.558 apply (simp_all (no_asm_simp))
1.559 done
1.560
1.561 -(* Similar for "less than" *)
1.562 +(* Similar for "less than" *)
1.563 lemma div_less_dividend [rule_format]:
1.564 "!!n::nat. 1<n ==> 0 < m --> m div n < m"
1.565 apply (induct_tac m rule: nat_less_induct)
1.566 apply (rename_tac "m")
1.567 apply (case_tac "m<n", simp)
1.568 apply (subgoal_tac "0<n")
1.569 - prefer 2 apply simp
1.570 + prefer 2 apply simp
1.571 apply (simp add: div_geq)
1.572 apply (case_tac "n<m")
1.573 apply (subgoal_tac "(m-n) div n < (m-n) ")
1.574 @@ -500,199 +483,187 @@
1.575 done
1.576
1.577 lemma nat_mod_div_trivial [simp]: "m mod n div n = (0 :: nat)"
1.578 -by (case_tac "n=0", auto)
1.579 + by (cases "n = 0") auto
1.580
1.581 lemma nat_mod_mod_trivial [simp]: "m mod n mod n = (m mod n :: nat)"
1.582 -by (case_tac "n=0", auto)
1.583 + by (cases "n = 0") auto
1.584
1.585
1.586 subsection{*The Divides Relation*}
1.587
1.588 lemma dvdI [intro?]: "n = m * k ==> m dvd n"
1.589 -by (unfold dvd_def, blast)
1.590 + unfolding dvd_def by blast
1.591
1.592 lemma dvdE [elim?]: "!!P. [|m dvd n; !!k. n = m*k ==> P|] ==> P"
1.593 -by (unfold dvd_def, blast)
1.594 + unfolding dvd_def by blast
1.595
1.596 lemma dvd_0_right [iff]: "m dvd (0::nat)"
1.597 -apply (unfold dvd_def)
1.598 -apply (blast intro: mult_0_right [symmetric])
1.599 -done
1.600 + unfolding dvd_def by (blast intro: mult_0_right [symmetric])
1.601
1.602 lemma dvd_0_left: "0 dvd m ==> m = (0::nat)"
1.603 -by (force simp add: dvd_def)
1.604 + by (force simp add: dvd_def)
1.605
1.606 lemma dvd_0_left_iff [iff]: "(0 dvd (m::nat)) = (m = 0)"
1.607 -by (blast intro: dvd_0_left)
1.608 + by (blast intro: dvd_0_left)
1.609
1.610 lemma dvd_1_left [iff]: "Suc 0 dvd k"
1.611 -by (unfold dvd_def, simp)
1.612 + unfolding dvd_def by simp
1.613
1.614 lemma dvd_1_iff_1 [simp]: "(m dvd Suc 0) = (m = Suc 0)"
1.615 -by (simp add: dvd_def)
1.616 + by (simp add: dvd_def)
1.617
1.618 lemma dvd_refl [simp]: "m dvd (m::nat)"
1.619 -apply (unfold dvd_def)
1.620 -apply (blast intro: mult_1_right [symmetric])
1.621 -done
1.622 + unfolding dvd_def by (blast intro: mult_1_right [symmetric])
1.623
1.624 lemma dvd_trans [trans]: "[| m dvd n; n dvd p |] ==> m dvd (p::nat)"
1.625 -apply (unfold dvd_def)
1.626 -apply (blast intro: mult_assoc)
1.627 -done
1.628 + unfolding dvd_def by (blast intro: mult_assoc)
1.629
1.630 lemma dvd_anti_sym: "[| m dvd n; n dvd m |] ==> m = (n::nat)"
1.631 -apply (unfold dvd_def)
1.632 -apply (force dest: mult_eq_self_implies_10 simp add: mult_assoc mult_eq_1_iff)
1.633 -done
1.634 + unfolding dvd_def
1.635 + by (force dest: mult_eq_self_implies_10 simp add: mult_assoc mult_eq_1_iff)
1.636
1.637 lemma dvd_add: "[| k dvd m; k dvd n |] ==> k dvd (m+n :: nat)"
1.638 -apply (unfold dvd_def)
1.639 -apply (blast intro: add_mult_distrib2 [symmetric])
1.640 -done
1.641 + unfolding dvd_def
1.642 + by (blast intro: add_mult_distrib2 [symmetric])
1.643
1.644 lemma dvd_diff: "[| k dvd m; k dvd n |] ==> k dvd (m-n :: nat)"
1.645 -apply (unfold dvd_def)
1.646 -apply (blast intro: diff_mult_distrib2 [symmetric])
1.647 -done
1.648 + unfolding dvd_def
1.649 + by (blast intro: diff_mult_distrib2 [symmetric])
1.650
1.651 lemma dvd_diffD: "[| k dvd m-n; k dvd n; n\<le>m |] ==> k dvd (m::nat)"
1.652 -apply (erule linorder_not_less [THEN iffD2, THEN add_diff_inverse, THEN subst])
1.653 -apply (blast intro: dvd_add)
1.654 -done
1.655 + apply (erule linorder_not_less [THEN iffD2, THEN add_diff_inverse, THEN subst])
1.656 + apply (blast intro: dvd_add)
1.657 + done
1.658
1.659 lemma dvd_diffD1: "[| k dvd m-n; k dvd m; n\<le>m |] ==> k dvd (n::nat)"
1.660 -by (drule_tac m = m in dvd_diff, auto)
1.661 + by (drule_tac m = m in dvd_diff, auto)
1.662
1.663 lemma dvd_mult: "k dvd n ==> k dvd (m*n :: nat)"
1.664 -apply (unfold dvd_def)
1.665 -apply (blast intro: mult_left_commute)
1.666 -done
1.667 + unfolding dvd_def by (blast intro: mult_left_commute)
1.668
1.669 lemma dvd_mult2: "k dvd m ==> k dvd (m*n :: nat)"
1.670 -apply (subst mult_commute)
1.671 -apply (erule dvd_mult)
1.672 -done
1.673 + apply (subst mult_commute)
1.674 + apply (erule dvd_mult)
1.675 + done
1.676
1.677 lemma dvd_triv_right [iff]: "k dvd (m*k :: nat)"
1.678 -by (rule dvd_refl [THEN dvd_mult])
1.679 + by (rule dvd_refl [THEN dvd_mult])
1.680
1.681 lemma dvd_triv_left [iff]: "k dvd (k*m :: nat)"
1.682 -by (rule dvd_refl [THEN dvd_mult2])
1.683 + by (rule dvd_refl [THEN dvd_mult2])
1.684
1.685 lemma dvd_reduce: "(k dvd n + k) = (k dvd (n::nat))"
1.686 -apply (rule iffI)
1.687 -apply (erule_tac [2] dvd_add)
1.688 -apply (rule_tac [2] dvd_refl)
1.689 -apply (subgoal_tac "n = (n+k) -k")
1.690 - prefer 2 apply simp
1.691 -apply (erule ssubst)
1.692 -apply (erule dvd_diff)
1.693 -apply (rule dvd_refl)
1.694 -done
1.695 + apply (rule iffI)
1.696 + apply (erule_tac [2] dvd_add)
1.697 + apply (rule_tac [2] dvd_refl)
1.698 + apply (subgoal_tac "n = (n+k) -k")
1.699 + prefer 2 apply simp
1.700 + apply (erule ssubst)
1.701 + apply (erule dvd_diff)
1.702 + apply (rule dvd_refl)
1.703 + done
1.704
1.705 lemma dvd_mod: "!!n::nat. [| f dvd m; f dvd n |] ==> f dvd m mod n"
1.706 -apply (unfold dvd_def)
1.707 -apply (case_tac "n=0", auto)
1.708 -apply (blast intro: mod_mult_distrib2 [symmetric])
1.709 -done
1.710 + unfolding dvd_def
1.711 + apply (case_tac "n = 0", auto)
1.712 + apply (blast intro: mod_mult_distrib2 [symmetric])
1.713 + done
1.714
1.715 lemma dvd_mod_imp_dvd: "[| (k::nat) dvd m mod n; k dvd n |] ==> k dvd m"
1.716 -apply (subgoal_tac "k dvd (m div n) *n + m mod n")
1.717 - apply (simp add: mod_div_equality)
1.718 -apply (simp only: dvd_add dvd_mult)
1.719 -done
1.720 + apply (subgoal_tac "k dvd (m div n) *n + m mod n")
1.721 + apply (simp add: mod_div_equality)
1.722 + apply (simp only: dvd_add dvd_mult)
1.723 + done
1.724
1.725 lemma dvd_mod_iff: "k dvd n ==> ((k::nat) dvd m mod n) = (k dvd m)"
1.726 -by (blast intro: dvd_mod_imp_dvd dvd_mod)
1.727 + by (blast intro: dvd_mod_imp_dvd dvd_mod)
1.728
1.729 lemma dvd_mult_cancel: "!!k::nat. [| k*m dvd k*n; 0<k |] ==> m dvd n"
1.730 -apply (unfold dvd_def)
1.731 -apply (erule exE)
1.732 -apply (simp add: mult_ac)
1.733 -done
1.734 + unfolding dvd_def
1.735 + apply (erule exE)
1.736 + apply (simp add: mult_ac)
1.737 + done
1.738
1.739 lemma dvd_mult_cancel1: "0<m ==> (m*n dvd m) = (n = (1::nat))"
1.740 -apply auto
1.741 -apply (subgoal_tac "m*n dvd m*1")
1.742 -apply (drule dvd_mult_cancel, auto)
1.743 -done
1.744 + apply auto
1.745 + apply (subgoal_tac "m*n dvd m*1")
1.746 + apply (drule dvd_mult_cancel, auto)
1.747 + done
1.748
1.749 lemma dvd_mult_cancel2: "0<m ==> (n*m dvd m) = (n = (1::nat))"
1.750 -apply (subst mult_commute)
1.751 -apply (erule dvd_mult_cancel1)
1.752 -done
1.753 + apply (subst mult_commute)
1.754 + apply (erule dvd_mult_cancel1)
1.755 + done
1.756
1.757 lemma mult_dvd_mono: "[| i dvd m; j dvd n|] ==> i*j dvd (m*n :: nat)"
1.758 -apply (unfold dvd_def, clarify)
1.759 -apply (rule_tac x = "k*ka" in exI)
1.760 -apply (simp add: mult_ac)
1.761 -done
1.762 + apply (unfold dvd_def, clarify)
1.763 + apply (rule_tac x = "k*ka" in exI)
1.764 + apply (simp add: mult_ac)
1.765 + done
1.766
1.767 lemma dvd_mult_left: "(i*j :: nat) dvd k ==> i dvd k"
1.768 -by (simp add: dvd_def mult_assoc, blast)
1.769 + by (simp add: dvd_def mult_assoc, blast)
1.770
1.771 lemma dvd_mult_right: "(i*j :: nat) dvd k ==> j dvd k"
1.772 -apply (unfold dvd_def, clarify)
1.773 -apply (rule_tac x = "i*k" in exI)
1.774 -apply (simp add: mult_ac)
1.775 -done
1.776 + apply (unfold dvd_def, clarify)
1.777 + apply (rule_tac x = "i*k" in exI)
1.778 + apply (simp add: mult_ac)
1.779 + done
1.780
1.781 lemma dvd_imp_le: "[| k dvd n; 0 < n |] ==> k \<le> (n::nat)"
1.782 -apply (unfold dvd_def, clarify)
1.783 -apply (simp_all (no_asm_use) add: zero_less_mult_iff)
1.784 -apply (erule conjE)
1.785 -apply (rule le_trans)
1.786 -apply (rule_tac [2] le_refl [THEN mult_le_mono])
1.787 -apply (erule_tac [2] Suc_leI, simp)
1.788 -done
1.789 + apply (unfold dvd_def, clarify)
1.790 + apply (simp_all (no_asm_use) add: zero_less_mult_iff)
1.791 + apply (erule conjE)
1.792 + apply (rule le_trans)
1.793 + apply (rule_tac [2] le_refl [THEN mult_le_mono])
1.794 + apply (erule_tac [2] Suc_leI, simp)
1.795 + done
1.796
1.797 lemma dvd_eq_mod_eq_0: "!!k::nat. (k dvd n) = (n mod k = 0)"
1.798 -apply (unfold dvd_def)
1.799 -apply (case_tac "k=0", simp, safe)
1.800 -apply (simp add: mult_commute)
1.801 -apply (rule_tac t = n and n1 = k in mod_div_equality [THEN subst])
1.802 -apply (subst mult_commute, simp)
1.803 -done
1.804 + apply (unfold dvd_def)
1.805 + apply (case_tac "k=0", simp, safe)
1.806 + apply (simp add: mult_commute)
1.807 + apply (rule_tac t = n and n1 = k in mod_div_equality [THEN subst])
1.808 + apply (subst mult_commute, simp)
1.809 + done
1.810
1.811 lemma dvd_mult_div_cancel: "n dvd m ==> n * (m div n) = (m::nat)"
1.812 -apply (subgoal_tac "m mod n = 0")
1.813 - apply (simp add: mult_div_cancel)
1.814 -apply (simp only: dvd_eq_mod_eq_0)
1.815 -done
1.816 + apply (subgoal_tac "m mod n = 0")
1.817 + apply (simp add: mult_div_cancel)
1.818 + apply (simp only: dvd_eq_mod_eq_0)
1.819 + done
1.820
1.821 lemma le_imp_power_dvd: "!!i::nat. m \<le> n ==> i^m dvd i^n"
1.822 -apply (unfold dvd_def)
1.823 -apply (erule linorder_not_less [THEN iffD2, THEN add_diff_inverse, THEN subst])
1.824 -apply (simp add: power_add)
1.825 -done
1.826 + apply (unfold dvd_def)
1.827 + apply (erule linorder_not_less [THEN iffD2, THEN add_diff_inverse, THEN subst])
1.828 + apply (simp add: power_add)
1.829 + done
1.830
1.831 lemma nat_zero_less_power_iff [simp]: "(0 < x^n) = (x \<noteq> (0::nat) | n=0)"
1.832 -by (induct "n", auto)
1.833 + by (induct n) auto
1.834
1.835 lemma power_le_dvd [rule_format]: "k^j dvd n --> i\<le>j --> k^i dvd (n::nat)"
1.836 -apply (induct "j")
1.837 -apply (simp_all add: le_Suc_eq)
1.838 -apply (blast dest!: dvd_mult_right)
1.839 -done
1.840 + apply (induct j)
1.841 + apply (simp_all add: le_Suc_eq)
1.842 + apply (blast dest!: dvd_mult_right)
1.843 + done
1.844
1.845 lemma power_dvd_imp_le: "[|i^m dvd i^n; (1::nat) < i|] ==> m \<le> n"
1.846 -apply (rule power_le_imp_le_exp, assumption)
1.847 -apply (erule dvd_imp_le, simp)
1.848 -done
1.849 + apply (rule power_le_imp_le_exp, assumption)
1.850 + apply (erule dvd_imp_le, simp)
1.851 + done
1.852
1.853 lemma mod_eq_0_iff: "(m mod d = 0) = (\<exists>q::nat. m = d*q)"
1.854 -by (auto simp add: dvd_eq_mod_eq_0 [symmetric] dvd_def)
1.855 + by (auto simp add: dvd_eq_mod_eq_0 [symmetric] dvd_def)
1.856
1.857 -lemmas mod_eq_0D = mod_eq_0_iff [THEN iffD1]
1.858 -declare mod_eq_0D [dest!]
1.859 +lemmas mod_eq_0D [dest!] = mod_eq_0_iff [THEN iffD1]
1.860
1.861 (*Loses information, namely we also have r<d provided d is nonzero*)
1.862 lemma mod_eqD: "(m mod d = r) ==> \<exists>q::nat. m = r + q*d"
1.863 -apply (cut_tac m = m in mod_div_equality)
1.864 -apply (simp only: add_ac)
1.865 -apply (blast intro: sym)
1.866 -done
1.867 + apply (cut_tac m = m in mod_div_equality)
1.868 + apply (simp only: add_ac)
1.869 + apply (blast intro: sym)
1.870 + done
1.871
1.872
1.873 lemma split_div:
1.874 @@ -713,11 +684,11 @@
1.875 assume n: "n = k*i + j" and j: "j < k"
1.876 show "P i"
1.877 proof (cases)
1.878 - assume "i = 0"
1.879 - with n j P show "P i" by simp
1.880 + assume "i = 0"
1.881 + with n j P show "P i" by simp
1.882 next
1.883 - assume "i \<noteq> 0"
1.884 - with not0 n j P show "P i" by(simp add:add_ac)
1.885 + assume "i \<noteq> 0"
1.886 + with not0 n j P show "P i" by(simp add:add_ac)
1.887 qed
1.888 qed
1.889 qed
1.890 @@ -818,28 +789,28 @@
1.891 assume ih: "?A n"
1.892 show "?A (Suc n)"
1.893 proof (clarsimp)
1.894 - assume y: "P (p - Suc n)"
1.895 - have n: "Suc n < p"
1.896 - proof (rule ccontr)
1.897 - assume "\<not>(Suc n < p)"
1.898 - hence "p - Suc n = 0"
1.899 - by simp
1.900 - with y contra show "False"
1.901 - by simp
1.902 - qed
1.903 - hence n2: "Suc (p - Suc n) = p-n" by arith
1.904 - from p have "p - Suc n < p" by arith
1.905 - with y step have z: "P ((Suc (p - Suc n)) mod p)"
1.906 - by blast
1.907 - show "False"
1.908 - proof (cases "n=0")
1.909 - case True
1.910 - with z n2 contra show ?thesis by simp
1.911 - next
1.912 - case False
1.913 - with p have "p-n < p" by arith
1.914 - with z n2 False ih show ?thesis by simp
1.915 - qed
1.916 + assume y: "P (p - Suc n)"
1.917 + have n: "Suc n < p"
1.918 + proof (rule ccontr)
1.919 + assume "\<not>(Suc n < p)"
1.920 + hence "p - Suc n = 0"
1.921 + by simp
1.922 + with y contra show "False"
1.923 + by simp
1.924 + qed
1.925 + hence n2: "Suc (p - Suc n) = p-n" by arith
1.926 + from p have "p - Suc n < p" by arith
1.927 + with y step have z: "P ((Suc (p - Suc n)) mod p)"
1.928 + by blast
1.929 + show "False"
1.930 + proof (cases "n=0")
1.931 + case True
1.932 + with z n2 contra show ?thesis by simp
1.933 + next
1.934 + case False
1.935 + with p have "p-n < p" by arith
1.936 + with z n2 False ih show ?thesis by simp
1.937 + qed
1.938 qed
1.939 qed
1.940 qed
1.941 @@ -864,22 +835,22 @@
1.942 show "j<p \<longrightarrow> P j" (is "?A j")
1.943 proof (induct j)
1.944 from step base i show "?A 0"
1.945 - by (auto elim: mod_induct_0)
1.946 + by (auto elim: mod_induct_0)
1.947 next
1.948 fix k
1.949 assume ih: "?A k"
1.950 show "?A (Suc k)"
1.951 proof
1.952 - assume suc: "Suc k < p"
1.953 - hence k: "k<p" by simp
1.954 - with ih have "P k" ..
1.955 - with step k have "P (Suc k mod p)"
1.956 - by blast
1.957 - moreover
1.958 - from suc have "Suc k mod p = Suc k"
1.959 - by simp
1.960 - ultimately
1.961 - show "P (Suc k)" by simp
1.962 + assume suc: "Suc k < p"
1.963 + hence k: "k<p" by simp
1.964 + with ih have "P k" ..
1.965 + with step k have "P (Suc k mod p)"
1.966 + by blast
1.967 + moreover
1.968 + from suc have "Suc k mod p = Suc k"
1.969 + by simp
1.970 + ultimately
1.971 + show "P (Suc k)" by simp
1.972 qed
1.973 qed
1.974 qed
1.975 @@ -889,15 +860,15 @@
1.976
1.977 lemma mod_add_left_eq: "((a::nat) + b) mod c = (a mod c + b) mod c"
1.978 apply (rule trans [symmetric])
1.979 - apply (rule mod_add1_eq, simp)
1.980 + apply (rule mod_add1_eq, simp)
1.981 apply (rule mod_add1_eq [symmetric])
1.982 done
1.983
1.984 lemma mod_add_right_eq: "(a+b) mod (c::nat) = (a + (b mod c)) mod c"
1.985 -apply (rule trans [symmetric])
1.986 -apply (rule mod_add1_eq, simp)
1.987 -apply (rule mod_add1_eq [symmetric])
1.988 -done
1.989 + apply (rule trans [symmetric])
1.990 + apply (rule mod_add1_eq, simp)
1.991 + apply (rule mod_add1_eq [symmetric])
1.992 + done
1.993
1.994
1.995 subsection {* Code generation for div and mod *}
1.996 @@ -905,25 +876,21 @@
1.997 definition
1.998 "divmod (m\<Colon>nat) n = (m div n, m mod n)"
1.999
1.1000 -lemma divmod_zero [code]:
1.1001 - "divmod m 0 = (0, m)"
1.1002 +lemma divmod_zero [code]: "divmod m 0 = (0, m)"
1.1003 unfolding divmod_def by simp
1.1004
1.1005 lemma divmod_succ [code]:
1.1006 "divmod m (Suc k) = (if m < Suc k then (0, m) else
1.1007 let
1.1008 (p, q) = divmod (m - Suc k) (Suc k)
1.1009 - in (Suc p, q)
1.1010 - )"
1.1011 + in (Suc p, q))"
1.1012 unfolding divmod_def Let_def split_def
1.1013 by (auto intro: div_geq mod_geq)
1.1014
1.1015 -lemma div_divmod [code]:
1.1016 - "m div n = fst (divmod m n)"
1.1017 +lemma div_divmod [code]: "m div n = fst (divmod m n)"
1.1018 unfolding divmod_def by simp
1.1019
1.1020 -lemma mod_divmod [code]:
1.1021 - "m mod n = snd (divmod m n)"
1.1022 +lemma mod_divmod [code]: "m mod n = snd (divmod m n)"
1.1023 unfolding divmod_def by simp
1.1024
1.1025 code_modulename SML
1.1026 @@ -934,7 +901,6 @@
1.1027
1.1028 hide (open) const divmod
1.1029
1.1030 -
1.1031 subsection {* Legacy bindings *}
1.1032
1.1033 ML
1.1034 @@ -1038,7 +1004,6 @@
1.1035 val mod_eqD = thm "mod_eqD";
1.1036 *}
1.1037
1.1038 -
1.1039 (*
1.1040 lemma split_div:
1.1041 assumes m: "m \<noteq> 0"
2.1 --- a/src/HOL/Nat.thy Mon Apr 16 16:11:03 2007 +0200
2.2 +++ b/src/HOL/Nat.thy Tue Apr 17 00:30:44 2007 +0200
2.3 @@ -48,13 +48,15 @@
2.4
2.5 consts
2.6 Suc :: "nat => nat"
2.7 - pred_nat :: "(nat * nat) set"
2.8
2.9 local
2.10
2.11 defs
2.12 Suc_def: "Suc == (%n. Abs_Nat (Suc_Rep (Rep_Nat n)))"
2.13 - pred_nat_def: "pred_nat == {(m, n). n = Suc m}"
2.14 +
2.15 +definition
2.16 + pred_nat :: "(nat * nat) set" where
2.17 + "pred_nat = {(m, n). n = Suc m}"
2.18
2.19 instance nat :: "{ord, zero, one}"
2.20 Zero_nat_def: "0 == Abs_Nat Zero_Rep"
2.21 @@ -64,8 +66,11 @@
2.22
2.23 text {* Induction *}
2.24
2.25 -lemmas Rep_Nat' = Rep_Nat [simplified mem_Collect_eq]
2.26 -lemmas Abs_Nat_inverse' = Abs_Nat_inverse [simplified mem_Collect_eq]
2.27 +lemma Rep_Nat': "Nat (Rep_Nat x)"
2.28 + by (rule Rep_Nat [simplified mem_Collect_eq])
2.29 +
2.30 +lemma Abs_Nat_inverse': "Nat y \<Longrightarrow> Rep_Nat (Abs_Nat y) = y"
2.31 + by (rule Abs_Nat_inverse [simplified mem_Collect_eq])
2.32
2.33 theorem nat_induct: "P 0 ==> (!!n. P n ==> P (Suc n)) ==> P n"
2.34 apply (unfold Zero_nat_def Suc_def)
2.35 @@ -78,7 +83,7 @@
2.36
2.37 lemma Suc_not_Zero [iff]: "Suc m \<noteq> 0"
2.38 by (simp add: Zero_nat_def Suc_def Abs_Nat_inject Rep_Nat' Suc_RepI Zero_RepI
2.39 - Suc_Rep_not_Zero_Rep)
2.40 + Suc_Rep_not_Zero_Rep)
2.41
2.42 lemma Zero_not_Suc [iff]: "0 \<noteq> Suc m"
2.43 by (rule not_sym, rule Suc_not_Zero not_sym)
2.44 @@ -92,8 +97,8 @@
2.45 text {* Injectiveness of @{term Suc} *}
2.46
2.47 lemma inj_Suc[simp]: "inj_on Suc N"
2.48 - by (simp add: Suc_def inj_on_def Abs_Nat_inject Rep_Nat' Suc_RepI
2.49 - inj_Suc_Rep [THEN inj_eq] Rep_Nat_inject)
2.50 + by (simp add: Suc_def inj_on_def Abs_Nat_inject Rep_Nat' Suc_RepI
2.51 + inj_Suc_Rep [THEN inj_eq] Rep_Nat_inject)
2.52
2.53 lemma Suc_inject: "Suc x = Suc y ==> x = y"
2.54 by (rule inj_Suc [THEN injD])
2.55 @@ -259,9 +264,9 @@
2.56
2.57 text {* "Less than" is antisymmetric, sort of *}
2.58 lemma less_antisym: "\<lbrakk> \<not> n < m; n < Suc m \<rbrakk> \<Longrightarrow> m = n"
2.59 -apply(simp only:less_Suc_eq)
2.60 -apply blast
2.61 -done
2.62 + apply(simp only:less_Suc_eq)
2.63 + apply blast
2.64 + done
2.65
2.66 lemma nat_neq_iff: "((m::nat) \<noteq> n) = (m < n | n < m)"
2.67 using less_linear by blast
2.68 @@ -318,13 +323,12 @@
2.69
2.70 text {* Can be used with @{text less_Suc_eq} to get @{term "n = m | n < m"} *}
2.71 lemma not_less_eq: "(~ m < n) = (n < Suc m)"
2.72 -by (rule_tac m = m and n = n in diff_induct, simp_all)
2.73 + by (induct m n rule: diff_induct) simp_all
2.74
2.75 text {* Complete induction, aka course-of-values induction *}
2.76 lemma nat_less_induct:
2.77 assumes prem: "!!n. \<forall>m::nat. m < n --> P m ==> P n" shows "P n"
2.78 - apply (rule_tac a=n in wf_induct)
2.79 - apply (rule wf_pred_nat [THEN wf_trancl])
2.80 + apply (induct n rule: wf_induct [OF wf_pred_nat [THEN wf_trancl]])
2.81 apply (rule prem)
2.82 apply (unfold less_def, assumption)
2.83 done
2.84 @@ -336,13 +340,13 @@
2.85
2.86 text {* Was @{text le_eq_less_Suc}, but this orientation is more useful *}
2.87 lemma less_Suc_eq_le: "(m < Suc n) = (m \<le> n)"
2.88 - by (unfold le_def, rule not_less_eq [symmetric])
2.89 + unfolding le_def by (rule not_less_eq [symmetric])
2.90
2.91 lemma le_imp_less_Suc: "m \<le> n ==> m < Suc n"
2.92 by (rule less_Suc_eq_le [THEN iffD2])
2.93
2.94 lemma le0 [iff]: "(0::nat) \<le> n"
2.95 - by (unfold le_def, rule not_less0)
2.96 + unfolding le_def by (rule not_less0)
2.97
2.98 lemma Suc_n_not_le_n: "~ Suc n \<le> n"
2.99 by (simp add: le_def)
2.100 @@ -387,23 +391,21 @@
2.101 text {* Equivalence of @{term "m \<le> n"} and @{term "m < n | m = n"} *}
2.102
2.103 lemma le_imp_less_or_eq: "m \<le> n ==> m < n | m = (n::nat)"
2.104 - apply (unfold le_def)
2.105 + unfolding le_def
2.106 using less_linear
2.107 - apply (blast elim: less_irrefl less_asym)
2.108 - done
2.109 + by (blast elim: less_irrefl less_asym)
2.110
2.111 lemma less_or_eq_imp_le: "m < n | m = n ==> m \<le> (n::nat)"
2.112 - apply (unfold le_def)
2.113 + unfolding le_def
2.114 using less_linear
2.115 - apply (blast elim!: less_irrefl elim: less_asym)
2.116 - done
2.117 + by (blast elim!: less_irrefl elim: less_asym)
2.118
2.119 lemma le_eq_less_or_eq: "(m \<le> (n::nat)) = (m < n | m=n)"
2.120 by (iprover intro: less_or_eq_imp_le le_imp_less_or_eq)
2.121
2.122 -text {* Useful with @{text Blast}. *}
2.123 +text {* Useful with @{text blast}. *}
2.124 lemma eq_imp_le: "(m::nat) = n ==> m \<le> n"
2.125 - by (rule less_or_eq_imp_le, rule disjI2)
2.126 + by (rule less_or_eq_imp_le) (rule disjI2)
2.127
2.128 lemma le_refl: "n \<le> (n::nat)"
2.129 by (simp add: le_eq_less_or_eq)
2.130 @@ -433,9 +435,7 @@
2.131 text {* Axiom @{text linorder_linear} of class @{text linorder}: *}
2.132 lemma nat_le_linear: "(m::nat) \<le> n | n \<le> m"
2.133 apply (simp add: le_eq_less_or_eq)
2.134 - using less_linear
2.135 - apply blast
2.136 - done
2.137 + using less_linear by blast
2.138
2.139 text {* Type {@typ nat} is a wellfounded linear order *}
2.140
2.141 @@ -444,7 +444,7 @@
2.142 (assumption |
2.143 rule le_refl le_trans le_anti_sym nat_less_le nat_le_linear wf_less)+
2.144
2.145 -lemmas linorder_neqE_nat = linorder_neqE[where 'a = nat]
2.146 +lemmas linorder_neqE_nat = linorder_neqE [where 'a = nat]
2.147
2.148 lemma not_less_less_Suc_eq: "~ n < m ==> (n < Suc m) = (n = m)"
2.149 by (blast elim!: less_SucE)
2.150 @@ -461,8 +461,8 @@
2.151
2.152
2.153 text {*
2.154 - Re-orientation of the equations @{text "0 = x"} and @{text "1 = x"}.
2.155 - No longer added as simprules (they loop)
2.156 + Re-orientation of the equations @{text "0 = x"} and @{text "1 = x"}.
2.157 + No longer added as simprules (they loop)
2.158 but via @{text reorient_simproc} in Bin
2.159 *}
2.160
2.161 @@ -495,7 +495,7 @@
2.162 mult_0: "0 * n = 0"
2.163 mult_Suc: "Suc m * n = n + (m * n)"
2.164
2.165 -text {* These two rules ease the use of primitive recursion.
2.166 +text {* These two rules ease the use of primitive recursion.
2.167 NOTE USE OF @{text "=="} *}
2.168 lemma def_nat_rec_0: "(!!n. f n == nat_rec c h n) ==> f 0 = c"
2.169 by simp
2.170 @@ -504,13 +504,13 @@
2.171 by simp
2.172
2.173 lemma not0_implies_Suc: "n \<noteq> 0 ==> \<exists>m. n = Suc m"
2.174 - by (case_tac n) simp_all
2.175 + by (cases n) simp_all
2.176
2.177 -lemma gr_implies_not0: "!!n::nat. m<n ==> n \<noteq> 0"
2.178 - by (case_tac n) simp_all
2.179 +lemma gr_implies_not0: fixes n :: nat shows "m<n ==> n \<noteq> 0"
2.180 + by (cases n) simp_all
2.181
2.182 -lemma neq0_conv [iff]: "!!n::nat. (n \<noteq> 0) = (0 < n)"
2.183 - by (case_tac n) simp_all
2.184 +lemma neq0_conv [iff]: fixes n :: nat shows "(n \<noteq> 0) = (0 < n)"
2.185 + by (cases n) simp_all
2.186
2.187 text {* This theorem is useful with @{text blast} *}
2.188 lemma gr0I: "((n::nat) = 0 ==> False) ==> 0 < n"
2.189 @@ -521,7 +521,8 @@
2.190
2.191 lemma not_gr0 [iff]: "!!n::nat. (~ (0 < n)) = (n = 0)"
2.192 apply (rule iffI)
2.193 - apply (rule ccontr, simp_all)
2.194 + apply (rule ccontr)
2.195 + apply simp_all
2.196 done
2.197
2.198 lemma Suc_le_D: "(Suc n \<le> m') ==> (? m. m' = Suc m)"
2.199 @@ -529,7 +530,7 @@
2.200
2.201 text {* Useful in certain inductive arguments *}
2.202 lemma less_Suc_eq_0_disj: "(m < Suc n) = (m = 0 | (\<exists>j. m = Suc j & j < n))"
2.203 - by (case_tac m) simp_all
2.204 + by (cases m) simp_all
2.205
2.206 lemma nat_induct2: "[|P 0; P (Suc 0); !!k. P k ==> P (Suc (Suc k))|] ==> P n"
2.207 apply (rule nat_less_induct)
2.208 @@ -571,7 +572,7 @@
2.209
2.210 lemma min_Suc1:
2.211 "min (Suc n) m = (case m of 0 => 0 | Suc m' => Suc(min n m'))"
2.212 - by (simp split: nat.split)
2.213 + by (simp split: nat.split)
2.214
2.215 lemma min_Suc2:
2.216 "min m (Suc n) = (case m of 0 => 0 | Suc m' => Suc(min m' n))"
2.217 @@ -588,7 +589,7 @@
2.218
2.219 lemma max_Suc1:
2.220 "max (Suc n) m = (case m of 0 => Suc n | Suc m' => Suc(max n m'))"
2.221 - by (simp split: nat.split)
2.222 + by (simp split: nat.split)
2.223
2.224 lemma max_Suc2:
2.225 "max m (Suc n) = (case m of 0 => Suc n | Suc m' => Suc(max m' n))"
2.226 @@ -657,11 +658,11 @@
2.227
2.228 text {* Reasoning about @{text "m + 0 = 0"}, etc. *}
2.229
2.230 -lemma add_is_0 [iff]: "!!m::nat. (m + n = 0) = (m = 0 & n = 0)"
2.231 - by (case_tac m) simp_all
2.232 +lemma add_is_0 [iff]: fixes m :: nat shows "(m + n = 0) = (m = 0 & n = 0)"
2.233 + by (cases m) simp_all
2.234
2.235 lemma add_is_1: "(m+n= Suc 0) = (m= Suc 0 & n=0 | m=0 & n= Suc 0)"
2.236 - by (case_tac m) simp_all
2.237 + by (cases m) simp_all
2.238
2.239 lemma one_is_add: "(Suc 0 = m + n) = (m = Suc 0 & n = 0 | m = 0 & n = Suc 0)"
2.240 by (rule trans, rule eq_commute, rule add_is_1)
2.241 @@ -674,13 +675,12 @@
2.242 apply (simp add: nat_add_assoc del: add_0_right)
2.243 done
2.244
2.245 -
2.246 lemma inj_on_add_nat[simp]: "inj_on (%n::nat. n+k) N"
2.247 -apply(induct k)
2.248 - apply simp
2.249 -apply(drule comp_inj_on[OF _ inj_Suc])
2.250 -apply (simp add:o_def)
2.251 -done
2.252 + apply (induct k)
2.253 + apply simp
2.254 + apply(drule comp_inj_on[OF _ inj_Suc])
2.255 + apply (simp add:o_def)
2.256 + done
2.257
2.258
2.259 subsection {* Multiplication *}
2.260 @@ -726,7 +726,8 @@
2.261
2.262 lemma mult_is_0 [simp]: "((m::nat) * n = 0) = (m=0 | n=0)"
2.263 apply (induct m)
2.264 - apply (induct_tac [2] n, simp_all)
2.265 + apply (induct_tac [2] n)
2.266 + apply simp_all
2.267 done
2.268
2.269
2.270 @@ -746,14 +747,14 @@
2.271 lemma less_imp_Suc_add: "m < n ==> (\<exists>k. n = Suc (m + k))"
2.272 apply (induct n)
2.273 apply (simp_all add: order_le_less)
2.274 - apply (blast elim!: less_SucE
2.275 + apply (blast elim!: less_SucE
2.276 intro!: add_0_right [symmetric] add_Suc_right [symmetric])
2.277 done
2.278
2.279 text {* strict, in 1st argument; proof is by induction on @{text "k > 0"} *}
2.280 lemma mult_less_mono2: "(i::nat) < j ==> 0 < k ==> k * i < k * j"
2.281 apply (erule_tac m1 = 0 in less_imp_Suc_add [THEN exE], simp)
2.282 - apply (induct_tac x)
2.283 + apply (induct_tac x)
2.284 apply (simp_all add: add_less_mono)
2.285 done
2.286
2.287 @@ -777,22 +778,22 @@
2.288 subsection {* Additional theorems about "less than" *}
2.289
2.290 text{*An induction rule for estabilishing binary relations*}
2.291 -lemma less_Suc_induct:
2.292 +lemma less_Suc_induct:
2.293 assumes less: "i < j"
2.294 and step: "!!i. P i (Suc i)"
2.295 and trans: "!!i j k. P i j ==> P j k ==> P i k"
2.296 shows "P i j"
2.297 proof -
2.298 - from less obtain k where j: "j = Suc(i+k)" by (auto dest: less_imp_Suc_add)
2.299 - have "P i (Suc(i+k))"
2.300 + from less obtain k where j: "j = Suc(i+k)" by (auto dest: less_imp_Suc_add)
2.301 + have "P i (Suc (i + k))"
2.302 proof (induct k)
2.303 - case 0
2.304 - show ?case by (simp add: step)
2.305 + case 0
2.306 + show ?case by (simp add: step)
2.307 next
2.308 case (Suc k)
2.309 - thus ?case by (auto intro: prems)
2.310 + thus ?case by (auto intro: assms)
2.311 qed
2.312 - thus "P i j" by (simp add: j)
2.313 + thus "P i j" by (simp add: j)
2.314 qed
2.315
2.316
2.317 @@ -800,7 +801,9 @@
2.318 monotonicity to @{text "\<le>"} monotonicity *}
2.319 lemma less_mono_imp_le_mono:
2.320 assumes lt_mono: "!!i j::nat. i < j ==> f i < f j"
2.321 - and le: "i \<le> j" shows "f i \<le> ((f j)::nat)" using le
2.322 + and le: "i \<le> j"
2.323 + shows "f i \<le> ((f j)::nat)"
2.324 + using le
2.325 apply (simp add: order_le_less)
2.326 apply (blast intro!: lt_mono)
2.327 done
2.328 @@ -814,7 +817,7 @@
2.329 by (rule add_mono)
2.330
2.331 lemma le_add2: "n \<le> ((m + n)::nat)"
2.332 - by (insert add_right_mono [of 0 m n], simp)
2.333 + by (insert add_right_mono [of 0 m n], simp)
2.334
2.335 lemma le_add1: "n \<le> ((n + m)::nat)"
2.336 by (simp add: add_commute, rule le_add2)
2.337 @@ -841,7 +844,7 @@
2.338 by (rule less_le_trans, assumption, rule le_add2)
2.339
2.340 lemma add_lessD1: "i + j < (k::nat) ==> i < k"
2.341 - apply (rule le_less_trans [of _ "i+j"])
2.342 + apply (rule le_less_trans [of _ "i+j"])
2.343 apply (simp_all add: le_add1)
2.344 done
2.345
2.346 @@ -854,7 +857,7 @@
2.347 by (simp add: add_commute not_add_less1)
2.348
2.349 lemma add_leD1: "m + k \<le> n ==> m \<le> (n::nat)"
2.350 - apply (rule order_trans [of _ "m+k"])
2.351 + apply (rule order_trans [of _ "m+k"])
2.352 apply (simp_all add: le_add1)
2.353 done
2.354
2.355 @@ -913,9 +916,7 @@
2.356 by (simp add: diff_diff_left)
2.357
2.358 lemma diff_Suc_less [simp]: "0<n ==> n - Suc i < n"
2.359 - apply (case_tac "n", safe)
2.360 - apply (simp add: le_simps)
2.361 - done
2.362 + by (cases n) (auto simp add: le_simps)
2.363
2.364 text {* This and the next few suggested by Florian Kammueller *}
2.365 lemma diff_commute: "(i::nat) - j - k = i - k - j"
2.366 @@ -934,9 +935,7 @@
2.367 by (simp add: diff_add_assoc)
2.368
2.369 lemma le_imp_diff_is_add: "i \<le> (j::nat) ==> (j - i = k) = (j = k + i)"
2.370 - apply safe
2.371 - apply (simp_all add: diff_add_inverse2)
2.372 - done
2.373 + by (auto simp add: diff_add_inverse2)
2.374
2.375 lemma diff_is_0_eq [simp]: "((m::nat) - n = 0) = (m \<le> n)"
2.376 by (induct m n rule: diff_induct) simp_all
2.377 @@ -947,10 +946,13 @@
2.378 lemma zero_less_diff [simp]: "(0 < n - (m::nat)) = (m < n)"
2.379 by (induct m n rule: diff_induct) simp_all
2.380
2.381 -lemma less_imp_add_positive: "i < j ==> \<exists>k::nat. 0 < k & i + k = j"
2.382 - apply (rule_tac x = "j - i" in exI)
2.383 - apply (simp (no_asm_simp) add: add_diff_inverse less_not_sym)
2.384 - done
2.385 +lemma less_imp_add_positive:
2.386 + assumes "i < j"
2.387 + shows "\<exists>k::nat. 0 < k & i + k = j"
2.388 +proof
2.389 + from assms show "0 < j - i & i + (j - i) = j"
2.390 + by (simp add: add_diff_inverse less_not_sym)
2.391 +qed
2.392
2.393 lemma zero_induct_lemma: "P k ==> (!!n. P (Suc n) ==> P n) ==> P (k - i)"
2.394 apply (induct k i rule: diff_induct)
2.395 @@ -989,33 +991,39 @@
2.396 subsection {* Monotonicity of Multiplication *}
2.397
2.398 lemma mult_le_mono1: "i \<le> (j::nat) ==> i * k \<le> j * k"
2.399 - by (simp add: mult_right_mono)
2.400 + by (simp add: mult_right_mono)
2.401
2.402 lemma mult_le_mono2: "i \<le> (j::nat) ==> k * i \<le> k * j"
2.403 - by (simp add: mult_left_mono)
2.404 + by (simp add: mult_left_mono)
2.405
2.406 text {* @{text "\<le>"} monotonicity, BOTH arguments *}
2.407 lemma mult_le_mono: "i \<le> (j::nat) ==> k \<le> l ==> i * k \<le> j * l"
2.408 - by (simp add: mult_mono)
2.409 + by (simp add: mult_mono)
2.410
2.411 lemma mult_less_mono1: "(i::nat) < j ==> 0 < k ==> i * k < j * k"
2.412 - by (simp add: mult_strict_right_mono)
2.413 + by (simp add: mult_strict_right_mono)
2.414
2.415 text{*Differs from the standard @{text zero_less_mult_iff} in that
2.416 there are no negative numbers.*}
2.417 lemma nat_0_less_mult_iff [simp]: "(0 < (m::nat) * n) = (0 < m & 0 < n)"
2.418 apply (induct m)
2.419 - apply (case_tac [2] n, simp_all)
2.420 + apply simp
2.421 + apply (case_tac n)
2.422 + apply simp_all
2.423 done
2.424
2.425 lemma one_le_mult_iff [simp]: "(Suc 0 \<le> m * n) = (1 \<le> m & 1 \<le> n)"
2.426 apply (induct m)
2.427 - apply (case_tac [2] n, simp_all)
2.428 + apply simp
2.429 + apply (case_tac n)
2.430 + apply simp_all
2.431 done
2.432
2.433 lemma mult_eq_1_iff [simp]: "(m * n = Suc 0) = (m = 1 & n = 1)"
2.434 - apply (induct m, simp)
2.435 - apply (induct n, simp, fastsimp)
2.436 + apply (induct m)
2.437 + apply simp
2.438 + apply (induct n)
2.439 + apply auto
2.440 done
2.441
2.442 lemma one_eq_mult_iff [simp]: "(Suc 0 = m * n) = (m = 1 & n = 1)"
2.443 @@ -1034,10 +1042,10 @@
2.444 by (simp add: mult_commute [of k])
2.445
2.446 lemma mult_le_cancel1 [simp]: "(k * (m::nat) \<le> k * n) = (0 < k --> m \<le> n)"
2.447 -by (simp add: linorder_not_less [symmetric], auto)
2.448 + by (simp add: linorder_not_less [symmetric], auto)
2.449
2.450 lemma mult_le_cancel2 [simp]: "((m::nat) * k \<le> n * k) = (0 < k --> m \<le> n)"
2.451 -by (simp add: linorder_not_less [symmetric], auto)
2.452 + by (simp add: linorder_not_less [symmetric], auto)
2.453
2.454 lemma mult_cancel2 [simp]: "(m * k = n * k) = (m = n | (k = (0::nat)))"
2.455 apply (cut_tac less_linear, safe, auto)
2.456 @@ -1068,24 +1076,23 @@
2.457
2.458 subsection {* Code generator setup *}
2.459
2.460 -lemma one_is_Suc_zero [code inline]:
2.461 - "1 = Suc 0"
2.462 +lemma one_is_Suc_zero [code inline]: "1 = Suc 0"
2.463 by simp
2.464
2.465 instance nat :: eq ..
2.466
2.467 lemma [code func]:
2.468 - "(0\<Colon>nat) = 0 \<longleftrightarrow> True"
2.469 - "Suc n = Suc m \<longleftrightarrow> n = m"
2.470 - "Suc n = 0 \<longleftrightarrow> False"
2.471 - "0 = Suc m \<longleftrightarrow> False"
2.472 + "(0\<Colon>nat) = 0 \<longleftrightarrow> True"
2.473 + "Suc n = Suc m \<longleftrightarrow> n = m"
2.474 + "Suc n = 0 \<longleftrightarrow> False"
2.475 + "0 = Suc m \<longleftrightarrow> False"
2.476 by auto
2.477
2.478 lemma [code func]:
2.479 - "(0\<Colon>nat) \<le> m \<longleftrightarrow> True"
2.480 - "Suc (n\<Colon>nat) \<le> m \<longleftrightarrow> n < m"
2.481 - "(n\<Colon>nat) < 0 \<longleftrightarrow> False"
2.482 - "(n\<Colon>nat) < Suc m \<longleftrightarrow> n \<le> m"
2.483 + "(0\<Colon>nat) \<le> m \<longleftrightarrow> True"
2.484 + "Suc (n\<Colon>nat) \<le> m \<longleftrightarrow> n < m"
2.485 + "(n\<Colon>nat) < 0 \<longleftrightarrow> False"
2.486 + "(n\<Colon>nat) < Suc m \<longleftrightarrow> n \<le> m"
2.487 using Suc_le_eq less_Suc_eq_le by simp_all
2.488
2.489
2.490 @@ -1100,14 +1107,12 @@
2.491 by (auto simp: le_eq_less_or_eq dest: less_imp_Suc_add)
2.492
2.493 lemma pred_nat_trancl_eq_le: "((m, n) : pred_nat^*) = (m \<le> n)"
2.494 -by (simp add: less_eq reflcl_trancl [symmetric]
2.495 - del: reflcl_trancl, arith)
2.496 + by (simp add: less_eq reflcl_trancl [symmetric] del: reflcl_trancl, arith)
2.497
2.498 lemma nat_diff_split:
2.499 - "P(a - b::nat) = ((a<b --> P 0) & (ALL d. a = b + d --> P d))"
2.500 + "P(a - b::nat) = ((a<b --> P 0) & (ALL d. a = b + d --> P d))"
2.501 -- {* elimination of @{text -} on @{text nat} *}
2.502 - by (cases "a<b" rule: case_split)
2.503 - (auto simp add: diff_is_0_eq [THEN iffD2])
2.504 + by (cases "a<b" rule: case_split) (auto simp add: diff_is_0_eq [THEN iffD2])
2.505
2.506 lemma nat_diff_split_asm:
2.507 "P(a - b::nat) = (~ (a < b & ~ P 0 | (EX d. a = b + d & ~ P d)))"
2.508 @@ -1117,7 +1122,6 @@
2.509 lemmas [arith_split] = nat_diff_split split_min split_max
2.510
2.511
2.512 -
2.513 lemma le_square: "m \<le> m * (m::nat)"
2.514 by (induct m) auto
2.515
2.516 @@ -1128,81 +1132,81 @@
2.517 text{*Subtraction laws, mostly by Clemens Ballarin*}
2.518
2.519 lemma diff_less_mono: "[| a < (b::nat); c \<le> a |] ==> a-c < b-c"
2.520 -by arith
2.521 + by arith
2.522
2.523 lemma less_diff_conv: "(i < j-k) = (i+k < (j::nat))"
2.524 -by arith
2.525 + by arith
2.526
2.527 lemma le_diff_conv: "(j-k \<le> (i::nat)) = (j \<le> i+k)"
2.528 -by arith
2.529 + by arith
2.530
2.531 lemma le_diff_conv2: "k \<le> j ==> (i \<le> j-k) = (i+k \<le> (j::nat))"
2.532 -by arith
2.533 + by arith
2.534
2.535 lemma diff_diff_cancel [simp]: "i \<le> (n::nat) ==> n - (n - i) = i"
2.536 -by arith
2.537 + by arith
2.538
2.539 lemma le_add_diff: "k \<le> (n::nat) ==> m \<le> n + m - k"
2.540 -by arith
2.541 + by arith
2.542
2.543 (*Replaces the previous diff_less and le_diff_less, which had the stronger
2.544 second premise n\<le>m*)
2.545 lemma diff_less[simp]: "!!m::nat. [| 0<n; 0<m |] ==> m - n < m"
2.546 -by arith
2.547 + by arith
2.548
2.549
2.550 (** Simplification of relational expressions involving subtraction **)
2.551
2.552 lemma diff_diff_eq: "[| k \<le> m; k \<le> (n::nat) |] ==> ((m-k) - (n-k)) = (m-n)"
2.553 -by (simp split add: nat_diff_split)
2.554 + by (simp split add: nat_diff_split)
2.555
2.556 lemma eq_diff_iff: "[| k \<le> m; k \<le> (n::nat) |] ==> (m-k = n-k) = (m=n)"
2.557 -by (auto split add: nat_diff_split)
2.558 + by (auto split add: nat_diff_split)
2.559
2.560 lemma less_diff_iff: "[| k \<le> m; k \<le> (n::nat) |] ==> (m-k < n-k) = (m<n)"
2.561 -by (auto split add: nat_diff_split)
2.562 + by (auto split add: nat_diff_split)
2.563
2.564 lemma le_diff_iff: "[| k \<le> m; k \<le> (n::nat) |] ==> (m-k \<le> n-k) = (m\<le>n)"
2.565 -by (auto split add: nat_diff_split)
2.566 + by (auto split add: nat_diff_split)
2.567
2.568
2.569 text{*(Anti)Monotonicity of subtraction -- by Stephan Merz*}
2.570
2.571 (* Monotonicity of subtraction in first argument *)
2.572 lemma diff_le_mono: "m \<le> (n::nat) ==> (m-l) \<le> (n-l)"
2.573 -by (simp split add: nat_diff_split)
2.574 + by (simp split add: nat_diff_split)
2.575
2.576 lemma diff_le_mono2: "m \<le> (n::nat) ==> (l-n) \<le> (l-m)"
2.577 -by (simp split add: nat_diff_split)
2.578 + by (simp split add: nat_diff_split)
2.579
2.580 lemma diff_less_mono2: "[| m < (n::nat); m<l |] ==> (l-n) < (l-m)"
2.581 -by (simp split add: nat_diff_split)
2.582 + by (simp split add: nat_diff_split)
2.583
2.584 lemma diffs0_imp_equal: "!!m::nat. [| m-n = 0; n-m = 0 |] ==> m=n"
2.585 -by (simp split add: nat_diff_split)
2.586 + by (simp split add: nat_diff_split)
2.587
2.588 text{*Lemmas for ex/Factorization*}
2.589
2.590 lemma one_less_mult: "[| Suc 0 < n; Suc 0 < m |] ==> Suc 0 < m*n"
2.591 -by (case_tac "m", auto)
2.592 + by (cases m) auto
2.593
2.594 lemma n_less_m_mult_n: "[| Suc 0 < n; Suc 0 < m |] ==> n<m*n"
2.595 -by (case_tac "m", auto)
2.596 + by (cases m) auto
2.597
2.598 lemma n_less_n_mult_m: "[| Suc 0 < n; Suc 0 < m |] ==> n<n*m"
2.599 -by (case_tac "m", auto)
2.600 + by (cases m) auto
2.601
2.602
2.603 text{*Rewriting to pull differences out*}
2.604
2.605 lemma diff_diff_right [simp]: "k\<le>j --> i - (j - k) = i + (k::nat) - j"
2.606 -by arith
2.607 + by arith
2.608
2.609 lemma diff_Suc_diff_eq1 [simp]: "k \<le> j ==> m - Suc (j - k) = m + k - Suc j"
2.610 -by arith
2.611 + by arith
2.612
2.613 lemma diff_Suc_diff_eq2 [simp]: "k \<le> j ==> Suc (j - k) - m = Suc j - (k + m)"
2.614 -by arith
2.615 + by arith
2.616
2.617 (*The others are
2.618 i - j - k = i - (j + k),
2.619 @@ -1245,8 +1249,9 @@
2.620 val diff_Suc_diff_eq2 = thm "diff_Suc_diff_eq2";
2.621 *}
2.622
2.623 -subsection{*Embedding of the Naturals into any @{text
2.624 -semiring_1_cancel}: @{term of_nat}*}
2.625 +
2.626 +subsection{*Embedding of the Naturals into any
2.627 + @{text semiring_1_cancel}: @{term of_nat}*}
2.628
2.629 consts of_nat :: "nat => 'a::semiring_1_cancel"
2.630
2.631 @@ -1255,74 +1260,72 @@
2.632 of_nat_Suc: "of_nat (Suc m) = of_nat m + 1"
2.633
2.634 lemma of_nat_1 [simp]: "of_nat 1 = 1"
2.635 -by simp
2.636 + by simp
2.637
2.638 lemma of_nat_add [simp]: "of_nat (m+n) = of_nat m + of_nat n"
2.639 -apply (induct m)
2.640 -apply (simp_all add: add_ac)
2.641 -done
2.642 + by (induct m) (simp_all add: add_ac)
2.643
2.644 lemma of_nat_mult [simp]: "of_nat (m*n) = of_nat m * of_nat n"
2.645 -apply (induct m)
2.646 -apply (simp_all add: add_ac left_distrib)
2.647 -done
2.648 + by (induct m) (simp_all add: add_ac left_distrib)
2.649
2.650 lemma zero_le_imp_of_nat: "0 \<le> (of_nat m::'a::ordered_semidom)"
2.651 -apply (induct m, simp_all)
2.652 -apply (erule order_trans)
2.653 -apply (rule less_add_one [THEN order_less_imp_le])
2.654 -done
2.655 + apply (induct m, simp_all)
2.656 + apply (erule order_trans)
2.657 + apply (rule less_add_one [THEN order_less_imp_le])
2.658 + done
2.659
2.660 lemma less_imp_of_nat_less:
2.661 - "m < n ==> of_nat m < (of_nat n::'a::ordered_semidom)"
2.662 -apply (induct m n rule: diff_induct, simp_all)
2.663 -apply (insert add_le_less_mono [OF zero_le_imp_of_nat zero_less_one], force)
2.664 -done
2.665 + "m < n ==> of_nat m < (of_nat n::'a::ordered_semidom)"
2.666 + apply (induct m n rule: diff_induct, simp_all)
2.667 + apply (insert add_le_less_mono [OF zero_le_imp_of_nat zero_less_one], force)
2.668 + done
2.669
2.670 lemma of_nat_less_imp_less:
2.671 - "of_nat m < (of_nat n::'a::ordered_semidom) ==> m < n"
2.672 -apply (induct m n rule: diff_induct, simp_all)
2.673 -apply (insert zero_le_imp_of_nat)
2.674 -apply (force simp add: linorder_not_less [symmetric])
2.675 -done
2.676 + "of_nat m < (of_nat n::'a::ordered_semidom) ==> m < n"
2.677 + apply (induct m n rule: diff_induct, simp_all)
2.678 + apply (insert zero_le_imp_of_nat)
2.679 + apply (force simp add: linorder_not_less [symmetric])
2.680 + done
2.681
2.682 lemma of_nat_less_iff [simp]:
2.683 - "(of_nat m < (of_nat n::'a::ordered_semidom)) = (m<n)"
2.684 -by (blast intro: of_nat_less_imp_less less_imp_of_nat_less)
2.685 + "(of_nat m < (of_nat n::'a::ordered_semidom)) = (m<n)"
2.686 + by (blast intro: of_nat_less_imp_less less_imp_of_nat_less)
2.687
2.688 text{*Special cases where either operand is zero*}
2.689 -lemmas of_nat_0_less_iff = of_nat_less_iff [of 0, simplified]
2.690 -lemmas of_nat_less_0_iff = of_nat_less_iff [of _ 0, simplified]
2.691 -declare of_nat_0_less_iff [simp]
2.692 -declare of_nat_less_0_iff [simp]
2.693 +
2.694 +lemma of_nat_0_less_iff [simp]: "((0::'a::ordered_semidom) < of_nat n) = (0 < n)"
2.695 + by (rule of_nat_less_iff [of 0, simplified])
2.696 +
2.697 +lemma of_nat_less_0_iff [simp]: "\<not> of_nat m < (0::'a::ordered_semidom)"
2.698 + by (rule of_nat_less_iff [of _ 0, simplified])
2.699
2.700 lemma of_nat_le_iff [simp]:
2.701 - "(of_nat m \<le> (of_nat n::'a::ordered_semidom)) = (m \<le> n)"
2.702 -by (simp add: linorder_not_less [symmetric])
2.703 + "(of_nat m \<le> (of_nat n::'a::ordered_semidom)) = (m \<le> n)"
2.704 + by (simp add: linorder_not_less [symmetric])
2.705
2.706 text{*Special cases where either operand is zero*}
2.707 -lemmas of_nat_0_le_iff = of_nat_le_iff [of 0, simplified]
2.708 -lemmas of_nat_le_0_iff = of_nat_le_iff [of _ 0, simplified]
2.709 -declare of_nat_0_le_iff [simp]
2.710 -declare of_nat_le_0_iff [simp]
2.711 +lemma of_nat_0_le_iff [simp]: "(0::'a::ordered_semidom) \<le> of_nat n"
2.712 + by (rule of_nat_le_iff [of 0, simplified])
2.713 +lemma of_nat_le_0_iff [simp]: "(of_nat m \<le> (0::'a::ordered_semidom)) = (m = 0)"
2.714 + by (rule of_nat_le_iff [of _ 0, simplified])
2.715
2.716 text{*The ordering on the @{text semiring_1_cancel} is necessary
2.717 to exclude the possibility of a finite field, which indeed wraps back to
2.718 zero.*}
2.719 lemma of_nat_eq_iff [simp]:
2.720 - "(of_nat m = (of_nat n::'a::ordered_semidom)) = (m = n)"
2.721 -by (simp add: order_eq_iff)
2.722 + "(of_nat m = (of_nat n::'a::ordered_semidom)) = (m = n)"
2.723 + by (simp add: order_eq_iff)
2.724
2.725 text{*Special cases where either operand is zero*}
2.726 -lemmas of_nat_0_eq_iff = of_nat_eq_iff [of 0, simplified]
2.727 -lemmas of_nat_eq_0_iff = of_nat_eq_iff [of _ 0, simplified]
2.728 -declare of_nat_0_eq_iff [simp]
2.729 -declare of_nat_eq_0_iff [simp]
2.730 +lemma of_nat_0_eq_iff [simp]: "((0::'a::ordered_semidom) = of_nat n) = (0 = n)"
2.731 + by (rule of_nat_eq_iff [of 0, simplified])
2.732 +lemma of_nat_eq_0_iff [simp]: "(of_nat m = (0::'a::ordered_semidom)) = (m = 0)"
2.733 + by (rule of_nat_eq_iff [of _ 0, simplified])
2.734
2.735 lemma of_nat_diff [simp]:
2.736 - "n \<le> m ==> of_nat (m - n) = of_nat m - (of_nat n :: 'a::ring_1)"
2.737 -by (simp del: of_nat_add
2.738 - add: compare_rls of_nat_add [symmetric] split add: nat_diff_split)
2.739 + "n \<le> m ==> of_nat (m - n) = of_nat m - (of_nat n :: 'a::ring_1)"
2.740 + by (simp del: of_nat_add
2.741 + add: compare_rls of_nat_add [symmetric] split add: nat_diff_split)
2.742
2.743 instance nat :: distrib_lattice
2.744 "inf \<equiv> min"
2.745 @@ -1332,7 +1335,7 @@
2.746
2.747 subsection {* Size function *}
2.748
2.749 -lemma nat_size[simp]: "size (n::nat) = n"
2.750 +lemma nat_size [simp]: "size (n::nat) = n"
2.751 by (induct n) simp_all
2.752
2.753 end