summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

src/HOL/Finite_Set.thy

changeset 15124 | 1d9b4fcd222d |

parent 15111 | c108189645f8 |

child 15131 | c69542757a4d |

--- a/src/HOL/Finite_Set.thy Fri Aug 06 17:29:24 2004 +0200 +++ b/src/HOL/Finite_Set.thy Mon Aug 09 10:09:44 2004 +0200 @@ -965,6 +965,34 @@ apply (drule_tac a = a in mk_disjoint_insert, auto) done +(* By Jeremy Siek: *) + +lemma setsum_diff: + assumes finB: "finite B" + shows "B \<subseteq> A \<Longrightarrow> (setsum f (A - B) :: nat) = (setsum f A) - (setsum f B)" +using finB +proof (induct) + show "setsum f (A - {}) = (setsum f A) - (setsum f {})" by simp +next + fix F x assume finF: "finite F" and xnotinF: "x \<notin> F" + and xFinA: "insert x F \<subseteq> A" + and IH: "F \<subseteq> A \<Longrightarrow> setsum f (A - F) = setsum f A - setsum f F" + from xnotinF xFinA have xinAF: "x \<in> (A - F)" by simp + from xinAF have A: "setsum f ((A - F) - {x}) = setsum f (A - F) - f x" + by (simp add: setsum_diff1) + from xFinA have "F \<subseteq> A" by simp + with IH have "setsum f (A - F) = setsum f A - setsum f F" by simp + with A have B: "setsum f ((A - F) - {x}) = setsum f A - setsum f F - f x" + by simp + from xnotinF have "A - insert x F = (A - F) - {x}" by auto + with B have C: "setsum f (A - insert x F) = setsum f A - setsum f F - f x" + by simp + from finF xnotinF have "setsum f (insert x F) = setsum f F + f x" by simp + with C have "setsum f (A - insert x F) = setsum f A - setsum f (insert x F)" + by simp + thus "setsum f (A - insert x F) = setsum f A - setsum f (insert x F)" by simp +qed + lemma setsum_negf: "finite A ==> setsum (%x. - (f x)::'a::comm_ring_1) A = - setsum f A" by (induct set: Finites, auto)