src/HOL/Finite_Set.thy
changeset 15837 7a567dcd4cda
parent 15791 446ec11266be
child 16550 e14b89d6ef13
equal deleted inserted replaced
15836:b805d85909c7 15837:7a567dcd4cda
  1130     by (simp add:setsum_Un_disjoint del:Un_Diff_cancel)
  1130     by (simp add:setsum_Un_disjoint del:Un_Diff_cancel)
  1131   also have "A \<union> (B-A) = B" using sub by blast
  1131   also have "A \<union> (B-A) = B" using sub by blast
  1132   finally show ?thesis .
  1132   finally show ?thesis .
  1133 qed
  1133 qed
  1134 
  1134 
       
  1135 (* FIXME: this is distributitivty, name as such! *)
       
  1136 
  1135 lemma setsum_mult: 
  1137 lemma setsum_mult: 
  1136   fixes f :: "'a => ('b::semiring_0_cancel)"
  1138   fixes f :: "'a => ('b::semiring_0_cancel)"
  1137   shows "r * setsum f A = setsum (%n. r * f n) A"
  1139   shows "r * setsum f A = setsum (%n. r * f n) A"
  1138 proof (cases "finite A")
  1140 proof (cases "finite A")
  1139   case True
  1141   case True
  2225 
  2227 
  2226 
  2228 
  2227 text{* Before we can do anything, we need to show that @{text min} and
  2229 text{* Before we can do anything, we need to show that @{text min} and
  2228 @{text max} are ACI and the ordering is linear: *}
  2230 @{text max} are ACI and the ordering is linear: *}
  2229 
  2231 
  2230 interpretation min [rule del]: ACf ["min:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2232 interpretation min: ACf ["min:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2231 apply(rule ACf.intro)
  2233 apply(rule ACf.intro)
  2232 apply(auto simp:min_def)
  2234 apply(auto simp:min_def)
  2233 done
  2235 done
  2234 
  2236 
  2235 interpretation min [rule del]: ACIf ["min:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2237 interpretation min: ACIf ["min:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2236 apply(rule ACIf_axioms.intro)
  2238 apply(rule ACIf_axioms.intro)
  2237 apply(auto simp:min_def)
  2239 apply(auto simp:min_def)
  2238 done
  2240 done
  2239 
  2241 
  2240 interpretation max [rule del]: ACf ["max :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2242 interpretation max: ACf ["max :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2241 apply(rule ACf.intro)
  2243 apply(rule ACf.intro)
  2242 apply(auto simp:max_def)
  2244 apply(auto simp:max_def)
  2243 done
  2245 done
  2244 
  2246 
  2245 interpretation max [rule del]: ACIf ["max:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2247 interpretation max: ACIf ["max:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a"]
  2246 apply(rule ACIf_axioms.intro)
  2248 apply(rule ACIf_axioms.intro)
  2247 apply(auto simp:max_def)
  2249 apply(auto simp:max_def)
  2248 done
  2250 done
  2249 
  2251 
  2250 interpretation min [rule del]:
  2252 interpretation min:
  2251   ACIfSL ["min:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "op \<le>"]
  2253   ACIfSL ["min:: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "op \<le>"]
  2252 apply(rule ACIfSL_axioms.intro)
  2254 apply(rule ACIfSL_axioms.intro)
  2253 apply(auto simp:min_def)
  2255 apply(auto simp:min_def)
  2254 done
  2256 done
  2255 
  2257 
  2256 interpretation min [rule del]:
  2258 interpretation min:
  2257   ACIfSLlin ["min :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "op \<le>"]
  2259   ACIfSLlin ["min :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "op \<le>"]
  2258 apply(rule ACIfSLlin_axioms.intro)
  2260 apply(rule ACIfSLlin_axioms.intro)
  2259 apply(auto simp:min_def)
  2261 apply(auto simp:min_def)
  2260 done
  2262 done
  2261 
  2263 
  2262 interpretation max [rule del]:
  2264 interpretation max:
  2263   ACIfSL ["max :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "%x y. y\<le>x"]
  2265   ACIfSL ["max :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "%x y. y\<le>x"]
  2264 apply(rule ACIfSL_axioms.intro)
  2266 apply(rule ACIfSL_axioms.intro)
  2265 apply(auto simp:max_def)
  2267 apply(auto simp:max_def)
  2266 done
  2268 done
  2267 
  2269 
  2268 interpretation max [rule del]:
  2270 interpretation max:
  2269   ACIfSLlin ["max :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "%x y. y\<le>x"]
  2271   ACIfSLlin ["max :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "%x y. y\<le>x"]
  2270 apply(rule ACIfSLlin_axioms.intro)
  2272 apply(rule ACIfSLlin_axioms.intro)
  2271 apply(auto simp:max_def)
  2273 apply(auto simp:max_def)
  2272 done
  2274 done
  2273 
  2275 
  2274 interpretation min_max [rule del]:
  2276 interpretation min_max:
  2275   Lattice ["op \<le>" "min :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "max" "Min" "Max"]
  2277   Lattice ["op \<le>" "min :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "max" "Min" "Max"]
  2276 apply -
  2278 apply -
  2277 apply(rule Min_def)
  2279 apply(rule Min_def)
  2278 apply(rule Max_def)
  2280 apply(rule Max_def)
  2279 done
  2281 done
  2280 
  2282 
  2281 
  2283 
  2282 interpretation min_max [rule del]:
  2284 interpretation min_max:
  2283   Distrib_Lattice ["op \<le>" "min :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "max" "Min" "Max"]
  2285   Distrib_Lattice ["op \<le>" "min :: 'a::linorder \<Rightarrow> 'a \<Rightarrow> 'a" "max" "Min" "Max"]
  2284 .
  2286 .
  2285 
       
  2286 text {* Classical rules from the locales are deleted in the above
       
  2287   interpretations, since they interfere with the claset setup for
       
  2288   @{text "op \<le>"}. *}
       
  2289 
  2287 
  2290 text{* Now we instantiate the recursion equations and declare them
  2288 text{* Now we instantiate the recursion equations and declare them
  2291 simplification rules: *}
  2289 simplification rules: *}
  2292 
  2290 
  2293 (* Making Min (resp. Max) a defined parameter of a locale suitably
  2291 (* Making Min (resp. Max) a defined parameter of a locale suitably