src/HOL/Library/Multiset.thy
changeset 26567 7bcebb8c2d33
parent 26178 3396ba6d0823
child 26818 b4a24433154e
equal deleted inserted replaced
26566:36a93808642c 26567:7bcebb8c2d33
   710 using one_step_implies_mult_aux by blast
   710 using one_step_implies_mult_aux by blast
   711 
   711 
   712 
   712 
   713 subsubsection {* Partial-order properties *}
   713 subsubsection {* Partial-order properties *}
   714 
   714 
   715 instance multiset :: (type) ord ..
   715 instantiation multiset :: (order) order
   716 
   716 begin
   717 defs (overloaded)
   717 
   718   less_multiset_def: "M' < M == (M', M) \<in> mult {(x', x). x' < x}"
   718 definition
   719   le_multiset_def: "M' <= M == M' = M \<or> M' < (M::'a multiset)"
   719   less_multiset_def: "M' < M \<longleftrightarrow> (M', M) \<in> mult {(x', x). x' < x}"
       
   720 
       
   721 definition
       
   722   le_multiset_def: "M' <= M \<longleftrightarrow> M' = M \<or> M' < (M::'a multiset)"
   720 
   723 
   721 lemma trans_base_order: "trans {(x', x). x' < (x::'a::order)}"
   724 lemma trans_base_order: "trans {(x', x). x' < (x::'a::order)}"
   722 unfolding trans_def by (blast intro: order_less_trans)
   725 unfolding trans_def by (blast intro: order_less_trans)
   723 
   726 
   724 text {*
   727 text {*
   773 unfolding le_multiset_def by (blast intro: mult_less_trans)
   776 unfolding le_multiset_def by (blast intro: mult_less_trans)
   774 
   777 
   775 theorem mult_less_le: "(M < N) = (M <= N \<and> M \<noteq> (N::'a::order multiset))"
   778 theorem mult_less_le: "(M < N) = (M <= N \<and> M \<noteq> (N::'a::order multiset))"
   776 unfolding le_multiset_def by auto
   779 unfolding le_multiset_def by auto
   777 
   780 
   778 text {* Partial order. *}
   781 instance
   779 
       
   780 instance multiset :: (order) order
       
   781 apply intro_classes
   782 apply intro_classes
   782    apply (rule mult_less_le)
   783    apply (rule mult_less_le)
   783   apply (rule mult_le_refl)
   784   apply (rule mult_le_refl)
   784  apply (erule mult_le_trans, assumption)
   785  apply (erule mult_le_trans, assumption)
   785 apply (erule mult_le_antisym, assumption)
   786 apply (erule mult_le_antisym, assumption)
   786 done
   787 done
       
   788 
       
   789 end
   787 
   790 
   788 
   791 
   789 subsubsection {* Monotonicity of multiset union *}
   792 subsubsection {* Monotonicity of multiset union *}
   790 
   793 
   791 lemma mult1_union:
   794 lemma mult1_union: