separate class for notions specific for integral (semi)domains, in contrast to fields where these are trivial
authorhaftmann
Fri Jun 19 07:53:35 2015 +0200 (2015-06-19)
changeset 60517f16e4fb20652
parent 60516 0826b7025d07
child 60525 278b65d9339c
separate class for notions specific for integral (semi)domains, in contrast to fields where these are trivial
CONTRIBUTORS
NEWS
src/HOL/Divides.thy
src/HOL/Equiv_Relations.thy
src/HOL/Number_Theory/Euclidean_Algorithm.thy
src/HOL/Rings.thy
     1.1 --- a/CONTRIBUTORS	Fri Jun 19 07:53:33 2015 +0200
     1.2 +++ b/CONTRIBUTORS	Fri Jun 19 07:53:35 2015 +0200
     1.3 @@ -10,6 +10,10 @@
     1.4    Generic partial division in rings as inverse operation
     1.5    of multiplication.
     1.6  
     1.7 +* Summer 2015: Manuel Eberl and Florian Haftmann, TUM
     1.8 +  Type class hierarchy with common algebraic notions of
     1.9 +  integral (semi)domains like units and associated elements.
    1.10 +
    1.11  
    1.12  Contributions to Isabelle2015
    1.13  -----------------------------
     2.1 --- a/NEWS	Fri Jun 19 07:53:33 2015 +0200
     2.2 +++ b/NEWS	Fri Jun 19 07:53:35 2015 +0200
     2.3 @@ -95,6 +95,12 @@
     2.4  * Tightened specification of class semiring_no_zero_divisors.  Slight
     2.5  INCOMPATIBILITY.
     2.6  
     2.7 +* Class algebraic_semidom introduced common algebraic notions of
     2.8 +integral (semi)domains like units and associated elements.  Although
     2.9 +logically subsumed by fields, is is not a super class of these
    2.10 +in order not to burden fields with notions that are trivial there.
    2.11 +INCOMPATIBILITY.
    2.12 +
    2.13  * Former constants Fields.divide (_ / _) and Divides.div (_ div _)
    2.14  are logically unified to Rings.divide in syntactic type class
    2.15  Rings.divide, with infix syntax (_ div _).  Infix syntax (_ / _)
     3.1 --- a/src/HOL/Divides.thy	Fri Jun 19 07:53:33 2015 +0200
     3.2 +++ b/src/HOL/Divides.thy	Fri Jun 19 07:53:35 2015 +0200
     3.3 @@ -22,7 +22,7 @@
     3.4      and div_mult_mult1 [simp]: "c \<noteq> 0 \<Longrightarrow> (c * a) div (c * b) = a div b"
     3.5  begin
     3.6  
     3.7 -subclass semidom_divide
     3.8 +subclass algebraic_semidom
     3.9  proof
    3.10    fix b a
    3.11    assume "b \<noteq> 0"
    3.12 @@ -212,18 +212,6 @@
    3.13    finally show ?thesis .
    3.14  qed
    3.15  
    3.16 -lemma dvd_div_mult_self [simp]:
    3.17 -  "a dvd b \<Longrightarrow> (b div a) * a = b"
    3.18 -  using mod_div_equality [of b a, symmetric] by simp
    3.19 -
    3.20 -lemma dvd_mult_div_cancel [simp]:
    3.21 -  "a dvd b \<Longrightarrow> a * (b div a) = b"
    3.22 -  using dvd_div_mult_self by (simp add: ac_simps)
    3.23 -
    3.24 -lemma dvd_div_mult:
    3.25 -  "a dvd b \<Longrightarrow> (b div a) * c = (b * c) div a"
    3.26 -  by (cases "a = 0") (auto elim!: dvdE simp add: mult.assoc)
    3.27 -
    3.28  lemma div_dvd_div [simp]:
    3.29    assumes "a dvd b" and "a dvd c"
    3.30    shows "b div a dvd c div a \<longleftrightarrow> b dvd c"
    3.31 @@ -359,15 +347,6 @@
    3.32    apply (simp add: no_zero_divisors)
    3.33    done
    3.34  
    3.35 -lemma div_mult_swap:
    3.36 -  assumes "c dvd b"
    3.37 -  shows "a * (b div c) = (a * b) div c"
    3.38 -proof -
    3.39 -  from assms have "b div c * (a div 1) = b * a div (c * 1)"
    3.40 -    by (simp only: div_mult_div_if_dvd one_dvd)
    3.41 -  then show ?thesis by (simp add: mult.commute)
    3.42 -qed
    3.43 -   
    3.44  lemma div_mult_mult2 [simp]:
    3.45    "c \<noteq> 0 \<Longrightarrow> (a * c) div (b * c) = a div b"
    3.46    by (drule div_mult_mult1) (simp add: mult.commute)
    3.47 @@ -1911,6 +1890,10 @@
    3.48  
    3.49  end
    3.50  
    3.51 +lemma is_unit_int:
    3.52 +  "is_unit (k::int) \<longleftrightarrow> k = 1 \<or> k = - 1"
    3.53 +  by auto
    3.54 +
    3.55  text{*Basic laws about division and remainder*}
    3.56  
    3.57  lemma zmod_zdiv_equality: "(a::int) = b * (a div b) + (a mod b)"
     4.1 --- a/src/HOL/Equiv_Relations.thy	Fri Jun 19 07:53:33 2015 +0200
     4.2 +++ b/src/HOL/Equiv_Relations.thy	Fri Jun 19 07:53:35 2015 +0200
     4.3 @@ -523,6 +523,20 @@
     4.4    "equivp R \<Longrightarrow> R x y \<Longrightarrow> R y z \<Longrightarrow> R x z"
     4.5    by (erule equivpE, erule transpE)
     4.6  
     4.7 +
     4.8 +subsection \<open>Prominent examples\<close>
     4.9 +
    4.10 +lemma equivp_associated:
    4.11 +  "equivp associated"
    4.12 +proof (rule equivpI)
    4.13 +  show "reflp associated"
    4.14 +    by (rule reflpI) simp
    4.15 +  show "symp associated"
    4.16 +    by (rule sympI) (simp add: associated_sym)
    4.17 +  show "transp associated"
    4.18 +    by (rule transpI) (fact associated_trans)
    4.19 +qed
    4.20 +
    4.21  hide_const (open) proj
    4.22  
    4.23  end
     5.1 --- a/src/HOL/Number_Theory/Euclidean_Algorithm.thy	Fri Jun 19 07:53:33 2015 +0200
     5.2 +++ b/src/HOL/Number_Theory/Euclidean_Algorithm.thy	Fri Jun 19 07:53:35 2015 +0200
     5.3 @@ -5,276 +5,6 @@
     5.4  theory Euclidean_Algorithm
     5.5  imports Complex_Main
     5.6  begin
     5.7 -
     5.8 -context semidom_divide
     5.9 -begin
    5.10 -
    5.11 -lemma dvd_div_mult_self [simp]:
    5.12 -  "a dvd b \<Longrightarrow> b div a * a = b"
    5.13 -  by (cases "a = 0") (auto elim: dvdE simp add: ac_simps)
    5.14 -
    5.15 -lemma dvd_mult_div_cancel [simp]:
    5.16 -  "a dvd b \<Longrightarrow> a * (b div a) = b"
    5.17 -  using dvd_div_mult_self [of a b] by (simp add: ac_simps)
    5.18 -  
    5.19 -lemma div_mult_swap:
    5.20 -  assumes "c dvd b"
    5.21 -  shows "a * (b div c) = (a * b) div c"
    5.22 -proof (cases "c = 0")
    5.23 -  case True then show ?thesis by simp
    5.24 -next
    5.25 -  case False from assms obtain d where "b = c * d" ..
    5.26 -  moreover from False have "a * divide (d * c) c = ((a * d) * c) div c"
    5.27 -    by simp
    5.28 -  ultimately show ?thesis by (simp add: ac_simps)
    5.29 -qed
    5.30 -
    5.31 -lemma dvd_div_mult:
    5.32 -  assumes "c dvd b"
    5.33 -  shows "b div c * a = (b * a) div c"
    5.34 -  using assms div_mult_swap [of c b a] by (simp add: ac_simps)
    5.35 -
    5.36 -  
    5.37 -text \<open>Units: invertible elements in a ring\<close>
    5.38 -
    5.39 -abbreviation is_unit :: "'a \<Rightarrow> bool"
    5.40 -where
    5.41 -  "is_unit a \<equiv> a dvd 1"
    5.42 -
    5.43 -lemma not_is_unit_0 [simp]:
    5.44 -  "\<not> is_unit 0"
    5.45 -  by simp
    5.46 -
    5.47 -lemma unit_imp_dvd [dest]: 
    5.48 -  "is_unit b \<Longrightarrow> b dvd a"
    5.49 -  by (rule dvd_trans [of _ 1]) simp_all
    5.50 -
    5.51 -lemma unit_dvdE:
    5.52 -  assumes "is_unit a"
    5.53 -  obtains c where "a \<noteq> 0" and "b = a * c"
    5.54 -proof -
    5.55 -  from assms have "a dvd b" by auto
    5.56 -  then obtain c where "b = a * c" ..
    5.57 -  moreover from assms have "a \<noteq> 0" by auto
    5.58 -  ultimately show thesis using that by blast
    5.59 -qed
    5.60 -
    5.61 -lemma dvd_unit_imp_unit:
    5.62 -  "a dvd b \<Longrightarrow> is_unit b \<Longrightarrow> is_unit a"
    5.63 -  by (rule dvd_trans)
    5.64 -
    5.65 -lemma unit_div_1_unit [simp, intro]:
    5.66 -  assumes "is_unit a"
    5.67 -  shows "is_unit (1 div a)"
    5.68 -proof -
    5.69 -  from assms have "1 = 1 div a * a" by simp
    5.70 -  then show "is_unit (1 div a)" by (rule dvdI)
    5.71 -qed
    5.72 -
    5.73 -lemma is_unitE [elim?]:
    5.74 -  assumes "is_unit a"
    5.75 -  obtains b where "a \<noteq> 0" and "b \<noteq> 0"
    5.76 -    and "is_unit b" and "1 div a = b" and "1 div b = a"
    5.77 -    and "a * b = 1" and "c div a = c * b"
    5.78 -proof (rule that)
    5.79 -  def b \<equiv> "1 div a"
    5.80 -  then show "1 div a = b" by simp
    5.81 -  from b_def `is_unit a` show "is_unit b" by simp
    5.82 -  from `is_unit a` and `is_unit b` show "a \<noteq> 0" and "b \<noteq> 0" by auto
    5.83 -  from b_def `is_unit a` show "a * b = 1" by simp
    5.84 -  then have "1 = a * b" ..
    5.85 -  with b_def `b \<noteq> 0` show "1 div b = a" by simp
    5.86 -  from `is_unit a` have "a dvd c" ..
    5.87 -  then obtain d where "c = a * d" ..
    5.88 -  with `a \<noteq> 0` `a * b = 1` show "c div a = c * b"
    5.89 -    by (simp add: mult.assoc mult.left_commute [of a])
    5.90 -qed
    5.91 -
    5.92 -lemma unit_prod [intro]:
    5.93 -  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a * b)"
    5.94 -  by (subst mult_1_left [of 1, symmetric]) (rule mult_dvd_mono) 
    5.95 -  
    5.96 -lemma unit_div [intro]:
    5.97 -  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a div b)"
    5.98 -  by (erule is_unitE [of b a]) (simp add: ac_simps unit_prod)
    5.99 -
   5.100 -lemma mult_unit_dvd_iff:
   5.101 -  assumes "is_unit b"
   5.102 -  shows "a * b dvd c \<longleftrightarrow> a dvd c"
   5.103 -proof
   5.104 -  assume "a * b dvd c"
   5.105 -  with assms show "a dvd c"
   5.106 -    by (simp add: dvd_mult_left)
   5.107 -next
   5.108 -  assume "a dvd c"
   5.109 -  then obtain k where "c = a * k" ..
   5.110 -  with assms have "c = (a * b) * (1 div b * k)"
   5.111 -    by (simp add: mult_ac)
   5.112 -  then show "a * b dvd c" by (rule dvdI)
   5.113 -qed
   5.114 -
   5.115 -lemma dvd_mult_unit_iff:
   5.116 -  assumes "is_unit b"
   5.117 -  shows "a dvd c * b \<longleftrightarrow> a dvd c"
   5.118 -proof
   5.119 -  assume "a dvd c * b"
   5.120 -  with assms have "c * b dvd c * (b * (1 div b))"
   5.121 -    by (subst mult_assoc [symmetric]) simp
   5.122 -  also from `is_unit b` have "b * (1 div b) = 1" by (rule is_unitE) simp
   5.123 -  finally have "c * b dvd c" by simp
   5.124 -  with `a dvd c * b` show "a dvd c" by (rule dvd_trans)
   5.125 -next
   5.126 -  assume "a dvd c"
   5.127 -  then show "a dvd c * b" by simp
   5.128 -qed
   5.129 -
   5.130 -lemma div_unit_dvd_iff:
   5.131 -  "is_unit b \<Longrightarrow> a div b dvd c \<longleftrightarrow> a dvd c"
   5.132 -  by (erule is_unitE [of _ a]) (auto simp add: mult_unit_dvd_iff)
   5.133 -
   5.134 -lemma dvd_div_unit_iff:
   5.135 -  "is_unit b \<Longrightarrow> a dvd c div b \<longleftrightarrow> a dvd c"
   5.136 -  by (erule is_unitE [of _ c]) (simp add: dvd_mult_unit_iff)
   5.137 -
   5.138 -lemmas unit_dvd_iff = mult_unit_dvd_iff div_unit_dvd_iff
   5.139 -  dvd_mult_unit_iff dvd_div_unit_iff -- \<open>FIXME consider fact collection\<close>
   5.140 -
   5.141 -lemma unit_mult_div_div [simp]:
   5.142 -  "is_unit a \<Longrightarrow> b * (1 div a) = b div a"
   5.143 -  by (erule is_unitE [of _ b]) simp
   5.144 -
   5.145 -lemma unit_div_mult_self [simp]:
   5.146 -  "is_unit a \<Longrightarrow> b div a * a = b"
   5.147 -  by (rule dvd_div_mult_self) auto
   5.148 -
   5.149 -lemma unit_div_1_div_1 [simp]:
   5.150 -  "is_unit a \<Longrightarrow> 1 div (1 div a) = a"
   5.151 -  by (erule is_unitE) simp
   5.152 -
   5.153 -lemma unit_div_mult_swap:
   5.154 -  "is_unit c \<Longrightarrow> a * (b div c) = (a * b) div c"
   5.155 -  by (erule unit_dvdE [of _ b]) (simp add: mult.left_commute [of _ c])
   5.156 -
   5.157 -lemma unit_div_commute:
   5.158 -  "is_unit b \<Longrightarrow> (a div b) * c = (a * c) div b"
   5.159 -  using unit_div_mult_swap [of b c a] by (simp add: ac_simps)
   5.160 -
   5.161 -lemma unit_eq_div1:
   5.162 -  "is_unit b \<Longrightarrow> a div b = c \<longleftrightarrow> a = c * b"
   5.163 -  by (auto elim: is_unitE)
   5.164 -
   5.165 -lemma unit_eq_div2:
   5.166 -  "is_unit b \<Longrightarrow> a = c div b \<longleftrightarrow> a * b = c"
   5.167 -  using unit_eq_div1 [of b c a] by auto
   5.168 -
   5.169 -lemma unit_mult_left_cancel:
   5.170 -  assumes "is_unit a"
   5.171 -  shows "a * b = a * c \<longleftrightarrow> b = c" (is "?P \<longleftrightarrow> ?Q")
   5.172 -  using assms mult_cancel_left [of a b c] by auto 
   5.173 -
   5.174 -lemma unit_mult_right_cancel:
   5.175 -  "is_unit a \<Longrightarrow> b * a = c * a \<longleftrightarrow> b = c"
   5.176 -  using unit_mult_left_cancel [of a b c] by (auto simp add: ac_simps)
   5.177 -
   5.178 -lemma unit_div_cancel:
   5.179 -  assumes "is_unit a"
   5.180 -  shows "b div a = c div a \<longleftrightarrow> b = c"
   5.181 -proof -
   5.182 -  from assms have "is_unit (1 div a)" by simp
   5.183 -  then have "b * (1 div a) = c * (1 div a) \<longleftrightarrow> b = c"
   5.184 -    by (rule unit_mult_right_cancel)
   5.185 -  with assms show ?thesis by simp
   5.186 -qed
   5.187 -  
   5.188 -
   5.189 -text \<open>Associated elements in a ring – an equivalence relation induced by the quasi-order divisibility \<close>
   5.190 -
   5.191 -definition associated :: "'a \<Rightarrow> 'a \<Rightarrow> bool" 
   5.192 -where
   5.193 -  "associated a b \<longleftrightarrow> a dvd b \<and> b dvd a"
   5.194 -
   5.195 -lemma associatedI:
   5.196 -  "a dvd b \<Longrightarrow> b dvd a \<Longrightarrow> associated a b"
   5.197 -  by (simp add: associated_def)
   5.198 -
   5.199 -lemma associatedD1:
   5.200 -  "associated a b \<Longrightarrow> a dvd b"
   5.201 -  by (simp add: associated_def)
   5.202 -
   5.203 -lemma associatedD2:
   5.204 -  "associated a b \<Longrightarrow> b dvd a"
   5.205 -  by (simp add: associated_def)
   5.206 -
   5.207 -lemma associated_refl [simp]:
   5.208 -  "associated a a"
   5.209 -  by (auto intro: associatedI)
   5.210 -
   5.211 -lemma associated_sym:
   5.212 -  "associated b a \<longleftrightarrow> associated a b"
   5.213 -  by (auto intro: associatedI dest: associatedD1 associatedD2)
   5.214 -
   5.215 -lemma associated_trans:
   5.216 -  "associated a b \<Longrightarrow> associated b c \<Longrightarrow> associated a c"
   5.217 -  by (auto intro: associatedI dvd_trans dest: associatedD1 associatedD2)
   5.218 -
   5.219 -lemma equivp_associated:
   5.220 -  "equivp associated"
   5.221 -proof (rule equivpI)
   5.222 -  show "reflp associated"
   5.223 -    by (rule reflpI) simp
   5.224 -  show "symp associated"
   5.225 -    by (rule sympI) (simp add: associated_sym)
   5.226 -  show "transp associated"
   5.227 -    by (rule transpI) (fact associated_trans)
   5.228 -qed
   5.229 -
   5.230 -lemma associated_0 [simp]:
   5.231 -  "associated 0 b \<longleftrightarrow> b = 0"
   5.232 -  "associated a 0 \<longleftrightarrow> a = 0"
   5.233 -  by (auto dest: associatedD1 associatedD2)
   5.234 -
   5.235 -lemma associated_unit:
   5.236 -  "associated a b \<Longrightarrow> is_unit a \<Longrightarrow> is_unit b"
   5.237 -  using dvd_unit_imp_unit by (auto dest!: associatedD1 associatedD2)
   5.238 -
   5.239 -lemma is_unit_associatedI:
   5.240 -  assumes "is_unit c" and "a = c * b"
   5.241 -  shows "associated a b"
   5.242 -proof (rule associatedI)
   5.243 -  from `a = c * b` show "b dvd a" by auto
   5.244 -  from `is_unit c` obtain d where "c * d = 1" by (rule is_unitE)
   5.245 -  moreover from `a = c * b` have "d * a = d * (c * b)" by simp
   5.246 -  ultimately have "b = a * d" by (simp add: ac_simps)
   5.247 -  then show "a dvd b" ..
   5.248 -qed
   5.249 -
   5.250 -lemma associated_is_unitE:
   5.251 -  assumes "associated a b"
   5.252 -  obtains c where "is_unit c" and "a = c * b"
   5.253 -proof (cases "b = 0")
   5.254 -  case True with assms have "is_unit 1" and "a = 1 * b" by simp_all
   5.255 -  with that show thesis .
   5.256 -next
   5.257 -  case False
   5.258 -  from assms have "a dvd b" and "b dvd a" by (auto dest: associatedD1 associatedD2)
   5.259 -  then obtain c d where "b = a * d" and "a = b * c" by (blast elim: dvdE)
   5.260 -  then have "a = c * b" and "(c * d) * b = 1 * b" by (simp_all add: ac_simps)
   5.261 -  with False have "c * d = 1" using mult_cancel_right [of "c * d" b 1] by simp
   5.262 -  then have "is_unit c" by auto
   5.263 -  with `a = c * b` that show thesis by blast
   5.264 -qed
   5.265 -  
   5.266 -lemmas unit_simps = mult_unit_dvd_iff div_unit_dvd_iff dvd_mult_unit_iff 
   5.267 -  dvd_div_unit_iff unit_div_mult_swap unit_div_commute
   5.268 -  unit_mult_left_cancel unit_mult_right_cancel unit_div_cancel 
   5.269 -  unit_eq_div1 unit_eq_div2
   5.270 -
   5.271 -end
   5.272 -
   5.273 -lemma is_unit_int:
   5.274 -  "is_unit (k::int) \<longleftrightarrow> k = 1 \<or> k = - 1"
   5.275 -  by auto
   5.276 -
   5.277    
   5.278  text {*
   5.279    A Euclidean semiring is a semiring upon which the Euclidean algorithm can be
     6.1 --- a/src/HOL/Rings.thy	Fri Jun 19 07:53:33 2015 +0200
     6.2 +++ b/src/HOL/Rings.thy	Fri Jun 19 07:53:35 2015 +0200
     6.3 @@ -630,6 +630,260 @@
     6.4  
     6.5  class idom_divide = idom + semidom_divide
     6.6  
     6.7 +class algebraic_semidom = semidom_divide
     6.8 +begin
     6.9 +
    6.10 +lemma dvd_div_mult_self [simp]:
    6.11 +  "a dvd b \<Longrightarrow> b div a * a = b"
    6.12 +  by (cases "a = 0") (auto elim: dvdE simp add: ac_simps)
    6.13 +
    6.14 +lemma dvd_mult_div_cancel [simp]:
    6.15 +  "a dvd b \<Longrightarrow> a * (b div a) = b"
    6.16 +  using dvd_div_mult_self [of a b] by (simp add: ac_simps)
    6.17 +  
    6.18 +lemma div_mult_swap:
    6.19 +  assumes "c dvd b"
    6.20 +  shows "a * (b div c) = (a * b) div c"
    6.21 +proof (cases "c = 0")
    6.22 +  case True then show ?thesis by simp
    6.23 +next
    6.24 +  case False from assms obtain d where "b = c * d" ..
    6.25 +  moreover from False have "a * divide (d * c) c = ((a * d) * c) div c"
    6.26 +    by simp
    6.27 +  ultimately show ?thesis by (simp add: ac_simps)
    6.28 +qed
    6.29 +
    6.30 +lemma dvd_div_mult:
    6.31 +  assumes "c dvd b"
    6.32 +  shows "b div c * a = (b * a) div c"
    6.33 +  using assms div_mult_swap [of c b a] by (simp add: ac_simps)
    6.34 +
    6.35 +  
    6.36 +text \<open>Units: invertible elements in a ring\<close>
    6.37 +
    6.38 +abbreviation is_unit :: "'a \<Rightarrow> bool"
    6.39 +where
    6.40 +  "is_unit a \<equiv> a dvd 1"
    6.41 +
    6.42 +lemma not_is_unit_0 [simp]:
    6.43 +  "\<not> is_unit 0"
    6.44 +  by simp
    6.45 +
    6.46 +lemma unit_imp_dvd [dest]: 
    6.47 +  "is_unit b \<Longrightarrow> b dvd a"
    6.48 +  by (rule dvd_trans [of _ 1]) simp_all
    6.49 +
    6.50 +lemma unit_dvdE:
    6.51 +  assumes "is_unit a"
    6.52 +  obtains c where "a \<noteq> 0" and "b = a * c"
    6.53 +proof -
    6.54 +  from assms have "a dvd b" by auto
    6.55 +  then obtain c where "b = a * c" ..
    6.56 +  moreover from assms have "a \<noteq> 0" by auto
    6.57 +  ultimately show thesis using that by blast
    6.58 +qed
    6.59 +
    6.60 +lemma dvd_unit_imp_unit:
    6.61 +  "a dvd b \<Longrightarrow> is_unit b \<Longrightarrow> is_unit a"
    6.62 +  by (rule dvd_trans)
    6.63 +
    6.64 +lemma unit_div_1_unit [simp, intro]:
    6.65 +  assumes "is_unit a"
    6.66 +  shows "is_unit (1 div a)"
    6.67 +proof -
    6.68 +  from assms have "1 = 1 div a * a" by simp
    6.69 +  then show "is_unit (1 div a)" by (rule dvdI)
    6.70 +qed
    6.71 +
    6.72 +lemma is_unitE [elim?]:
    6.73 +  assumes "is_unit a"
    6.74 +  obtains b where "a \<noteq> 0" and "b \<noteq> 0"
    6.75 +    and "is_unit b" and "1 div a = b" and "1 div b = a"
    6.76 +    and "a * b = 1" and "c div a = c * b"
    6.77 +proof (rule that)
    6.78 +  def b \<equiv> "1 div a"
    6.79 +  then show "1 div a = b" by simp
    6.80 +  from b_def `is_unit a` show "is_unit b" by simp
    6.81 +  from `is_unit a` and `is_unit b` show "a \<noteq> 0" and "b \<noteq> 0" by auto
    6.82 +  from b_def `is_unit a` show "a * b = 1" by simp
    6.83 +  then have "1 = a * b" ..
    6.84 +  with b_def `b \<noteq> 0` show "1 div b = a" by simp
    6.85 +  from `is_unit a` have "a dvd c" ..
    6.86 +  then obtain d where "c = a * d" ..
    6.87 +  with `a \<noteq> 0` `a * b = 1` show "c div a = c * b"
    6.88 +    by (simp add: mult.assoc mult.left_commute [of a])
    6.89 +qed
    6.90 +
    6.91 +lemma unit_prod [intro]:
    6.92 +  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a * b)"
    6.93 +  by (subst mult_1_left [of 1, symmetric]) (rule mult_dvd_mono) 
    6.94 +  
    6.95 +lemma unit_div [intro]:
    6.96 +  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a div b)"
    6.97 +  by (erule is_unitE [of b a]) (simp add: ac_simps unit_prod)
    6.98 +
    6.99 +lemma mult_unit_dvd_iff:
   6.100 +  assumes "is_unit b"
   6.101 +  shows "a * b dvd c \<longleftrightarrow> a dvd c"
   6.102 +proof
   6.103 +  assume "a * b dvd c"
   6.104 +  with assms show "a dvd c"
   6.105 +    by (simp add: dvd_mult_left)
   6.106 +next
   6.107 +  assume "a dvd c"
   6.108 +  then obtain k where "c = a * k" ..
   6.109 +  with assms have "c = (a * b) * (1 div b * k)"
   6.110 +    by (simp add: mult_ac)
   6.111 +  then show "a * b dvd c" by (rule dvdI)
   6.112 +qed
   6.113 +
   6.114 +lemma dvd_mult_unit_iff:
   6.115 +  assumes "is_unit b"
   6.116 +  shows "a dvd c * b \<longleftrightarrow> a dvd c"
   6.117 +proof
   6.118 +  assume "a dvd c * b"
   6.119 +  with assms have "c * b dvd c * (b * (1 div b))"
   6.120 +    by (subst mult_assoc [symmetric]) simp
   6.121 +  also from `is_unit b` have "b * (1 div b) = 1" by (rule is_unitE) simp
   6.122 +  finally have "c * b dvd c" by simp
   6.123 +  with `a dvd c * b` show "a dvd c" by (rule dvd_trans)
   6.124 +next
   6.125 +  assume "a dvd c"
   6.126 +  then show "a dvd c * b" by simp
   6.127 +qed
   6.128 +
   6.129 +lemma div_unit_dvd_iff:
   6.130 +  "is_unit b \<Longrightarrow> a div b dvd c \<longleftrightarrow> a dvd c"
   6.131 +  by (erule is_unitE [of _ a]) (auto simp add: mult_unit_dvd_iff)
   6.132 +
   6.133 +lemma dvd_div_unit_iff:
   6.134 +  "is_unit b \<Longrightarrow> a dvd c div b \<longleftrightarrow> a dvd c"
   6.135 +  by (erule is_unitE [of _ c]) (simp add: dvd_mult_unit_iff)
   6.136 +
   6.137 +lemmas unit_dvd_iff = mult_unit_dvd_iff div_unit_dvd_iff
   6.138 +  dvd_mult_unit_iff dvd_div_unit_iff -- \<open>FIXME consider fact collection\<close>
   6.139 +
   6.140 +lemma unit_mult_div_div [simp]:
   6.141 +  "is_unit a \<Longrightarrow> b * (1 div a) = b div a"
   6.142 +  by (erule is_unitE [of _ b]) simp
   6.143 +
   6.144 +lemma unit_div_mult_self [simp]:
   6.145 +  "is_unit a \<Longrightarrow> b div a * a = b"
   6.146 +  by (rule dvd_div_mult_self) auto
   6.147 +
   6.148 +lemma unit_div_1_div_1 [simp]:
   6.149 +  "is_unit a \<Longrightarrow> 1 div (1 div a) = a"
   6.150 +  by (erule is_unitE) simp
   6.151 +
   6.152 +lemma unit_div_mult_swap:
   6.153 +  "is_unit c \<Longrightarrow> a * (b div c) = (a * b) div c"
   6.154 +  by (erule unit_dvdE [of _ b]) (simp add: mult.left_commute [of _ c])
   6.155 +
   6.156 +lemma unit_div_commute:
   6.157 +  "is_unit b \<Longrightarrow> (a div b) * c = (a * c) div b"
   6.158 +  using unit_div_mult_swap [of b c a] by (simp add: ac_simps)
   6.159 +
   6.160 +lemma unit_eq_div1:
   6.161 +  "is_unit b \<Longrightarrow> a div b = c \<longleftrightarrow> a = c * b"
   6.162 +  by (auto elim: is_unitE)
   6.163 +
   6.164 +lemma unit_eq_div2:
   6.165 +  "is_unit b \<Longrightarrow> a = c div b \<longleftrightarrow> a * b = c"
   6.166 +  using unit_eq_div1 [of b c a] by auto
   6.167 +
   6.168 +lemma unit_mult_left_cancel:
   6.169 +  assumes "is_unit a"
   6.170 +  shows "a * b = a * c \<longleftrightarrow> b = c" (is "?P \<longleftrightarrow> ?Q")
   6.171 +  using assms mult_cancel_left [of a b c] by auto 
   6.172 +
   6.173 +lemma unit_mult_right_cancel:
   6.174 +  "is_unit a \<Longrightarrow> b * a = c * a \<longleftrightarrow> b = c"
   6.175 +  using unit_mult_left_cancel [of a b c] by (auto simp add: ac_simps)
   6.176 +
   6.177 +lemma unit_div_cancel:
   6.178 +  assumes "is_unit a"
   6.179 +  shows "b div a = c div a \<longleftrightarrow> b = c"
   6.180 +proof -
   6.181 +  from assms have "is_unit (1 div a)" by simp
   6.182 +  then have "b * (1 div a) = c * (1 div a) \<longleftrightarrow> b = c"
   6.183 +    by (rule unit_mult_right_cancel)
   6.184 +  with assms show ?thesis by simp
   6.185 +qed
   6.186 +  
   6.187 +
   6.188 +text \<open>Associated elements in a ring – an equivalence relation induced by the quasi-order divisibility \<close>
   6.189 +
   6.190 +definition associated :: "'a \<Rightarrow> 'a \<Rightarrow> bool" 
   6.191 +where
   6.192 +  "associated a b \<longleftrightarrow> a dvd b \<and> b dvd a"
   6.193 +
   6.194 +lemma associatedI:
   6.195 +  "a dvd b \<Longrightarrow> b dvd a \<Longrightarrow> associated a b"
   6.196 +  by (simp add: associated_def)
   6.197 +
   6.198 +lemma associatedD1:
   6.199 +  "associated a b \<Longrightarrow> a dvd b"
   6.200 +  by (simp add: associated_def)
   6.201 +
   6.202 +lemma associatedD2:
   6.203 +  "associated a b \<Longrightarrow> b dvd a"
   6.204 +  by (simp add: associated_def)
   6.205 +
   6.206 +lemma associated_refl [simp]:
   6.207 +  "associated a a"
   6.208 +  by (auto intro: associatedI)
   6.209 +
   6.210 +lemma associated_sym:
   6.211 +  "associated b a \<longleftrightarrow> associated a b"
   6.212 +  by (auto intro: associatedI dest: associatedD1 associatedD2)
   6.213 +
   6.214 +lemma associated_trans:
   6.215 +  "associated a b \<Longrightarrow> associated b c \<Longrightarrow> associated a c"
   6.216 +  by (auto intro: associatedI dvd_trans dest: associatedD1 associatedD2)
   6.217 +
   6.218 +lemma associated_0 [simp]:
   6.219 +  "associated 0 b \<longleftrightarrow> b = 0"
   6.220 +  "associated a 0 \<longleftrightarrow> a = 0"
   6.221 +  by (auto dest: associatedD1 associatedD2)
   6.222 +
   6.223 +lemma associated_unit:
   6.224 +  "associated a b \<Longrightarrow> is_unit a \<Longrightarrow> is_unit b"
   6.225 +  using dvd_unit_imp_unit by (auto dest!: associatedD1 associatedD2)
   6.226 +
   6.227 +lemma is_unit_associatedI:
   6.228 +  assumes "is_unit c" and "a = c * b"
   6.229 +  shows "associated a b"
   6.230 +proof (rule associatedI)
   6.231 +  from `a = c * b` show "b dvd a" by auto
   6.232 +  from `is_unit c` obtain d where "c * d = 1" by (rule is_unitE)
   6.233 +  moreover from `a = c * b` have "d * a = d * (c * b)" by simp
   6.234 +  ultimately have "b = a * d" by (simp add: ac_simps)
   6.235 +  then show "a dvd b" ..
   6.236 +qed
   6.237 +
   6.238 +lemma associated_is_unitE:
   6.239 +  assumes "associated a b"
   6.240 +  obtains c where "is_unit c" and "a = c * b"
   6.241 +proof (cases "b = 0")
   6.242 +  case True with assms have "is_unit 1" and "a = 1 * b" by simp_all
   6.243 +  with that show thesis .
   6.244 +next
   6.245 +  case False
   6.246 +  from assms have "a dvd b" and "b dvd a" by (auto dest: associatedD1 associatedD2)
   6.247 +  then obtain c d where "b = a * d" and "a = b * c" by (blast elim: dvdE)
   6.248 +  then have "a = c * b" and "(c * d) * b = 1 * b" by (simp_all add: ac_simps)
   6.249 +  with False have "c * d = 1" using mult_cancel_right [of "c * d" b 1] by simp
   6.250 +  then have "is_unit c" by auto
   6.251 +  with `a = c * b` that show thesis by blast
   6.252 +qed
   6.253 +  
   6.254 +lemmas unit_simps = mult_unit_dvd_iff div_unit_dvd_iff dvd_mult_unit_iff 
   6.255 +  dvd_div_unit_iff unit_div_mult_swap unit_div_commute
   6.256 +  unit_mult_left_cancel unit_mult_right_cancel unit_div_cancel 
   6.257 +  unit_eq_div1 unit_eq_div2
   6.258 +
   6.259 +end
   6.260 +
   6.261  class ordered_semiring = semiring + comm_monoid_add + ordered_ab_semigroup_add +
   6.262    assumes mult_left_mono: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> c * a \<le> c * b"
   6.263    assumes mult_right_mono: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> a * c \<le> b * c"