src/HOL/Library/Multiset.thy
changeset 57518 2f640245fc6d
parent 57514 bdc2c6b40bf2
child 57966 6fab7e95587d
equal deleted inserted replaced
57517:f4904e2b3040 57518:2f640245fc6d
  1204 
  1204 
  1205 lemma setsum_unfold_msetsum:
  1205 lemma setsum_unfold_msetsum:
  1206   "setsum f A = msetsum (image_mset f (multiset_of_set A))"
  1206   "setsum f A = msetsum (image_mset f (multiset_of_set A))"
  1207   by (cases "finite A") (induct A rule: finite_induct, simp_all)
  1207   by (cases "finite A") (induct A rule: finite_induct, simp_all)
  1208 
  1208 
  1209 abbreviation msetsum_image :: "('b \<Rightarrow> 'a) \<Rightarrow> 'b multiset \<Rightarrow> 'a"
       
  1210 where
       
  1211   "msetsum_image f M \<equiv> msetsum (image_mset f M)"
       
  1212 
       
  1213 end
  1209 end
  1214 
  1210 
  1215 syntax
  1211 syntax
  1216   "_msetsum_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add" 
  1212   "_msetsum_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add" 
  1217       ("(3SUM _:#_. _)" [0, 51, 10] 10)
  1213       ("(3SUM _:#_. _)" [0, 51, 10] 10)
  1218 
  1214 
  1219 syntax (xsymbols)
  1215 syntax (xsymbols)
  1220   "_msetsum_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add" 
  1216   "_msetsum_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add" 
  1221       ("(3\<Sum>_:#_. _)" [0, 51, 10] 10)
  1217       ("(3\<Sum>_\<in>#_. _)" [0, 51, 10] 10)
  1222 
  1218 
  1223 syntax (HTML output)
  1219 syntax (HTML output)
  1224   "_msetsum_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add" 
  1220   "_msetsum_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add" 
  1225       ("(3\<Sum>_\<in>#_. _)" [0, 51, 10] 10)
  1221       ("(3\<Sum>_\<in>#_. _)" [0, 51, 10] 10)
  1226 
  1222 
  1227 translations
  1223 translations
  1228   "SUM i :# A. b" == "CONST msetsum_image (\<lambda>i. b) A"
  1224   "SUM i :# A. b" == "CONST msetsum (CONST image_mset (\<lambda>i. b) A)"
  1229 
  1225 
  1230 context comm_monoid_mult
  1226 context comm_monoid_mult
  1231 begin
  1227 begin
  1232 
  1228 
  1233 definition msetprod :: "'a multiset \<Rightarrow> 'a"
  1229 definition msetprod :: "'a multiset \<Rightarrow> 'a"
  1260 
  1256 
  1261 lemma msetprod_multiplicity:
  1257 lemma msetprod_multiplicity:
  1262   "msetprod M = setprod (\<lambda>x. x ^ count M x) (set_of M)"
  1258   "msetprod M = setprod (\<lambda>x. x ^ count M x) (set_of M)"
  1263   by (simp add: Multiset.fold_def setprod.eq_fold msetprod.eq_fold funpow_times_power comp_def)
  1259   by (simp add: Multiset.fold_def setprod.eq_fold msetprod.eq_fold funpow_times_power comp_def)
  1264 
  1260 
  1265 abbreviation msetprod_image :: "('b \<Rightarrow> 'a) \<Rightarrow> 'b multiset \<Rightarrow> 'a"
       
  1266 where
       
  1267   "msetprod_image f M \<equiv> msetprod (image_mset f M)"
       
  1268 
       
  1269 end
  1261 end
  1270 
  1262 
  1271 syntax
  1263 syntax
  1272   "_msetprod_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_mult" 
  1264   "_msetprod_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_mult" 
  1273       ("(3PROD _:#_. _)" [0, 51, 10] 10)
  1265       ("(3PROD _:#_. _)" [0, 51, 10] 10)
  1279 syntax (HTML output)
  1271 syntax (HTML output)
  1280   "_msetprod_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_mult" 
  1272   "_msetprod_image" :: "pttrn \<Rightarrow> 'b set \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_mult" 
  1281       ("(3\<Prod>_\<in>#_. _)" [0, 51, 10] 10)
  1273       ("(3\<Prod>_\<in>#_. _)" [0, 51, 10] 10)
  1282 
  1274 
  1283 translations
  1275 translations
  1284   "PROD i :# A. b" == "CONST msetprod_image (\<lambda>i. b) A"
  1276   "PROD i :# A. b" == "CONST msetprod (CONST image_mset (\<lambda>i. b) A)"
  1285 
  1277 
  1286 lemma (in comm_semiring_1) dvd_msetprod:
  1278 lemma (in comm_semiring_1) dvd_msetprod:
  1287   assumes "x \<in># A"
  1279   assumes "x \<in># A"
  1288   shows "x dvd msetprod A"
  1280   shows "x dvd msetprod A"
  1289 proof -
  1281 proof -