src/HOL/Finite_Set.thy
changeset 13400 dbb608cd11c4
parent 13390 c48c634605f1
child 13421 8fcdf4a26468
equal deleted inserted replaced
13399:c136276dc847 13400:dbb608cd11c4
   718 lemma (in ACe) fold_Un_Int:
   718 lemma (in ACe) fold_Un_Int:
   719   "finite A ==> finite B ==>
   719   "finite A ==> finite B ==>
   720     fold f e A \<cdot> fold f e B = fold f e (A Un B) \<cdot> fold f e (A Int B)"
   720     fold f e A \<cdot> fold f e B = fold f e (A Un B) \<cdot> fold f e (A Int B)"
   721   apply (induct set: Finites)
   721   apply (induct set: Finites)
   722    apply simp
   722    apply simp
   723   apply (simp add: AC ACe_axioms ACe_axioms_def
   723   apply (simp add: AC insert_absorb Int_insert_left
   724     LC_axioms_def LC.fold_insert insert_absorb Int_insert_left)
   724     LC.fold_insert [OF LC.intro, OF LC_axioms.intro])
   725   done
   725   done
   726 
   726 
   727 lemma (in ACe) fold_Un_disjoint:
   727 lemma (in ACe) fold_Un_disjoint:
   728   "finite A ==> finite B ==> A Int B = {} ==>
   728   "finite A ==> finite B ==> A Int B = {} ==>
   729     fold f e (A Un B) = fold f e A \<cdot> fold f e B"
   729     fold f e (A Un B) = fold f e A \<cdot> fold f e B"
   743   next
   743   next
   744     case (insert F x)
   744     case (insert F x)
   745     have "fold (f \<circ> g) e (insert x F \<union> B) = fold (f \<circ> g) e (insert x (F \<union> B))"
   745     have "fold (f \<circ> g) e (insert x F \<union> B) = fold (f \<circ> g) e (insert x (F \<union> B))"
   746       by simp
   746       by simp
   747     also have "... = (f \<circ> g) x (fold (f \<circ> g) e (F \<union> B))"
   747     also have "... = (f \<circ> g) x (fold (f \<circ> g) e (F \<union> B))"
   748       by (rule LC.fold_insert)
   748       by (rule LC.fold_insert [OF LC.intro])
   749         (insert b insert, auto simp add: left_commute intro: LC_axioms.intro)
   749         (insert b insert, auto simp add: left_commute intro: LC_axioms.intro)
   750     also from insert have "fold (f \<circ> g) e (F \<union> B) =
   750     also from insert have "fold (f \<circ> g) e (F \<union> B) =
   751       fold (f \<circ> g) e F \<cdot> fold (f \<circ> g) e B" by blast
   751       fold (f \<circ> g) e F \<cdot> fold (f \<circ> g) e B" by blast
   752     also have "(f \<circ> g) x ... = (f \<circ> g) x (fold (f \<circ> g) e F) \<cdot> fold (f \<circ> g) e B"
   752     also have "(f \<circ> g) x ... = (f \<circ> g) x (fold (f \<circ> g) e F) \<cdot> fold (f \<circ> g) e B"
   753       by (simp add: AC)
   753       by (simp add: AC)
   754     also have "(f \<circ> g) x (fold (f \<circ> g) e F) = fold (f \<circ> g) e (insert x F)"
   754     also have "(f \<circ> g) x (fold (f \<circ> g) e F) = fold (f \<circ> g) e (insert x F)"
   755       by (rule LC.fold_insert [symmetric]) (insert b insert,
   755       by (rule LC.fold_insert [OF LC.intro, symmetric]) (insert b insert,
   756 	auto simp add: left_commute intro: LC_axioms.intro)
   756 	auto simp add: left_commute intro: LC_axioms.intro)
   757     finally show ?case .
   757     finally show ?case .
   758   qed
   758   qed
   759 qed
   759 qed
   760 
   760 
   777   by (simp add: setsum_def)
   777   by (simp add: setsum_def)
   778 
   778 
   779 lemma setsum_insert [simp]:
   779 lemma setsum_insert [simp]:
   780     "finite F ==> a \<notin> F ==> setsum f (insert a F) = f a + setsum f F"
   780     "finite F ==> a \<notin> F ==> setsum f (insert a F) = f a + setsum f F"
   781   by (simp add: setsum_def
   781   by (simp add: setsum_def
   782     LC_axioms_def LC.fold_insert plus_ac0_left_commute)
   782     LC.fold_insert [OF LC.intro, OF LC_axioms.intro] plus_ac0_left_commute)
   783 
   783 
   784 lemma setsum_0: "setsum (\<lambda>i. 0) A = 0"
   784 lemma setsum_0: "setsum (\<lambda>i. 0) A = 0"
   785   apply (case_tac "finite A")
   785   apply (case_tac "finite A")
   786    prefer 2 apply (simp add: setsum_def)
   786    prefer 2 apply (simp add: setsum_def)
   787   apply (erule finite_induct)
   787   apply (erule finite_induct)