src/HOL/Library/Multiset.thy
changeset 37765 26bdfb7b680b
parent 37751 89e16802b6cc
child 38242 f26d590dce0f
equal deleted inserted replaced
37764:3489daf839d5 37765:26bdfb7b680b
   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