equal
deleted
inserted
replaced
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: |