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 |