equal
deleted
inserted
replaced
976 subsection {* The multiset order *} |
976 subsection {* The multiset order *} |
977 |
977 |
978 subsubsection {* Well-foundedness *} |
978 subsubsection {* Well-foundedness *} |
979 |
979 |
980 definition mult1 :: "('a \<times> 'a) set => ('a multiset \<times> 'a multiset) set" where |
980 definition mult1 :: "('a \<times> 'a) set => ('a multiset \<times> 'a multiset) set" where |
981 [code del]: "mult1 r = {(N, M). \<exists>a M0 K. M = M0 + {#a#} \<and> N = M0 + K \<and> |
981 "mult1 r = {(N, M). \<exists>a M0 K. M = M0 + {#a#} \<and> N = M0 + K \<and> |
982 (\<forall>b. b :# K --> (b, a) \<in> r)}" |
982 (\<forall>b. b :# K --> (b, a) \<in> r)}" |
983 |
983 |
984 definition mult :: "('a \<times> 'a) set => ('a multiset \<times> 'a multiset) set" where |
984 definition mult :: "('a \<times> 'a) set => ('a multiset \<times> 'a multiset) set" where |
985 [code del]: "mult r = (mult1 r)\<^sup>+" |
985 "mult r = (mult1 r)\<^sup>+" |
986 |
986 |
987 lemma not_less_empty [iff]: "(M, {#}) \<notin> mult1 r" |
987 lemma not_less_empty [iff]: "(M, {#}) \<notin> mult1 r" |
988 by (simp add: mult1_def) |
988 by (simp add: mult1_def) |
989 |
989 |
990 lemma less_add: "(N, M0 + {#a#}) \<in> mult1 r ==> |
990 lemma less_add: "(N, M0 + {#a#}) \<in> mult1 r ==> |
1496 and multi_member_this: "x \<in># {# x #} + XS" |
1496 and multi_member_this: "x \<in># {# x #} + XS" |
1497 and multi_member_last: "x \<in># {# x #}" |
1497 and multi_member_last: "x \<in># {# x #}" |
1498 by auto |
1498 by auto |
1499 |
1499 |
1500 definition "ms_strict = mult pair_less" |
1500 definition "ms_strict = mult pair_less" |
1501 definition [code del]: "ms_weak = ms_strict \<union> Id" |
1501 definition "ms_weak = ms_strict \<union> Id" |
1502 |
1502 |
1503 lemma ms_reduction_pair: "reduction_pair (ms_strict, ms_weak)" |
1503 lemma ms_reduction_pair: "reduction_pair (ms_strict, ms_weak)" |
1504 unfolding reduction_pair_def ms_strict_def ms_weak_def pair_less_def |
1504 unfolding reduction_pair_def ms_strict_def ms_weak_def pair_less_def |
1505 by (auto intro: wf_mult1 wf_trancl simp: mult_def) |
1505 by (auto intro: wf_mult1 wf_trancl simp: mult_def) |
1506 |
1506 |