src/HOL/Finite_Set.thy
changeset 23477 f4b83f03cac9
parent 23413 5caa2710dd5b
child 23706 b7abba3c230e
equal deleted inserted replaced
23476:839db6346cc8 23477:f4b83f03cac9
   968   by (induct set: finite) auto
   968   by (induct set: finite) auto
   969 
   969 
   970 lemma setsum_Un_nat: "finite A ==> finite B ==>
   970 lemma setsum_Un_nat: "finite A ==> finite B ==>
   971     (setsum f (A Un B) :: nat) = setsum f A + setsum f B - setsum f (A Int B)"
   971     (setsum f (A Un B) :: nat) = setsum f A + setsum f B - setsum f (A Int B)"
   972   -- {* For the natural numbers, we have subtraction. *}
   972   -- {* For the natural numbers, we have subtraction. *}
   973   by (subst setsum_Un_Int [symmetric], auto simp add: ring_eq_simps)
   973   by (subst setsum_Un_Int [symmetric], auto simp add: ring_simps)
   974 
   974 
   975 lemma setsum_Un: "finite A ==> finite B ==>
   975 lemma setsum_Un: "finite A ==> finite B ==>
   976     (setsum f (A Un B) :: 'a :: ab_group_add) =
   976     (setsum f (A Un B) :: 'a :: ab_group_add) =
   977       setsum f A + setsum f B - setsum f (A Int B)"
   977       setsum f A + setsum f B - setsum f (A Int B)"
   978   by (subst setsum_Un_Int [symmetric], auto simp add: ring_eq_simps)
   978   by (subst setsum_Un_Int [symmetric], auto simp add: ring_simps)
   979 
   979 
   980 lemma setsum_diff1_nat: "(setsum f (A - {a}) :: nat) =
   980 lemma setsum_diff1_nat: "(setsum f (A - {a}) :: nat) =
   981     (if a:A then setsum f A - f a else setsum f A)"
   981     (if a:A then setsum f A - f a else setsum f A)"
   982   apply (case_tac "finite A")
   982   apply (case_tac "finite A")
   983    prefer 2 apply (simp add: setsum_def)
   983    prefer 2 apply (simp add: setsum_def)
  1647 
  1647 
  1648 
  1648 
  1649 lemma setsum_constant [simp]: "(\<Sum>x \<in> A. y) = of_nat(card A) * y"
  1649 lemma setsum_constant [simp]: "(\<Sum>x \<in> A. y) = of_nat(card A) * y"
  1650 apply (cases "finite A")
  1650 apply (cases "finite A")
  1651 apply (erule finite_induct)
  1651 apply (erule finite_induct)
  1652 apply (auto simp add: ring_distrib add_ac)
  1652 apply (auto simp add: ring_simps)
  1653 done
  1653 done
  1654 
  1654 
  1655 lemma setprod_constant: "finite A ==> (\<Prod>x\<in> A. (y::'a::{recpower, comm_monoid_mult})) = y^(card A)"
  1655 lemma setprod_constant: "finite A ==> (\<Prod>x\<in> A. (y::'a::{recpower, comm_monoid_mult})) = y^(card A)"
  1656   apply (erule finite_induct)
  1656   apply (erule finite_induct)
  1657   apply (auto simp add: power_Suc)
  1657   apply (auto simp add: power_Suc)