131 apply (simp add: card_s_0_eq_empty choose_deconstruct) |
131 apply (simp add: card_s_0_eq_empty choose_deconstruct) |
132 apply (subst card_Un_disjoint) |
132 apply (subst card_Un_disjoint) |
133 prefer 4 apply (force simp add: constr_bij) |
133 prefer 4 apply (force simp add: constr_bij) |
134 prefer 3 apply force |
134 prefer 3 apply force |
135 prefer 2 apply (blast intro: finite_Pow_iff [THEN iffD2] |
135 prefer 2 apply (blast intro: finite_Pow_iff [THEN iffD2] |
136 finite_subset [of _ "Pow (insert x F)", standard]) |
136 finite_subset [of _ "Pow (insert x F)" for F]) |
137 apply (blast intro: finite_Pow_iff [THEN iffD2, THEN [2] finite_subset]) |
137 apply (blast intro: finite_Pow_iff [THEN iffD2, THEN [2] finite_subset]) |
138 done |
138 done |
139 qed |
139 qed |
140 qed |
140 qed |
141 |
141 |
667 with `finite A` have K: "finite K" by auto |
667 with `finite A` have K: "finite K" by auto |
668 let ?I = "\<lambda>i. {I. I \<subseteq> A \<and> card I = i \<and> x \<in> \<Inter>I}" |
668 let ?I = "\<lambda>i. {I. I \<subseteq> A \<and> card I = i \<and> x \<in> \<Inter>I}" |
669 have "inj_on snd (SIGMA i:{1..card A}. ?I i)" |
669 have "inj_on snd (SIGMA i:{1..card A}. ?I i)" |
670 using assms by(auto intro!: inj_onI) |
670 using assms by(auto intro!: inj_onI) |
671 moreover have [symmetric]: "snd ` (SIGMA i:{1..card A}. ?I i) = {I. I \<subseteq> A \<and> I \<noteq> {} \<and> x \<in> \<Inter>I}" |
671 moreover have [symmetric]: "snd ` (SIGMA i:{1..card A}. ?I i) = {I. I \<subseteq> A \<and> I \<noteq> {} \<and> x \<in> \<Inter>I}" |
672 using assms by(auto intro!: rev_image_eqI[where x="(card a, a)", standard] simp add: card_gt_0_iff[folded Suc_le_eq] dest: finite_subset intro: card_mono) |
672 using assms by(auto intro!: rev_image_eqI[where x="(card a, a)" for a] |
|
673 simp add: card_gt_0_iff[folded Suc_le_eq] |
|
674 dest: finite_subset intro: card_mono) |
673 ultimately have "?lhs x = (\<Sum>(i, I)\<in>(SIGMA i:{1..card A}. ?I i). -1 ^ (i + 1))" |
675 ultimately have "?lhs x = (\<Sum>(i, I)\<in>(SIGMA i:{1..card A}. ?I i). -1 ^ (i + 1))" |
674 by(rule setsum_reindex_cong[where f=snd]) fastforce |
676 by(rule setsum_reindex_cong[where f=snd]) fastforce |
675 also have "\<dots> = (\<Sum>i=1..card A. (\<Sum>I|I \<subseteq> A \<and> card I = i \<and> x \<in> \<Inter>I. -1 ^ (i + 1)))" |
677 also have "\<dots> = (\<Sum>i=1..card A. (\<Sum>I|I \<subseteq> A \<and> card I = i \<and> x \<in> \<Inter>I. -1 ^ (i + 1)))" |
676 using assms by(subst setsum_Sigma) auto |
678 using assms by(subst setsum_Sigma) auto |
677 also have "\<dots> = (\<Sum>i=1..card A. -1 ^ (i + 1) * (\<Sum>I|I \<subseteq> A \<and> card I = i \<and> x \<in> \<Inter>I. 1))" |
679 also have "\<dots> = (\<Sum>i=1..card A. -1 ^ (i + 1) * (\<Sum>I|I \<subseteq> A \<and> card I = i \<and> x \<in> \<Inter>I. 1))" |