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: |