src/HOL/Groups_Big.thy
changeset 66804 3f9bb52082c4
parent 66364 fa3247e6ee4b
child 66936 cf8d8fc23891
equal deleted inserted replaced
66803:dd8922885a68 66804:3f9bb52082c4
   423     by (simp add: union_inter_neutral)
   423     by (simp add: union_inter_neutral)
   424   with \<open>finite B\<close> \<open>A \<notin> B\<close> show ?case
   424   with \<open>finite B\<close> \<open>A \<notin> B\<close> show ?case
   425     by (simp add: H)
   425     by (simp add: H)
   426 qed
   426 qed
   427 
   427 
   428 lemma commute: "F (\<lambda>i. F (g i) B) A = F (\<lambda>j. F (\<lambda>i. g i j) A) B"
   428 lemma swap: "F (\<lambda>i. F (g i) B) A = F (\<lambda>j. F (\<lambda>i. g i j) A) B"
   429   unfolding cartesian_product
   429   unfolding cartesian_product
   430   by (rule reindex_bij_witness [where i = "\<lambda>(i, j). (j, i)" and j = "\<lambda>(i, j). (j, i)"]) auto
   430   by (rule reindex_bij_witness [where i = "\<lambda>(i, j). (j, i)" and j = "\<lambda>(i, j). (j, i)"]) auto
   431 
   431 
   432 lemma commute_restrict:
   432 lemma swap_restrict:
   433   "finite A \<Longrightarrow> finite B \<Longrightarrow>
   433   "finite A \<Longrightarrow> finite B \<Longrightarrow>
   434     F (\<lambda>x. F (g x) {y. y \<in> B \<and> R x y}) A = F (\<lambda>y. F (\<lambda>x. g x y) {x. x \<in> A \<and> R x y}) B"
   434     F (\<lambda>x. F (g x) {y. y \<in> B \<and> R x y}) A = F (\<lambda>y. F (\<lambda>x. g x y) {x. x \<in> A \<and> R x y}) B"
   435   by (simp add: inter_filter) (rule commute)
   435   by (simp add: inter_filter) (rule swap)
   436 
   436 
   437 lemma Plus:
   437 lemma Plus:
   438   fixes A :: "'b set" and B :: "'c set"
   438   fixes A :: "'b set" and B :: "'c set"
   439   assumes fin: "finite A" "finite B"
   439   assumes fin: "finite A" "finite B"
   440   shows "F g (A <+> B) = F (g \<circ> Inl) A \<^bold>* F (g \<circ> Inr) B"
   440   shows "F g (A <+> B) = F (g \<circ> Inl) A \<^bold>* F (g \<circ> Inr) B"
   538   have "{y. y\<in> f`S \<and> f x = y} = {f x}" if "x \<in> S" for x
   538   have "{y. y\<in> f`S \<and> f x = y} = {f x}" if "x \<in> S" for x
   539     using that by auto
   539     using that by auto
   540   then have "sum g S = sum (\<lambda>x. sum (\<lambda>y. g x) {y. y\<in> f`S \<and> f x = y}) S"
   540   then have "sum g S = sum (\<lambda>x. sum (\<lambda>y. g x) {y. y\<in> f`S \<and> f x = y}) S"
   541     by simp
   541     by simp
   542   also have "\<dots> = sum (\<lambda>y. sum g {x. x \<in> S \<and> f x = y}) (f ` S)"
   542   also have "\<dots> = sum (\<lambda>y. sum g {x. x \<in> S \<and> f x = y}) (f ` S)"
   543     by (rule sum.commute_restrict [OF fin finite_imageI [OF fin]])
   543     by (rule sum.swap_restrict [OF fin finite_imageI [OF fin]])
   544   finally show ?thesis .
   544   finally show ?thesis .
   545 qed
   545 qed
   546 
   546 
   547 
   547 
   548 subsubsection \<open>Properties in more restricted classes of structures\<close>
   548 subsubsection \<open>Properties in more restricted classes of structures\<close>
   841   unfolding sum.remove [OF assms] by auto
   841   unfolding sum.remove [OF assms] by auto
   842 
   842 
   843 lemma sum_product:
   843 lemma sum_product:
   844   fixes f :: "'a \<Rightarrow> 'b::semiring_0"
   844   fixes f :: "'a \<Rightarrow> 'b::semiring_0"
   845   shows "sum f A * sum g B = (\<Sum>i\<in>A. \<Sum>j\<in>B. f i * g j)"
   845   shows "sum f A * sum g B = (\<Sum>i\<in>A. \<Sum>j\<in>B. f i * g j)"
   846   by (simp add: sum_distrib_left sum_distrib_right) (rule sum.commute)
   846   by (simp add: sum_distrib_left sum_distrib_right) (rule sum.swap)
   847 
   847 
   848 lemma sum_mult_sum_if_inj:
   848 lemma sum_mult_sum_if_inj:
   849   fixes f :: "'a \<Rightarrow> 'b::semiring_0"
   849   fixes f :: "'a \<Rightarrow> 'b::semiring_0"
   850   shows "inj_on (\<lambda>(a, b). f a * g b) (A \<times> B) \<Longrightarrow>
   850   shows "inj_on (\<lambda>(a, b). f a * g b) (A \<times> B) \<Longrightarrow>
   851     sum f A * sum g B = sum id {f a * g b |a b. a \<in> A \<and> b \<in> B}"
   851     sum f A * sum g B = sum id {f a * g b |a b. a \<in> A \<and> b \<in> B}"
  1019     (is "?l = ?r")
  1019     (is "?l = ?r")
  1020 proof-
  1020 proof-
  1021   have "?l = sum (\<lambda>i. sum (\<lambda>x.1) {j\<in>t. R i j}) s"
  1021   have "?l = sum (\<lambda>i. sum (\<lambda>x.1) {j\<in>t. R i j}) s"
  1022     by auto
  1022     by auto
  1023   also have "\<dots> = ?r"
  1023   also have "\<dots> = ?r"
  1024     unfolding sum.commute_restrict [OF assms(1-2)]
  1024     unfolding sum.swap_restrict [OF assms(1-2)]
  1025     using assms(3) by auto
  1025     using assms(3) by auto
  1026   finally show ?thesis .
  1026   finally show ?thesis .
  1027 qed
  1027 qed
  1028 
  1028 
  1029 lemma sum_multicount:
  1029 lemma sum_multicount: