91 \<exists>a \<in> A. \<exists>M0 \<in> Mult(A). \<exists>K \<in> Mult(A). |
91 \<exists>a \<in> A. \<exists>M0 \<in> Mult(A). \<exists>K \<in> Mult(A). |
92 N=M0 +# {#a#} & M=M0 +# K & (\<forall>b \<in> mset_of(K). <b,a> \<in> r)}" |
92 N=M0 +# {#a#} & M=M0 +# K & (\<forall>b \<in> mset_of(K). <b,a> \<in> r)}" |
93 |
93 |
94 definition |
94 definition |
95 multirel :: "[i, i] => i" where |
95 multirel :: "[i, i] => i" where |
96 "multirel(A, r) == multirel1(A, r)^+" |
96 "multirel(A, r) == multirel1(A, r)^+" |
97 |
97 |
98 (* ordinal multiset orderings *) |
98 (* ordinal multiset orderings *) |
99 |
99 |
100 definition |
100 definition |
101 omultiset :: "i => o" where |
101 omultiset :: "i => o" where |
444 |
444 |
445 lemma nat_add_eq_1_cases: "[| m \<in> nat; n \<in> nat |] ==> (m #+ n = 1) \<longleftrightarrow> (m=1 & n=0) | (m=0 & n=1)" |
445 lemma nat_add_eq_1_cases: "[| m \<in> nat; n \<in> nat |] ==> (m #+ n = 1) \<longleftrightarrow> (m=1 & n=0) | (m=0 & n=1)" |
446 by (induct_tac n) auto |
446 by (induct_tac n) auto |
447 |
447 |
448 lemma munion_is_single: |
448 lemma munion_is_single: |
449 "[|multiset(M); multiset(N)|] |
449 "[|multiset(M); multiset(N)|] |
450 ==> (M +# N = {#a#}) \<longleftrightarrow> (M={#a#} & N=0) | (M = 0 & N = {#a#})" |
450 ==> (M +# N = {#a#}) \<longleftrightarrow> (M={#a#} & N=0) | (M = 0 & N = {#a#})" |
451 apply (simp (no_asm_simp) add: multiset_equality) |
451 apply (simp (no_asm_simp) add: multiset_equality) |
452 apply safe |
452 apply safe |
453 apply simp_all |
453 apply simp_all |
454 apply (case_tac "aa=a") |
454 apply (case_tac "aa=a") |
745 apply (rule_tac x = K in bexI) |
745 apply (rule_tac x = K in bexI) |
746 apply (auto simp add: Mult_iff_multiset) |
746 apply (auto simp add: Mult_iff_multiset) |
747 done |
747 done |
748 |
748 |
749 lemma multirel1_mono2: "r\<subseteq>s ==> multirel1(A,r)\<subseteq>multirel1(A, s)" |
749 lemma multirel1_mono2: "r\<subseteq>s ==> multirel1(A,r)\<subseteq>multirel1(A, s)" |
750 apply (simp add: multirel1_def, auto) |
750 apply (simp add: multirel1_def, auto) |
751 apply (rule_tac x = a in bexI) |
751 apply (rule_tac x = a in bexI) |
752 apply (rule_tac x = M0 in bexI) |
752 apply (rule_tac x = M0 in bexI) |
753 apply (simp_all add: Mult_iff_multiset) |
753 apply (simp_all add: Mult_iff_multiset) |
754 apply (rule_tac x = K in bexI) |
754 apply (rule_tac x = K in bexI) |
755 apply (simp_all add: Mult_iff_multiset, auto) |
755 apply (simp_all add: Mult_iff_multiset, auto) |
805 apply (auto simp add: Mult_iff_multiset) |
805 apply (auto simp add: Mult_iff_multiset) |
806 apply (erule_tac P = "\<forall>x \<in> mset_of (K) . <x, a> \<in> r" in rev_mp) |
806 apply (erule_tac P = "\<forall>x \<in> mset_of (K) . <x, a> \<in> r" in rev_mp) |
807 apply (erule_tac P = "mset_of (K) \<subseteq>A" in rev_mp) |
807 apply (erule_tac P = "mset_of (K) \<subseteq>A" in rev_mp) |
808 apply (erule_tac M = K in multiset_induct) |
808 apply (erule_tac M = K in multiset_induct) |
809 (* three subgoals *) |
809 (* three subgoals *) |
810 (* subgoal 1: the induction base case *) |
810 (* subgoal 1 \<in> the induction base case *) |
811 apply (simp (no_asm_simp)) |
811 apply (simp (no_asm_simp)) |
812 (* subgoal 2: the induction general case *) |
812 (* subgoal 2 \<in> the induction general case *) |
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)" in spec) |
819 apply (simp add: munion_assoc [symmetric]) |
819 apply (simp add: munion_assoc [symmetric]) |
820 (* subgoal 3: 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 |
824 lemma lemma2: "[| \<forall>b \<in> A. <b,a> \<in> r |
824 lemma lemma2: "[| \<forall>b \<in> A. <b,a> \<in> r |
825 \<longrightarrow> (\<forall>M \<in> acc(multirel1(A, r)). M +# {#b#} :acc(multirel1(A, r))); |
825 \<longrightarrow> (\<forall>M \<in> acc(multirel1(A, r)). M +# {#b#} :acc(multirel1(A, r))); |