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.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.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.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.125 -apply (case_tac "k=0")
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.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.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.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.306 +lemma of_int_eq_iff [simp]: "of_int w = of_int z \<longleftrightarrow> w = z"
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.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.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.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.527
1.528 -lemma nat_1 [simp]:
1.529 -  "nat 1 = Suc 0"
1.530 +lemma nat_1 [simp]: "nat 1 = Suc 0"
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.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.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.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.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.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.802 -                             le_imp_0_less [THEN order_less_imp_le])
1.803 +  then show ?thesis
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.809 +  then show ?thesis
1.810 +    by (simp del: of_nat_Suc of_nat_add of_nat_1
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.828 +  have le: "0 \<le> z + z"
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.840 -    also have "... = - (1 + z + z)"
1.841 +    also have "\<dots> = - (1 + z + z)"
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.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.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  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  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.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.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.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.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
```