equal
deleted
inserted
replaced
19 |
19 |
20 lemma ex_new_if_finite: -- "does not depend on def of finite at all" |
20 lemma ex_new_if_finite: -- "does not depend on def of finite at all" |
21 assumes "\<not> finite (UNIV :: 'a set)" and "finite A" |
21 assumes "\<not> finite (UNIV :: 'a set)" and "finite A" |
22 shows "\<exists>a::'a. a \<notin> A" |
22 shows "\<exists>a::'a. a \<notin> A" |
23 proof - |
23 proof - |
24 from prems have "A \<noteq> UNIV" by blast |
24 from assms have "A \<noteq> UNIV" by blast |
25 thus ?thesis by blast |
25 thus ?thesis by blast |
26 qed |
26 qed |
27 |
27 |
28 lemma finite_induct [case_names empty insert, induct set: finite]: |
28 lemma finite_induct [case_names empty insert, induct set: finite]: |
29 "finite F ==> |
29 "finite F ==> |
831 |
831 |
832 |
832 |
833 subsection {* Generalized summation over a set *} |
833 subsection {* Generalized summation over a set *} |
834 |
834 |
835 interpretation comm_monoid_add: comm_monoid_mult ["0::'a::comm_monoid_add" "op +"] |
835 interpretation comm_monoid_add: comm_monoid_mult ["0::'a::comm_monoid_add" "op +"] |
836 by unfold_locales (auto intro: add_assoc add_commute) |
836 proof qed (auto intro: add_assoc add_commute) |
837 |
837 |
838 constdefs |
838 constdefs |
839 setsum :: "('a => 'b) => 'a set => 'b::comm_monoid_add" |
839 setsum :: "('a => 'b) => 'a set => 'b::comm_monoid_add" |
840 "setsum f A == if finite A then fold (op +) f 0 A else 0" |
840 "setsum f A == if finite A then fold (op +) f 0 A else 0" |
841 |
841 |
1725 lemma image_eq_fold: "finite A ==> f ` A = fold (op Un) (%x. {f x}) {} A" |
1725 lemma image_eq_fold: "finite A ==> f ` A = fold (op Un) (%x. {f x}) {} A" |
1726 proof (induct rule: finite_induct) |
1726 proof (induct rule: finite_induct) |
1727 case empty then show ?case by simp |
1727 case empty then show ?case by simp |
1728 next |
1728 next |
1729 interpret ab_semigroup_mult ["op Un"] |
1729 interpret ab_semigroup_mult ["op Un"] |
1730 by unfold_locales auto |
1730 proof qed auto |
1731 case insert |
1731 case insert |
1732 then show ?case by simp |
1732 then show ?case by simp |
1733 qed |
1733 qed |
1734 |
1734 |
1735 lemma card_image_le: "finite A ==> card (f ` A) <= card A" |
1735 lemma card_image_le: "finite A ==> card (f ` A) <= card A" |
2123 context lower_semilattice |
2123 context lower_semilattice |
2124 begin |
2124 begin |
2125 |
2125 |
2126 lemma ab_semigroup_idem_mult_inf: |
2126 lemma ab_semigroup_idem_mult_inf: |
2127 "ab_semigroup_idem_mult inf" |
2127 "ab_semigroup_idem_mult inf" |
2128 apply unfold_locales |
2128 proof qed (rule inf_assoc inf_commute inf_idem)+ |
2129 apply (rule inf_assoc) |
|
2130 apply (rule inf_commute) |
|
2131 apply (rule inf_idem) |
|
2132 done |
|
2133 |
2129 |
2134 lemma below_fold1_iff: |
2130 lemma below_fold1_iff: |
2135 assumes "finite A" "A \<noteq> {}" |
2131 assumes "finite A" "A \<noteq> {}" |
2136 shows "x \<le> fold1 inf A \<longleftrightarrow> (\<forall>a\<in>A. x \<le> a)" |
2132 shows "x \<le> fold1 inf A \<longleftrightarrow> (\<forall>a\<in>A. x \<le> a)" |
2137 proof - |
2133 proof - |
2355 context linorder |
2351 context linorder |
2356 begin |
2352 begin |
2357 |
2353 |
2358 lemma ab_semigroup_idem_mult_min: |
2354 lemma ab_semigroup_idem_mult_min: |
2359 "ab_semigroup_idem_mult min" |
2355 "ab_semigroup_idem_mult min" |
2360 by unfold_locales (auto simp add: min_def) |
2356 proof qed (auto simp add: min_def) |
2361 |
2357 |
2362 lemma ab_semigroup_idem_mult_max: |
2358 lemma ab_semigroup_idem_mult_max: |
2363 "ab_semigroup_idem_mult max" |
2359 "ab_semigroup_idem_mult max" |
2364 by unfold_locales (auto simp add: max_def) |
2360 proof qed (auto simp add: max_def) |
2365 |
2361 |
2366 lemma min_lattice: |
2362 lemma min_lattice: |
2367 "lower_semilattice (op \<le>) (op <) min" |
2363 "lower_semilattice (op \<le>) (op <) min" |
2368 by unfold_locales (auto simp add: min_def) |
2364 proof qed (auto simp add: min_def) |
2369 |
2365 |
2370 lemma max_lattice: |
2366 lemma max_lattice: |
2371 "lower_semilattice (op \<ge>) (op >) max" |
2367 "lower_semilattice (op \<ge>) (op >) max" |
2372 by unfold_locales (auto simp add: max_def) |
2368 proof qed (auto simp add: max_def) |
2373 |
2369 |
2374 lemma dual_max: |
2370 lemma dual_max: |
2375 "ord.max (op \<ge>) = min" |
2371 "ord.max (op \<ge>) = min" |
2376 by (auto simp add: ord.max_def_raw min_def_raw expand_fun_eq) |
2372 by (auto simp add: ord.max_def_raw min_def_raw expand_fun_eq) |
2377 |
2373 |