author wenzelm Tue Apr 17 00:30:44 2007 +0200 (2007-04-17) changeset 22718 936f7580937d parent 22717 74dbc7696083 child 22719 c51667189bd3
tuned proofs;
 src/HOL/Divides.thy file | annotate | diff | revisions src/HOL/Nat.thy file | annotate | diff | revisions
```     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.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.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.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.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.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.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.113
1.114  lemma mod_mult_self1 [simp]: "(m + k*n) mod n = m mod (n::nat)"
1.115 -apply (induct "k")
1.117 -done
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.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.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.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.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.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.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.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.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.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.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.296 -done
1.297 +  apply (rule leI)
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.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.357 -done
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.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.404
1.405  (*NOT suitable for rewriting: the RHS has an instance of the LHS*)
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.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.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.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.445 -done
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.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.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.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.521
1.522  lemma div_mult_self1 [simp]: "!!n::nat. 0<n ==> (m + k*n) div n = k + m div n"
1.524 -apply (subst div_mult1_eq, simp)
1.525 -done
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.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.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.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.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.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.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.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.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.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.825 -done
1.826 +  apply (unfold dvd_def)
1.827 +  apply (erule linorder_not_less [THEN iffD2, THEN add_diff_inverse, THEN subst])
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.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.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.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.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.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.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.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.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.251 -done
2.252 +  apply (induct k)
2.253 +   apply simp
2.254 +  apply(drule comp_inj_on[OF _ inj_Suc])
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.274 -  apply (blast elim!: less_SucE
2.275 +  apply (blast elim!: less_SucE
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.285    done
2.286
2.287 @@ -777,22 +778,22 @@
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.326    apply (blast intro!: lt_mono)
2.327    done
2.328 @@ -814,7 +817,7 @@
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.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.344    done
2.345
2.346 @@ -854,7 +857,7 @@
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.353    done
2.354
2.355 @@ -913,9 +916,7 @@
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.368
2.369  lemma le_imp_diff_is_add: "i \<le> (j::nat) ==> (j - i = k) = (j = k + i)"
2.370 -  apply safe
2.372 -  done
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.384 -  done
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.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.641 -done
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.647 -done
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.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.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