src/HOL/Number_Theory/Binomial.thy
changeset 55143 04448228381d
parent 55130 70db8d380d62
child 56178 2a6f58938573
equal deleted inserted replaced
55142:378ae9e46175 55143:04448228381d
   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))"