tuned proofs;
authorwenzelm
Tue Apr 17 00:30:44 2007 +0200 (2007-04-17)
changeset 22718936f7580937d
parent 22717 74dbc7696083
child 22719 c51667189bd3
tuned proofs;
src/HOL/Divides.thy
src/HOL/Nat.thy
     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