src/HOL/Finite_Set.thy
changeset 28823 dcbef866c9e2
parent 27981 feb0c01cf0fb
child 28853 69eb69659bf3
equal deleted inserted replaced
28822:7ca11ecbc4fb 28823:dcbef866c9e2
    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