equal
deleted
inserted
replaced
1086 using insert |
1086 using insert |
1087 by (subst sum.insert) (auto simp: pairwise_insert) |
1087 by (subst sum.insert) (auto simp: pairwise_insert) |
1088 with insert show ?case by (simp add: pairwise_insert) |
1088 with insert show ?case by (simp add: pairwise_insert) |
1089 qed |
1089 qed |
1090 qed simp |
1090 qed simp |
1091 |
|
1092 lemma card_Union_image: |
|
1093 assumes "finite S" |
|
1094 assumes "\<And>s. s \<in> S \<Longrightarrow> finite (f s)" |
|
1095 assumes "pairwise (\<lambda>s t. disjnt (f s) (f t)) S" |
|
1096 shows "card (\<Union>(f ` S)) = sum (\<lambda>x. card (f x)) S" |
|
1097 proof - |
|
1098 have "pairwise disjnt (f ` S)" |
|
1099 using assms(3) |
|
1100 by (metis pairwiseD pairwise_imageI) |
|
1101 then have "card (\<Union>(f ` S)) = sum card (f ` S)" |
|
1102 by (subst card_Union_disjoint) (use assms in auto) |
|
1103 also have "... = sum (\<lambda>x. card (f x)) S" |
|
1104 by (metis (mono_tags, lifting) assms(1) assms(3) sum_card_image) |
|
1105 finally show ?thesis . |
|
1106 qed |
|
1107 |
1091 |
1108 |
1092 |
1109 subsubsection \<open>Cardinality of products\<close> |
1093 subsubsection \<open>Cardinality of products\<close> |
1110 |
1094 |
1111 lemma card_SigmaI [simp]: |
1095 lemma card_SigmaI [simp]: |