src/HOL/Rings.thy
 changeset 60517 f16e4fb20652 parent 60516 0826b7025d07 child 60529 24c2ef12318b
1.1 --- a/src/HOL/Rings.thy	Fri Jun 19 07:53:33 2015 +0200
1.2 +++ b/src/HOL/Rings.thy	Fri Jun 19 07:53:35 2015 +0200
1.3 @@ -630,6 +630,260 @@
1.5  class idom_divide = idom + semidom_divide
1.7 +class algebraic_semidom = semidom_divide
1.8 +begin
1.9 +
1.10 +lemma dvd_div_mult_self [simp]:
1.11 +  "a dvd b \<Longrightarrow> b div a * a = b"
1.12 +  by (cases "a = 0") (auto elim: dvdE simp add: ac_simps)
1.13 +
1.14 +lemma dvd_mult_div_cancel [simp]:
1.15 +  "a dvd b \<Longrightarrow> a * (b div a) = b"
1.16 +  using dvd_div_mult_self [of a b] by (simp add: ac_simps)
1.17 +
1.18 +lemma div_mult_swap:
1.19 +  assumes "c dvd b"
1.20 +  shows "a * (b div c) = (a * b) div c"
1.21 +proof (cases "c = 0")
1.22 +  case True then show ?thesis by simp
1.23 +next
1.24 +  case False from assms obtain d where "b = c * d" ..
1.25 +  moreover from False have "a * divide (d * c) c = ((a * d) * c) div c"
1.26 +    by simp
1.27 +  ultimately show ?thesis by (simp add: ac_simps)
1.28 +qed
1.29 +
1.30 +lemma dvd_div_mult:
1.31 +  assumes "c dvd b"
1.32 +  shows "b div c * a = (b * a) div c"
1.33 +  using assms div_mult_swap [of c b a] by (simp add: ac_simps)
1.34 +
1.35 +
1.36 +text \<open>Units: invertible elements in a ring\<close>
1.37 +
1.38 +abbreviation is_unit :: "'a \<Rightarrow> bool"
1.39 +where
1.40 +  "is_unit a \<equiv> a dvd 1"
1.41 +
1.42 +lemma not_is_unit_0 [simp]:
1.43 +  "\<not> is_unit 0"
1.44 +  by simp
1.45 +
1.46 +lemma unit_imp_dvd [dest]:
1.47 +  "is_unit b \<Longrightarrow> b dvd a"
1.48 +  by (rule dvd_trans [of _ 1]) simp_all
1.49 +
1.50 +lemma unit_dvdE:
1.51 +  assumes "is_unit a"
1.52 +  obtains c where "a \<noteq> 0" and "b = a * c"
1.53 +proof -
1.54 +  from assms have "a dvd b" by auto
1.55 +  then obtain c where "b = a * c" ..
1.56 +  moreover from assms have "a \<noteq> 0" by auto
1.57 +  ultimately show thesis using that by blast
1.58 +qed
1.59 +
1.60 +lemma dvd_unit_imp_unit:
1.61 +  "a dvd b \<Longrightarrow> is_unit b \<Longrightarrow> is_unit a"
1.62 +  by (rule dvd_trans)
1.63 +
1.64 +lemma unit_div_1_unit [simp, intro]:
1.65 +  assumes "is_unit a"
1.66 +  shows "is_unit (1 div a)"
1.67 +proof -
1.68 +  from assms have "1 = 1 div a * a" by simp
1.69 +  then show "is_unit (1 div a)" by (rule dvdI)
1.70 +qed
1.71 +
1.72 +lemma is_unitE [elim?]:
1.73 +  assumes "is_unit a"
1.74 +  obtains b where "a \<noteq> 0" and "b \<noteq> 0"
1.75 +    and "is_unit b" and "1 div a = b" and "1 div b = a"
1.76 +    and "a * b = 1" and "c div a = c * b"
1.77 +proof (rule that)
1.78 +  def b \<equiv> "1 div a"
1.79 +  then show "1 div a = b" by simp
1.80 +  from b_def `is_unit a` show "is_unit b" by simp
1.81 +  from `is_unit a` and `is_unit b` show "a \<noteq> 0" and "b \<noteq> 0" by auto
1.82 +  from b_def `is_unit a` show "a * b = 1" by simp
1.83 +  then have "1 = a * b" ..
1.84 +  with b_def `b \<noteq> 0` show "1 div b = a" by simp
1.85 +  from `is_unit a` have "a dvd c" ..
1.86 +  then obtain d where "c = a * d" ..
1.87 +  with `a \<noteq> 0` `a * b = 1` show "c div a = c * b"
1.88 +    by (simp add: mult.assoc mult.left_commute [of a])
1.89 +qed
1.90 +
1.91 +lemma unit_prod [intro]:
1.92 +  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a * b)"
1.93 +  by (subst mult_1_left [of 1, symmetric]) (rule mult_dvd_mono)
1.94 +
1.95 +lemma unit_div [intro]:
1.96 +  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a div b)"
1.97 +  by (erule is_unitE [of b a]) (simp add: ac_simps unit_prod)
1.98 +
1.99 +lemma mult_unit_dvd_iff:
1.100 +  assumes "is_unit b"
1.101 +  shows "a * b dvd c \<longleftrightarrow> a dvd c"
1.102 +proof
1.103 +  assume "a * b dvd c"
1.104 +  with assms show "a dvd c"
1.105 +    by (simp add: dvd_mult_left)
1.106 +next
1.107 +  assume "a dvd c"
1.108 +  then obtain k where "c = a * k" ..
1.109 +  with assms have "c = (a * b) * (1 div b * k)"
1.110 +    by (simp add: mult_ac)
1.111 +  then show "a * b dvd c" by (rule dvdI)
1.112 +qed
1.114 +lemma dvd_mult_unit_iff:
1.115 +  assumes "is_unit b"
1.116 +  shows "a dvd c * b \<longleftrightarrow> a dvd c"
1.117 +proof
1.118 +  assume "a dvd c * b"
1.119 +  with assms have "c * b dvd c * (b * (1 div b))"
1.120 +    by (subst mult_assoc [symmetric]) simp
1.121 +  also from `is_unit b` have "b * (1 div b) = 1" by (rule is_unitE) simp
1.122 +  finally have "c * b dvd c" by simp
1.123 +  with `a dvd c * b` show "a dvd c" by (rule dvd_trans)
1.124 +next
1.125 +  assume "a dvd c"
1.126 +  then show "a dvd c * b" by simp
1.127 +qed
1.129 +lemma div_unit_dvd_iff:
1.130 +  "is_unit b \<Longrightarrow> a div b dvd c \<longleftrightarrow> a dvd c"
1.131 +  by (erule is_unitE [of _ a]) (auto simp add: mult_unit_dvd_iff)
1.133 +lemma dvd_div_unit_iff:
1.134 +  "is_unit b \<Longrightarrow> a dvd c div b \<longleftrightarrow> a dvd c"
1.135 +  by (erule is_unitE [of _ c]) (simp add: dvd_mult_unit_iff)
1.137 +lemmas unit_dvd_iff = mult_unit_dvd_iff div_unit_dvd_iff
1.138 +  dvd_mult_unit_iff dvd_div_unit_iff -- \<open>FIXME consider fact collection\<close>
1.140 +lemma unit_mult_div_div [simp]:
1.141 +  "is_unit a \<Longrightarrow> b * (1 div a) = b div a"
1.142 +  by (erule is_unitE [of _ b]) simp
1.144 +lemma unit_div_mult_self [simp]:
1.145 +  "is_unit a \<Longrightarrow> b div a * a = b"
1.146 +  by (rule dvd_div_mult_self) auto
1.148 +lemma unit_div_1_div_1 [simp]:
1.149 +  "is_unit a \<Longrightarrow> 1 div (1 div a) = a"
1.150 +  by (erule is_unitE) simp
1.152 +lemma unit_div_mult_swap:
1.153 +  "is_unit c \<Longrightarrow> a * (b div c) = (a * b) div c"
1.154 +  by (erule unit_dvdE [of _ b]) (simp add: mult.left_commute [of _ c])
1.156 +lemma unit_div_commute:
1.157 +  "is_unit b \<Longrightarrow> (a div b) * c = (a * c) div b"
1.158 +  using unit_div_mult_swap [of b c a] by (simp add: ac_simps)
1.160 +lemma unit_eq_div1:
1.161 +  "is_unit b \<Longrightarrow> a div b = c \<longleftrightarrow> a = c * b"
1.162 +  by (auto elim: is_unitE)
1.164 +lemma unit_eq_div2:
1.165 +  "is_unit b \<Longrightarrow> a = c div b \<longleftrightarrow> a * b = c"
1.166 +  using unit_eq_div1 [of b c a] by auto
1.168 +lemma unit_mult_left_cancel:
1.169 +  assumes "is_unit a"
1.170 +  shows "a * b = a * c \<longleftrightarrow> b = c" (is "?P \<longleftrightarrow> ?Q")
1.171 +  using assms mult_cancel_left [of a b c] by auto
1.173 +lemma unit_mult_right_cancel:
1.174 +  "is_unit a \<Longrightarrow> b * a = c * a \<longleftrightarrow> b = c"
1.175 +  using unit_mult_left_cancel [of a b c] by (auto simp add: ac_simps)
1.177 +lemma unit_div_cancel:
1.178 +  assumes "is_unit a"
1.179 +  shows "b div a = c div a \<longleftrightarrow> b = c"
1.180 +proof -
1.181 +  from assms have "is_unit (1 div a)" by simp
1.182 +  then have "b * (1 div a) = c * (1 div a) \<longleftrightarrow> b = c"
1.183 +    by (rule unit_mult_right_cancel)
1.184 +  with assms show ?thesis by simp
1.185 +qed
1.188 +text \<open>Associated elements in a ring – an equivalence relation induced by the quasi-order divisibility \<close>
1.190 +definition associated :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
1.191 +where
1.192 +  "associated a b \<longleftrightarrow> a dvd b \<and> b dvd a"
1.194 +lemma associatedI:
1.195 +  "a dvd b \<Longrightarrow> b dvd a \<Longrightarrow> associated a b"
1.196 +  by (simp add: associated_def)
1.198 +lemma associatedD1:
1.199 +  "associated a b \<Longrightarrow> a dvd b"
1.200 +  by (simp add: associated_def)
1.202 +lemma associatedD2:
1.203 +  "associated a b \<Longrightarrow> b dvd a"
1.204 +  by (simp add: associated_def)
1.206 +lemma associated_refl [simp]:
1.207 +  "associated a a"
1.208 +  by (auto intro: associatedI)
1.210 +lemma associated_sym:
1.211 +  "associated b a \<longleftrightarrow> associated a b"
1.212 +  by (auto intro: associatedI dest: associatedD1 associatedD2)
1.214 +lemma associated_trans:
1.215 +  "associated a b \<Longrightarrow> associated b c \<Longrightarrow> associated a c"
1.216 +  by (auto intro: associatedI dvd_trans dest: associatedD1 associatedD2)
1.218 +lemma associated_0 [simp]:
1.219 +  "associated 0 b \<longleftrightarrow> b = 0"
1.220 +  "associated a 0 \<longleftrightarrow> a = 0"
1.221 +  by (auto dest: associatedD1 associatedD2)
1.223 +lemma associated_unit:
1.224 +  "associated a b \<Longrightarrow> is_unit a \<Longrightarrow> is_unit b"
1.225 +  using dvd_unit_imp_unit by (auto dest!: associatedD1 associatedD2)
1.227 +lemma is_unit_associatedI:
1.228 +  assumes "is_unit c" and "a = c * b"
1.229 +  shows "associated a b"
1.230 +proof (rule associatedI)
1.231 +  from `a = c * b` show "b dvd a" by auto
1.232 +  from `is_unit c` obtain d where "c * d = 1" by (rule is_unitE)
1.233 +  moreover from `a = c * b` have "d * a = d * (c * b)" by simp
1.234 +  ultimately have "b = a * d" by (simp add: ac_simps)
1.235 +  then show "a dvd b" ..
1.236 +qed
1.238 +lemma associated_is_unitE:
1.239 +  assumes "associated a b"
1.240 +  obtains c where "is_unit c" and "a = c * b"
1.241 +proof (cases "b = 0")
1.242 +  case True with assms have "is_unit 1" and "a = 1 * b" by simp_all
1.243 +  with that show thesis .
1.244 +next
1.245 +  case False
1.246 +  from assms have "a dvd b" and "b dvd a" by (auto dest: associatedD1 associatedD2)
1.247 +  then obtain c d where "b = a * d" and "a = b * c" by (blast elim: dvdE)
1.248 +  then have "a = c * b" and "(c * d) * b = 1 * b" by (simp_all add: ac_simps)
1.249 +  with False have "c * d = 1" using mult_cancel_right [of "c * d" b 1] by simp
1.250 +  then have "is_unit c" by auto
1.251 +  with `a = c * b` that show thesis by blast
1.252 +qed
1.254 +lemmas unit_simps = mult_unit_dvd_iff div_unit_dvd_iff dvd_mult_unit_iff
1.255 +  dvd_div_unit_iff unit_div_mult_swap unit_div_commute
1.256 +  unit_mult_left_cancel unit_mult_right_cancel unit_div_cancel
1.257 +  unit_eq_div1 unit_eq_div2
1.259 +end
1.261  class ordered_semiring = semiring + comm_monoid_add + ordered_ab_semigroup_add +
1.262    assumes mult_left_mono: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> c * a \<le> c * b"
1.263    assumes mult_right_mono: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> a * c \<le> b * c"