src/HOL/Int.thy
changeset 63652 804b80a80016
parent 63648 f9f3006a5579
child 64014 ca1239a3277b
     1.1 --- a/src/HOL/Int.thy	Wed Aug 10 16:55:49 2016 +0200
     1.2 +++ b/src/HOL/Int.thy	Wed Aug 10 22:03:58 2016 +0200
     1.3 @@ -6,13 +6,13 @@
     1.4  section \<open>The Integers as Equivalence Classes over Pairs of Natural Numbers\<close>
     1.5  
     1.6  theory Int
     1.7 -imports Equiv_Relations Power Quotient Fun_Def
     1.8 +  imports Equiv_Relations Power Quotient Fun_Def
     1.9  begin
    1.10  
    1.11  subsection \<open>Definition of integers as a quotient type\<close>
    1.12  
    1.13 -definition intrel :: "(nat \<times> nat) \<Rightarrow> (nat \<times> nat) \<Rightarrow> bool" where
    1.14 -  "intrel = (\<lambda>(x, y) (u, v). x + v = u + y)"
    1.15 +definition intrel :: "(nat \<times> nat) \<Rightarrow> (nat \<times> nat) \<Rightarrow> bool"
    1.16 +  where "intrel = (\<lambda>(x, y) (u, v). x + v = u + y)"
    1.17  
    1.18  lemma intrel_iff [simp]: "intrel (x, y) (u, v) \<longleftrightarrow> x + v = u + y"
    1.19    by (simp add: intrel_def)
    1.20 @@ -20,17 +20,15 @@
    1.21  quotient_type int = "nat \<times> nat" / "intrel"
    1.22    morphisms Rep_Integ Abs_Integ
    1.23  proof (rule equivpI)
    1.24 -  show "reflp intrel"
    1.25 -    unfolding reflp_def by auto
    1.26 -  show "symp intrel"
    1.27 -    unfolding symp_def by auto
    1.28 -  show "transp intrel"
    1.29 -    unfolding transp_def by auto
    1.30 +  show "reflp intrel" by (auto simp: reflp_def)
    1.31 +  show "symp intrel" by (auto simp: symp_def)
    1.32 +  show "transp intrel" by (auto simp: transp_def)
    1.33  qed
    1.34  
    1.35  lemma eq_Abs_Integ [case_names Abs_Integ, cases type: int]:
    1.36 -     "(!!x y. z = Abs_Integ (x, y) ==> P) ==> P"
    1.37 -by (induct z) auto
    1.38 +  "(\<And>x y. z = Abs_Integ (x, y) \<Longrightarrow> P) \<Longrightarrow> P"
    1.39 +  by (induct z) auto
    1.40 +
    1.41  
    1.42  subsection \<open>Integers form a commutative ring\<close>
    1.43  
    1.44 @@ -58,33 +56,31 @@
    1.45  proof (clarsimp)
    1.46    fix s t u v w x y z :: nat
    1.47    assume "s + v = u + t" and "w + z = y + x"
    1.48 -  hence "(s + v) * w + (u + t) * x + u * (w + z) + v * (y + x)
    1.49 -       = (u + t) * w + (s + v) * x + u * (y + x) + v * (w + z)"
    1.50 +  then have "(s + v) * w + (u + t) * x + u * (w + z) + v * (y + x) =
    1.51 +    (u + t) * w + (s + v) * x + u * (y + x) + v * (w + z)"
    1.52      by simp
    1.53 -  thus "(s * w + t * x) + (u * z + v * y) = (u * y + v * z) + (s * x + t * w)"
    1.54 +  then show "(s * w + t * x) + (u * z + v * y) = (u * y + v * z) + (s * x + t * w)"
    1.55      by (simp add: algebra_simps)
    1.56  qed
    1.57  
    1.58  instance
    1.59 -  by standard (transfer, clarsimp simp: algebra_simps)+
    1.60 +  by standard (transfer; clarsimp simp: algebra_simps)+
    1.61  
    1.62  end
    1.63  
    1.64 -abbreviation int :: "nat \<Rightarrow> int" where
    1.65 -  "int \<equiv> of_nat"
    1.66 +abbreviation int :: "nat \<Rightarrow> int"
    1.67 +  where "int \<equiv> of_nat"
    1.68  
    1.69  lemma int_def: "int n = Abs_Integ (n, 0)"
    1.70 -  by (induct n, simp add: zero_int.abs_eq,
    1.71 -    simp add: one_int.abs_eq plus_int.abs_eq)
    1.72 +  by (induct n) (simp add: zero_int.abs_eq, simp add: one_int.abs_eq plus_int.abs_eq)
    1.73  
    1.74 -lemma int_transfer [transfer_rule]:
    1.75 -  "(rel_fun (op =) pcr_int) (\<lambda>n. (n, 0)) int"
    1.76 -  unfolding rel_fun_def int.pcr_cr_eq cr_int_def int_def by simp
    1.77 +lemma int_transfer [transfer_rule]: "(rel_fun (op =) pcr_int) (\<lambda>n. (n, 0)) int"
    1.78 +  by (simp add: rel_fun_def int.pcr_cr_eq cr_int_def int_def)
    1.79  
    1.80 -lemma int_diff_cases:
    1.81 -  obtains (diff) m n where "z = int m - int n"
    1.82 +lemma int_diff_cases: obtains (diff) m n where "z = int m - int n"
    1.83    by transfer clarsimp
    1.84  
    1.85 +
    1.86  subsection \<open>Integers are totally ordered\<close>
    1.87  
    1.88  instantiation int :: linorder
    1.89 @@ -106,18 +102,16 @@
    1.90  instantiation int :: distrib_lattice
    1.91  begin
    1.92  
    1.93 -definition
    1.94 -  "(inf :: int \<Rightarrow> int \<Rightarrow> int) = min"
    1.95 +definition "(inf :: int \<Rightarrow> int \<Rightarrow> int) = min"
    1.96  
    1.97 -definition
    1.98 -  "(sup :: int \<Rightarrow> int \<Rightarrow> int) = max"
    1.99 +definition "(sup :: int \<Rightarrow> int \<Rightarrow> int) = max"
   1.100  
   1.101  instance
   1.102 -  by intro_classes
   1.103 -    (auto simp add: inf_int_def sup_int_def max_min_distrib2)
   1.104 +  by standard (auto simp add: inf_int_def sup_int_def max_min_distrib2)
   1.105  
   1.106  end
   1.107  
   1.108 +
   1.109  subsection \<open>Ordering properties of arithmetic operations\<close>
   1.110  
   1.111  instance int :: ordered_cancel_ab_semigroup_add
   1.112 @@ -127,46 +121,52 @@
   1.113      by transfer clarsimp
   1.114  qed
   1.115  
   1.116 -text\<open>Strict Monotonicity of Multiplication\<close>
   1.117 +text \<open>Strict Monotonicity of Multiplication.\<close>
   1.118  
   1.119 -text\<open>strict, in 1st argument; proof is by induction on k>0\<close>
   1.120 -lemma zmult_zless_mono2_lemma:
   1.121 -     "(i::int)<j ==> 0<k ==> int k * i < int k * j"
   1.122 -apply (induct k)
   1.123 -apply simp
   1.124 -apply (simp add: distrib_right)
   1.125 -apply (case_tac "k=0")
   1.126 -apply (simp_all add: add_strict_mono)
   1.127 -done
   1.128 +text \<open>Strict, in 1st argument; proof is by induction on \<open>k > 0\<close>.\<close>
   1.129 +lemma zmult_zless_mono2_lemma: "i < j \<Longrightarrow> 0 < k \<Longrightarrow> int k * i < int k * j"
   1.130 +  for i j :: int
   1.131 +proof (induct k)
   1.132 +  case 0
   1.133 +  then show ?case by simp
   1.134 +next
   1.135 +  case (Suc k)
   1.136 +  then show ?case
   1.137 +    by (cases "k = 0") (simp_all add: distrib_right add_strict_mono)
   1.138 +qed
   1.139  
   1.140 -lemma zero_le_imp_eq_int: "(0::int) \<le> k ==> \<exists>n. k = int n"
   1.141 -apply transfer
   1.142 -apply clarsimp
   1.143 -apply (rule_tac x="a - b" in exI, simp)
   1.144 -done
   1.145 +lemma zero_le_imp_eq_int: "0 \<le> k \<Longrightarrow> \<exists>n. k = int n"
   1.146 +  for k :: int
   1.147 +  apply transfer
   1.148 +  apply clarsimp
   1.149 +  apply (rule_tac x="a - b" in exI)
   1.150 +  apply simp
   1.151 +  done
   1.152  
   1.153 -lemma zero_less_imp_eq_int: "(0::int) < k ==> \<exists>n>0. k = int n"
   1.154 -apply transfer
   1.155 -apply clarsimp
   1.156 -apply (rule_tac x="a - b" in exI, simp)
   1.157 -done
   1.158 +lemma zero_less_imp_eq_int: "0 < k \<Longrightarrow> \<exists>n>0. k = int n"
   1.159 +  for k :: int
   1.160 +  apply transfer
   1.161 +  apply clarsimp
   1.162 +  apply (rule_tac x="a - b" in exI)
   1.163 +  apply simp
   1.164 +  done
   1.165  
   1.166 -lemma zmult_zless_mono2: "[| i<j;  (0::int) < k |] ==> k*i < k*j"
   1.167 -apply (drule zero_less_imp_eq_int)
   1.168 -apply (auto simp add: zmult_zless_mono2_lemma)
   1.169 -done
   1.170 +lemma zmult_zless_mono2: "i < j \<Longrightarrow> 0 < k \<Longrightarrow> k * i < k * j"
   1.171 +  for i j k :: int
   1.172 +  by (drule zero_less_imp_eq_int) (auto simp add: zmult_zless_mono2_lemma)
   1.173  
   1.174 -text\<open>The integers form an ordered integral domain\<close>
   1.175 +
   1.176 +text \<open>The integers form an ordered integral domain.\<close>
   1.177 +
   1.178  instantiation int :: linordered_idom
   1.179  begin
   1.180  
   1.181 -definition
   1.182 -  zabs_def: "\<bar>i::int\<bar> = (if i < 0 then - i else i)"
   1.183 +definition zabs_def: "\<bar>i::int\<bar> = (if i < 0 then - i else i)"
   1.184  
   1.185 -definition
   1.186 -  zsgn_def: "sgn (i::int) = (if i=0 then 0 else if 0<i then 1 else - 1)"
   1.187 +definition zsgn_def: "sgn (i::int) = (if i = 0 then 0 else if 0 < i then 1 else - 1)"
   1.188  
   1.189 -instance proof
   1.190 +instance
   1.191 +proof
   1.192    fix i j k :: int
   1.193    show "i < j \<Longrightarrow> 0 < k \<Longrightarrow> k * i < k * j"
   1.194      by (rule zmult_zless_mono2)
   1.195 @@ -178,31 +178,29 @@
   1.196  
   1.197  end
   1.198  
   1.199 -lemma zless_imp_add1_zle: "w < z \<Longrightarrow> w + (1::int) \<le> z"
   1.200 +lemma zless_imp_add1_zle: "w < z \<Longrightarrow> w + 1 \<le> z"
   1.201 +  for w z :: int
   1.202    by transfer clarsimp
   1.203  
   1.204 -lemma zless_iff_Suc_zadd:
   1.205 -  "(w :: int) < z \<longleftrightarrow> (\<exists>n. z = w + int (Suc n))"
   1.206 -apply transfer
   1.207 -apply auto
   1.208 -apply (rename_tac a b c d)
   1.209 -apply (rule_tac x="c+b - Suc(a+d)" in exI)
   1.210 -apply arith
   1.211 -done
   1.212 +lemma zless_iff_Suc_zadd: "w < z \<longleftrightarrow> (\<exists>n. z = w + int (Suc n))"
   1.213 +  for w z :: int
   1.214 +  apply transfer
   1.215 +  apply auto
   1.216 +  apply (rename_tac a b c d)
   1.217 +  apply (rule_tac x="c+b - Suc(a+d)" in exI)
   1.218 +  apply arith
   1.219 +  done
   1.220  
   1.221 -lemma zabs_less_one_iff [simp]:
   1.222 -  fixes z :: int
   1.223 -  shows "\<bar>z\<bar> < 1 \<longleftrightarrow> z = 0" (is "?P \<longleftrightarrow> ?Q")
   1.224 +lemma zabs_less_one_iff [simp]: "\<bar>z\<bar> < 1 \<longleftrightarrow> z = 0" (is "?lhs \<longleftrightarrow> ?rhs")
   1.225 +  for z :: int
   1.226  proof
   1.227 -  assume ?Q then show ?P by simp
   1.228 +  assume ?rhs
   1.229 +  then show ?lhs by simp
   1.230  next
   1.231 -  assume ?P
   1.232 -  with zless_imp_add1_zle [of "\<bar>z\<bar>" 1] have "\<bar>z\<bar> + 1 \<le> 1"
   1.233 -    by simp
   1.234 -  then have "\<bar>z\<bar> \<le> 0"
   1.235 -    by simp
   1.236 -  then show ?Q
   1.237 -    by simp
   1.238 +  assume ?lhs
   1.239 +  with zless_imp_add1_zle [of "\<bar>z\<bar>" 1] have "\<bar>z\<bar> + 1 \<le> 1" by simp
   1.240 +  then have "\<bar>z\<bar> \<le> 0" by simp
   1.241 +  then show ?rhs by simp
   1.242  qed
   1.243  
   1.244  lemmas int_distrib =
   1.245 @@ -218,9 +216,10 @@
   1.246  context ring_1
   1.247  begin
   1.248  
   1.249 -lift_definition of_int :: "int \<Rightarrow> 'a" is "\<lambda>(i, j). of_nat i - of_nat j"
   1.250 +lift_definition of_int :: "int \<Rightarrow> 'a"
   1.251 +  is "\<lambda>(i, j). of_nat i - of_nat j"
   1.252    by (clarsimp simp add: diff_eq_eq eq_diff_eq diff_add_eq
   1.253 -    of_nat_add [symmetric] simp del: of_nat_add)
   1.254 +      of_nat_add [symmetric] simp del: of_nat_add)
   1.255  
   1.256  lemma of_int_0 [simp]: "of_int 0 = 0"
   1.257    by transfer simp
   1.258 @@ -228,24 +227,24 @@
   1.259  lemma of_int_1 [simp]: "of_int 1 = 1"
   1.260    by transfer simp
   1.261  
   1.262 -lemma of_int_add [simp]: "of_int (w+z) = of_int w + of_int z"
   1.263 +lemma of_int_add [simp]: "of_int (w + z) = of_int w + of_int z"
   1.264    by transfer (clarsimp simp add: algebra_simps)
   1.265  
   1.266 -lemma of_int_minus [simp]: "of_int (-z) = - (of_int z)"
   1.267 +lemma of_int_minus [simp]: "of_int (- z) = - (of_int z)"
   1.268    by (transfer fixing: uminus) clarsimp
   1.269  
   1.270  lemma of_int_diff [simp]: "of_int (w - z) = of_int w - of_int z"
   1.271    using of_int_add [of w "- z"] by simp
   1.272  
   1.273  lemma of_int_mult [simp]: "of_int (w*z) = of_int w * of_int z"
   1.274 -  by (transfer fixing: times) (clarsimp simp add: algebra_simps of_nat_mult)
   1.275 +  by (transfer fixing: times) (clarsimp simp add: algebra_simps)
   1.276  
   1.277  lemma mult_of_int_commute: "of_int x * y = y * of_int x"
   1.278    by (transfer fixing: times) (auto simp: algebra_simps mult_of_nat_commute)
   1.279  
   1.280 -text\<open>Collapse nested embeddings\<close>
   1.281 +text \<open>Collapse nested embeddings.\<close>
   1.282  lemma of_int_of_nat_eq [simp]: "of_int (int n) = of_nat n"
   1.283 -by (induct n) auto
   1.284 +  by (induct n) auto
   1.285  
   1.286  lemma of_int_numeral [simp, code_post]: "of_int (numeral k) = numeral k"
   1.287    by (simp add: of_nat_numeral [symmetric] of_int_of_nat_eq [symmetric])
   1.288 @@ -253,8 +252,7 @@
   1.289  lemma of_int_neg_numeral [code_post]: "of_int (- numeral k) = - numeral k"
   1.290    by simp
   1.291  
   1.292 -lemma of_int_power [simp]:
   1.293 -  "of_int (z ^ n) = of_int z ^ n"
   1.294 +lemma of_int_power [simp]: "of_int (z ^ n) = of_int z ^ n"
   1.295    by (induct n) simp_all
   1.296  
   1.297  end
   1.298 @@ -262,22 +260,17 @@
   1.299  context ring_char_0
   1.300  begin
   1.301  
   1.302 -lemma of_int_eq_iff [simp]:
   1.303 -   "of_int w = of_int z \<longleftrightarrow> w = z"
   1.304 -  by transfer (clarsimp simp add: algebra_simps
   1.305 -    of_nat_add [symmetric] simp del: of_nat_add)
   1.306 +lemma of_int_eq_iff [simp]: "of_int w = of_int z \<longleftrightarrow> w = z"
   1.307 +  by transfer (clarsimp simp add: algebra_simps of_nat_add [symmetric] simp del: of_nat_add)
   1.308  
   1.309 -text\<open>Special cases where either operand is zero\<close>
   1.310 -lemma of_int_eq_0_iff [simp]:
   1.311 -  "of_int z = 0 \<longleftrightarrow> z = 0"
   1.312 +text \<open>Special cases where either operand is zero.\<close>
   1.313 +lemma of_int_eq_0_iff [simp]: "of_int z = 0 \<longleftrightarrow> z = 0"
   1.314    using of_int_eq_iff [of z 0] by simp
   1.315  
   1.316 -lemma of_int_0_eq_iff [simp]:
   1.317 -  "0 = of_int z \<longleftrightarrow> z = 0"
   1.318 +lemma of_int_0_eq_iff [simp]: "0 = of_int z \<longleftrightarrow> z = 0"
   1.319    using of_int_eq_iff [of 0 z] by simp
   1.320  
   1.321 -lemma of_int_eq_1_iff [iff]:
   1.322 -   "of_int z = 1 \<longleftrightarrow> z = 1"
   1.323 +lemma of_int_eq_1_iff [iff]: "of_int z = 1 \<longleftrightarrow> z = 1"
   1.324    using of_int_eq_iff [of z 1] by simp
   1.325  
   1.326  end
   1.327 @@ -285,48 +278,38 @@
   1.328  context linordered_idom
   1.329  begin
   1.330  
   1.331 -text\<open>Every \<open>linordered_idom\<close> has characteristic zero.\<close>
   1.332 +text \<open>Every \<open>linordered_idom\<close> has characteristic zero.\<close>
   1.333  subclass ring_char_0 ..
   1.334  
   1.335 -lemma of_int_le_iff [simp]:
   1.336 -  "of_int w \<le> of_int z \<longleftrightarrow> w \<le> z"
   1.337 -  by (transfer fixing: less_eq) (clarsimp simp add: algebra_simps
   1.338 -    of_nat_add [symmetric] simp del: of_nat_add)
   1.339 +lemma of_int_le_iff [simp]: "of_int w \<le> of_int z \<longleftrightarrow> w \<le> z"
   1.340 +  by (transfer fixing: less_eq)
   1.341 +    (clarsimp simp add: algebra_simps of_nat_add [symmetric] simp del: of_nat_add)
   1.342  
   1.343 -lemma of_int_less_iff [simp]:
   1.344 -  "of_int w < of_int z \<longleftrightarrow> w < z"
   1.345 +lemma of_int_less_iff [simp]: "of_int w < of_int z \<longleftrightarrow> w < z"
   1.346    by (simp add: less_le order_less_le)
   1.347  
   1.348 -lemma of_int_0_le_iff [simp]:
   1.349 -  "0 \<le> of_int z \<longleftrightarrow> 0 \<le> z"
   1.350 +lemma of_int_0_le_iff [simp]: "0 \<le> of_int z \<longleftrightarrow> 0 \<le> z"
   1.351    using of_int_le_iff [of 0 z] by simp
   1.352  
   1.353 -lemma of_int_le_0_iff [simp]:
   1.354 -  "of_int z \<le> 0 \<longleftrightarrow> z \<le> 0"
   1.355 +lemma of_int_le_0_iff [simp]: "of_int z \<le> 0 \<longleftrightarrow> z \<le> 0"
   1.356    using of_int_le_iff [of z 0] by simp
   1.357  
   1.358 -lemma of_int_0_less_iff [simp]:
   1.359 -  "0 < of_int z \<longleftrightarrow> 0 < z"
   1.360 +lemma of_int_0_less_iff [simp]: "0 < of_int z \<longleftrightarrow> 0 < z"
   1.361    using of_int_less_iff [of 0 z] by simp
   1.362  
   1.363 -lemma of_int_less_0_iff [simp]:
   1.364 -  "of_int z < 0 \<longleftrightarrow> z < 0"
   1.365 +lemma of_int_less_0_iff [simp]: "of_int z < 0 \<longleftrightarrow> z < 0"
   1.366    using of_int_less_iff [of z 0] by simp
   1.367  
   1.368 -lemma of_int_1_le_iff [simp]:
   1.369 -  "1 \<le> of_int z \<longleftrightarrow> 1 \<le> z"
   1.370 +lemma of_int_1_le_iff [simp]: "1 \<le> of_int z \<longleftrightarrow> 1 \<le> z"
   1.371    using of_int_le_iff [of 1 z] by simp
   1.372  
   1.373 -lemma of_int_le_1_iff [simp]:
   1.374 -  "of_int z \<le> 1 \<longleftrightarrow> z \<le> 1"
   1.375 +lemma of_int_le_1_iff [simp]: "of_int z \<le> 1 \<longleftrightarrow> z \<le> 1"
   1.376    using of_int_le_iff [of z 1] by simp
   1.377  
   1.378 -lemma of_int_1_less_iff [simp]:
   1.379 -  "1 < of_int z \<longleftrightarrow> 1 < z"
   1.380 +lemma of_int_1_less_iff [simp]: "1 < of_int z \<longleftrightarrow> 1 < z"
   1.381    using of_int_less_iff [of 1 z] by simp
   1.382  
   1.383 -lemma of_int_less_1_iff [simp]:
   1.384 -  "of_int z < 1 \<longleftrightarrow> z < 1"
   1.385 +lemma of_int_less_1_iff [simp]: "of_int z < 1 \<longleftrightarrow> z < 1"
   1.386    using of_int_less_iff [of z 1] by simp
   1.387  
   1.388  lemma of_int_pos: "z > 0 \<Longrightarrow> of_int z > 0"
   1.389 @@ -335,15 +318,15 @@
   1.390  lemma of_int_nonneg: "z \<ge> 0 \<Longrightarrow> of_int z \<ge> 0"
   1.391    by simp
   1.392  
   1.393 -lemma of_int_abs [simp]:
   1.394 -  "of_int \<bar>x\<bar> = \<bar>of_int x\<bar>"
   1.395 +lemma of_int_abs [simp]: "of_int \<bar>x\<bar> = \<bar>of_int x\<bar>"
   1.396    by (auto simp add: abs_if)
   1.397  
   1.398  lemma of_int_lessD:
   1.399    assumes "\<bar>of_int n\<bar> < x"
   1.400    shows "n = 0 \<or> x > 1"
   1.401  proof (cases "n = 0")
   1.402 -  case True then show ?thesis by simp
   1.403 +  case True
   1.404 +  then show ?thesis by simp
   1.405  next
   1.406    case False
   1.407    then have "\<bar>n\<bar> \<noteq> 0" by simp
   1.408 @@ -360,7 +343,8 @@
   1.409    assumes "\<bar>of_int n\<bar> \<le> x"
   1.410    shows "n = 0 \<or> 1 \<le> x"
   1.411  proof (cases "n = 0")
   1.412 -  case True then show ?thesis by simp
   1.413 +  case True
   1.414 +  then show ?thesis by simp
   1.415  next
   1.416    case False
   1.417    then have "\<bar>n\<bar> \<noteq> 0" by simp
   1.418 @@ -378,40 +362,34 @@
   1.419  
   1.420  text \<open>Comparisons involving @{term of_int}.\<close>
   1.421  
   1.422 -lemma of_int_eq_numeral_iff [iff]:
   1.423 -   "of_int z = (numeral n :: 'a::ring_char_0)
   1.424 -   \<longleftrightarrow> z = numeral n"
   1.425 +lemma of_int_eq_numeral_iff [iff]: "of_int z = (numeral n :: 'a::ring_char_0) \<longleftrightarrow> z = numeral n"
   1.426    using of_int_eq_iff by fastforce
   1.427  
   1.428  lemma of_int_le_numeral_iff [simp]:
   1.429 -   "of_int z \<le> (numeral n :: 'a::linordered_idom)
   1.430 -   \<longleftrightarrow> z \<le> numeral n"
   1.431 +  "of_int z \<le> (numeral n :: 'a::linordered_idom) \<longleftrightarrow> z \<le> numeral n"
   1.432    using of_int_le_iff [of z "numeral n"] by simp
   1.433  
   1.434  lemma of_int_numeral_le_iff [simp]:
   1.435 -   "(numeral n :: 'a::linordered_idom) \<le> of_int z \<longleftrightarrow> numeral n \<le> z"
   1.436 +  "(numeral n :: 'a::linordered_idom) \<le> of_int z \<longleftrightarrow> numeral n \<le> z"
   1.437    using of_int_le_iff [of "numeral n"] by simp
   1.438  
   1.439  lemma of_int_less_numeral_iff [simp]:
   1.440 -   "of_int z < (numeral n :: 'a::linordered_idom)
   1.441 -   \<longleftrightarrow> z < numeral n"
   1.442 +  "of_int z < (numeral n :: 'a::linordered_idom) \<longleftrightarrow> z < numeral n"
   1.443    using of_int_less_iff [of z "numeral n"] by simp
   1.444  
   1.445  lemma of_int_numeral_less_iff [simp]:
   1.446 -   "(numeral n :: 'a::linordered_idom) < of_int z \<longleftrightarrow> numeral n < z"
   1.447 +  "(numeral n :: 'a::linordered_idom) < of_int z \<longleftrightarrow> numeral n < z"
   1.448    using of_int_less_iff [of "numeral n" z] by simp
   1.449  
   1.450 -lemma of_nat_less_of_int_iff:
   1.451 -  "(of_nat n::'a::linordered_idom) < of_int x \<longleftrightarrow> int n < x"
   1.452 +lemma of_nat_less_of_int_iff: "(of_nat n::'a::linordered_idom) < of_int x \<longleftrightarrow> int n < x"
   1.453    by (metis of_int_of_nat_eq of_int_less_iff)
   1.454  
   1.455  lemma of_int_eq_id [simp]: "of_int = id"
   1.456  proof
   1.457 -  fix z show "of_int z = id z"
   1.458 -    by (cases z rule: int_diff_cases, simp)
   1.459 +  show "of_int z = id z" for z
   1.460 +    by (cases z rule: int_diff_cases) simp
   1.461  qed
   1.462  
   1.463 -
   1.464  instance int :: no_top
   1.465    apply standard
   1.466    apply (rule_tac x="x + 1" in exI)
   1.467 @@ -424,6 +402,7 @@
   1.468    apply simp
   1.469    done
   1.470  
   1.471 +
   1.472  subsection \<open>Magnitude of an Integer, as a Natural Number: \<open>nat\<close>\<close>
   1.473  
   1.474  lift_definition nat :: "int \<Rightarrow> nat" is "\<lambda>(x, y). x - y"
   1.475 @@ -435,23 +414,23 @@
   1.476  lemma int_nat_eq [simp]: "int (nat z) = (if 0 \<le> z then z else 0)"
   1.477    by transfer clarsimp
   1.478  
   1.479 -corollary nat_0_le: "0 \<le> z ==> int (nat z) = z"
   1.480 -by simp
   1.481 +lemma nat_0_le: "0 \<le> z \<Longrightarrow> int (nat z) = z"
   1.482 +  by simp
   1.483  
   1.484 -lemma nat_le_0 [simp]: "z \<le> 0 ==> nat z = 0"
   1.485 +lemma nat_le_0 [simp]: "z \<le> 0 \<Longrightarrow> nat z = 0"
   1.486    by transfer clarsimp
   1.487  
   1.488 -lemma nat_le_eq_zle: "0 < w | 0 \<le> z ==> (nat w \<le> nat z) = (w\<le>z)"
   1.489 +lemma nat_le_eq_zle: "0 < w \<or> 0 \<le> z \<Longrightarrow> nat w \<le> nat z \<longleftrightarrow> w \<le> z"
   1.490    by transfer (clarsimp, arith)
   1.491  
   1.492 -text\<open>An alternative condition is @{term "0 \<le> w"}\<close>
   1.493 -corollary nat_mono_iff: "0 < z ==> (nat w < nat z) = (w < z)"
   1.494 -by (simp add: nat_le_eq_zle linorder_not_le [symmetric])
   1.495 +text \<open>An alternative condition is @{term "0 \<le> w"}.\<close>
   1.496 +lemma nat_mono_iff: "0 < z \<Longrightarrow> nat w < nat z \<longleftrightarrow> w < z"
   1.497 +  by (simp add: nat_le_eq_zle linorder_not_le [symmetric])
   1.498  
   1.499 -corollary nat_less_eq_zless: "0 \<le> w ==> (nat w < nat z) = (w<z)"
   1.500 -by (simp add: nat_le_eq_zle linorder_not_le [symmetric])
   1.501 +lemma nat_less_eq_zless: "0 \<le> w \<Longrightarrow> nat w < nat z \<longleftrightarrow> w < z"
   1.502 +  by (simp add: nat_le_eq_zle linorder_not_le [symmetric])
   1.503  
   1.504 -lemma zless_nat_conj [simp]: "(nat w < nat z) = (0 < z & w < z)"
   1.505 +lemma zless_nat_conj [simp]: "nat w < nat z \<longleftrightarrow> 0 < z \<and> w < z"
   1.506    by transfer (clarsimp, arith)
   1.507  
   1.508  lemma nonneg_eq_int:
   1.509 @@ -460,34 +439,28 @@
   1.510    shows P
   1.511    using assms by (blast dest: nat_0_le sym)
   1.512  
   1.513 -lemma nat_eq_iff:
   1.514 -  "nat w = m \<longleftrightarrow> (if 0 \<le> w then w = int m else m = 0)"
   1.515 +lemma nat_eq_iff: "nat w = m \<longleftrightarrow> (if 0 \<le> w then w = int m else m = 0)"
   1.516    by transfer (clarsimp simp add: le_imp_diff_is_add)
   1.517  
   1.518 -corollary nat_eq_iff2:
   1.519 -  "m = nat w \<longleftrightarrow> (if 0 \<le> w then w = int m else m = 0)"
   1.520 +lemma nat_eq_iff2: "m = nat w \<longleftrightarrow> (if 0 \<le> w then w = int m else m = 0)"
   1.521    using nat_eq_iff [of w m] by auto
   1.522  
   1.523 -lemma nat_0 [simp]:
   1.524 -  "nat 0 = 0"
   1.525 +lemma nat_0 [simp]: "nat 0 = 0"
   1.526    by (simp add: nat_eq_iff)
   1.527  
   1.528 -lemma nat_1 [simp]:
   1.529 -  "nat 1 = Suc 0"
   1.530 +lemma nat_1 [simp]: "nat 1 = Suc 0"
   1.531    by (simp add: nat_eq_iff)
   1.532  
   1.533 -lemma nat_numeral [simp]:
   1.534 -  "nat (numeral k) = numeral k"
   1.535 +lemma nat_numeral [simp]: "nat (numeral k) = numeral k"
   1.536    by (simp add: nat_eq_iff)
   1.537  
   1.538 -lemma nat_neg_numeral [simp]:
   1.539 -  "nat (- numeral k) = 0"
   1.540 +lemma nat_neg_numeral [simp]: "nat (- numeral k) = 0"
   1.541    by simp
   1.542  
   1.543  lemma nat_2: "nat 2 = Suc (Suc 0)"
   1.544    by simp
   1.545  
   1.546 -lemma nat_less_iff: "0 \<le> w ==> (nat w < m) = (w < of_nat m)"
   1.547 +lemma nat_less_iff: "0 \<le> w \<Longrightarrow> nat w < m \<longleftrightarrow> w < of_nat m"
   1.548    by transfer (clarsimp, arith)
   1.549  
   1.550  lemma nat_le_iff: "nat x \<le> n \<longleftrightarrow> x \<le> int n"
   1.551 @@ -496,133 +469,127 @@
   1.552  lemma nat_mono: "x \<le> y \<Longrightarrow> nat x \<le> nat y"
   1.553    by transfer auto
   1.554  
   1.555 -lemma nat_0_iff[simp]: "nat(i::int) = 0 \<longleftrightarrow> i\<le>0"
   1.556 +lemma nat_0_iff[simp]: "nat i = 0 \<longleftrightarrow> i \<le> 0"
   1.557 +  for i :: int
   1.558    by transfer clarsimp
   1.559  
   1.560 -lemma int_eq_iff: "(of_nat m = z) = (m = nat z & 0 \<le> z)"
   1.561 -by (auto simp add: nat_eq_iff2)
   1.562 +lemma int_eq_iff: "of_nat m = z \<longleftrightarrow> m = nat z \<and> 0 \<le> z"
   1.563 +  by (auto simp add: nat_eq_iff2)
   1.564  
   1.565 -lemma zero_less_nat_eq [simp]: "(0 < nat z) = (0 < z)"
   1.566 -by (insert zless_nat_conj [of 0], auto)
   1.567 +lemma zero_less_nat_eq [simp]: "0 < nat z \<longleftrightarrow> 0 < z"
   1.568 +  using zless_nat_conj [of 0] by auto
   1.569  
   1.570 -lemma nat_add_distrib:
   1.571 -  "0 \<le> z \<Longrightarrow> 0 \<le> z' \<Longrightarrow> nat (z + z') = nat z + nat z'"
   1.572 +lemma nat_add_distrib: "0 \<le> z \<Longrightarrow> 0 \<le> z' \<Longrightarrow> nat (z + z') = nat z + nat z'"
   1.573    by transfer clarsimp
   1.574  
   1.575 -lemma nat_diff_distrib':
   1.576 -  "0 \<le> x \<Longrightarrow> 0 \<le> y \<Longrightarrow> nat (x - y) = nat x - nat y"
   1.577 +lemma nat_diff_distrib': "0 \<le> x \<Longrightarrow> 0 \<le> y \<Longrightarrow> nat (x - y) = nat x - nat y"
   1.578    by transfer clarsimp
   1.579  
   1.580 -lemma nat_diff_distrib:
   1.581 -  "0 \<le> z' \<Longrightarrow> z' \<le> z \<Longrightarrow> nat (z - z') = nat z - nat z'"
   1.582 +lemma nat_diff_distrib: "0 \<le> z' \<Longrightarrow> z' \<le> z \<Longrightarrow> nat (z - z') = nat z - nat z'"
   1.583    by (rule nat_diff_distrib') auto
   1.584  
   1.585  lemma nat_zminus_int [simp]: "nat (- int n) = 0"
   1.586    by transfer simp
   1.587  
   1.588 -lemma le_nat_iff:
   1.589 -  "k \<ge> 0 \<Longrightarrow> n \<le> nat k \<longleftrightarrow> int n \<le> k"
   1.590 +lemma le_nat_iff: "k \<ge> 0 \<Longrightarrow> n \<le> nat k \<longleftrightarrow> int n \<le> k"
   1.591    by transfer auto
   1.592  
   1.593 -lemma zless_nat_eq_int_zless: "(m < nat z) = (int m < z)"
   1.594 +lemma zless_nat_eq_int_zless: "m < nat z \<longleftrightarrow> int m < z"
   1.595    by transfer (clarsimp simp add: less_diff_conv)
   1.596  
   1.597 -context ring_1
   1.598 -begin
   1.599 -
   1.600 -lemma of_nat_nat [simp]: "0 \<le> z \<Longrightarrow> of_nat (nat z) = of_int z"
   1.601 +lemma (in ring_1) of_nat_nat [simp]: "0 \<le> z \<Longrightarrow> of_nat (nat z) = of_int z"
   1.602    by transfer (clarsimp simp add: of_nat_diff)
   1.603  
   1.604 -end
   1.605 -
   1.606 -lemma diff_nat_numeral [simp]:
   1.607 -  "(numeral v :: nat) - numeral v' = nat (numeral v - numeral v')"
   1.608 +lemma diff_nat_numeral [simp]: "(numeral v :: nat) - numeral v' = nat (numeral v - numeral v')"
   1.609    by (simp only: nat_diff_distrib' zero_le_numeral nat_numeral)
   1.610  
   1.611  
   1.612  text \<open>For termination proofs:\<close>
   1.613 -lemma measure_function_int[measure_function]: "is_measure (nat o abs)" ..
   1.614 +lemma measure_function_int[measure_function]: "is_measure (nat \<circ> abs)" ..
   1.615  
   1.616  
   1.617 -subsection\<open>Lemmas about the Function @{term of_nat} and Orderings\<close>
   1.618 +subsection \<open>Lemmas about the Function @{term of_nat} and Orderings\<close>
   1.619  
   1.620  lemma negative_zless_0: "- (int (Suc n)) < (0 :: int)"
   1.621 -by (simp add: order_less_le del: of_nat_Suc)
   1.622 +  by (simp add: order_less_le del: of_nat_Suc)
   1.623  
   1.624  lemma negative_zless [iff]: "- (int (Suc n)) < int m"
   1.625 -by (rule negative_zless_0 [THEN order_less_le_trans], simp)
   1.626 +  by (rule negative_zless_0 [THEN order_less_le_trans], simp)
   1.627  
   1.628  lemma negative_zle_0: "- int n \<le> 0"
   1.629 -by (simp add: minus_le_iff)
   1.630 +  by (simp add: minus_le_iff)
   1.631  
   1.632  lemma negative_zle [iff]: "- int n \<le> int m"
   1.633 -by (rule order_trans [OF negative_zle_0 of_nat_0_le_iff])
   1.634 +  by (rule order_trans [OF negative_zle_0 of_nat_0_le_iff])
   1.635  
   1.636 -lemma not_zle_0_negative [simp]: "~ (0 \<le> - (int (Suc n)))"
   1.637 -by (subst le_minus_iff, simp del: of_nat_Suc)
   1.638 +lemma not_zle_0_negative [simp]: "\<not> 0 \<le> - int (Suc n)"
   1.639 +  by (subst le_minus_iff) (simp del: of_nat_Suc)
   1.640  
   1.641 -lemma int_zle_neg: "(int n \<le> - int m) = (n = 0 & m = 0)"
   1.642 +lemma int_zle_neg: "int n \<le> - int m \<longleftrightarrow> n = 0 \<and> m = 0"
   1.643    by transfer simp
   1.644  
   1.645 -lemma not_int_zless_negative [simp]: "~ (int n < - int m)"
   1.646 -by (simp add: linorder_not_less)
   1.647 +lemma not_int_zless_negative [simp]: "\<not> int n < - int m"
   1.648 +  by (simp add: linorder_not_less)
   1.649  
   1.650 -lemma negative_eq_positive [simp]: "(- int n = of_nat m) = (n = 0 & m = 0)"
   1.651 -by (force simp add: order_eq_iff [of "- of_nat n"] int_zle_neg)
   1.652 +lemma negative_eq_positive [simp]: "- int n = of_nat m \<longleftrightarrow> n = 0 \<and> m = 0"
   1.653 +  by (force simp add: order_eq_iff [of "- of_nat n"] int_zle_neg)
   1.654  
   1.655 -lemma zle_iff_zadd:
   1.656 -  "w \<le> z \<longleftrightarrow> (\<exists>n. z = w + int n)" (is "?P \<longleftrightarrow> ?Q")
   1.657 +lemma zle_iff_zadd: "w \<le> z \<longleftrightarrow> (\<exists>n. z = w + int n)"
   1.658 +  (is "?lhs \<longleftrightarrow> ?rhs")
   1.659  proof
   1.660 -  assume ?Q
   1.661 -  then show ?P by auto
   1.662 +  assume ?rhs
   1.663 +  then show ?lhs by auto
   1.664  next
   1.665 -  assume ?P
   1.666 +  assume ?lhs
   1.667    then have "0 \<le> z - w" by simp
   1.668    then obtain n where "z - w = int n"
   1.669      using zero_le_imp_eq_int [of "z - w"] by blast
   1.670 -  then have "z = w + int n"
   1.671 -    by simp
   1.672 -  then show ?Q ..
   1.673 +  then have "z = w + int n" by simp
   1.674 +  then show ?rhs ..
   1.675  qed
   1.676  
   1.677  lemma zadd_int_left: "int m + (int n + z) = int (m + n) + z"
   1.678 -by simp
   1.679 +  by simp
   1.680  
   1.681 -text\<open>This version is proved for all ordered rings, not just integers!
   1.682 -      It is proved here because attribute \<open>arith_split\<close> is not available
   1.683 -      in theory \<open>Rings\<close>.
   1.684 -      But is it really better than just rewriting with \<open>abs_if\<close>?\<close>
   1.685 -lemma abs_split [arith_split, no_atp]:
   1.686 -     "P \<bar>a::'a::linordered_idom\<bar> = ((0 \<le> a --> P a) & (a < 0 --> P(-a)))"
   1.687 -by (force dest: order_less_le_trans simp add: abs_if linorder_not_less)
   1.688 +text \<open>
   1.689 +  This version is proved for all ordered rings, not just integers!
   1.690 +  It is proved here because attribute \<open>arith_split\<close> is not available
   1.691 +  in theory \<open>Rings\<close>.
   1.692 +  But is it really better than just rewriting with \<open>abs_if\<close>?
   1.693 +\<close>
   1.694 +lemma abs_split [arith_split, no_atp]: "P \<bar>a\<bar> \<longleftrightarrow> (0 \<le> a \<longrightarrow> P a) \<and> (a < 0 \<longrightarrow> P (- a))"
   1.695 +  for a :: "'a::linordered_idom"
   1.696 +  by (force dest: order_less_le_trans simp add: abs_if linorder_not_less)
   1.697  
   1.698  lemma negD: "x < 0 \<Longrightarrow> \<exists>n. x = - (int (Suc n))"
   1.699 -apply transfer
   1.700 -apply clarsimp
   1.701 -apply (rule_tac x="b - Suc a" in exI, arith)
   1.702 -done
   1.703 +  apply transfer
   1.704 +  apply clarsimp
   1.705 +  apply (rule_tac x="b - Suc a" in exI)
   1.706 +  apply arith
   1.707 +  done
   1.708 +
   1.709  
   1.710  subsection \<open>Cases and induction\<close>
   1.711  
   1.712 -text\<open>Now we replace the case analysis rule by a more conventional one:
   1.713 -whether an integer is negative or not.\<close>
   1.714 +text \<open>
   1.715 +  Now we replace the case analysis rule by a more conventional one:
   1.716 +  whether an integer is negative or not.
   1.717 +\<close>
   1.718  
   1.719 -text\<open>This version is symmetric in the two subgoals.\<close>
   1.720 -theorem int_cases2 [case_names nonneg nonpos, cases type: int]:
   1.721 -  "\<lbrakk>!! n. z = int n \<Longrightarrow> P;  !! n. z = - (int n) \<Longrightarrow> P\<rbrakk> \<Longrightarrow> P"
   1.722 -apply (cases "z < 0")
   1.723 -apply (auto simp add: linorder_not_less dest!: negD nat_0_le [THEN sym])
   1.724 -done
   1.725 +text \<open>This version is symmetric in the two subgoals.\<close>
   1.726 +lemma int_cases2 [case_names nonneg nonpos, cases type: int]:
   1.727 +  "(\<And>n. z = int n \<Longrightarrow> P) \<Longrightarrow> (\<And>n. z = - (int n) \<Longrightarrow> P) \<Longrightarrow> P"
   1.728 +  by (cases "z < 0") (auto simp add: linorder_not_less dest!: negD nat_0_le [THEN sym])
   1.729  
   1.730 -text\<open>This is the default, with a negative case.\<close>
   1.731 -theorem int_cases [case_names nonneg neg, cases type: int]:
   1.732 -  "[|!! n. z = int n ==> P;  !! n. z = - (int (Suc n)) ==> P |] ==> P"
   1.733 -apply (cases "z < 0")
   1.734 -apply (blast dest!: negD)
   1.735 -apply (simp add: linorder_not_less del: of_nat_Suc)
   1.736 -apply auto
   1.737 -apply (blast dest: nat_0_le [THEN sym])
   1.738 -done
   1.739 +text \<open>This is the default, with a negative case.\<close>
   1.740 +lemma int_cases [case_names nonneg neg, cases type: int]:
   1.741 +  "(\<And>n. z = int n \<Longrightarrow> P) \<Longrightarrow> (\<And>n. z = - (int (Suc n)) \<Longrightarrow> P) \<Longrightarrow> P"
   1.742 +  apply (cases "z < 0")
   1.743 +   apply (blast dest!: negD)
   1.744 +  apply (simp add: linorder_not_less del: of_nat_Suc)
   1.745 +  apply auto
   1.746 +  apply (blast dest: nat_0_le [THEN sym])
   1.747 +  done
   1.748  
   1.749  lemma int_cases3 [case_names zero pos neg]:
   1.750    fixes k :: int
   1.751 @@ -630,7 +597,8 @@
   1.752      and "\<And>n. k = - int n \<Longrightarrow> n > 0 \<Longrightarrow> P"
   1.753    shows "P"
   1.754  proof (cases k "0::int" rule: linorder_cases)
   1.755 -  case equal with assms(1) show P by simp
   1.756 +  case equal
   1.757 +  with assms(1) show P by simp
   1.758  next
   1.759    case greater
   1.760    then have *: "nat k > 0" by simp
   1.761 @@ -643,12 +611,13 @@
   1.762    ultimately show P using assms(3) by blast
   1.763  qed
   1.764  
   1.765 -theorem int_of_nat_induct [case_names nonneg neg, induct type: int]:
   1.766 -     "[|!! n. P (int n);  !!n. P (- (int (Suc n))) |] ==> P z"
   1.767 +lemma int_of_nat_induct [case_names nonneg neg, induct type: int]:
   1.768 +  "(\<And>n. P (int n)) \<Longrightarrow> (\<And>n. P (- (int (Suc n)))) \<Longrightarrow> P z"
   1.769    by (cases z) auto
   1.770  
   1.771  lemma nonneg_int_cases:
   1.772 -  assumes "0 \<le> k" obtains n where "k = int n"
   1.773 +  assumes "0 \<le> k"
   1.774 +  obtains n where "k = int n"
   1.775    using assms by (rule nonneg_eq_int)
   1.776  
   1.777  lemma Let_numeral [simp]: "Let (numeral v) f = f (numeral v)"
   1.778 @@ -679,50 +648,54 @@
   1.779  text \<open>Preliminaries\<close>
   1.780  
   1.781  lemma le_imp_0_less:
   1.782 +  fixes z :: int
   1.783    assumes le: "0 \<le> z"
   1.784 -  shows "(0::int) < 1 + z"
   1.785 +  shows "0 < 1 + z"
   1.786  proof -
   1.787    have "0 \<le> z" by fact
   1.788 -  also have "... < z + 1" by (rule less_add_one)
   1.789 -  also have "... = 1 + z" by (simp add: ac_simps)
   1.790 +  also have "\<dots> < z + 1" by (rule less_add_one)
   1.791 +  also have "\<dots> = 1 + z" by (simp add: ac_simps)
   1.792    finally show "0 < 1 + z" .
   1.793  qed
   1.794  
   1.795 -lemma odd_less_0_iff:
   1.796 -  "(1 + z + z < 0) = (z < (0::int))"
   1.797 +lemma odd_less_0_iff: "1 + z + z < 0 \<longleftrightarrow> z < 0"
   1.798 +  for z :: int
   1.799  proof (cases z)
   1.800    case (nonneg n)
   1.801 -  thus ?thesis by (simp add: linorder_not_less add.assoc add_increasing
   1.802 -                             le_imp_0_less [THEN order_less_imp_le])
   1.803 +  then show ?thesis
   1.804 +    by (simp add: linorder_not_less add.assoc add_increasing le_imp_0_less [THEN order_less_imp_le])
   1.805  next
   1.806    case (neg n)
   1.807 -  thus ?thesis by (simp del: of_nat_Suc of_nat_add of_nat_1
   1.808 -    add: algebra_simps of_nat_1 [where 'a=int, symmetric] of_nat_add [symmetric])
   1.809 +  then show ?thesis
   1.810 +    by (simp del: of_nat_Suc of_nat_add of_nat_1
   1.811 +        add: algebra_simps of_nat_1 [where 'a=int, symmetric] of_nat_add [symmetric])
   1.812  qed
   1.813  
   1.814 +
   1.815  subsubsection \<open>Comparisons, for Ordered Rings\<close>
   1.816  
   1.817  lemmas double_eq_0_iff = double_zero
   1.818  
   1.819 -lemma odd_nonzero:
   1.820 -  "1 + z + z \<noteq> (0::int)"
   1.821 +lemma odd_nonzero: "1 + z + z \<noteq> 0"
   1.822 +  for z :: int
   1.823  proof (cases z)
   1.824    case (nonneg n)
   1.825 -  have le: "0 \<le> z+z" by (simp add: nonneg add_increasing)
   1.826 -  thus ?thesis using  le_imp_0_less [OF le]
   1.827 -    by (auto simp add: add.assoc)
   1.828 +  have le: "0 \<le> z + z"
   1.829 +    by (simp add: nonneg add_increasing)
   1.830 +  then show ?thesis
   1.831 +    using  le_imp_0_less [OF le] by (auto simp: add.assoc)
   1.832  next
   1.833    case (neg n)
   1.834    show ?thesis
   1.835    proof
   1.836      assume eq: "1 + z + z = 0"
   1.837 -    have "(0::int) < 1 + (int n + int n)"
   1.838 +    have "0 < 1 + (int n + int n)"
   1.839        by (simp add: le_imp_0_less add_increasing)
   1.840 -    also have "... = - (1 + z + z)"
   1.841 +    also have "\<dots> = - (1 + z + z)"
   1.842        by (simp add: neg add.assoc [symmetric])
   1.843 -    also have "... = 0" by (simp add: eq)
   1.844 +    also have "\<dots> = 0" by (simp add: eq)
   1.845      finally have "0<0" ..
   1.846 -    thus False by blast
   1.847 +    then show False by blast
   1.848    qed
   1.849  qed
   1.850  
   1.851 @@ -751,31 +724,31 @@
   1.852    by (subst of_nat_numeral [symmetric], rule Ints_of_nat)
   1.853  
   1.854  lemma Ints_add [simp]: "a \<in> \<int> \<Longrightarrow> b \<in> \<int> \<Longrightarrow> a + b \<in> \<int>"
   1.855 -apply (auto simp add: Ints_def)
   1.856 -apply (rule range_eqI)
   1.857 -apply (rule of_int_add [symmetric])
   1.858 -done
   1.859 +  apply (auto simp add: Ints_def)
   1.860 +  apply (rule range_eqI)
   1.861 +  apply (rule of_int_add [symmetric])
   1.862 +  done
   1.863  
   1.864  lemma Ints_minus [simp]: "a \<in> \<int> \<Longrightarrow> -a \<in> \<int>"
   1.865 -apply (auto simp add: Ints_def)
   1.866 -apply (rule range_eqI)
   1.867 -apply (rule of_int_minus [symmetric])
   1.868 -done
   1.869 +  apply (auto simp add: Ints_def)
   1.870 +  apply (rule range_eqI)
   1.871 +  apply (rule of_int_minus [symmetric])
   1.872 +  done
   1.873  
   1.874  lemma Ints_diff [simp]: "a \<in> \<int> \<Longrightarrow> b \<in> \<int> \<Longrightarrow> a - b \<in> \<int>"
   1.875 -apply (auto simp add: Ints_def)
   1.876 -apply (rule range_eqI)
   1.877 -apply (rule of_int_diff [symmetric])
   1.878 -done
   1.879 +  apply (auto simp add: Ints_def)
   1.880 +  apply (rule range_eqI)
   1.881 +  apply (rule of_int_diff [symmetric])
   1.882 +  done
   1.883  
   1.884  lemma Ints_mult [simp]: "a \<in> \<int> \<Longrightarrow> b \<in> \<int> \<Longrightarrow> a * b \<in> \<int>"
   1.885 -apply (auto simp add: Ints_def)
   1.886 -apply (rule range_eqI)
   1.887 -apply (rule of_int_mult [symmetric])
   1.888 -done
   1.889 +  apply (auto simp add: Ints_def)
   1.890 +  apply (rule range_eqI)
   1.891 +  apply (rule of_int_mult [symmetric])
   1.892 +  done
   1.893  
   1.894  lemma Ints_power [simp]: "a \<in> \<int> \<Longrightarrow> a ^ n \<in> \<int>"
   1.895 -by (induct n) simp_all
   1.896 +  by (induct n) simp_all
   1.897  
   1.898  lemma Ints_cases [cases set: Ints]:
   1.899    assumes "q \<in> \<int>"
   1.900 @@ -797,16 +770,22 @@
   1.901  
   1.902  lemma Nats_altdef1: "\<nat> = {of_int n |n. n \<ge> 0}"
   1.903  proof (intro subsetI equalityI)
   1.904 -  fix x :: 'a assume "x \<in> {of_int n |n. n \<ge> 0}"
   1.905 -  then obtain n where "x = of_int n" "n \<ge> 0" by (auto elim!: Ints_cases)
   1.906 -  hence "x = of_nat (nat n)" by (subst of_nat_nat) simp_all
   1.907 -  thus "x \<in> \<nat>" by simp
   1.908 +  fix x :: 'a
   1.909 +  assume "x \<in> {of_int n |n. n \<ge> 0}"
   1.910 +  then obtain n where "x = of_int n" "n \<ge> 0"
   1.911 +    by (auto elim!: Ints_cases)
   1.912 +  then have "x = of_nat (nat n)"
   1.913 +    by (subst of_nat_nat) simp_all
   1.914 +  then show "x \<in> \<nat>"
   1.915 +    by simp
   1.916  next
   1.917 -  fix x :: 'a assume "x \<in> \<nat>"
   1.918 -  then obtain n where "x = of_nat n" by (auto elim!: Nats_cases)
   1.919 -  hence "x = of_int (int n)" by simp
   1.920 +  fix x :: 'a
   1.921 +  assume "x \<in> \<nat>"
   1.922 +  then obtain n where "x = of_nat n"
   1.923 +    by (auto elim!: Nats_cases)
   1.924 +  then have "x = of_int (int n)" by simp
   1.925    also have "int n \<ge> 0" by simp
   1.926 -  hence "of_int (int n) \<in> {of_int n |n. n \<ge> 0}" by blast
   1.927 +  then have "of_int (int n) \<in> {of_int n |n. n \<ge> 0}" by blast
   1.928    finally show "x \<in> {of_int n |n. n \<ge> 0}" .
   1.929  qed
   1.930  
   1.931 @@ -814,45 +793,54 @@
   1.932  
   1.933  lemma (in linordered_idom) Nats_altdef2: "\<nat> = {n \<in> \<int>. n \<ge> 0}"
   1.934  proof (intro subsetI equalityI)
   1.935 -  fix x :: 'a assume "x \<in> {n \<in> \<int>. n \<ge> 0}"
   1.936 -  then obtain n where "x = of_int n" "n \<ge> 0" by (auto elim!: Ints_cases)
   1.937 -  hence "x = of_nat (nat n)" by (subst of_nat_nat) simp_all
   1.938 -  thus "x \<in> \<nat>" by simp
   1.939 +  fix x :: 'a
   1.940 +  assume "x \<in> {n \<in> \<int>. n \<ge> 0}"
   1.941 +  then obtain n where "x = of_int n" "n \<ge> 0"
   1.942 +    by (auto elim!: Ints_cases)
   1.943 +  then have "x = of_nat (nat n)"
   1.944 +    by (subst of_nat_nat) simp_all
   1.945 +  then show "x \<in> \<nat>"
   1.946 +    by simp
   1.947  qed (auto elim!: Nats_cases)
   1.948  
   1.949  
   1.950  text \<open>The premise involving @{term Ints} prevents @{term "a = 1/2"}.\<close>
   1.951  
   1.952  lemma Ints_double_eq_0_iff:
   1.953 +  fixes a :: "'a::ring_char_0"
   1.954    assumes in_Ints: "a \<in> \<int>"
   1.955 -  shows "(a + a = 0) = (a = (0::'a::ring_char_0))"
   1.956 +  shows "a + a = 0 \<longleftrightarrow> a = 0"
   1.957 +    (is "?lhs \<longleftrightarrow> ?rhs")
   1.958  proof -
   1.959 -  from in_Ints have "a \<in> range of_int" unfolding Ints_def [symmetric] .
   1.960 +  from in_Ints have "a \<in> range of_int"
   1.961 +    unfolding Ints_def [symmetric] .
   1.962    then obtain z where a: "a = of_int z" ..
   1.963    show ?thesis
   1.964    proof
   1.965 -    assume "a = 0"
   1.966 -    thus "a + a = 0" by simp
   1.967 +    assume ?rhs
   1.968 +    then show ?lhs by simp
   1.969    next
   1.970 -    assume eq: "a + a = 0"
   1.971 -    hence "of_int (z + z) = (of_int 0 :: 'a)" by (simp add: a)
   1.972 -    hence "z + z = 0" by (simp only: of_int_eq_iff)
   1.973 -    hence "z = 0" by (simp only: double_eq_0_iff)
   1.974 -    thus "a = 0" by (simp add: a)
   1.975 +    assume ?lhs
   1.976 +    with a have "of_int (z + z) = (of_int 0 :: 'a)" by simp
   1.977 +    then have "z + z = 0" by (simp only: of_int_eq_iff)
   1.978 +    then have "z = 0" by (simp only: double_eq_0_iff)
   1.979 +    with a show ?rhs by simp
   1.980    qed
   1.981  qed
   1.982  
   1.983  lemma Ints_odd_nonzero:
   1.984 +  fixes a :: "'a::ring_char_0"
   1.985    assumes in_Ints: "a \<in> \<int>"
   1.986 -  shows "1 + a + a \<noteq> (0::'a::ring_char_0)"
   1.987 +  shows "1 + a + a \<noteq> 0"
   1.988  proof -
   1.989 -  from in_Ints have "a \<in> range of_int" unfolding Ints_def [symmetric] .
   1.990 +  from in_Ints have "a \<in> range of_int"
   1.991 +    unfolding Ints_def [symmetric] .
   1.992    then obtain z where a: "a = of_int z" ..
   1.993    show ?thesis
   1.994    proof
   1.995 -    assume eq: "1 + a + a = 0"
   1.996 -    hence "of_int (1 + z + z) = (of_int 0 :: 'a)" by (simp add: a)
   1.997 -    hence "1 + z + z = 0" by (simp only: of_int_eq_iff)
   1.998 +    assume "1 + a + a = 0"
   1.999 +    with a have "of_int (1 + z + z) = (of_int 0 :: 'a)" by simp
  1.1000 +    then have "1 + z + z = 0" by (simp only: of_int_eq_iff)
  1.1001      with odd_nonzero show False by blast
  1.1002    qed
  1.1003  qed
  1.1004 @@ -861,15 +849,19 @@
  1.1005    using of_nat_in_Nats [of "numeral w"] by simp
  1.1006  
  1.1007  lemma Ints_odd_less_0:
  1.1008 +  fixes a :: "'a::linordered_idom"
  1.1009    assumes in_Ints: "a \<in> \<int>"
  1.1010 -  shows "(1 + a + a < 0) = (a < (0::'a::linordered_idom))"
  1.1011 +  shows "1 + a + a < 0 \<longleftrightarrow> a < 0"
  1.1012  proof -
  1.1013 -  from in_Ints have "a \<in> range of_int" unfolding Ints_def [symmetric] .
  1.1014 +  from in_Ints have "a \<in> range of_int"
  1.1015 +    unfolding Ints_def [symmetric] .
  1.1016    then obtain z where a: "a = of_int z" ..
  1.1017 -  hence "((1::'a) + a + a < 0) = (of_int (1 + z + z) < (of_int 0 :: 'a))"
  1.1018 +  with a have "1 + a + a < 0 \<longleftrightarrow> of_int (1 + z + z) < (of_int 0 :: 'a)"
  1.1019 +    by simp
  1.1020 +  also have "\<dots> \<longleftrightarrow> z < 0"
  1.1021 +    by (simp only: of_int_less_iff odd_less_0_iff)
  1.1022 +  also have "\<dots> \<longleftrightarrow> a < 0"
  1.1023      by (simp add: a)
  1.1024 -  also have "... = (z < 0)" by (simp only: of_int_less_iff odd_less_0_iff)
  1.1025 -  also have "... = (a < 0)" by (simp add: a)
  1.1026    finally show ?thesis .
  1.1027  qed
  1.1028  
  1.1029 @@ -877,24 +869,16 @@
  1.1030  subsection \<open>@{term setsum} and @{term setprod}\<close>
  1.1031  
  1.1032  lemma of_nat_setsum [simp]: "of_nat (setsum f A) = (\<Sum>x\<in>A. of_nat(f x))"
  1.1033 -  apply (cases "finite A")
  1.1034 -  apply (erule finite_induct, auto)
  1.1035 -  done
  1.1036 +  by (induct A rule: infinite_finite_induct) auto
  1.1037  
  1.1038  lemma of_int_setsum [simp]: "of_int (setsum f A) = (\<Sum>x\<in>A. of_int(f x))"
  1.1039 -  apply (cases "finite A")
  1.1040 -  apply (erule finite_induct, auto)
  1.1041 -  done
  1.1042 +  by (induct A rule: infinite_finite_induct) auto
  1.1043  
  1.1044  lemma of_nat_setprod [simp]: "of_nat (setprod f A) = (\<Prod>x\<in>A. of_nat(f x))"
  1.1045 -  apply (cases "finite A")
  1.1046 -  apply (erule finite_induct, auto simp add: of_nat_mult)
  1.1047 -  done
  1.1048 +  by (induct A rule: infinite_finite_induct) auto
  1.1049  
  1.1050  lemma of_int_setprod [simp]: "of_int (setprod f A) = (\<Prod>x\<in>A. of_int(f x))"
  1.1051 -  apply (cases "finite A")
  1.1052 -  apply (erule finite_induct, auto)
  1.1053 -  done
  1.1054 +  by (induct A rule: infinite_finite_induct) auto
  1.1055  
  1.1056  lemmas int_setsum = of_nat_setsum [where 'a=int]
  1.1057  lemmas int_setprod = of_nat_setprod [where 'a=int]
  1.1058 @@ -905,6 +889,7 @@
  1.1059  lemmas zle_int = of_nat_le_iff [where 'a=int]
  1.1060  lemmas int_int_eq = of_nat_eq_iff [where 'a=int]
  1.1061  
  1.1062 +
  1.1063  subsection \<open>Setting up simplification procedures\<close>
  1.1064  
  1.1065  lemmas of_int_simps =
  1.1066 @@ -913,53 +898,64 @@
  1.1067  ML_file "Tools/int_arith.ML"
  1.1068  declaration \<open>K Int_Arith.setup\<close>
  1.1069  
  1.1070 -simproc_setup fast_arith ("(m::'a::linordered_idom) < n" |
  1.1071 -  "(m::'a::linordered_idom) \<le> n" |
  1.1072 -  "(m::'a::linordered_idom) = n") =
  1.1073 +simproc_setup fast_arith
  1.1074 +  ("(m::'a::linordered_idom) < n" |
  1.1075 +    "(m::'a::linordered_idom) \<le> n" |
  1.1076 +    "(m::'a::linordered_idom) = n") =
  1.1077    \<open>K Lin_Arith.simproc\<close>
  1.1078  
  1.1079  
  1.1080  subsection\<open>More Inequality Reasoning\<close>
  1.1081  
  1.1082 -lemma zless_add1_eq: "(w < z + (1::int)) = (w<z | w=z)"
  1.1083 -by arith
  1.1084 +lemma zless_add1_eq: "w < z + 1 \<longleftrightarrow> w < z \<or> w = z"
  1.1085 +  for w z :: int
  1.1086 +  by arith
  1.1087  
  1.1088 -lemma add1_zle_eq: "(w + (1::int) \<le> z) = (w<z)"
  1.1089 -by arith
  1.1090 +lemma add1_zle_eq: "w + 1 \<le> z \<longleftrightarrow> w < z"
  1.1091 +  for w z :: int
  1.1092 +  by arith
  1.1093  
  1.1094 -lemma zle_diff1_eq [simp]: "(w \<le> z - (1::int)) = (w<z)"
  1.1095 -by arith
  1.1096 +lemma zle_diff1_eq [simp]: "w \<le> z - 1 \<longleftrightarrow> w < z"
  1.1097 +  for w z :: int
  1.1098 +  by arith
  1.1099  
  1.1100 -lemma zle_add1_eq_le [simp]: "(w < z + (1::int)) = (w\<le>z)"
  1.1101 -by arith
  1.1102 +lemma zle_add1_eq_le [simp]: "w < z + 1 \<longleftrightarrow> w \<le> z"
  1.1103 +  for w z :: int
  1.1104 +  by arith
  1.1105  
  1.1106 -lemma int_one_le_iff_zero_less: "((1::int) \<le> z) = (0 < z)"
  1.1107 -by arith
  1.1108 +lemma int_one_le_iff_zero_less: "1 \<le> z \<longleftrightarrow> 0 < z"
  1.1109 +  for z :: int
  1.1110 +  by arith
  1.1111  
  1.1112  
  1.1113 -subsection\<open>The functions @{term nat} and @{term int}\<close>
  1.1114 +subsection \<open>The functions @{term nat} and @{term int}\<close>
  1.1115  
  1.1116 -text\<open>Simplify the term @{term "w + - z"}\<close>
  1.1117 +text \<open>Simplify the term @{term "w + - z"}.\<close>
  1.1118  
  1.1119 -lemma one_less_nat_eq [simp]: "(Suc 0 < nat z) = (1 < z)"
  1.1120 +lemma one_less_nat_eq [simp]: "Suc 0 < nat z \<longleftrightarrow> 1 < z"
  1.1121    using zless_nat_conj [of 1 z] by auto
  1.1122  
  1.1123 -text\<open>This simplifies expressions of the form @{term "int n = z"} where
  1.1124 -      z is an integer literal.\<close>
  1.1125 +text \<open>
  1.1126 +  This simplifies expressions of the form @{term "int n = z"} where
  1.1127 +  \<open>z\<close> is an integer literal.
  1.1128 +\<close>
  1.1129  lemmas int_eq_iff_numeral [simp] = int_eq_iff [of _ "numeral v"] for v
  1.1130  
  1.1131 -lemma split_nat [arith_split]:
  1.1132 -  "P(nat(i::int)) = ((\<forall>n. i = int n \<longrightarrow> P n) & (i < 0 \<longrightarrow> P 0))"
  1.1133 -  (is "?P = (?L & ?R)")
  1.1134 +lemma split_nat [arith_split]: "P (nat i) = ((\<forall>n. i = int n \<longrightarrow> P n) \<and> (i < 0 \<longrightarrow> P 0))"
  1.1135 +  (is "?P = (?L \<and> ?R)")
  1.1136 +  for i :: int
  1.1137  proof (cases "i < 0")
  1.1138 -  case True thus ?thesis by auto
  1.1139 +  case True
  1.1140 +  then show ?thesis by auto
  1.1141  next
  1.1142    case False
  1.1143    have "?P = ?L"
  1.1144    proof
  1.1145 -    assume ?P thus ?L using False by clarsimp
  1.1146 +    assume ?P
  1.1147 +    then show ?L using False by auto
  1.1148    next
  1.1149 -    assume ?L thus ?P using False by simp
  1.1150 +    assume ?L
  1.1151 +    then show ?P using False by simp
  1.1152    qed
  1.1153    with False show ?thesis by simp
  1.1154  qed
  1.1155 @@ -976,11 +972,13 @@
  1.1156  lemma of_int_of_nat [nitpick_simp]:
  1.1157    "of_int k = (if k < 0 then - of_nat (nat (- k)) else of_nat (nat k))"
  1.1158  proof (cases "k < 0")
  1.1159 -  case True then have "0 \<le> - k" by simp
  1.1160 +  case True
  1.1161 +  then have "0 \<le> - k" by simp
  1.1162    then have "of_nat (nat (- k)) = of_int (- k)" by (rule of_nat_nat)
  1.1163    with True show ?thesis by simp
  1.1164  next
  1.1165 -  case False then show ?thesis by (simp add: not_less of_nat_nat)
  1.1166 +  case False
  1.1167 +  then show ?thesis by (simp add: not_less)
  1.1168  qed
  1.1169  
  1.1170  end
  1.1171 @@ -990,39 +988,39 @@
  1.1172    assumes "0 \<le> z"
  1.1173    shows "nat (z * z') = nat z * nat z'"
  1.1174  proof (cases "0 \<le> z'")
  1.1175 -  case False with assms have "z * z' \<le> 0"
  1.1176 +  case False
  1.1177 +  with assms have "z * z' \<le> 0"
  1.1178      by (simp add: not_le mult_le_0_iff)
  1.1179    then have "nat (z * z') = 0" by simp
  1.1180    moreover from False have "nat z' = 0" by simp
  1.1181    ultimately show ?thesis by simp
  1.1182  next
  1.1183 -  case True with assms have ge_0: "z * z' \<ge> 0" by (simp add: zero_le_mult_iff)
  1.1184 +  case True
  1.1185 +  with assms have ge_0: "z * z' \<ge> 0" by (simp add: zero_le_mult_iff)
  1.1186    show ?thesis
  1.1187      by (rule injD [of "of_nat :: nat \<Rightarrow> int", OF inj_of_nat])
  1.1188        (simp only: of_nat_mult of_nat_nat [OF True]
  1.1189           of_nat_nat [OF assms] of_nat_nat [OF ge_0], simp)
  1.1190  qed
  1.1191  
  1.1192 -lemma nat_mult_distrib_neg: "z \<le> (0::int) ==> nat(z*z') = nat(-z) * nat(-z')"
  1.1193 -apply (rule trans)
  1.1194 -apply (rule_tac [2] nat_mult_distrib, auto)
  1.1195 -done
  1.1196 +lemma nat_mult_distrib_neg: "z \<le> 0 \<Longrightarrow> nat (z * z') = nat (- z) * nat (- z')"
  1.1197 +  for z z' :: int
  1.1198 +  apply (rule trans)
  1.1199 +   apply (rule_tac [2] nat_mult_distrib)
  1.1200 +   apply auto
  1.1201 +  done
  1.1202  
  1.1203  lemma nat_abs_mult_distrib: "nat \<bar>w * z\<bar> = nat \<bar>w\<bar> * nat \<bar>z\<bar>"
  1.1204 -apply (cases "z=0 | w=0")
  1.1205 -apply (auto simp add: abs_if nat_mult_distrib [symmetric]
  1.1206 -                      nat_mult_distrib_neg [symmetric] mult_less_0_iff)
  1.1207 -done
  1.1208 +  by (cases "z = 0 \<or> w = 0")
  1.1209 +    (auto simp add: abs_if nat_mult_distrib [symmetric]
  1.1210 +      nat_mult_distrib_neg [symmetric] mult_less_0_iff)
  1.1211  
  1.1212 -lemma int_in_range_abs [simp]:
  1.1213 -  "int n \<in> range abs"
  1.1214 +lemma int_in_range_abs [simp]: "int n \<in> range abs"
  1.1215  proof (rule range_eqI)
  1.1216 -  show "int n = \<bar>int n\<bar>"
  1.1217 -    by simp
  1.1218 +  show "int n = \<bar>int n\<bar>" by simp
  1.1219  qed
  1.1220  
  1.1221 -lemma range_abs_Nats [simp]:
  1.1222 -  "range abs = (\<nat> :: int set)"
  1.1223 +lemma range_abs_Nats [simp]: "range abs = (\<nat> :: int set)"
  1.1224  proof -
  1.1225    have "\<bar>k\<bar> \<in> \<nat>" for k :: int
  1.1226      by (cases k) simp_all
  1.1227 @@ -1031,130 +1029,123 @@
  1.1228    ultimately show ?thesis by blast
  1.1229  qed
  1.1230  
  1.1231 -lemma Suc_nat_eq_nat_zadd1: "(0::int) <= z ==> Suc (nat z) = nat (1 + z)"
  1.1232 -apply (rule sym)
  1.1233 -apply (simp add: nat_eq_iff)
  1.1234 -done
  1.1235 +lemma Suc_nat_eq_nat_zadd1: "0 \<le> z \<Longrightarrow> Suc (nat z) = nat (1 + z)"
  1.1236 +  for z :: int
  1.1237 +  by (rule sym) (simp add: nat_eq_iff)
  1.1238  
  1.1239  lemma diff_nat_eq_if:
  1.1240 -     "nat z - nat z' =
  1.1241 -        (if z' < 0 then nat z
  1.1242 -         else let d = z-z' in
  1.1243 -              if d < 0 then 0 else nat d)"
  1.1244 -by (simp add: Let_def nat_diff_distrib [symmetric])
  1.1245 +  "nat z - nat z' =
  1.1246 +    (if z' < 0 then nat z
  1.1247 +     else
  1.1248 +      let d = z - z'
  1.1249 +      in if d < 0 then 0 else nat d)"
  1.1250 +  by (simp add: Let_def nat_diff_distrib [symmetric])
  1.1251  
  1.1252 -lemma nat_numeral_diff_1 [simp]:
  1.1253 -  "numeral v - (1::nat) = nat (numeral v - 1)"
  1.1254 +lemma nat_numeral_diff_1 [simp]: "numeral v - (1::nat) = nat (numeral v - 1)"
  1.1255    using diff_nat_numeral [of v Num.One] by simp
  1.1256  
  1.1257  
  1.1258 -subsection "Induction principles for int"
  1.1259 +subsection \<open>Induction principles for int\<close>
  1.1260  
  1.1261 -text\<open>Well-founded segments of the integers\<close>
  1.1262 +text \<open>Well-founded segments of the integers.\<close>
  1.1263  
  1.1264 -definition
  1.1265 -  int_ge_less_than  ::  "int => (int * int) set"
  1.1266 -where
  1.1267 -  "int_ge_less_than d = {(z',z). d \<le> z' & z' < z}"
  1.1268 +definition int_ge_less_than :: "int \<Rightarrow> (int \<times> int) set"
  1.1269 +  where "int_ge_less_than d = {(z', z). d \<le> z' \<and> z' < z}"
  1.1270  
  1.1271 -theorem wf_int_ge_less_than: "wf (int_ge_less_than d)"
  1.1272 +lemma wf_int_ge_less_than: "wf (int_ge_less_than d)"
  1.1273  proof -
  1.1274 -  have "int_ge_less_than d \<subseteq> measure (%z. nat (z-d))"
  1.1275 +  have "int_ge_less_than d \<subseteq> measure (\<lambda>z. nat (z - d))"
  1.1276      by (auto simp add: int_ge_less_than_def)
  1.1277 -  thus ?thesis
  1.1278 +  then show ?thesis
  1.1279      by (rule wf_subset [OF wf_measure])
  1.1280  qed
  1.1281  
  1.1282 -text\<open>This variant looks odd, but is typical of the relations suggested
  1.1283 -by RankFinder.\<close>
  1.1284 +text \<open>
  1.1285 +  This variant looks odd, but is typical of the relations suggested
  1.1286 +  by RankFinder.\<close>
  1.1287  
  1.1288 -definition
  1.1289 -  int_ge_less_than2 ::  "int => (int * int) set"
  1.1290 -where
  1.1291 -  "int_ge_less_than2 d = {(z',z). d \<le> z & z' < z}"
  1.1292 +definition int_ge_less_than2 :: "int \<Rightarrow> (int \<times> int) set"
  1.1293 +  where "int_ge_less_than2 d = {(z',z). d \<le> z \<and> z' < z}"
  1.1294  
  1.1295 -theorem wf_int_ge_less_than2: "wf (int_ge_less_than2 d)"
  1.1296 +lemma wf_int_ge_less_than2: "wf (int_ge_less_than2 d)"
  1.1297  proof -
  1.1298 -  have "int_ge_less_than2 d \<subseteq> measure (%z. nat (1+z-d))"
  1.1299 +  have "int_ge_less_than2 d \<subseteq> measure (\<lambda>z. nat (1 + z - d))"
  1.1300      by (auto simp add: int_ge_less_than2_def)
  1.1301 -  thus ?thesis
  1.1302 +  then show ?thesis
  1.1303      by (rule wf_subset [OF wf_measure])
  1.1304  qed
  1.1305  
  1.1306  (* `set:int': dummy construction *)
  1.1307  theorem int_ge_induct [case_names base step, induct set: int]:
  1.1308    fixes i :: int
  1.1309 -  assumes ge: "k \<le> i" and
  1.1310 -    base: "P k" and
  1.1311 -    step: "\<And>i. k \<le> i \<Longrightarrow> P i \<Longrightarrow> P (i + 1)"
  1.1312 +  assumes ge: "k \<le> i"
  1.1313 +    and base: "P k"
  1.1314 +    and step: "\<And>i. k \<le> i \<Longrightarrow> P i \<Longrightarrow> P (i + 1)"
  1.1315    shows "P i"
  1.1316  proof -
  1.1317 -  { fix n
  1.1318 -    have "\<And>i::int. n = nat (i - k) \<Longrightarrow> k \<le> i \<Longrightarrow> P i"
  1.1319 -    proof (induct n)
  1.1320 -      case 0
  1.1321 -      hence "i = k" by arith
  1.1322 -      thus "P i" using base by simp
  1.1323 -    next
  1.1324 -      case (Suc n)
  1.1325 -      then have "n = nat((i - 1) - k)" by arith
  1.1326 -      moreover
  1.1327 -      have ki1: "k \<le> i - 1" using Suc.prems by arith
  1.1328 -      ultimately
  1.1329 -      have "P (i - 1)" by (rule Suc.hyps)
  1.1330 -      from step [OF ki1 this] show ?case by simp
  1.1331 -    qed
  1.1332 -  }
  1.1333 +  have "\<And>i::int. n = nat (i - k) \<Longrightarrow> k \<le> i \<Longrightarrow> P i" for n
  1.1334 +  proof (induct n)
  1.1335 +    case 0
  1.1336 +    then have "i = k" by arith
  1.1337 +    with base show "P i" by simp
  1.1338 +  next
  1.1339 +    case (Suc n)
  1.1340 +    then have "n = nat ((i - 1) - k)" by arith
  1.1341 +    moreover have k: "k \<le> i - 1" using Suc.prems by arith
  1.1342 +    ultimately have "P (i - 1)" by (rule Suc.hyps)
  1.1343 +    from step [OF k this] show ?case by simp
  1.1344 +  qed
  1.1345    with ge show ?thesis by fast
  1.1346  qed
  1.1347  
  1.1348  (* `set:int': dummy construction *)
  1.1349  theorem int_gr_induct [case_names base step, induct set: int]:
  1.1350 -  assumes gr: "k < (i::int)" and
  1.1351 -        base: "P(k+1)" and
  1.1352 -        step: "\<And>i. \<lbrakk>k < i; P i\<rbrakk> \<Longrightarrow> P(i+1)"
  1.1353 +  fixes i k :: int
  1.1354 +  assumes gr: "k < i"
  1.1355 +    and base: "P (k + 1)"
  1.1356 +    and step: "\<And>i. k < i \<Longrightarrow> P i \<Longrightarrow> P (i + 1)"
  1.1357    shows "P i"
  1.1358 -apply(rule int_ge_induct[of "k + 1"])
  1.1359 +  apply (rule int_ge_induct[of "k + 1"])
  1.1360    using gr apply arith
  1.1361 - apply(rule base)
  1.1362 -apply (rule step, simp+)
  1.1363 -done
  1.1364 +   apply (rule base)
  1.1365 +  apply (rule step)
  1.1366 +   apply simp_all
  1.1367 +  done
  1.1368  
  1.1369  theorem int_le_induct [consumes 1, case_names base step]:
  1.1370 -  assumes le: "i \<le> (k::int)" and
  1.1371 -        base: "P(k)" and
  1.1372 -        step: "\<And>i. \<lbrakk>i \<le> k; P i\<rbrakk> \<Longrightarrow> P(i - 1)"
  1.1373 +  fixes i k :: int
  1.1374 +  assumes le: "i \<le> k"
  1.1375 +    and base: "P k"
  1.1376 +    and step: "\<And>i. i \<le> k \<Longrightarrow> P i \<Longrightarrow> P (i - 1)"
  1.1377    shows "P i"
  1.1378  proof -
  1.1379 -  { fix n
  1.1380 -    have "\<And>i::int. n = nat(k-i) \<Longrightarrow> i \<le> k \<Longrightarrow> P i"
  1.1381 -    proof (induct n)
  1.1382 -      case 0
  1.1383 -      hence "i = k" by arith
  1.1384 -      thus "P i" using base by simp
  1.1385 -    next
  1.1386 -      case (Suc n)
  1.1387 -      hence "n = nat (k - (i + 1))" by arith
  1.1388 -      moreover
  1.1389 -      have ki1: "i + 1 \<le> k" using Suc.prems by arith
  1.1390 -      ultimately
  1.1391 -      have "P (i + 1)" by(rule Suc.hyps)
  1.1392 -      from step[OF ki1 this] show ?case by simp
  1.1393 -    qed
  1.1394 -  }
  1.1395 +  have "\<And>i::int. n = nat(k-i) \<Longrightarrow> i \<le> k \<Longrightarrow> P i" for n
  1.1396 +  proof (induct n)
  1.1397 +    case 0
  1.1398 +    then have "i = k" by arith
  1.1399 +    with base show "P i" by simp
  1.1400 +  next
  1.1401 +    case (Suc n)
  1.1402 +    then have "n = nat (k - (i + 1))" by arith
  1.1403 +    moreover have k: "i + 1 \<le> k" using Suc.prems by arith
  1.1404 +    ultimately have "P (i + 1)" by (rule Suc.hyps)
  1.1405 +    from step[OF k this] show ?case by simp
  1.1406 +  qed
  1.1407    with le show ?thesis by fast
  1.1408  qed
  1.1409  
  1.1410  theorem int_less_induct [consumes 1, case_names base step]:
  1.1411 -  assumes less: "(i::int) < k" and
  1.1412 -        base: "P(k - 1)" and
  1.1413 -        step: "\<And>i. \<lbrakk>i < k; P i\<rbrakk> \<Longrightarrow> P(i - 1)"
  1.1414 +  fixes i k :: int
  1.1415 +  assumes less: "i < k"
  1.1416 +    and base: "P (k - 1)"
  1.1417 +    and step: "\<And>i. i < k \<Longrightarrow> P i \<Longrightarrow> P (i - 1)"
  1.1418    shows "P i"
  1.1419 -apply(rule int_le_induct[of _ "k - 1"])
  1.1420 +  apply (rule int_le_induct[of _ "k - 1"])
  1.1421    using less apply arith
  1.1422 - apply(rule base)
  1.1423 -apply (rule step, simp+)
  1.1424 -done
  1.1425 +   apply (rule base)
  1.1426 +  apply (rule step)
  1.1427 +   apply simp_all
  1.1428 +  done
  1.1429  
  1.1430  theorem int_induct [case_names base step1 step2]:
  1.1431    fixes k :: int
  1.1432 @@ -1167,88 +1158,93 @@
  1.1433    then show ?thesis
  1.1434    proof
  1.1435      assume "i \<ge> k"
  1.1436 -    then show ?thesis using base
  1.1437 -      by (rule int_ge_induct) (fact step1)
  1.1438 +    then show ?thesis
  1.1439 +      using base by (rule int_ge_induct) (fact step1)
  1.1440    next
  1.1441      assume "i \<le> k"
  1.1442 -    then show ?thesis using base
  1.1443 -      by (rule int_le_induct) (fact step2)
  1.1444 +    then show ?thesis
  1.1445 +      using base by (rule int_le_induct) (fact step2)
  1.1446    qed
  1.1447  qed
  1.1448  
  1.1449 -subsection\<open>Intermediate value theorems\<close>
  1.1450 +
  1.1451 +subsection \<open>Intermediate value theorems\<close>
  1.1452  
  1.1453 -lemma int_val_lemma:
  1.1454 -     "(\<forall>i<n::nat. \<bar>f(i+1) - f i\<bar> \<le> 1) -->
  1.1455 -      f 0 \<le> k --> k \<le> f n --> (\<exists>i \<le> n. f i = (k::int))"
  1.1456 -unfolding One_nat_def
  1.1457 -apply (induct n)
  1.1458 -apply simp
  1.1459 -apply (intro strip)
  1.1460 -apply (erule impE, simp)
  1.1461 -apply (erule_tac x = n in allE, simp)
  1.1462 -apply (case_tac "k = f (Suc n)")
  1.1463 -apply force
  1.1464 -apply (erule impE)
  1.1465 - apply (simp add: abs_if split: if_split_asm)
  1.1466 -apply (blast intro: le_SucI)
  1.1467 -done
  1.1468 +lemma int_val_lemma: "(\<forall>i<n. \<bar>f (i + 1) - f i\<bar> \<le> 1) \<longrightarrow> f 0 \<le> k \<longrightarrow> k \<le> f n \<longrightarrow> (\<exists>i \<le> n. f i = k)"
  1.1469 +  for n :: nat and k :: int
  1.1470 +  unfolding One_nat_def
  1.1471 +  apply (induct n)
  1.1472 +   apply simp
  1.1473 +  apply (intro strip)
  1.1474 +  apply (erule impE)
  1.1475 +   apply simp
  1.1476 +  apply (erule_tac x = n in allE)
  1.1477 +  apply simp
  1.1478 +  apply (case_tac "k = f (Suc n)")
  1.1479 +   apply force
  1.1480 +  apply (erule impE)
  1.1481 +   apply (simp add: abs_if split: if_split_asm)
  1.1482 +  apply (blast intro: le_SucI)
  1.1483 +  done
  1.1484  
  1.1485  lemmas nat0_intermed_int_val = int_val_lemma [rule_format (no_asm)]
  1.1486  
  1.1487  lemma nat_intermed_int_val:
  1.1488 -     "[| \<forall>i. m \<le> i & i < n --> \<bar>f(i + 1::nat) - f i\<bar> \<le> 1; m < n;
  1.1489 -         f m \<le> k; k \<le> f n |] ==> ? i. m \<le> i & i \<le> n & f i = (k::int)"
  1.1490 -apply (cut_tac n = "n-m" and f = "%i. f (i+m) " and k = k
  1.1491 -       in int_val_lemma)
  1.1492 -unfolding One_nat_def
  1.1493 -apply simp
  1.1494 -apply (erule exE)
  1.1495 -apply (rule_tac x = "i+m" in exI, arith)
  1.1496 -done
  1.1497 +  "\<forall>i. m \<le> i \<and> i < n \<longrightarrow> \<bar>f (i + 1) - f i\<bar> \<le> 1 \<Longrightarrow> m < n \<Longrightarrow>
  1.1498 +    f m \<le> k \<Longrightarrow> k \<le> f n \<Longrightarrow> \<exists>i. m \<le> i \<and> i \<le> n \<and> f i = k"
  1.1499 +    for f :: "nat \<Rightarrow> int" and k :: int
  1.1500 +  apply (cut_tac n = "n-m" and f = "\<lambda>i. f (i + m)" and k = k in int_val_lemma)
  1.1501 +  unfolding One_nat_def
  1.1502 +  apply simp
  1.1503 +  apply (erule exE)
  1.1504 +  apply (rule_tac x = "i+m" in exI)
  1.1505 +  apply arith
  1.1506 +  done
  1.1507  
  1.1508  
  1.1509 -subsection\<open>Products and 1, by T. M. Rasmussen\<close>
  1.1510 +subsection \<open>Products and 1, by T. M. Rasmussen\<close>
  1.1511  
  1.1512  lemma abs_zmult_eq_1:
  1.1513 +  fixes m n :: int
  1.1514    assumes mn: "\<bar>m * n\<bar> = 1"
  1.1515 -  shows "\<bar>m\<bar> = (1::int)"
  1.1516 +  shows "\<bar>m\<bar> = 1"
  1.1517  proof -
  1.1518 -  have 0: "m \<noteq> 0 & n \<noteq> 0" using mn
  1.1519 -    by auto
  1.1520 -  have "~ (2 \<le> \<bar>m\<bar>)"
  1.1521 +  from mn have 0: "m \<noteq> 0" "n \<noteq> 0" by auto
  1.1522 +  have "\<not> 2 \<le> \<bar>m\<bar>"
  1.1523    proof
  1.1524      assume "2 \<le> \<bar>m\<bar>"
  1.1525 -    hence "2*\<bar>n\<bar> \<le> \<bar>m\<bar>*\<bar>n\<bar>"
  1.1526 -      by (simp add: mult_mono 0)
  1.1527 -    also have "... = \<bar>m*n\<bar>"
  1.1528 -      by (simp add: abs_mult)
  1.1529 -    also have "... = 1"
  1.1530 -      by (simp add: mn)
  1.1531 -    finally have "2*\<bar>n\<bar> \<le> 1" .
  1.1532 -    thus "False" using 0
  1.1533 -      by arith
  1.1534 +    then have "2 * \<bar>n\<bar> \<le> \<bar>m\<bar> * \<bar>n\<bar>" by (simp add: mult_mono 0)
  1.1535 +    also have "\<dots> = \<bar>m * n\<bar>" by (simp add: abs_mult)
  1.1536 +    also from mn have "\<dots> = 1" by simp
  1.1537 +    finally have "2 * \<bar>n\<bar> \<le> 1" .
  1.1538 +    with 0 show "False" by arith
  1.1539    qed
  1.1540 -  thus ?thesis using 0
  1.1541 -    by auto
  1.1542 +  with 0 show ?thesis by auto
  1.1543  qed
  1.1544  
  1.1545 -lemma pos_zmult_eq_1_iff_lemma: "(m * n = 1) ==> m = (1::int) | m = -1"
  1.1546 -by (insert abs_zmult_eq_1 [of m n], arith)
  1.1547 +lemma pos_zmult_eq_1_iff_lemma: "m * n = 1 \<Longrightarrow> m = 1 \<or> m = - 1"
  1.1548 +  for m n :: int
  1.1549 +  using abs_zmult_eq_1 [of m n] by arith
  1.1550  
  1.1551  lemma pos_zmult_eq_1_iff:
  1.1552 -  assumes "0 < (m::int)" shows "(m * n = 1) = (m = 1 & n = 1)"
  1.1553 +  fixes m n :: int
  1.1554 +  assumes "0 < m"
  1.1555 +  shows "m * n = 1 \<longleftrightarrow> m = 1 \<and> n = 1"
  1.1556  proof -
  1.1557 -  from assms have "m * n = 1 ==> m = 1" by (auto dest: pos_zmult_eq_1_iff_lemma)
  1.1558 -  thus ?thesis by (auto dest: pos_zmult_eq_1_iff_lemma)
  1.1559 +  from assms have "m * n = 1 \<Longrightarrow> m = 1"
  1.1560 +    by (auto dest: pos_zmult_eq_1_iff_lemma)
  1.1561 +  then show ?thesis
  1.1562 +    by (auto dest: pos_zmult_eq_1_iff_lemma)
  1.1563  qed
  1.1564  
  1.1565 -lemma zmult_eq_1_iff: "(m*n = (1::int)) = ((m = 1 & n = 1) | (m = -1 & n = -1))"
  1.1566 -apply (rule iffI)
  1.1567 - apply (frule pos_zmult_eq_1_iff_lemma)
  1.1568 - apply (simp add: mult.commute [of m])
  1.1569 - apply (frule pos_zmult_eq_1_iff_lemma, auto)
  1.1570 -done
  1.1571 +lemma zmult_eq_1_iff: "m * n = 1 \<longleftrightarrow> (m = 1 \<and> n = 1) \<or> (m = - 1 \<and> n = - 1)"
  1.1572 +  for m n :: int
  1.1573 +  apply (rule iffI)
  1.1574 +   apply (frule pos_zmult_eq_1_iff_lemma)
  1.1575 +   apply (simp add: mult.commute [of m])
  1.1576 +   apply (frule pos_zmult_eq_1_iff_lemma)
  1.1577 +   apply auto
  1.1578 +  done
  1.1579  
  1.1580  lemma infinite_UNIV_int: "\<not> finite (UNIV::int set)"
  1.1581  proof
  1.1582 @@ -1264,16 +1260,16 @@
  1.1583  
  1.1584  subsection \<open>Further theorems on numerals\<close>
  1.1585  
  1.1586 -subsubsection\<open>Special Simplification for Constants\<close>
  1.1587 +subsubsection \<open>Special Simplification for Constants\<close>
  1.1588  
  1.1589 -text\<open>These distributive laws move literals inside sums and differences.\<close>
  1.1590 +text \<open>These distributive laws move literals inside sums and differences.\<close>
  1.1591  
  1.1592  lemmas distrib_right_numeral [simp] = distrib_right [of _ _ "numeral v"] for v
  1.1593  lemmas distrib_left_numeral [simp] = distrib_left [of "numeral v"] for v
  1.1594  lemmas left_diff_distrib_numeral [simp] = left_diff_distrib [of _ _ "numeral v"] for v
  1.1595  lemmas right_diff_distrib_numeral [simp] = right_diff_distrib [of "numeral v"] for v
  1.1596  
  1.1597 -text\<open>These are actually for fields, like real: but where else to put them?\<close>
  1.1598 +text \<open>These are actually for fields, like real: but where else to put them?\<close>
  1.1599  
  1.1600  lemmas zero_less_divide_iff_numeral [simp, no_atp] = zero_less_divide_iff [of "numeral w"] for w
  1.1601  lemmas divide_less_0_iff_numeral [simp, no_atp] = divide_less_0_iff [of "numeral w"] for w
  1.1602 @@ -1291,7 +1287,7 @@
  1.1603    inverse_eq_divide [of "- numeral w"] for w
  1.1604  
  1.1605  text \<open>These laws simplify inequalities, moving unary minus from a term
  1.1606 -into the literal.\<close>
  1.1607 +  into the literal.\<close>
  1.1608  
  1.1609  lemmas equation_minus_iff_numeral [no_atp] =
  1.1610    equation_minus_iff [of "numeral v"] for v
  1.1611 @@ -1311,7 +1307,7 @@
  1.1612  lemmas minus_less_iff_numeral [no_atp] =
  1.1613    minus_less_iff [of _ "numeral v"] for v
  1.1614  
  1.1615 -\<comment> \<open>FIXME maybe simproc\<close>
  1.1616 +(* FIXME maybe simproc *)
  1.1617  
  1.1618  
  1.1619  text \<open>Cancellation of constant factors in comparisons (\<open><\<close> and \<open>\<le>\<close>)\<close>
  1.1620 @@ -1351,9 +1347,9 @@
  1.1621    divide_eq_eq [of _ "- numeral w"] for w
  1.1622  
  1.1623  
  1.1624 -subsubsection\<open>Optional Simplification Rules Involving Constants\<close>
  1.1625 +subsubsection \<open>Optional Simplification Rules Involving Constants\<close>
  1.1626  
  1.1627 -text\<open>Simplify quotients that are compared with a literal constant.\<close>
  1.1628 +text \<open>Simplify quotients that are compared with a literal constant.\<close>
  1.1629  
  1.1630  lemmas le_divide_eq_numeral [divide_const_simps] =
  1.1631    le_divide_eq [of "numeral w"]
  1.1632 @@ -1380,37 +1376,44 @@
  1.1633    divide_eq_eq [of _ _ "- numeral w"] for w
  1.1634  
  1.1635  
  1.1636 -text\<open>Not good as automatic simprules because they cause case splits.\<close>
  1.1637 -lemmas [divide_const_simps] = le_divide_eq_1 divide_le_eq_1 less_divide_eq_1 divide_less_eq_1 
  1.1638 +text \<open>Not good as automatic simprules because they cause case splits.\<close>
  1.1639 +lemmas [divide_const_simps] =
  1.1640 +  le_divide_eq_1 divide_le_eq_1 less_divide_eq_1 divide_less_eq_1
  1.1641  
  1.1642  
  1.1643  subsection \<open>The divides relation\<close>
  1.1644  
  1.1645 -lemma zdvd_antisym_nonneg:
  1.1646 -    "0 <= m ==> 0 <= n ==> m dvd n ==> n dvd m ==> m = (n::int)"
  1.1647 -  apply (simp add: dvd_def, auto)
  1.1648 -  apply (auto simp add: mult.assoc zero_le_mult_iff zmult_eq_1_iff)
  1.1649 -  done
  1.1650 +lemma zdvd_antisym_nonneg: "0 \<le> m \<Longrightarrow> 0 \<le> n \<Longrightarrow> m dvd n \<Longrightarrow> n dvd m \<Longrightarrow> m = n"
  1.1651 +  for m n :: int
  1.1652 +  by (auto simp add: dvd_def mult.assoc zero_le_mult_iff zmult_eq_1_iff)
  1.1653  
  1.1654 -lemma zdvd_antisym_abs: assumes "(a::int) dvd b" and "b dvd a"
  1.1655 +lemma zdvd_antisym_abs:
  1.1656 +  fixes a b :: int
  1.1657 +  assumes "a dvd b" and "b dvd a"
  1.1658    shows "\<bar>a\<bar> = \<bar>b\<bar>"
  1.1659 -proof cases
  1.1660 -  assume "a = 0" with assms show ?thesis by simp
  1.1661 +proof (cases "a = 0")
  1.1662 +  case True
  1.1663 +  with assms show ?thesis by simp
  1.1664  next
  1.1665 -  assume "a \<noteq> 0"
  1.1666 -  from \<open>a dvd b\<close> obtain k where k:"b = a*k" unfolding dvd_def by blast
  1.1667 -  from \<open>b dvd a\<close> obtain k' where k':"a = b*k'" unfolding dvd_def by blast
  1.1668 -  from k k' have "a = a*k*k'" by simp
  1.1669 -  with mult_cancel_left1[where c="a" and b="k*k'"]
  1.1670 -  have kk':"k*k' = 1" using \<open>a\<noteq>0\<close> by (simp add: mult.assoc)
  1.1671 -  hence "k = 1 \<and> k' = 1 \<or> k = -1 \<and> k' = -1" by (simp add: zmult_eq_1_iff)
  1.1672 -  thus ?thesis using k k' by auto
  1.1673 +  case False
  1.1674 +  from \<open>a dvd b\<close> obtain k where k: "b = a * k"
  1.1675 +    unfolding dvd_def by blast
  1.1676 +  from \<open>b dvd a\<close> obtain k' where k': "a = b * k'"
  1.1677 +    unfolding dvd_def by blast
  1.1678 +  from k k' have "a = a * k * k'" by simp
  1.1679 +  with mult_cancel_left1[where c="a" and b="k*k'"] have kk': "k * k' = 1"
  1.1680 +    using \<open>a \<noteq> 0\<close> by (simp add: mult.assoc)
  1.1681 +  then have "k = 1 \<and> k' = 1 \<or> k = -1 \<and> k' = -1"
  1.1682 +    by (simp add: zmult_eq_1_iff)
  1.1683 +  with k k' show ?thesis by auto
  1.1684  qed
  1.1685  
  1.1686 -lemma zdvd_zdiffD: "k dvd m - n ==> k dvd n ==> k dvd (m::int)"
  1.1687 +lemma zdvd_zdiffD: "k dvd m - n \<Longrightarrow> k dvd n \<Longrightarrow> k dvd m"
  1.1688 +  for k m n :: int
  1.1689    using dvd_add_right_iff [of k "- n" m] by simp
  1.1690  
  1.1691 -lemma zdvd_reduce: "(k dvd n + k * m) = (k dvd (n::int))"
  1.1692 +lemma zdvd_reduce: "k dvd n + k * m \<longleftrightarrow> k dvd n"
  1.1693 +  for k m n :: int
  1.1694    using dvd_add_times_triv_right_iff [of k n m] by (simp add: ac_simps)
  1.1695  
  1.1696  lemma dvd_imp_le_int:
  1.1697 @@ -1438,167 +1441,184 @@
  1.1698    with \<open>0 < n\<close> \<open>0 < k\<close> show False unfolding mult_less_cancel_left by auto
  1.1699  qed
  1.1700  
  1.1701 -lemma zdvd_mult_cancel: assumes d:"k * m dvd k * n" and kz:"k \<noteq> (0::int)"
  1.1702 +lemma zdvd_mult_cancel:
  1.1703 +  fixes k m n :: int
  1.1704 +  assumes d: "k * m dvd k * n"
  1.1705 +    and "k \<noteq> 0"
  1.1706    shows "m dvd n"
  1.1707 -proof-
  1.1708 -  from d obtain h where h: "k*n = k*m * h" unfolding dvd_def by blast
  1.1709 -  {assume "n \<noteq> m*h" hence "k* n \<noteq> k* (m*h)" using kz by simp
  1.1710 -    with h have False by (simp add: mult.assoc)}
  1.1711 -  hence "n = m * h" by blast
  1.1712 -  thus ?thesis by simp
  1.1713 +proof -
  1.1714 +  from d obtain h where h: "k * n = k * m * h"
  1.1715 +    unfolding dvd_def by blast
  1.1716 +  have "n = m * h"
  1.1717 +  proof (rule ccontr)
  1.1718 +    assume "\<not> ?thesis"
  1.1719 +    with \<open>k \<noteq> 0\<close> have "k * n \<noteq> k * (m * h)" by simp
  1.1720 +    with h show False
  1.1721 +      by (simp add: mult.assoc)
  1.1722 +  qed
  1.1723 +  then show ?thesis by simp
  1.1724  qed
  1.1725  
  1.1726 -theorem zdvd_int: "(x dvd y) = (int x dvd int y)"
  1.1727 +theorem zdvd_int: "x dvd y \<longleftrightarrow> int x dvd int y"
  1.1728  proof -
  1.1729 -  have "\<And>k. int y = int x * k \<Longrightarrow> x dvd y"
  1.1730 -  proof -
  1.1731 -    fix k
  1.1732 -    assume A: "int y = int x * k"
  1.1733 -    then show "x dvd y"
  1.1734 -    proof (cases k)
  1.1735 -      case (nonneg n)
  1.1736 -      with A have "y = x * n" by (simp del: of_nat_mult add: of_nat_mult [symmetric])
  1.1737 -      then show ?thesis ..
  1.1738 -    next
  1.1739 -      case (neg n)
  1.1740 -      with A have "int y = int x * (- int (Suc n))" by simp
  1.1741 -      also have "\<dots> = - (int x * int (Suc n))" by (simp only: mult_minus_right)
  1.1742 -      also have "\<dots> = - int (x * Suc n)" by (simp only: of_nat_mult [symmetric])
  1.1743 -      finally have "- int (x * Suc n) = int y" ..
  1.1744 -      then show ?thesis by (simp only: negative_eq_positive) auto
  1.1745 -    qed
  1.1746 +  have "x dvd y" if "int y = int x * k" for k
  1.1747 +  proof (cases k)
  1.1748 +    case (nonneg n)
  1.1749 +    with that have "y = x * n"
  1.1750 +      by (simp del: of_nat_mult add: of_nat_mult [symmetric])
  1.1751 +    then show ?thesis ..
  1.1752 +  next
  1.1753 +    case (neg n)
  1.1754 +    with that have "int y = int x * (- int (Suc n))"
  1.1755 +      by simp
  1.1756 +    also have "\<dots> = - (int x * int (Suc n))"
  1.1757 +      by (simp only: mult_minus_right)
  1.1758 +    also have "\<dots> = - int (x * Suc n)"
  1.1759 +      by (simp only: of_nat_mult [symmetric])
  1.1760 +    finally have "- int (x * Suc n) = int y" ..
  1.1761 +    then show ?thesis
  1.1762 +      by (simp only: negative_eq_positive) auto
  1.1763    qed
  1.1764 -  then show ?thesis by (auto elim!: dvdE simp only: dvd_triv_left of_nat_mult)
  1.1765 +  then show ?thesis
  1.1766 +    by (auto elim!: dvdE simp only: dvd_triv_left of_nat_mult)
  1.1767  qed
  1.1768  
  1.1769 -lemma zdvd1_eq[simp]: "(x::int) dvd 1 = (\<bar>x\<bar> = 1)"
  1.1770 +lemma zdvd1_eq[simp]: "x dvd 1 \<longleftrightarrow> \<bar>x\<bar> = 1"
  1.1771 +  (is "?lhs \<longleftrightarrow> ?rhs")
  1.1772 +  for x :: int
  1.1773  proof
  1.1774 -  assume d: "x dvd 1" hence "int (nat \<bar>x\<bar>) dvd int (nat 1)" by simp
  1.1775 -  hence "nat \<bar>x\<bar> dvd 1" by (simp add: zdvd_int)
  1.1776 -  hence "nat \<bar>x\<bar> = 1"  by simp
  1.1777 -  thus "\<bar>x\<bar> = 1" by (cases "x < 0") auto
  1.1778 +  assume ?lhs
  1.1779 +  then have "int (nat \<bar>x\<bar>) dvd int (nat 1)" by simp
  1.1780 +  then have "nat \<bar>x\<bar> dvd 1" by (simp add: zdvd_int)
  1.1781 +  then have "nat \<bar>x\<bar> = 1" by simp
  1.1782 +  then show ?rhs by (cases "x < 0") auto
  1.1783  next
  1.1784 -  assume "\<bar>x\<bar>=1"
  1.1785 -  then have "x = 1 \<or> x = -1" by auto
  1.1786 -  then show "x dvd 1" by (auto intro: dvdI)
  1.1787 +  assume ?rhs
  1.1788 +  then have "x = 1 \<or> x = - 1" by auto
  1.1789 +  then show ?lhs by (auto intro: dvdI)
  1.1790  qed
  1.1791  
  1.1792  lemma zdvd_mult_cancel1:
  1.1793 -  assumes mp:"m \<noteq>(0::int)" shows "(m * n dvd m) = (\<bar>n\<bar> = 1)"
  1.1794 +  fixes m :: int
  1.1795 +  assumes mp: "m \<noteq> 0"
  1.1796 +  shows "m * n dvd m \<longleftrightarrow> \<bar>n\<bar> = 1"
  1.1797 +    (is "?lhs \<longleftrightarrow> ?rhs")
  1.1798  proof
  1.1799 -  assume n1: "\<bar>n\<bar> = 1" thus "m * n dvd m"
  1.1800 -    by (cases "n >0") (auto simp add: minus_equation_iff)
  1.1801 +  assume ?rhs
  1.1802 +  then show ?lhs
  1.1803 +    by (cases "n > 0") (auto simp add: minus_equation_iff)
  1.1804  next
  1.1805 -  assume H: "m * n dvd m" hence H2: "m * n dvd m * 1" by simp
  1.1806 -  from zdvd_mult_cancel[OF H2 mp] show "\<bar>n\<bar> = 1" by (simp only: zdvd1_eq)
  1.1807 +  assume ?lhs
  1.1808 +  then have "m * n dvd m * 1" by simp
  1.1809 +  from zdvd_mult_cancel[OF this mp] show ?rhs
  1.1810 +    by (simp only: zdvd1_eq)
  1.1811  qed
  1.1812  
  1.1813 -lemma int_dvd_iff: "(int m dvd z) = (m dvd nat \<bar>z\<bar>)"
  1.1814 -  unfolding zdvd_int by (cases "z \<ge> 0") simp_all
  1.1815 -
  1.1816 -lemma dvd_int_iff: "(z dvd int m) = (nat \<bar>z\<bar> dvd m)"
  1.1817 -  unfolding zdvd_int by (cases "z \<ge> 0") simp_all
  1.1818 +lemma int_dvd_iff: "int m dvd z \<longleftrightarrow> m dvd nat \<bar>z\<bar>"
  1.1819 +  by (cases "z \<ge> 0") (simp_all add: zdvd_int)
  1.1820  
  1.1821 -lemma dvd_int_unfold_dvd_nat:
  1.1822 -  "k dvd l \<longleftrightarrow> nat \<bar>k\<bar> dvd nat \<bar>l\<bar>"
  1.1823 -  unfolding dvd_int_iff [symmetric] by simp
  1.1824 +lemma dvd_int_iff: "z dvd int m \<longleftrightarrow> nat \<bar>z\<bar> dvd m"
  1.1825 +  by (cases "z \<ge> 0") (simp_all add: zdvd_int)
  1.1826  
  1.1827 -lemma nat_dvd_iff: "(nat z dvd m) = (if 0 \<le> z then (z dvd int m) else m = 0)"
  1.1828 +lemma dvd_int_unfold_dvd_nat: "k dvd l \<longleftrightarrow> nat \<bar>k\<bar> dvd nat \<bar>l\<bar>"
  1.1829 +  by (simp add: dvd_int_iff [symmetric])
  1.1830 +
  1.1831 +lemma nat_dvd_iff: "nat z dvd m \<longleftrightarrow> (if 0 \<le> z then z dvd int m else m = 0)"
  1.1832    by (auto simp add: dvd_int_iff)
  1.1833  
  1.1834 -lemma eq_nat_nat_iff:
  1.1835 -  "0 \<le> z \<Longrightarrow> 0 \<le> z' \<Longrightarrow> nat z = nat z' \<longleftrightarrow> z = z'"
  1.1836 +lemma eq_nat_nat_iff: "0 \<le> z \<Longrightarrow> 0 \<le> z' \<Longrightarrow> nat z = nat z' \<longleftrightarrow> z = z'"
  1.1837    by (auto elim!: nonneg_eq_int)
  1.1838  
  1.1839 -lemma nat_power_eq:
  1.1840 -  "0 \<le> z \<Longrightarrow> nat (z ^ n) = nat z ^ n"
  1.1841 +lemma nat_power_eq: "0 \<le> z \<Longrightarrow> nat (z ^ n) = nat z ^ n"
  1.1842    by (induct n) (simp_all add: nat_mult_distrib)
  1.1843  
  1.1844 -lemma zdvd_imp_le: "[| z dvd n; 0 < n |] ==> z \<le> (n::int)"
  1.1845 +lemma zdvd_imp_le: "z dvd n \<Longrightarrow> 0 < n \<Longrightarrow> z \<le> n"
  1.1846 +  for n z :: int
  1.1847    apply (cases n)
  1.1848 -  apply (auto simp add: dvd_int_iff)
  1.1849 +   apply (auto simp add: dvd_int_iff)
  1.1850    apply (cases z)
  1.1851 -  apply (auto simp add: dvd_imp_le)
  1.1852 +   apply (auto simp add: dvd_imp_le)
  1.1853    done
  1.1854  
  1.1855  lemma zdvd_period:
  1.1856    fixes a d :: int
  1.1857    assumes "a dvd d"
  1.1858    shows "a dvd (x + t) \<longleftrightarrow> a dvd ((x + c * d) + t)"
  1.1859 +    (is "?lhs \<longleftrightarrow> ?rhs")
  1.1860  proof -
  1.1861    from assms obtain k where "d = a * k" by (rule dvdE)
  1.1862    show ?thesis
  1.1863    proof
  1.1864 -    assume "a dvd (x + t)"
  1.1865 +    assume ?lhs
  1.1866      then obtain l where "x + t = a * l" by (rule dvdE)
  1.1867      then have "x = a * l - t" by simp
  1.1868 -    with \<open>d = a * k\<close> show "a dvd x + c * d + t" by simp
  1.1869 +    with \<open>d = a * k\<close> show ?rhs by simp
  1.1870    next
  1.1871 -    assume "a dvd x + c * d + t"
  1.1872 +    assume ?rhs
  1.1873      then obtain l where "x + c * d + t = a * l" by (rule dvdE)
  1.1874      then have "x = a * l - c * d - t" by simp
  1.1875 -    with \<open>d = a * k\<close> show "a dvd (x + t)" by simp
  1.1876 +    with \<open>d = a * k\<close> show ?lhs by simp
  1.1877    qed
  1.1878  qed
  1.1879  
  1.1880  
  1.1881  subsection \<open>Finiteness of intervals\<close>
  1.1882  
  1.1883 -lemma finite_interval_int1 [iff]: "finite {i :: int. a <= i & i <= b}"
  1.1884 -proof (cases "a <= b")
  1.1885 +lemma finite_interval_int1 [iff]: "finite {i :: int. a \<le> i \<and> i \<le> b}"
  1.1886 +proof (cases "a \<le> b")
  1.1887    case True
  1.1888 -  from this show ?thesis
  1.1889 +  then show ?thesis
  1.1890    proof (induct b rule: int_ge_induct)
  1.1891      case base
  1.1892 -    have "{i. a <= i & i <= a} = {a}" by auto
  1.1893 -    from this show ?case by simp
  1.1894 +    have "{i. a \<le> i \<and> i \<le> a} = {a}" by auto
  1.1895 +    then show ?case by simp
  1.1896    next
  1.1897      case (step b)
  1.1898 -    from this have "{i. a <= i & i <= b + 1} = {i. a <= i & i <= b} \<union> {b + 1}" by auto
  1.1899 -    from this step show ?case by simp
  1.1900 +    then have "{i. a \<le> i \<and> i \<le> b + 1} = {i. a \<le> i \<and> i \<le> b} \<union> {b + 1}" by auto
  1.1901 +    with step show ?case by simp
  1.1902    qed
  1.1903  next
  1.1904 -  case False from this show ?thesis
  1.1905 +  case False
  1.1906 +  then show ?thesis
  1.1907      by (metis (lifting, no_types) Collect_empty_eq finite.emptyI order_trans)
  1.1908  qed
  1.1909  
  1.1910 -lemma finite_interval_int2 [iff]: "finite {i :: int. a <= i & i < b}"
  1.1911 -by (rule rev_finite_subset[OF finite_interval_int1[of "a" "b"]]) auto
  1.1912 +lemma finite_interval_int2 [iff]: "finite {i :: int. a \<le> i \<and> i < b}"
  1.1913 +  by (rule rev_finite_subset[OF finite_interval_int1[of "a" "b"]]) auto
  1.1914  
  1.1915 -lemma finite_interval_int3 [iff]: "finite {i :: int. a < i & i <= b}"
  1.1916 -by (rule rev_finite_subset[OF finite_interval_int1[of "a" "b"]]) auto
  1.1917 +lemma finite_interval_int3 [iff]: "finite {i :: int. a < i \<and> i \<le> b}"
  1.1918 +  by (rule rev_finite_subset[OF finite_interval_int1[of "a" "b"]]) auto
  1.1919  
  1.1920 -lemma finite_interval_int4 [iff]: "finite {i :: int. a < i & i < b}"
  1.1921 -by (rule rev_finite_subset[OF finite_interval_int1[of "a" "b"]]) auto
  1.1922 +lemma finite_interval_int4 [iff]: "finite {i :: int. a < i \<and> i < b}"
  1.1923 +  by (rule rev_finite_subset[OF finite_interval_int1[of "a" "b"]]) auto
  1.1924  
  1.1925  
  1.1926  subsection \<open>Configuration of the code generator\<close>
  1.1927  
  1.1928  text \<open>Constructors\<close>
  1.1929  
  1.1930 -definition Pos :: "num \<Rightarrow> int" where
  1.1931 -  [simp, code_abbrev]: "Pos = numeral"
  1.1932 +definition Pos :: "num \<Rightarrow> int"
  1.1933 +  where [simp, code_abbrev]: "Pos = numeral"
  1.1934  
  1.1935 -definition Neg :: "num \<Rightarrow> int" where
  1.1936 -  [simp, code_abbrev]: "Neg n = - (Pos n)"
  1.1937 +definition Neg :: "num \<Rightarrow> int"
  1.1938 +  where [simp, code_abbrev]: "Neg n = - (Pos n)"
  1.1939  
  1.1940  code_datatype "0::int" Pos Neg
  1.1941  
  1.1942  
  1.1943 -text \<open>Auxiliary operations\<close>
  1.1944 +text \<open>Auxiliary operations.\<close>
  1.1945  
  1.1946 -definition dup :: "int \<Rightarrow> int" where
  1.1947 -  [simp]: "dup k = k + k"
  1.1948 +definition dup :: "int \<Rightarrow> int"
  1.1949 +  where [simp]: "dup k = k + k"
  1.1950  
  1.1951  lemma dup_code [code]:
  1.1952    "dup 0 = 0"
  1.1953    "dup (Pos n) = Pos (Num.Bit0 n)"
  1.1954    "dup (Neg n) = Neg (Num.Bit0 n)"
  1.1955 -  unfolding Pos_def Neg_def
  1.1956    by (simp_all add: numeral_Bit0)
  1.1957  
  1.1958 -definition sub :: "num \<Rightarrow> num \<Rightarrow> int" where
  1.1959 -  [simp]: "sub m n = numeral m - numeral n"
  1.1960 +definition sub :: "num \<Rightarrow> num \<Rightarrow> int"
  1.1961 +  where [simp]: "sub m n = numeral m - numeral n"
  1.1962  
  1.1963  lemma sub_code [code]:
  1.1964    "sub Num.One Num.One = 0"
  1.1965 @@ -1610,25 +1630,25 @@
  1.1966    "sub (Num.Bit1 m) (Num.Bit1 n) = dup (sub m n)"
  1.1967    "sub (Num.Bit1 m) (Num.Bit0 n) = dup (sub m n) + 1"
  1.1968    "sub (Num.Bit0 m) (Num.Bit1 n) = dup (sub m n) - 1"
  1.1969 -  apply (simp_all only: sub_def dup_def numeral.simps Pos_def Neg_def numeral_BitM)
  1.1970 -  apply (simp_all only: algebra_simps minus_diff_eq)
  1.1971 +          apply (simp_all only: sub_def dup_def numeral.simps Pos_def Neg_def numeral_BitM)
  1.1972 +        apply (simp_all only: algebra_simps minus_diff_eq)
  1.1973    apply (simp_all only: add.commute [of _ "- (numeral n + numeral n)"])
  1.1974    apply (simp_all only: minus_add add.assoc left_minus)
  1.1975    done
  1.1976  
  1.1977 -text \<open>Implementations\<close>
  1.1978 +text \<open>Implementations.\<close>
  1.1979  
  1.1980 -lemma one_int_code [code, code_unfold]:
  1.1981 -  "1 = Pos Num.One"
  1.1982 +lemma one_int_code [code, code_unfold]: "1 = Pos Num.One"
  1.1983    by simp
  1.1984  
  1.1985  lemma plus_int_code [code]:
  1.1986 -  "k + 0 = (k::int)"
  1.1987 -  "0 + l = (l::int)"
  1.1988 +  "k + 0 = k"
  1.1989 +  "0 + l = l"
  1.1990    "Pos m + Pos n = Pos (m + n)"
  1.1991    "Pos m + Neg n = sub m n"
  1.1992    "Neg m + Pos n = sub n m"
  1.1993    "Neg m + Neg n = Neg (m + n)"
  1.1994 +  for k l :: int
  1.1995    by simp_all
  1.1996  
  1.1997  lemma uminus_int_code [code]:
  1.1998 @@ -1638,28 +1658,29 @@
  1.1999    by simp_all
  1.2000  
  1.2001  lemma minus_int_code [code]:
  1.2002 -  "k - 0 = (k::int)"
  1.2003 -  "0 - l = uminus (l::int)"
  1.2004 +  "k - 0 = k"
  1.2005 +  "0 - l = uminus l"
  1.2006    "Pos m - Pos n = sub m n"
  1.2007    "Pos m - Neg n = Pos (m + n)"
  1.2008    "Neg m - Pos n = Neg (m + n)"
  1.2009    "Neg m - Neg n = sub n m"
  1.2010 +  for k l :: int
  1.2011    by simp_all
  1.2012  
  1.2013  lemma times_int_code [code]:
  1.2014 -  "k * 0 = (0::int)"
  1.2015 -  "0 * l = (0::int)"
  1.2016 +  "k * 0 = 0"
  1.2017 +  "0 * l = 0"
  1.2018    "Pos m * Pos n = Pos (m * n)"
  1.2019    "Pos m * Neg n = Neg (m * n)"
  1.2020    "Neg m * Pos n = Neg (m * n)"
  1.2021    "Neg m * Neg n = Pos (m * n)"
  1.2022 +  for k l :: int
  1.2023    by simp_all
  1.2024  
  1.2025  instantiation int :: equal
  1.2026  begin
  1.2027  
  1.2028 -definition
  1.2029 -  "HOL.equal k l \<longleftrightarrow> k = (l::int)"
  1.2030 +definition "HOL.equal k l \<longleftrightarrow> k = (l::int)"
  1.2031  
  1.2032  instance
  1.2033    by standard (rule equal_int_def)
  1.2034 @@ -1678,8 +1699,8 @@
  1.2035    "HOL.equal (Neg k) (Neg l) \<longleftrightarrow> HOL.equal k l"
  1.2036    by (auto simp add: equal)
  1.2037  
  1.2038 -lemma equal_int_refl [code nbe]:
  1.2039 -  "HOL.equal (k::int) k \<longleftrightarrow> True"
  1.2040 +lemma equal_int_refl [code nbe]: "HOL.equal k k \<longleftrightarrow> True"
  1.2041 +  for k :: int
  1.2042    by (fact equal_refl)
  1.2043  
  1.2044  lemma less_eq_int_code [code]:
  1.2045 @@ -1719,7 +1740,7 @@
  1.2046    by simp_all
  1.2047  
  1.2048  
  1.2049 -text \<open>Serializer setup\<close>
  1.2050 +text \<open>Serializer setup.\<close>
  1.2051  
  1.2052  code_identifier
  1.2053    code_module Int \<rightharpoonup> (SML) Arith and (OCaml) Arith and (Haskell) Arith