src/HOL/Library/Multiset.thy
changeset 39198 f967a16dfcdd
parent 38857 97775f3e8722
child 39301 e1bd8a54c40f
equal deleted inserted replaced
39166:19efc2af3e6c 39198:f967a16dfcdd
    24 notation (xsymbols)
    24 notation (xsymbols)
    25   Melem (infix "\<in>#" 50)
    25   Melem (infix "\<in>#" 50)
    26 
    26 
    27 lemma multiset_ext_iff:
    27 lemma multiset_ext_iff:
    28   "M = N \<longleftrightarrow> (\<forall>a. count M a = count N a)"
    28   "M = N \<longleftrightarrow> (\<forall>a. count M a = count N a)"
    29   by (simp only: count_inject [symmetric] expand_fun_eq)
    29   by (simp only: count_inject [symmetric] ext_iff)
    30 
    30 
    31 lemma multiset_ext:
    31 lemma multiset_ext:
    32   "(\<And>x. count A x = count B x) \<Longrightarrow> A = B"
    32   "(\<And>x. count A x = count B x) \<Longrightarrow> A = B"
    33   using multiset_ext_iff by auto
    33   using multiset_ext_iff by auto
    34 
    34 
   579     apply (rule count_inverse [THEN subst])
   579     apply (rule count_inverse [THEN subst])
   580     apply (rule count [THEN rep_multiset_induct])
   580     apply (rule count [THEN rep_multiset_induct])
   581      apply (rule empty [unfolded defns])
   581      apply (rule empty [unfolded defns])
   582     apply (subgoal_tac "f(b := f b + 1) = (\<lambda>a. f a + (if a=b then 1 else 0))")
   582     apply (subgoal_tac "f(b := f b + 1) = (\<lambda>a. f a + (if a=b then 1 else 0))")
   583      prefer 2
   583      prefer 2
   584      apply (simp add: expand_fun_eq)
   584      apply (simp add: ext_iff)
   585     apply (erule ssubst)
   585     apply (erule ssubst)
   586     apply (erule Abs_multiset_inverse [THEN subst])
   586     apply (erule Abs_multiset_inverse [THEN subst])
   587     apply (drule add')
   587     apply (drule add')
   588     apply (simp add: aux)
   588     apply (simp add: aux)
   589     done
   589     done
   881     then show "x \<in> dom (map_of xs)" by auto
   881     then show "x \<in> dom (map_of xs)" by auto
   882   qed
   882   qed
   883   with finite_dom_map_of [of xs] have "finite ?A"
   883   with finite_dom_map_of [of xs] have "finite ?A"
   884     by (auto intro: finite_subset)
   884     by (auto intro: finite_subset)
   885   then show ?thesis
   885   then show ?thesis
   886     by (simp add: count_of_def expand_fun_eq multiset_def)
   886     by (simp add: count_of_def ext_iff multiset_def)
   887 qed
   887 qed
   888 
   888 
   889 lemma count_simps [simp]:
   889 lemma count_simps [simp]:
   890   "count_of [] = (\<lambda>_. 0)"
   890   "count_of [] = (\<lambda>_. 0)"
   891   "count_of ((x, n) # xs) = (\<lambda>y. if x = y then n else count_of xs y)"
   891   "count_of ((x, n) # xs) = (\<lambda>y. if x = y then n else count_of xs y)"
   892   by (simp_all add: count_of_def expand_fun_eq)
   892   by (simp_all add: count_of_def ext_iff)
   893 
   893 
   894 lemma count_of_empty:
   894 lemma count_of_empty:
   895   "x \<notin> fst ` set xs \<Longrightarrow> count_of xs x = 0"
   895   "x \<notin> fst ` set xs \<Longrightarrow> count_of xs x = 0"
   896   by (induct xs) (simp_all add: count_of_def)
   896   by (induct xs) (simp_all add: count_of_def)
   897 
   897