src/HOL/Library/Multiset_Order.thy
author haftmann
Fri Feb 26 22:44:11 2016 +0100 (2016-02-26)
changeset 62430 9527ff088c15
parent 61424 c3658c18b7bc
child 63040 eb4ddd18d635
permissions -rw-r--r--
more succint formulation of membership for multisets, similar to lists;
discontinued ASCII notation for multiset membership;
more theorems on multisets, dropping redundant interpretation;
modernized notation;
some annotations concerning future work
blanchet@59813
     1
(*  Title:      HOL/Library/Multiset_Order.thy
blanchet@59813
     2
    Author:     Dmitriy Traytel, TU Muenchen
blanchet@59813
     3
    Author:     Jasmin Blanchette, Inria, LORIA, MPII
blanchet@59813
     4
*)
blanchet@59813
     5
wenzelm@60500
     6
section \<open>More Theorems about the Multiset Order\<close>
blanchet@59813
     7
blanchet@59813
     8
theory Multiset_Order
blanchet@59813
     9
imports Multiset
blanchet@59813
    10
begin
blanchet@59813
    11
wenzelm@60500
    12
subsubsection \<open>Alternative characterizations\<close>
blanchet@59813
    13
blanchet@59813
    14
context order
blanchet@59813
    15
begin
blanchet@59813
    16
blanchet@59813
    17
lemma reflp_le: "reflp (op \<le>)"
blanchet@59813
    18
  unfolding reflp_def by simp
blanchet@59813
    19
blanchet@59813
    20
lemma antisymP_le: "antisymP (op \<le>)"
blanchet@59813
    21
  unfolding antisym_def by auto
blanchet@59813
    22
blanchet@59813
    23
lemma transp_le: "transp (op \<le>)"
blanchet@59813
    24
  unfolding transp_def by auto
blanchet@59813
    25
blanchet@59813
    26
lemma irreflp_less: "irreflp (op <)"
blanchet@59813
    27
  unfolding irreflp_def by simp
blanchet@59813
    28
blanchet@59813
    29
lemma antisymP_less: "antisymP (op <)"
blanchet@59813
    30
  unfolding antisym_def by auto
blanchet@59813
    31
blanchet@59813
    32
lemma transp_less: "transp (op <)"
blanchet@59813
    33
  unfolding transp_def by auto
blanchet@59813
    34
blanchet@59813
    35
lemmas le_trans = transp_le[unfolded transp_def, rule_format]
blanchet@59813
    36
blanchet@59813
    37
lemma order_mult: "class.order
blanchet@59813
    38
  (\<lambda>M N. (M, N) \<in> mult {(x, y). x < y} \<or> M = N)
blanchet@59813
    39
  (\<lambda>M N. (M, N) \<in> mult {(x, y). x < y})"
blanchet@59813
    40
  (is "class.order ?le ?less")
blanchet@59813
    41
proof -
blanchet@59813
    42
  have irrefl: "\<And>M :: 'a multiset. \<not> ?less M M"
blanchet@59813
    43
  proof
blanchet@59813
    44
    fix M :: "'a multiset"
blanchet@59813
    45
    have "trans {(x'::'a, x). x' < x}"
blanchet@59813
    46
      by (rule transI) simp
blanchet@59813
    47
    moreover
blanchet@59813
    48
    assume "(M, M) \<in> mult {(x, y). x < y}"
blanchet@59813
    49
    ultimately have "\<exists>I J K. M = I + J \<and> M = I + K
nipkow@60495
    50
      \<and> J \<noteq> {#} \<and> (\<forall>k\<in>set_mset K. \<exists>j\<in>set_mset J. (k, j) \<in> {(x, y). x < y})"
blanchet@59813
    51
      by (rule mult_implies_one_step)
blanchet@59813
    52
    then obtain I J K where "M = I + J" and "M = I + K"
nipkow@60495
    53
      and "J \<noteq> {#}" and "(\<forall>k\<in>set_mset K. \<exists>j\<in>set_mset J. (k, j) \<in> {(x, y). x < y})" by blast
nipkow@60495
    54
    then have aux1: "K \<noteq> {#}" and aux2: "\<forall>k\<in>set_mset K. \<exists>j\<in>set_mset K. k < j" by auto
nipkow@60495
    55
    have "finite (set_mset K)" by simp
blanchet@59813
    56
    moreover note aux2
nipkow@60495
    57
    ultimately have "set_mset K = {}"
blanchet@59813
    58
      by (induct rule: finite_induct)
blanchet@59813
    59
       (simp, metis (mono_tags) insert_absorb insert_iff insert_not_empty less_irrefl less_trans)
blanchet@59813
    60
    with aux1 show False by simp
blanchet@59813
    61
  qed
blanchet@59813
    62
  have trans: "\<And>K M N :: 'a multiset. ?less K M \<Longrightarrow> ?less M N \<Longrightarrow> ?less K N"
blanchet@59813
    63
    unfolding mult_def by (blast intro: trancl_trans)
blanchet@59813
    64
  show "class.order ?le ?less"
wenzelm@60679
    65
    by standard (auto simp add: le_multiset_def irrefl dest: trans)
blanchet@59813
    66
qed
blanchet@59813
    67
wenzelm@60500
    68
text \<open>The Dershowitz--Manna ordering:\<close>
blanchet@59813
    69
blanchet@59813
    70
definition less_multiset\<^sub>D\<^sub>M where
blanchet@59813
    71
  "less_multiset\<^sub>D\<^sub>M M N \<longleftrightarrow>
Mathias@60397
    72
   (\<exists>X Y. X \<noteq> {#} \<and> X \<le># N \<and> M = (N - X) + Y \<and> (\<forall>k. k \<in># Y \<longrightarrow> (\<exists>a. a \<in># X \<and> k < a)))"
blanchet@59813
    73
blanchet@59813
    74
wenzelm@60500
    75
text \<open>The Huet--Oppen ordering:\<close>
blanchet@59813
    76
blanchet@59813
    77
definition less_multiset\<^sub>H\<^sub>O where
blanchet@59813
    78
  "less_multiset\<^sub>H\<^sub>O M N \<longleftrightarrow> M \<noteq> N \<and> (\<forall>y. count N y < count M y \<longrightarrow> (\<exists>x. y < x \<and> count M x < count N x))"
blanchet@59813
    79
haftmann@62430
    80
lemma mult_imp_less_multiset\<^sub>H\<^sub>O:
haftmann@62430
    81
  "(M, N) \<in> mult {(x, y). x < y} \<Longrightarrow> less_multiset\<^sub>H\<^sub>O M N"
haftmann@62430
    82
proof (unfold mult_def, induct rule: trancl_induct)
blanchet@59813
    83
  case (base P)
haftmann@62430
    84
  then show ?case
haftmann@62430
    85
    by (auto elim!: mult1_lessE simp add: count_eq_zero_iff less_multiset\<^sub>H\<^sub>O_def split: if_splits dest!: Suc_lessD)
blanchet@59813
    86
next
blanchet@59813
    87
  case (step N P)
haftmann@62430
    88
  from step(3) have "M \<noteq> N" and
haftmann@62430
    89
    **: "\<And>y. count N y < count M y \<Longrightarrow> (\<exists>x>y. count M x < count N x)"
haftmann@62430
    90
    by (simp_all add: less_multiset\<^sub>H\<^sub>O_def)
blanchet@59813
    91
  from step(2) obtain M0 a K where
haftmann@62430
    92
    *: "P = M0 + {#a#}" "N = M0 + K" "a \<notin># K" "\<And>b. b \<in># K \<Longrightarrow> b < a"
haftmann@62430
    93
    by (blast elim: mult1_lessE)
haftmann@62430
    94
  from \<open>M \<noteq> N\<close> ** *(1,2,3) have "M \<noteq> P" by (force dest: *(4) split: if_splits)
blanchet@59813
    95
  moreover
blanchet@59813
    96
  { assume "count P a \<le> count M a"
haftmann@62430
    97
    with \<open>a \<notin># K\<close> have "count N a < count M a" unfolding *(1,2)
haftmann@62430
    98
      by (auto simp add: not_in_iff)
haftmann@62430
    99
      with ** obtain z where z: "z > a" "count M z < count N z"
haftmann@62430
   100
        by blast
haftmann@62430
   101
      with * have "count N z \<le> count P z" 
haftmann@62430
   102
        by (force simp add: not_in_iff)
blanchet@59813
   103
      with z have "\<exists>z > a. count M z < count P z" by auto
blanchet@59813
   104
  } note count_a = this
blanchet@59813
   105
  { fix y
blanchet@59813
   106
    assume count_y: "count P y < count M y"
blanchet@59813
   107
    have "\<exists>x>y. count M x < count P x"
blanchet@59813
   108
    proof (cases "y = a")
blanchet@59813
   109
      case True
blanchet@59813
   110
      with count_y count_a show ?thesis by auto
blanchet@59813
   111
    next
blanchet@59813
   112
      case False
blanchet@59813
   113
      show ?thesis
blanchet@59813
   114
      proof (cases "y \<in># K")
blanchet@59813
   115
        case True
haftmann@62430
   116
        with *(4) have "y < a" by simp
blanchet@59813
   117
        then show ?thesis by (cases "count P a \<le> count M a") (auto dest: count_a intro: less_trans)
blanchet@59813
   118
      next
blanchet@59813
   119
        case False
haftmann@62430
   120
        with \<open>y \<noteq> a\<close> have "count P y = count N y" unfolding *(1,2)
haftmann@62430
   121
          by (simp add: not_in_iff)
haftmann@62430
   122
        with count_y ** obtain z where z: "z > y" "count M z < count N z" by auto
blanchet@59813
   123
        show ?thesis
blanchet@59813
   124
        proof (cases "z \<in># K")
blanchet@59813
   125
          case True
haftmann@62430
   126
          with *(4) have "z < a" by simp
blanchet@59813
   127
          with z(1) show ?thesis
blanchet@59813
   128
            by (cases "count P a \<le> count M a") (auto dest!: count_a intro: less_trans)
blanchet@59813
   129
        next
blanchet@59813
   130
          case False
haftmann@62430
   131
          with \<open>a \<notin># K\<close> have "count N z \<le> count P z" unfolding *
haftmann@62430
   132
            by (auto simp add: not_in_iff)
blanchet@59813
   133
          with z show ?thesis by auto
blanchet@59813
   134
        qed
blanchet@59813
   135
      qed
blanchet@59813
   136
    qed
blanchet@59813
   137
  }
haftmann@62430
   138
  ultimately show ?case unfolding less_multiset\<^sub>H\<^sub>O_def by blast
blanchet@59813
   139
qed
blanchet@59813
   140
blanchet@59813
   141
lemma less_multiset\<^sub>D\<^sub>M_imp_mult:
blanchet@59813
   142
  "less_multiset\<^sub>D\<^sub>M M N \<Longrightarrow> (M, N) \<in> mult {(x, y). x < y}"
blanchet@59813
   143
proof -
blanchet@59813
   144
  assume "less_multiset\<^sub>D\<^sub>M M N"
blanchet@59813
   145
  then obtain X Y where
Mathias@60397
   146
    "X \<noteq> {#}" and "X \<le># N" and "M = N - X + Y" and "\<forall>k. k \<in># Y \<longrightarrow> (\<exists>a. a \<in># X \<and> k < a)"
blanchet@59813
   147
    unfolding less_multiset\<^sub>D\<^sub>M_def by blast
blanchet@59813
   148
  then have "(N - X + Y, N - X + X) \<in> mult {(x, y). x < y}"
blanchet@59813
   149
    by (intro one_step_implies_mult) (auto simp: Bex_def trans_def)
wenzelm@60500
   150
  with \<open>M = N - X + Y\<close> \<open>X \<le># N\<close> show "(M, N) \<in> mult {(x, y). x < y}"
Mathias@60397
   151
    by (metis subset_mset.diff_add)
blanchet@59813
   152
qed
blanchet@59813
   153
blanchet@59813
   154
lemma less_multiset\<^sub>H\<^sub>O_imp_less_multiset\<^sub>D\<^sub>M: "less_multiset\<^sub>H\<^sub>O M N \<Longrightarrow> less_multiset\<^sub>D\<^sub>M M N"
blanchet@59813
   155
unfolding less_multiset\<^sub>D\<^sub>M_def
blanchet@59813
   156
proof (intro iffI exI conjI)
blanchet@59813
   157
  assume "less_multiset\<^sub>H\<^sub>O M N"
blanchet@59813
   158
  then obtain z where z: "count M z < count N z"
blanchet@59813
   159
    unfolding less_multiset\<^sub>H\<^sub>O_def by (auto simp: multiset_eq_iff nat_neq_iff)
blanchet@59813
   160
  def X \<equiv> "N - M"
blanchet@59813
   161
  def Y \<equiv> "M - N"
blanchet@59813
   162
  from z show "X \<noteq> {#}" unfolding X_def by (auto simp: multiset_eq_iff not_less_eq_eq Suc_le_eq)
Mathias@60397
   163
  from z show "X \<le># N" unfolding X_def by auto
blanchet@59813
   164
  show "M = (N - X) + Y" unfolding X_def Y_def multiset_eq_iff count_union count_diff by force
blanchet@59813
   165
  show "\<forall>k. k \<in># Y \<longrightarrow> (\<exists>a. a \<in># X \<and> k < a)"
blanchet@59813
   166
  proof (intro allI impI)
blanchet@59813
   167
    fix k
blanchet@59813
   168
    assume "k \<in># Y"
haftmann@62430
   169
    then have "count N k < count M k" unfolding Y_def
haftmann@62430
   170
      by (auto simp add: in_diff_count)
wenzelm@60500
   171
    with \<open>less_multiset\<^sub>H\<^sub>O M N\<close> obtain a where "k < a" and "count M a < count N a"
blanchet@59813
   172
      unfolding less_multiset\<^sub>H\<^sub>O_def by blast
haftmann@62430
   173
    then show "\<exists>a. a \<in># X \<and> k < a" unfolding X_def
haftmann@62430
   174
      by (auto simp add: in_diff_count)
blanchet@59813
   175
  qed
blanchet@59813
   176
qed
blanchet@59813
   177
blanchet@59813
   178
lemma mult_less_multiset\<^sub>D\<^sub>M: "(M, N) \<in> mult {(x, y). x < y} \<longleftrightarrow> less_multiset\<^sub>D\<^sub>M M N"
blanchet@59813
   179
  by (metis less_multiset\<^sub>D\<^sub>M_imp_mult less_multiset\<^sub>H\<^sub>O_imp_less_multiset\<^sub>D\<^sub>M mult_imp_less_multiset\<^sub>H\<^sub>O)
blanchet@59813
   180
blanchet@59813
   181
lemma mult_less_multiset\<^sub>H\<^sub>O: "(M, N) \<in> mult {(x, y). x < y} \<longleftrightarrow> less_multiset\<^sub>H\<^sub>O M N"
blanchet@59813
   182
  by (metis less_multiset\<^sub>D\<^sub>M_imp_mult less_multiset\<^sub>H\<^sub>O_imp_less_multiset\<^sub>D\<^sub>M mult_imp_less_multiset\<^sub>H\<^sub>O)
blanchet@59813
   183
blanchet@59813
   184
lemmas mult\<^sub>D\<^sub>M = mult_less_multiset\<^sub>D\<^sub>M[unfolded less_multiset\<^sub>D\<^sub>M_def]
blanchet@59813
   185
lemmas mult\<^sub>H\<^sub>O = mult_less_multiset\<^sub>H\<^sub>O[unfolded less_multiset\<^sub>H\<^sub>O_def]
blanchet@59813
   186
blanchet@59813
   187
end
blanchet@59813
   188
blanchet@59813
   189
context linorder
blanchet@59813
   190
begin
blanchet@59813
   191
wenzelm@61076
   192
lemma total_le: "total {(a :: 'a, b). a \<le> b}"
blanchet@59813
   193
  unfolding total_on_def by auto
blanchet@59813
   194
wenzelm@61076
   195
lemma total_less: "total {(a :: 'a, b). a < b}"
blanchet@59813
   196
  unfolding total_on_def by auto
blanchet@59813
   197
blanchet@59813
   198
lemma linorder_mult: "class.linorder
blanchet@59813
   199
  (\<lambda>M N. (M, N) \<in> mult {(x, y). x < y} \<or> M = N)
blanchet@59813
   200
  (\<lambda>M N. (M, N) \<in> mult {(x, y). x < y})"
blanchet@59813
   201
proof -
blanchet@59813
   202
  interpret o: order
blanchet@59813
   203
    "(\<lambda>M N. (M, N) \<in> mult {(x, y). x < y} \<or> M = N)"
blanchet@59813
   204
    "(\<lambda>M N. (M, N) \<in> mult {(x, y). x < y})"
blanchet@59813
   205
    by (rule order_mult)
blanchet@59813
   206
  show ?thesis by unfold_locales (auto 0 3 simp: mult\<^sub>H\<^sub>O not_less_iff_gr_or_eq)
blanchet@59813
   207
qed
blanchet@59813
   208
blanchet@59813
   209
end
blanchet@59813
   210
blanchet@59813
   211
lemma less_multiset_less_multiset\<^sub>H\<^sub>O:
blanchet@59958
   212
  "M #\<subset># N \<longleftrightarrow> less_multiset\<^sub>H\<^sub>O M N"
blanchet@59813
   213
  unfolding less_multiset_def mult\<^sub>H\<^sub>O less_multiset\<^sub>H\<^sub>O_def ..
blanchet@59813
   214
blanchet@59813
   215
lemmas less_multiset\<^sub>D\<^sub>M = mult\<^sub>D\<^sub>M[folded less_multiset_def]
blanchet@59813
   216
lemmas less_multiset\<^sub>H\<^sub>O = mult\<^sub>H\<^sub>O[folded less_multiset_def]
blanchet@59813
   217
blanchet@59813
   218
lemma le_multiset\<^sub>H\<^sub>O:
wenzelm@61076
   219
  fixes M N :: "('a :: linorder) multiset"
blanchet@59958
   220
  shows "M #\<subseteq># N \<longleftrightarrow> (\<forall>y. count N y < count M y \<longrightarrow> (\<exists>x. y < x \<and> count M x < count N x))"
blanchet@59813
   221
  by (auto simp: le_multiset_def less_multiset\<^sub>H\<^sub>O)
blanchet@59813
   222
wenzelm@61076
   223
lemma wf_less_multiset: "wf {(M :: ('a :: wellorder) multiset, N). M #\<subset># N}"
blanchet@59813
   224
  unfolding less_multiset_def by (auto intro: wf_mult wf)
blanchet@59813
   225
blanchet@59813
   226
lemma order_multiset: "class.order
wenzelm@61076
   227
  (le_multiset :: ('a :: order) multiset \<Rightarrow> ('a :: order) multiset \<Rightarrow> bool)
wenzelm@61076
   228
  (less_multiset :: ('a :: order) multiset \<Rightarrow> ('a :: order) multiset \<Rightarrow> bool)"
blanchet@59813
   229
  by unfold_locales
blanchet@59813
   230
blanchet@59813
   231
lemma linorder_multiset: "class.linorder
wenzelm@61076
   232
  (le_multiset :: ('a :: linorder) multiset \<Rightarrow> ('a :: linorder) multiset \<Rightarrow> bool)
wenzelm@61076
   233
  (less_multiset :: ('a :: linorder) multiset \<Rightarrow> ('a :: linorder) multiset \<Rightarrow> bool)"
blanchet@59813
   234
  by unfold_locales (fastforce simp add: less_multiset\<^sub>H\<^sub>O le_multiset_def not_less_iff_gr_or_eq)
blanchet@59813
   235
blanchet@59813
   236
interpretation multiset_linorder: linorder
wenzelm@61076
   237
  "le_multiset :: ('a :: linorder) multiset \<Rightarrow> ('a :: linorder) multiset \<Rightarrow> bool"
wenzelm@61076
   238
  "less_multiset :: ('a :: linorder) multiset \<Rightarrow> ('a :: linorder) multiset \<Rightarrow> bool"
blanchet@59813
   239
  by (rule linorder_multiset)
blanchet@59813
   240
blanchet@59813
   241
interpretation multiset_wellorder: wellorder
wenzelm@61076
   242
  "le_multiset :: ('a :: wellorder) multiset \<Rightarrow> ('a :: wellorder) multiset \<Rightarrow> bool"
wenzelm@61076
   243
  "less_multiset :: ('a :: wellorder) multiset \<Rightarrow> ('a :: wellorder) multiset \<Rightarrow> bool"
haftmann@61424
   244
  by unfold_locales (blast intro: wf_less_multiset [unfolded wf_def, simplified, rule_format])
blanchet@59813
   245
blanchet@59813
   246
lemma le_multiset_total:
wenzelm@61076
   247
  fixes M N :: "('a :: linorder) multiset"
blanchet@59958
   248
  shows "\<not> M #\<subseteq># N \<Longrightarrow> N #\<subseteq># M"
blanchet@59813
   249
  by (metis multiset_linorder.le_cases)
blanchet@59813
   250
blanchet@59813
   251
lemma less_eq_imp_le_multiset:
wenzelm@61076
   252
  fixes M N :: "('a :: linorder) multiset"
Mathias@60397
   253
  shows "M \<le># N \<Longrightarrow> M #\<subseteq># N"
blanchet@59813
   254
  unfolding le_multiset_def less_multiset\<^sub>H\<^sub>O
Mathias@60397
   255
  by (simp add: less_le_not_le subseteq_mset_def)
blanchet@59813
   256
blanchet@59813
   257
lemma less_multiset_right_total:
wenzelm@61076
   258
  fixes M :: "('a :: linorder) multiset"
blanchet@59958
   259
  shows "M #\<subset># M + {#undefined#}"
blanchet@59813
   260
  unfolding le_multiset_def less_multiset\<^sub>H\<^sub>O by simp
blanchet@59813
   261
blanchet@59813
   262
lemma le_multiset_empty_left[simp]:
wenzelm@61076
   263
  fixes M :: "('a :: linorder) multiset"
blanchet@59958
   264
  shows "{#} #\<subseteq># M"
blanchet@59813
   265
  by (simp add: less_eq_imp_le_multiset)
blanchet@59813
   266
blanchet@59813
   267
lemma le_multiset_empty_right[simp]:
wenzelm@61076
   268
  fixes M :: "('a :: linorder) multiset"
blanchet@59958
   269
  shows "M \<noteq> {#} \<Longrightarrow> \<not> M #\<subseteq># {#}"
blanchet@59813
   270
  by (metis le_multiset_empty_left multiset_order.antisym)
blanchet@59813
   271
blanchet@59813
   272
lemma less_multiset_empty_left[simp]:
wenzelm@61076
   273
  fixes M :: "('a :: linorder) multiset"
blanchet@59958
   274
  shows "M \<noteq> {#} \<Longrightarrow> {#} #\<subset># M"
blanchet@59813
   275
  by (simp add: less_multiset\<^sub>H\<^sub>O)
blanchet@59813
   276
blanchet@59813
   277
lemma less_multiset_empty_right[simp]:
wenzelm@61076
   278
  fixes M :: "('a :: linorder) multiset"
blanchet@59958
   279
  shows "\<not> M #\<subset># {#}"
blanchet@59813
   280
  using le_empty less_multiset\<^sub>D\<^sub>M by blast
blanchet@59813
   281
blanchet@59813
   282
lemma
wenzelm@61076
   283
  fixes M N :: "('a :: linorder) multiset"
blanchet@59813
   284
  shows
blanchet@59958
   285
    le_multiset_plus_left[simp]: "N #\<subseteq># (M + N)" and
blanchet@59958
   286
    le_multiset_plus_right[simp]: "M #\<subseteq># (M + N)"
blanchet@59813
   287
  using [[metis_verbose = false]] by (metis less_eq_imp_le_multiset mset_le_add_left add.commute)+
blanchet@59813
   288
blanchet@59813
   289
lemma
wenzelm@61076
   290
  fixes M N :: "('a :: linorder) multiset"
blanchet@59813
   291
  shows
blanchet@59958
   292
    less_multiset_plus_plus_left_iff[simp]: "M + N #\<subset># M' + N \<longleftrightarrow> M #\<subset># M'" and
blanchet@59958
   293
    less_multiset_plus_plus_right_iff[simp]: "M + N #\<subset># M + N' \<longleftrightarrow> N #\<subset># N'"
blanchet@59813
   294
  unfolding less_multiset\<^sub>H\<^sub>O by auto
blanchet@59813
   295
blanchet@59813
   296
lemma add_eq_self_empty_iff: "M + N = M \<longleftrightarrow> N = {#}"
blanchet@59813
   297
  by (metis add.commute add_diff_cancel_right' monoid_add_class.add.left_neutral)
blanchet@59813
   298
blanchet@59813
   299
lemma
wenzelm@61076
   300
  fixes M N :: "('a :: linorder) multiset"
blanchet@59813
   301
  shows
blanchet@59958
   302
    less_multiset_plus_left_nonempty[simp]: "M \<noteq> {#} \<Longrightarrow> N #\<subset># M + N" and
blanchet@59958
   303
    less_multiset_plus_right_nonempty[simp]: "N \<noteq> {#} \<Longrightarrow> M #\<subset># M + N"
blanchet@59813
   304
  using [[metis_verbose = false]]
blanchet@59813
   305
  by (metis add.right_neutral less_multiset_empty_left less_multiset_plus_plus_right_iff
blanchet@59813
   306
    add.commute)+
blanchet@59813
   307
wenzelm@61076
   308
lemma ex_gt_imp_less_multiset: "(\<exists>y :: 'a :: linorder. y \<in># N \<and> (\<forall>x. x \<in># M \<longrightarrow> x < y)) \<Longrightarrow> M #\<subset># N"
haftmann@62430
   309
  unfolding less_multiset\<^sub>H\<^sub>O
haftmann@62430
   310
  by (metis count_eq_zero_iff count_greater_zero_iff less_le_not_le)
haftmann@62430
   311
  
blanchet@59813
   312
lemma ex_gt_count_imp_less_multiset:
wenzelm@61076
   313
  "(\<forall>y :: 'a :: linorder. y \<in># M + N \<longrightarrow> y \<le> x) \<Longrightarrow> count M x < count N x \<Longrightarrow> M #\<subset># N"
haftmann@62430
   314
  unfolding less_multiset\<^sub>H\<^sub>O
haftmann@62430
   315
  by (metis add_gr_0 count_union mem_Collect_eq not_gr0 not_le not_less_iff_gr_or_eq set_mset_def)
blanchet@59813
   316
Mathias@60397
   317
lemma union_less_diff_plus: "P \<le># M \<Longrightarrow> N #\<subset># P \<Longrightarrow> M - P + N #\<subset># M"
Mathias@60397
   318
  by (drule subset_mset.diff_add[symmetric]) (metis union_less_mono2)
blanchet@59813
   319
blanchet@59813
   320
end