src/ZF/Induct/Multiset.thy
changeset 59788 6f7b6adac439
parent 58318 f95754ca7082
child 60770 240563fbf41d
equal deleted inserted replaced
59787:6e2a20486897 59788:6f7b6adac439
   361 apply (blast dest!: fun_is_rel)
   361 apply (blast dest!: fun_is_rel)
   362 done
   362 done
   363 
   363 
   364 lemma msize_eq_0_iff: "multiset(M) ==> msize(M)=#0 \<longleftrightarrow> M=0"
   364 lemma msize_eq_0_iff: "multiset(M) ==> msize(M)=#0 \<longleftrightarrow> M=0"
   365 apply (simp add: msize_def, auto)
   365 apply (simp add: msize_def, auto)
   366 apply (rule_tac P = "setsum (?u,?v) \<noteq> #0" in swap)
   366 apply (rule_tac P = "setsum (u,v) \<noteq> #0" for u v in swap)
   367 apply blast
   367 apply blast
   368 apply (drule not_empty_multiset_imp_exist, assumption, clarify)
   368 apply (drule not_empty_multiset_imp_exist, assumption, clarify)
   369 apply (subgoal_tac "Finite (mset_of (M) - {a}) ")
   369 apply (subgoal_tac "Finite (mset_of (M) - {a}) ")
   370  prefer 2 apply (simp add: Finite_Diff)
   370  prefer 2 apply (simp add: Finite_Diff)
   371 apply (subgoal_tac "setsum (%x. $# mcount (M, x), cons (a, mset_of (M) -{a}))=#0")
   371 apply (subgoal_tac "setsum (%x. $# mcount (M, x), cons (a, mset_of (M) -{a}))=#0")
   569 apply (subgoal_tac "multiset (M) ")
   569 apply (subgoal_tac "multiset (M) ")
   570  prefer 2
   570  prefer 2
   571  apply (simp add: multiset_def multiset_fun_iff)
   571  apply (simp add: multiset_def multiset_fun_iff)
   572  apply (rule_tac x = A in exI, force)
   572  apply (rule_tac x = A in exI, force)
   573 apply (simp_all add: mset_of_def)
   573 apply (simp_all add: mset_of_def)
   574 apply (drule_tac psi = "\<forall>x \<in> A. ?u (x) " in asm_rl)
   574 apply (drule_tac psi = "\<forall>x \<in> A. u(x)" for u in asm_rl)
   575 apply (drule_tac x = a in bspec)
   575 apply (drule_tac x = a in bspec)
   576 apply (simp (no_asm_simp))
   576 apply (simp (no_asm_simp))
   577 apply (subgoal_tac "cons (a, A) = A")
   577 apply (subgoal_tac "cons (a, A) = A")
   578 prefer 2 apply blast
   578 prefer 2 apply blast
   579 apply simp
   579 apply simp
   594 apply (auto intro: Finite_Diff funrestrict_type simp add: funrestrict)
   594 apply (auto intro: Finite_Diff funrestrict_type simp add: funrestrict)
   595 apply (frule_tac A = A and M = M and a = a in setsum_decr3)
   595 apply (frule_tac A = A and M = M and a = a in setsum_decr3)
   596 apply (simp (no_asm_simp) add: multiset_def multiset_fun_iff)
   596 apply (simp (no_asm_simp) add: multiset_def multiset_fun_iff)
   597 apply blast
   597 apply blast
   598 apply (simp (no_asm_simp) add: mset_of_def)
   598 apply (simp (no_asm_simp) add: mset_of_def)
   599 apply (drule_tac b = "if ?u then ?v else ?w" in sym, simp_all)
   599 apply (drule_tac b = "if u then v else w" for u v w in sym, simp_all)
   600 apply (subgoal_tac "{x \<in> A - {a} . 0 < funrestrict (M, A - {x}) ` x} = A - {a}")
   600 apply (subgoal_tac "{x \<in> A - {a} . 0 < funrestrict (M, A - {x}) ` x} = A - {a}")
   601 apply (auto intro!: setsum_cong simp add: zdiff_eq_iff zadd_commute multiset_def multiset_fun_iff mset_of_def)
   601 apply (auto intro!: setsum_cong simp add: zdiff_eq_iff zadd_commute multiset_def multiset_fun_iff mset_of_def)
   602 done
   602 done
   603 
   603 
   604 lemma multiset_induct2:
   604 lemma multiset_induct2:
   813 apply (simp add: Ball_def Un_subset_iff, clarify)
   813 apply (simp add: Ball_def Un_subset_iff, clarify)
   814 apply (drule_tac x = aa in spec, simp)
   814 apply (drule_tac x = aa in spec, simp)
   815 apply (subgoal_tac "aa \<in> A")
   815 apply (subgoal_tac "aa \<in> A")
   816 prefer 2 apply blast
   816 prefer 2 apply blast
   817 apply (drule_tac x = "M0 +# M" and P =
   817 apply (drule_tac x = "M0 +# M" and P =
   818        "%x. x \<in> acc(multirel1(A, r)) \<longrightarrow> ?Q(x)" in spec)
   818        "%x. x \<in> acc(multirel1(A, r)) \<longrightarrow> Q(x)" for Q in spec)
   819 apply (simp add: munion_assoc [symmetric])
   819 apply (simp add: munion_assoc [symmetric])
   820 (* subgoal 3 \<in> additional conditions *)
   820 (* subgoal 3 \<in> additional conditions *)
   821 apply (auto intro!: multirel1_base [THEN fieldI2] simp add: Mult_iff_multiset)
   821 apply (auto intro!: multirel1_base [THEN fieldI2] simp add: Mult_iff_multiset)
   822 done
   822 done
   823 
   823 
   940 apply (simp (no_asm_simp) add: munion_assoc [symmetric])
   940 apply (simp (no_asm_simp) add: munion_assoc [symmetric])
   941 apply (drule_tac t = "%M. M-#{#a#}" in subst_context)
   941 apply (drule_tac t = "%M. M-#{#a#}" in subst_context)
   942 apply (simp add: mdiff_union_single_conv melem_diff_single, clarify)
   942 apply (simp add: mdiff_union_single_conv melem_diff_single, clarify)
   943 apply (erule disjE, simp)
   943 apply (erule disjE, simp)
   944 apply (erule disjE, simp)
   944 apply (erule disjE, simp)
   945 apply (drule_tac x = a and P = "%x. x :# Ka \<longrightarrow> ?Q(x)" in spec)
   945 apply (drule_tac x = a and P = "%x. x :# Ka \<longrightarrow> Q(x)" for Q in spec)
   946 apply clarify
   946 apply clarify
   947 apply (rule_tac x = xa in exI)
   947 apply (rule_tac x = xa in exI)
   948 apply (simp (no_asm_simp))
   948 apply (simp (no_asm_simp))
   949 apply (blast dest: trans_onD)
   949 apply (blast dest: trans_onD)
   950 (* new we know that  a\<notin>mset_of(Ka) *)
   950 (* new we know that  a\<notin>mset_of(Ka) *)
  1003 apply (simp add: multirel1_iff Mult_iff_multiset, force)
  1003 apply (simp add: multirel1_iff Mult_iff_multiset, force)
  1004 (*Now we know J' \<noteq>  0*)
  1004 (*Now we know J' \<noteq>  0*)
  1005 apply (drule sym, rotate_tac -1, simp)
  1005 apply (drule sym, rotate_tac -1, simp)
  1006 apply (erule_tac V = "$# x = msize (J') " in thin_rl)
  1006 apply (erule_tac V = "$# x = msize (J') " in thin_rl)
  1007 apply (frule_tac M = K and P = "%x. <x,a> \<in> r" in multiset_partition)
  1007 apply (frule_tac M = K and P = "%x. <x,a> \<in> r" in multiset_partition)
  1008 apply (erule_tac P = "\<forall>k \<in> mset_of (K) . ?P (k) " in rev_mp)
  1008 apply (erule_tac P = "\<forall>k \<in> mset_of (K) . P(k)" for P in rev_mp)
  1009 apply (erule ssubst)
  1009 apply (erule ssubst)
  1010 apply (simp add: Ball_def, auto)
  1010 apply (simp add: Ball_def, auto)
  1011 apply (subgoal_tac "< (I +# {# x \<in> K. <x, a> \<in> r#}) +# {# x \<in> K. <x, a> \<notin> r#}, (I +# {# x \<in> K. <x, a> \<in> r#}) +# J'> \<in> multirel(A, r) ")
  1011 apply (subgoal_tac "< (I +# {# x \<in> K. <x, a> \<in> r#}) +# {# x \<in> K. <x, a> \<notin> r#}, (I +# {# x \<in> K. <x, a> \<in> r#}) +# J'> \<in> multirel(A, r) ")
  1012  prefer 2
  1012  prefer 2
  1013  apply (drule_tac x = "I +# {# x \<in> K. <x, a> \<in> r#}" in spec)
  1013  apply (drule_tac x = "I +# {# x \<in> K. <x, a> \<in> r#}" in spec)
  1117 done
  1117 done
  1118 
  1118 
  1119 lemma munion_multirel_mono1:
  1119 lemma munion_multirel_mono1:
  1120      "[|<M, N> \<in> multirel(A, r); K \<in> Mult(A)|] ==> <M +# K, N +# K> \<in> multirel(A, r)"
  1120      "[|<M, N> \<in> multirel(A, r); K \<in> Mult(A)|] ==> <M +# K, N +# K> \<in> multirel(A, r)"
  1121 apply (frule multirel_type [THEN subsetD])
  1121 apply (frule multirel_type [THEN subsetD])
  1122 apply (rule_tac P = "%x. <x,?u> \<in> multirel(A, r) " in munion_commute [THEN subst])
  1122 apply (rule_tac P = "%x. <x,u> \<in> multirel(A, r)" for u in munion_commute [THEN subst])
  1123 apply (subst munion_commute [of N])
  1123 apply (subst munion_commute [of N])
  1124 apply (rule munion_multirel_mono2)
  1124 apply (rule munion_multirel_mono2)
  1125 apply (auto simp add: Mult_iff_multiset)
  1125 apply (auto simp add: Mult_iff_multiset)
  1126 done
  1126 done
  1127 
  1127