src/HOL/Rings.thy
changeset 60685 cb21b7022b00
parent 60615 e5fa1d5d3952
child 60688 01488b559910
     1.1 --- a/src/HOL/Rings.thy	Wed Jul 08 00:04:15 2015 +0200
     1.2 +++ b/src/HOL/Rings.thy	Wed Jul 08 14:01:34 2015 +0200
     1.3 @@ -909,6 +909,289 @@
     1.4  
     1.5  end
     1.6  
     1.7 +context algebraic_semidom
     1.8 +begin
     1.9 +
    1.10 +lemma is_unit_divide_mult_cancel_left:
    1.11 +  assumes "a \<noteq> 0" and "is_unit b"
    1.12 +  shows "a div (a * b) = 1 div b"
    1.13 +proof -
    1.14 +  from assms have "a div (a * b) = a div a div b"
    1.15 +    by (simp add: mult_unit_dvd_iff dvd_div_mult2_eq)
    1.16 +  with assms show ?thesis by simp
    1.17 +qed
    1.18 +
    1.19 +lemma is_unit_divide_mult_cancel_right:
    1.20 +  assumes "a \<noteq> 0" and "is_unit b"
    1.21 +  shows "a div (b * a) = 1 div b"
    1.22 +  using assms is_unit_divide_mult_cancel_left [of a b] by (simp add: ac_simps)
    1.23 +
    1.24 +end
    1.25 +
    1.26 +class normalization_semidom = algebraic_semidom +
    1.27 +  fixes normalize :: "'a \<Rightarrow> 'a"
    1.28 +    and unit_factor :: "'a \<Rightarrow> 'a"
    1.29 +  assumes unit_factor_mult_normalize [simp]: "unit_factor a * normalize a = a"
    1.30 +  assumes normalize_0 [simp]: "normalize 0 = 0"
    1.31 +    and unit_factor_0 [simp]: "unit_factor 0 = 0"
    1.32 +  assumes is_unit_normalize:
    1.33 +    "is_unit a  \<Longrightarrow> normalize a = 1"
    1.34 +  assumes unit_factor_is_unit [iff]: 
    1.35 +    "a \<noteq> 0 \<Longrightarrow> is_unit (unit_factor a)"
    1.36 +  assumes unit_factor_mult: "unit_factor (a * b) = unit_factor a * unit_factor b"
    1.37 +begin
    1.38 +
    1.39 +lemma unit_factor_dvd [simp]:
    1.40 +  "a \<noteq> 0 \<Longrightarrow> unit_factor a dvd b"
    1.41 +  by (rule unit_imp_dvd) simp
    1.42 +
    1.43 +lemma unit_factor_self [simp]:
    1.44 +  "unit_factor a dvd a"
    1.45 +  by (cases "a = 0") simp_all 
    1.46 +  
    1.47 +lemma normalize_mult_unit_factor [simp]:
    1.48 +  "normalize a * unit_factor a = a"
    1.49 +  using unit_factor_mult_normalize [of a] by (simp add: ac_simps)
    1.50 +
    1.51 +lemma normalize_eq_0_iff [simp]:
    1.52 +  "normalize a = 0 \<longleftrightarrow> a = 0" (is "?P \<longleftrightarrow> ?Q")
    1.53 +proof
    1.54 +  assume ?P
    1.55 +  moreover have "unit_factor a * normalize a = a" by simp
    1.56 +  ultimately show ?Q by simp 
    1.57 +next
    1.58 +  assume ?Q then show ?P by simp
    1.59 +qed
    1.60 +
    1.61 +lemma unit_factor_eq_0_iff [simp]:
    1.62 +  "unit_factor a = 0 \<longleftrightarrow> a = 0" (is "?P \<longleftrightarrow> ?Q")
    1.63 +proof
    1.64 +  assume ?P
    1.65 +  moreover have "unit_factor a * normalize a = a" by simp
    1.66 +  ultimately show ?Q by simp 
    1.67 +next
    1.68 +  assume ?Q then show ?P by simp
    1.69 +qed
    1.70 +
    1.71 +lemma is_unit_unit_factor:
    1.72 +  assumes "is_unit a" shows "unit_factor a = a"
    1.73 +proof - 
    1.74 +  from assms have "normalize a = 1" by (rule is_unit_normalize)
    1.75 +  moreover from unit_factor_mult_normalize have "unit_factor a * normalize a = a" .
    1.76 +  ultimately show ?thesis by simp
    1.77 +qed
    1.78 +
    1.79 +lemma unit_factor_1 [simp]:
    1.80 +  "unit_factor 1 = 1"
    1.81 +  by (rule is_unit_unit_factor) simp
    1.82 +
    1.83 +lemma normalize_1 [simp]:
    1.84 +  "normalize 1 = 1"
    1.85 +  by (rule is_unit_normalize) simp
    1.86 +
    1.87 +lemma normalize_1_iff:
    1.88 +  "normalize a = 1 \<longleftrightarrow> is_unit a" (is "?P \<longleftrightarrow> ?Q")
    1.89 +proof
    1.90 +  assume ?Q then show ?P by (rule is_unit_normalize)
    1.91 +next
    1.92 +  assume ?P
    1.93 +  then have "a \<noteq> 0" by auto
    1.94 +  from \<open>?P\<close> have "unit_factor a * normalize a = unit_factor a * 1"
    1.95 +    by simp
    1.96 +  then have "unit_factor a = a"
    1.97 +    by simp
    1.98 +  moreover have "is_unit (unit_factor a)"
    1.99 +    using \<open>a \<noteq> 0\<close> by simp
   1.100 +  ultimately show ?Q by simp
   1.101 +qed
   1.102 +  
   1.103 +lemma div_normalize [simp]:
   1.104 +  "a div normalize a = unit_factor a"
   1.105 +proof (cases "a = 0")
   1.106 +  case True then show ?thesis by simp
   1.107 +next
   1.108 +  case False then have "normalize a \<noteq> 0" by simp 
   1.109 +  with nonzero_mult_divide_cancel_right
   1.110 +  have "unit_factor a * normalize a div normalize a = unit_factor a" by blast
   1.111 +  then show ?thesis by simp
   1.112 +qed
   1.113 +
   1.114 +lemma div_unit_factor [simp]:
   1.115 +  "a div unit_factor a = normalize a"
   1.116 +proof (cases "a = 0")
   1.117 +  case True then show ?thesis by simp
   1.118 +next
   1.119 +  case False then have "unit_factor a \<noteq> 0" by simp 
   1.120 +  with nonzero_mult_divide_cancel_left
   1.121 +  have "unit_factor a * normalize a div unit_factor a = normalize a" by blast
   1.122 +  then show ?thesis by simp
   1.123 +qed
   1.124 +
   1.125 +lemma normalize_div [simp]:
   1.126 +  "normalize a div a = 1 div unit_factor a"
   1.127 +proof (cases "a = 0")
   1.128 +  case True then show ?thesis by simp
   1.129 +next
   1.130 +  case False
   1.131 +  have "normalize a div a = normalize a div (unit_factor a * normalize a)"
   1.132 +    by simp
   1.133 +  also have "\<dots> = 1 div unit_factor a"
   1.134 +    using False by (subst is_unit_divide_mult_cancel_right) simp_all
   1.135 +  finally show ?thesis .
   1.136 +qed
   1.137 +
   1.138 +lemma mult_one_div_unit_factor [simp]:
   1.139 +  "a * (1 div unit_factor b) = a div unit_factor b"
   1.140 +  by (cases "b = 0") simp_all
   1.141 +
   1.142 +lemma normalize_mult:
   1.143 +  "normalize (a * b) = normalize a * normalize b"
   1.144 +proof (cases "a = 0 \<or> b = 0")
   1.145 +  case True then show ?thesis by auto
   1.146 +next
   1.147 +  case False
   1.148 +  from unit_factor_mult_normalize have "unit_factor (a * b) * normalize (a * b) = a * b" .
   1.149 +  then have "normalize (a * b) = a * b div unit_factor (a * b)" by simp
   1.150 +  also have "\<dots> = a * b div unit_factor (b * a)" by (simp add: ac_simps)
   1.151 +  also have "\<dots> = a * b div unit_factor b div unit_factor a"
   1.152 +    using False by (simp add: unit_factor_mult is_unit_div_mult2_eq [symmetric])
   1.153 +  also have "\<dots> = a * (b div unit_factor b) div unit_factor a"
   1.154 +    using False by (subst unit_div_mult_swap) simp_all
   1.155 +  also have "\<dots> = normalize a * normalize b"
   1.156 +    using False by (simp add: mult.commute [of a] mult.commute [of "normalize a"] unit_div_mult_swap [symmetric])
   1.157 +  finally show ?thesis .
   1.158 +qed
   1.159 + 
   1.160 +lemma unit_factor_idem [simp]:
   1.161 +  "unit_factor (unit_factor a) = unit_factor a"
   1.162 +  by (cases "a = 0") (auto intro: is_unit_unit_factor)
   1.163 +
   1.164 +lemma normalize_unit_factor [simp]:
   1.165 +  "a \<noteq> 0 \<Longrightarrow> normalize (unit_factor a) = 1"
   1.166 +  by (rule is_unit_normalize) simp
   1.167 +  
   1.168 +lemma normalize_idem [simp]:
   1.169 +  "normalize (normalize a) = normalize a"
   1.170 +proof (cases "a = 0")
   1.171 +  case True then show ?thesis by simp
   1.172 +next
   1.173 +  case False
   1.174 +  have "normalize a = normalize (unit_factor a * normalize a)" by simp
   1.175 +  also have "\<dots> = normalize (unit_factor a) * normalize (normalize a)"
   1.176 +    by (simp only: normalize_mult)
   1.177 +  finally show ?thesis using False by simp_all
   1.178 +qed
   1.179 +
   1.180 +lemma unit_factor_normalize [simp]:
   1.181 +  assumes "a \<noteq> 0"
   1.182 +  shows "unit_factor (normalize a) = 1"
   1.183 +proof -
   1.184 +  from assms have "normalize a \<noteq> 0" by simp
   1.185 +  have "unit_factor (normalize a) * normalize (normalize a) = normalize a"
   1.186 +    by (simp only: unit_factor_mult_normalize)
   1.187 +  then have "unit_factor (normalize a) * normalize a = normalize a"
   1.188 +    by simp
   1.189 +  with \<open>normalize a \<noteq> 0\<close>
   1.190 +  have "unit_factor (normalize a) * normalize a div normalize a = normalize a div normalize a"
   1.191 +    by simp
   1.192 +  with \<open>normalize a \<noteq> 0\<close>
   1.193 +  show ?thesis by simp
   1.194 +qed
   1.195 +
   1.196 +lemma dvd_unit_factor_div:
   1.197 +  assumes "b dvd a"
   1.198 +  shows "unit_factor (a div b) = unit_factor a div unit_factor b"
   1.199 +proof -
   1.200 +  from assms have "a = a div b * b"
   1.201 +    by simp
   1.202 +  then have "unit_factor a = unit_factor (a div b * b)"
   1.203 +    by simp
   1.204 +  then show ?thesis
   1.205 +    by (cases "b = 0") (simp_all add: unit_factor_mult)
   1.206 +qed
   1.207 +
   1.208 +lemma dvd_normalize_div:
   1.209 +  assumes "b dvd a"
   1.210 +  shows "normalize (a div b) = normalize a div normalize b"
   1.211 +proof -
   1.212 +  from assms have "a = a div b * b"
   1.213 +    by simp
   1.214 +  then have "normalize a = normalize (a div b * b)"
   1.215 +    by simp
   1.216 +  then show ?thesis
   1.217 +    by (cases "b = 0") (simp_all add: normalize_mult)
   1.218 +qed
   1.219 +
   1.220 +lemma normalize_dvd_iff [simp]:
   1.221 +  "normalize a dvd b \<longleftrightarrow> a dvd b"
   1.222 +proof -
   1.223 +  have "normalize a dvd b \<longleftrightarrow> unit_factor a * normalize a dvd b"
   1.224 +    using mult_unit_dvd_iff [of "unit_factor a" "normalize a" b]
   1.225 +      by (cases "a = 0") simp_all
   1.226 +  then show ?thesis by simp
   1.227 +qed
   1.228 +
   1.229 +lemma dvd_normalize_iff [simp]:
   1.230 +  "a dvd normalize b \<longleftrightarrow> a dvd b"
   1.231 +proof -
   1.232 +  have "a dvd normalize  b \<longleftrightarrow> a dvd normalize b * unit_factor b"
   1.233 +    using dvd_mult_unit_iff [of "unit_factor b" a "normalize b"]
   1.234 +      by (cases "b = 0") simp_all
   1.235 +  then show ?thesis by simp
   1.236 +qed
   1.237 +
   1.238 +lemma associated_normalize_left [simp]:
   1.239 +  "associated (normalize a) b \<longleftrightarrow> associated a b"
   1.240 +  by (auto simp add: associated_def)
   1.241 +
   1.242 +lemma associated_normalize_right [simp]:
   1.243 +  "associated a (normalize b) \<longleftrightarrow> associated a b"
   1.244 +  by (auto simp add: associated_def)
   1.245 +
   1.246 +lemma associated_iff_normalize:
   1.247 +  "associated a b \<longleftrightarrow> normalize a = normalize b" (is "?P \<longleftrightarrow> ?Q")
   1.248 +proof (cases "a = 0 \<or> b = 0")
   1.249 +  case True then show ?thesis by auto
   1.250 +next
   1.251 +  case False
   1.252 +  show ?thesis
   1.253 +  proof
   1.254 +    assume ?P then show ?Q
   1.255 +      by (rule associated_is_unitE) (simp add: normalize_mult is_unit_normalize)
   1.256 +  next
   1.257 +    from False have *: "is_unit (unit_factor a div unit_factor b)"
   1.258 +      by auto
   1.259 +    assume ?Q then have "unit_factor a * normalize a = unit_factor a * normalize b"
   1.260 +      by simp
   1.261 +    then have "a = unit_factor a * (b div unit_factor b)"
   1.262 +      by simp
   1.263 +    with False have "a = (unit_factor a div unit_factor b) * b"
   1.264 +      by (simp add: unit_div_commute unit_div_mult_swap [symmetric])
   1.265 +    with * show ?P 
   1.266 +      by (rule is_unit_associatedI)
   1.267 +  qed
   1.268 +qed
   1.269 +
   1.270 +lemma associated_eqI:
   1.271 +  assumes "associated a b"
   1.272 +  assumes "a \<noteq> 0 \<Longrightarrow> unit_factor a = 1" and "b \<noteq> 0 \<Longrightarrow> unit_factor b = 1"
   1.273 +  shows "a = b"
   1.274 +proof (cases "a = 0")
   1.275 +  case True with assms show ?thesis by simp
   1.276 +next
   1.277 +  case False with assms have "b \<noteq> 0" by auto
   1.278 +  with False assms have "unit_factor a = unit_factor b"
   1.279 +    by simp
   1.280 +  moreover from assms have "normalize a = normalize b"
   1.281 +    by (simp add: associated_iff_normalize)
   1.282 +  ultimately have "unit_factor a * normalize a = unit_factor b * normalize b"
   1.283 +    by simp
   1.284 +  then show ?thesis
   1.285 +    by simp
   1.286 +qed
   1.287 +
   1.288 +end
   1.289 +
   1.290  class ordered_semiring = semiring + comm_monoid_add + ordered_ab_semigroup_add +
   1.291    assumes mult_left_mono: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> c * a \<le> c * b"
   1.292    assumes mult_right_mono: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> a * c \<le> b * c"