5628
|
1 |
(* Title: HOL/Induct/Multiset.ML
|
|
2 |
ID: $Id$
|
|
3 |
Author: Tobias Nipkow
|
|
4 |
Copyright 1998 TUM
|
|
5 |
*)
|
|
6 |
|
8952
|
7 |
Addsimps [Abs_multiset_inverse, Rep_multiset_inverse, Rep_multiset,
|
|
8 |
Zero_def];
|
5628
|
9 |
|
|
10 |
(** Preservation of representing set `multiset' **)
|
|
11 |
|
|
12 |
Goalw [multiset_def] "(%a. 0) : multiset";
|
6162
|
13 |
by (Simp_tac 1);
|
5628
|
14 |
qed "const0_in_multiset";
|
|
15 |
Addsimps [const0_in_multiset];
|
|
16 |
|
|
17 |
Goalw [multiset_def] "(%b. if b=a then 1 else 0) : multiset";
|
6162
|
18 |
by (Simp_tac 1);
|
5628
|
19 |
qed "only1_in_multiset";
|
|
20 |
Addsimps [only1_in_multiset];
|
|
21 |
|
|
22 |
Goalw [multiset_def]
|
|
23 |
"[| M : multiset; N : multiset |] ==> (%a. M a + N a) : multiset";
|
6162
|
24 |
by (Asm_full_simp_tac 1);
|
|
25 |
by (dtac finite_UnI 1);
|
|
26 |
by (assume_tac 1);
|
|
27 |
by (asm_full_simp_tac (simpset() delsimps [finite_Un]addsimps [Un_def]) 1);
|
5628
|
28 |
qed "union_preserves_multiset";
|
|
29 |
Addsimps [union_preserves_multiset];
|
|
30 |
|
|
31 |
Goalw [multiset_def]
|
|
32 |
"[| M : multiset |] ==> (%a. M a - N a) : multiset";
|
6162
|
33 |
by (Asm_full_simp_tac 1);
|
|
34 |
by (etac (rotate_prems 1 finite_subset) 1);
|
8952
|
35 |
by Auto_tac;
|
5628
|
36 |
qed "diff_preserves_multiset";
|
|
37 |
Addsimps [diff_preserves_multiset];
|
|
38 |
|
|
39 |
(** Injectivity of Rep_multiset **)
|
|
40 |
|
|
41 |
Goal "(M = N) = (Rep_multiset M = Rep_multiset N)";
|
6162
|
42 |
by (rtac iffI 1);
|
|
43 |
by (Asm_simp_tac 1);
|
|
44 |
by (dres_inst_tac [("f","Abs_multiset")] arg_cong 1);
|
|
45 |
by (Asm_full_simp_tac 1);
|
5628
|
46 |
qed "multiset_eq_conv_Rep_eq";
|
|
47 |
Addsimps [multiset_eq_conv_Rep_eq];
|
|
48 |
Addsimps [expand_fun_eq];
|
|
49 |
(*
|
|
50 |
Goal
|
|
51 |
"[| f : multiset; g : multiset |] ==> \
|
|
52 |
\ (Abs_multiset f = Abs_multiset g) = (!x. f x = g x)";
|
6162
|
53 |
by (rtac iffI 1);
|
|
54 |
by (dres_inst_tac [("f","Rep_multiset")] arg_cong 1);
|
|
55 |
by (Asm_full_simp_tac 1);
|
|
56 |
by (subgoal_tac "f = g" 1);
|
|
57 |
by (Asm_simp_tac 1);
|
|
58 |
by (rtac ext 1);
|
|
59 |
by (Blast_tac 1);
|
5628
|
60 |
qed "Abs_multiset_eq";
|
|
61 |
Addsimps [Abs_multiset_eq];
|
|
62 |
*)
|
|
63 |
|
|
64 |
(** Equations **)
|
|
65 |
|
|
66 |
(* union *)
|
|
67 |
|
|
68 |
Goalw [union_def,empty_def]
|
|
69 |
"M + {#} = M & {#} + M = M";
|
6162
|
70 |
by (Simp_tac 1);
|
5628
|
71 |
qed "union_empty";
|
|
72 |
Addsimps [union_empty];
|
|
73 |
|
|
74 |
Goalw [union_def]
|
|
75 |
"(M::'a multiset) + N = N + M";
|
6162
|
76 |
by (simp_tac (simpset() addsimps add_ac) 1);
|
5628
|
77 |
qed "union_comm";
|
|
78 |
|
|
79 |
Goalw [union_def]
|
|
80 |
"((M::'a multiset)+N)+K = M+(N+K)";
|
6162
|
81 |
by (simp_tac (simpset() addsimps add_ac) 1);
|
5628
|
82 |
qed "union_assoc";
|
|
83 |
|
|
84 |
qed_goal "union_lcomm" thy "M+(N+K) = N+((M+K)::'a multiset)"
|
|
85 |
(fn _ => [rtac (union_comm RS trans) 1, rtac (union_assoc RS trans) 1,
|
|
86 |
rtac (union_comm RS arg_cong) 1]);
|
|
87 |
|
7454
|
88 |
bind_thms ("union_ac", [union_assoc, union_comm, union_lcomm]);
|
5628
|
89 |
|
|
90 |
(* diff *)
|
|
91 |
|
|
92 |
Goalw [empty_def,diff_def]
|
|
93 |
"M-{#} = M & {#}-M = {#}";
|
6162
|
94 |
by (Simp_tac 1);
|
5628
|
95 |
qed "diff_empty";
|
|
96 |
Addsimps [diff_empty];
|
|
97 |
|
|
98 |
Goalw [union_def,diff_def]
|
|
99 |
"M+{#a#}-{#a#} = M";
|
6162
|
100 |
by (Simp_tac 1);
|
5628
|
101 |
qed "diff_union_inverse2";
|
|
102 |
Addsimps [diff_union_inverse2];
|
|
103 |
|
|
104 |
(* count *)
|
|
105 |
|
|
106 |
Goalw [count_def,empty_def]
|
|
107 |
"count {#} a = 0";
|
6162
|
108 |
by (Simp_tac 1);
|
5628
|
109 |
qed "count_empty";
|
|
110 |
Addsimps [count_empty];
|
|
111 |
|
|
112 |
Goalw [count_def,single_def]
|
|
113 |
"count {#b#} a = (if b=a then 1 else 0)";
|
6162
|
114 |
by (Simp_tac 1);
|
5628
|
115 |
qed "count_single";
|
|
116 |
Addsimps [count_single];
|
|
117 |
|
|
118 |
Goalw [count_def,union_def]
|
|
119 |
"count (M+N) a = count M a + count N a";
|
6162
|
120 |
by (Simp_tac 1);
|
5628
|
121 |
qed "count_union";
|
|
122 |
Addsimps [count_union];
|
|
123 |
|
5772
|
124 |
Goalw [count_def,diff_def]
|
|
125 |
"count (M-N) a = count M a - count N a";
|
6162
|
126 |
by (Simp_tac 1);
|
5772
|
127 |
qed "count_diff";
|
|
128 |
Addsimps [count_diff];
|
|
129 |
|
5628
|
130 |
(* set_of *)
|
|
131 |
|
|
132 |
Goalw [set_of_def] "set_of {#} = {}";
|
6162
|
133 |
by (Simp_tac 1);
|
5628
|
134 |
qed "set_of_empty";
|
|
135 |
Addsimps [set_of_empty];
|
|
136 |
|
|
137 |
Goalw [set_of_def]
|
|
138 |
"set_of {#b#} = {b}";
|
6162
|
139 |
by (Simp_tac 1);
|
5628
|
140 |
qed "set_of_single";
|
|
141 |
Addsimps [set_of_single];
|
|
142 |
|
|
143 |
Goalw [set_of_def]
|
|
144 |
"set_of(M+N) = set_of M Un set_of N";
|
8952
|
145 |
by Auto_tac;
|
5628
|
146 |
qed "set_of_union";
|
|
147 |
Addsimps [set_of_union];
|
|
148 |
|
8914
|
149 |
Goalw [set_of_def, empty_def, count_def] "(set_of M = {}) = (M = {#})";
|
|
150 |
by Auto_tac;
|
|
151 |
qed "set_of_eq_empty_iff";
|
|
152 |
|
5628
|
153 |
(* size *)
|
|
154 |
|
|
155 |
Goalw [size_def] "size {#} = 0";
|
6162
|
156 |
by (Simp_tac 1);
|
5628
|
157 |
qed "size_empty";
|
|
158 |
Addsimps [size_empty];
|
|
159 |
|
8914
|
160 |
Goalw [size_def] "size {#b#} = 1";
|
6162
|
161 |
by (Simp_tac 1);
|
5628
|
162 |
qed "size_single";
|
|
163 |
Addsimps [size_single];
|
|
164 |
|
8914
|
165 |
Goal "finite (set_of M)";
|
|
166 |
by (cut_inst_tac [("x", "M")] Rep_multiset 1);
|
|
167 |
by (asm_full_simp_tac
|
|
168 |
(simpset() addsimps [multiset_def, set_of_def, count_def]) 1);
|
|
169 |
qed "finite_set_of";
|
|
170 |
AddIffs [finite_set_of];
|
|
171 |
|
|
172 |
Goal "finite A ==> setsum (count N) (A Int set_of N) = setsum (count N) A";
|
|
173 |
by (etac finite_induct 1);
|
|
174 |
by (Simp_tac 1);
|
|
175 |
by (asm_full_simp_tac (simpset() addsimps [Int_insert_left, set_of_def]) 1);
|
|
176 |
qed "setsum_count_Int";
|
|
177 |
|
|
178 |
Goalw [size_def] "size (M+N::'a multiset) = size M + size N";
|
|
179 |
by (subgoal_tac "count (M+N) = (%a. count M a + count N a)" 1);
|
|
180 |
by (rtac ext 2);
|
|
181 |
by (Simp_tac 2);
|
|
182 |
by (asm_simp_tac
|
|
183 |
(simpset() addsimps [setsum_Un, setsum_addf, setsum_count_Int]) 1);
|
|
184 |
by (stac Int_commute 1);
|
|
185 |
by (asm_simp_tac (simpset() addsimps [setsum_count_Int]) 1);
|
|
186 |
qed "size_union";
|
|
187 |
Addsimps [size_union];
|
|
188 |
|
5628
|
189 |
|
|
190 |
(* equalities *)
|
|
191 |
|
5772
|
192 |
Goalw [count_def] "(M = N) = (!a. count M a = count N a)";
|
6162
|
193 |
by (Simp_tac 1);
|
5772
|
194 |
qed "multiset_eq_conv_count_eq";
|
|
195 |
|
5628
|
196 |
Goalw [single_def,empty_def] "{#a#} ~= {#} & {#} ~= {#a#}";
|
6162
|
197 |
by (Simp_tac 1);
|
5628
|
198 |
qed "single_not_empty";
|
|
199 |
Addsimps [single_not_empty];
|
|
200 |
|
|
201 |
Goalw [single_def] "({#a#}={#b#}) = (a=b)";
|
8952
|
202 |
by Auto_tac;
|
5628
|
203 |
qed "single_eq_single";
|
|
204 |
Addsimps [single_eq_single];
|
|
205 |
|
|
206 |
Goalw [union_def,empty_def]
|
|
207 |
"(M+N = {#}) = (M = {#} & N = {#})";
|
6162
|
208 |
by (Simp_tac 1);
|
|
209 |
by (Blast_tac 1);
|
5628
|
210 |
qed "union_eq_empty";
|
|
211 |
AddIffs [union_eq_empty];
|
|
212 |
|
|
213 |
Goalw [union_def,empty_def]
|
|
214 |
"({#} = M+N) = (M = {#} & N = {#})";
|
6162
|
215 |
by (Simp_tac 1);
|
|
216 |
by (Blast_tac 1);
|
5628
|
217 |
qed "empty_eq_union";
|
|
218 |
AddIffs [empty_eq_union];
|
|
219 |
|
|
220 |
Goalw [union_def]
|
|
221 |
"(M+K = N+K) = (M=(N::'a multiset))";
|
6162
|
222 |
by (Simp_tac 1);
|
5628
|
223 |
qed "union_right_cancel";
|
|
224 |
Addsimps [union_right_cancel];
|
|
225 |
|
|
226 |
Goalw [union_def]
|
|
227 |
"(K+M = K+N) = (M=(N::'a multiset))";
|
6162
|
228 |
by (Simp_tac 1);
|
5628
|
229 |
qed "union_left_cancel";
|
|
230 |
Addsimps [union_left_cancel];
|
|
231 |
|
|
232 |
Goalw [empty_def,single_def,union_def]
|
|
233 |
"(M+N = {#a#}) = (M={#a#} & N={#} | M={#} & N={#a#})";
|
6162
|
234 |
by (simp_tac (simpset() addsimps [add_is_1]) 1);
|
|
235 |
by (Blast_tac 1);
|
5628
|
236 |
qed "union_is_single";
|
|
237 |
|
|
238 |
Goalw [empty_def,single_def,union_def]
|
|
239 |
"({#a#} = M+N) = ({#a#}=M & N={#} | M={#} & {#a#}=N)";
|
6162
|
240 |
by (simp_tac (simpset() addsimps [one_is_add]) 1);
|
|
241 |
by (blast_tac (claset() addDs [sym]) 1);
|
5628
|
242 |
qed "single_is_union";
|
|
243 |
|
|
244 |
Goalw [single_def,union_def,diff_def]
|
|
245 |
"(M+{#a#} = N+{#b#}) = (M=N & a=b | M = N-{#a#}+{#b#} & N = M-{#b#}+{#a#})";
|
6162
|
246 |
by (Simp_tac 1);
|
|
247 |
by (rtac conjI 1);
|
|
248 |
by (Force_tac 1);
|
|
249 |
by (Clarify_tac 1);
|
|
250 |
by (rtac conjI 1);
|
|
251 |
by (Blast_tac 1);
|
|
252 |
by (Clarify_tac 1);
|
|
253 |
by (rtac iffI 1);
|
|
254 |
by (rtac conjI 1);
|
|
255 |
by (Clarify_tac 1);
|
|
256 |
by (rtac conjI 1);
|
|
257 |
by (asm_full_simp_tac (simpset() addsimps [eq_sym_conv]) 1);
|
5628
|
258 |
(* PROOF FAILED:
|
6162
|
259 |
by (Blast_tac 1);
|
5628
|
260 |
*)
|
6162
|
261 |
by (Fast_tac 1);
|
|
262 |
by (Asm_simp_tac 1);
|
|
263 |
by (Force_tac 1);
|
5628
|
264 |
qed "add_eq_conv_diff";
|
|
265 |
|
|
266 |
(* FIXME
|
|
267 |
val prems = Goal
|
|
268 |
"[| !!F. [| finite F; !G. G < F --> P G |] ==> P F |] ==> finite F --> P F";
|
6162
|
269 |
by (res_inst_tac [("a","F"),("f","%A. if finite A then card A else 0")]
|
5628
|
270 |
measure_induct 1);
|
6162
|
271 |
by (Clarify_tac 1);
|
|
272 |
by (resolve_tac prems 1);
|
|
273 |
by (assume_tac 1);
|
|
274 |
by (Clarify_tac 1);
|
|
275 |
by (subgoal_tac "finite G" 1);
|
|
276 |
by (fast_tac (claset() addDs [finite_subset,order_less_le RS iffD1]) 2);
|
|
277 |
by (etac allE 1);
|
|
278 |
by (etac impE 1);
|
|
279 |
by (Blast_tac 2);
|
|
280 |
by (asm_simp_tac (simpset() addsimps [psubset_card]) 1);
|
7454
|
281 |
no_qed();
|
5628
|
282 |
val lemma = result();
|
|
283 |
|
|
284 |
val prems = Goal
|
|
285 |
"[| finite F; !!F. [| finite F; !G. G < F --> P G |] ==> P F |] ==> P F";
|
6162
|
286 |
by (rtac (lemma RS mp) 1);
|
5628
|
287 |
by (REPEAT(ares_tac prems 1));
|
|
288 |
qed "finite_psubset_induct";
|
|
289 |
|
|
290 |
Better: use wf_finite_psubset in WF_Rel
|
|
291 |
*)
|
|
292 |
|
|
293 |
(** Towards the induction rule **)
|
|
294 |
|
8952
|
295 |
Goal "finite F ==> (setsum f F = 0) = (! a:F. f a = (0::nat))";
|
6162
|
296 |
by (etac finite_induct 1);
|
8952
|
297 |
by Auto_tac;
|
5628
|
298 |
qed "setsum_0";
|
|
299 |
Addsimps [setsum_0];
|
|
300 |
|
|
301 |
Goal "finite F ==> setsum f F = Suc n --> (? a:F. 0 < f a)";
|
6162
|
302 |
by (etac finite_induct 1);
|
8952
|
303 |
by Auto_tac;
|
7454
|
304 |
no_qed();
|
5628
|
305 |
val lemma = result();
|
|
306 |
|
|
307 |
Goal "[| setsum f F = Suc n; finite F |] ==> ? a:F. 0 < f a";
|
6162
|
308 |
by (dtac lemma 1);
|
|
309 |
by (Fast_tac 1);
|
5628
|
310 |
qed "setsum_SucD";
|
|
311 |
|
|
312 |
Goal "[| finite F; 0 < f a |] ==> \
|
|
313 |
\ setsum (f(a:=f(a)-1)) F = (if a:F then setsum f F - 1 else setsum f F)";
|
6162
|
314 |
by (etac finite_induct 1);
|
8952
|
315 |
by Auto_tac;
|
6162
|
316 |
by (asm_simp_tac (simpset() addsimps add_ac) 1);
|
|
317 |
by (dres_inst_tac [("a","a")] mk_disjoint_insert 1);
|
8952
|
318 |
by Auto_tac;
|
5628
|
319 |
qed "setsum_decr";
|
|
320 |
|
|
321 |
val prems = Goalw [multiset_def]
|
|
322 |
"[| P(%a.0); \
|
|
323 |
\ !!f b. [| f : multiset; P(f) |] ==> P(f(b:=f(b)+1)) |] \
|
|
324 |
\ ==> !f. f : multiset --> setsum f {x. 0 < f x} = n --> P(f)";
|
6162
|
325 |
by (induct_tac "n" 1);
|
|
326 |
by (Asm_simp_tac 1);
|
|
327 |
by (Clarify_tac 1);
|
|
328 |
by (subgoal_tac "f = (%a.0)" 1);
|
|
329 |
by (Asm_simp_tac 1);
|
|
330 |
by (resolve_tac prems 1);
|
|
331 |
by (rtac ext 1);
|
|
332 |
by (Force_tac 1);
|
|
333 |
by (Clarify_tac 1);
|
7499
|
334 |
by (ftac setsum_SucD 1);
|
6162
|
335 |
by (assume_tac 1);
|
|
336 |
by (Clarify_tac 1);
|
|
337 |
by (rename_tac "a" 1);
|
|
338 |
by (subgoal_tac "finite{x. 0 < (f(a:=f(a)-1)) x}" 1);
|
|
339 |
by (etac (rotate_prems 1 finite_subset) 2);
|
|
340 |
by (Simp_tac 2);
|
|
341 |
by (Blast_tac 2);
|
|
342 |
by (subgoal_tac
|
5628
|
343 |
"f = (f(a:=f(a)-1))(a:=(f(a:=f(a)-1))a+1)" 1);
|
6162
|
344 |
by (rtac ext 2);
|
|
345 |
by (Asm_simp_tac 2);
|
|
346 |
by (EVERY1[etac ssubst, resolve_tac prems]);
|
|
347 |
by (Blast_tac 1);
|
|
348 |
by (EVERY[etac allE 1, etac impE 1, etac mp 2]);
|
|
349 |
by (Blast_tac 1);
|
|
350 |
by (asm_simp_tac (simpset() addsimps [setsum_decr] delsimps [fun_upd_apply]) 1);
|
|
351 |
by (subgoal_tac "{x. x ~= a --> 0 < f x} = {x. 0 < f x}" 1);
|
|
352 |
by (Blast_tac 2);
|
|
353 |
by (subgoal_tac "{x. x ~= a & 0 < f x} = {x. 0 < f x} - {a}" 1);
|
|
354 |
by (Blast_tac 2);
|
|
355 |
by (asm_simp_tac (simpset() addsimps [le_imp_diff_is_add,setsum_diff1]
|
5983
|
356 |
addcongs [conj_cong]) 1);
|
7454
|
357 |
no_qed();
|
5628
|
358 |
val lemma = result();
|
|
359 |
|
|
360 |
val major::prems = Goal
|
|
361 |
"[| f : multiset; \
|
|
362 |
\ P(%a.0); \
|
|
363 |
\ !!f b. [| f : multiset; P(f) |] ==> P(f(b:=f(b)+1)) |] ==> P(f)";
|
6162
|
364 |
by (rtac (major RSN (3, lemma RS spec RS mp RS mp)) 1);
|
|
365 |
by (REPEAT(ares_tac (refl::prems) 1));
|
5628
|
366 |
qed "Rep_multiset_induct";
|
|
367 |
|
|
368 |
val [prem1,prem2] = Goalw [union_def,single_def,empty_def]
|
|
369 |
"[| P({#}); !!M x. P(M) ==> P(M + {#x#}) |] ==> P(M)";
|
|
370 |
by (rtac (Rep_multiset_inverse RS subst) 1);
|
|
371 |
by (rtac (Rep_multiset RS Rep_multiset_induct) 1);
|
6162
|
372 |
by (rtac prem1 1);
|
|
373 |
by (Clarify_tac 1);
|
|
374 |
by (subgoal_tac
|
5628
|
375 |
"f(b := f b + 1) = (%a. f a + (if a = b then 1 else 0))" 1);
|
6162
|
376 |
by (Simp_tac 2);
|
|
377 |
by (etac ssubst 1);
|
|
378 |
by (etac (Abs_multiset_inverse RS subst) 1);
|
|
379 |
by (etac(simplify (simpset()) prem2)1);
|
5628
|
380 |
qed "multiset_induct";
|
|
381 |
|
|
382 |
Delsimps [multiset_eq_conv_Rep_eq, expand_fun_eq];
|
|
383 |
Delsimps [Abs_multiset_inverse,Rep_multiset_inverse,Rep_multiset];
|
|
384 |
|
|
385 |
Goal
|
|
386 |
"(M+{#a#} = N+{#b#}) = (M = N & a = b | (? K. M = K+{#b#} & N = K+{#a#}))";
|
6162
|
387 |
by (simp_tac (simpset() addsimps [add_eq_conv_diff]) 1);
|
8952
|
388 |
by Auto_tac;
|
5628
|
389 |
qed "add_eq_conv_ex";
|
|
390 |
|
|
391 |
(** order **)
|
|
392 |
|
|
393 |
Goalw [mult1_def] "(M, {#}) ~: mult1(r)";
|
6162
|
394 |
by (Simp_tac 1);
|
5628
|
395 |
qed "not_less_empty";
|
|
396 |
AddIffs [not_less_empty];
|
|
397 |
|
|
398 |
Goalw [mult1_def]
|
|
399 |
"(N,M0 + {#a#}) : mult1(r) = \
|
|
400 |
\ ((? M. (M,M0) : mult1(r) & N = M + {#a#}) | \
|
8914
|
401 |
\ (? K. (!b. K :# b --> (b,a) : r) & N = M0 + K))";
|
6162
|
402 |
by (rtac iffI 1);
|
|
403 |
by (asm_full_simp_tac (simpset() addsimps [add_eq_conv_ex]) 1);
|
|
404 |
by (Clarify_tac 1);
|
|
405 |
by (etac disjE 1);
|
|
406 |
by (Blast_tac 1);
|
|
407 |
by (Clarify_tac 1);
|
|
408 |
by (res_inst_tac [("x","Ka+K")] exI 1);
|
|
409 |
by (simp_tac (simpset() addsimps union_ac) 1);
|
|
410 |
by (Blast_tac 1);
|
|
411 |
by (etac disjE 1);
|
|
412 |
by (Clarify_tac 1);
|
|
413 |
by (res_inst_tac [("x","aa")] exI 1);
|
|
414 |
by (res_inst_tac [("x","M0+{#a#}")] exI 1);
|
|
415 |
by (res_inst_tac [("x","K")] exI 1);
|
|
416 |
by (simp_tac (simpset() addsimps union_ac) 1);
|
|
417 |
by (Blast_tac 1);
|
5628
|
418 |
qed "less_add_conv";
|
|
419 |
|
|
420 |
Open_locale "MSOrd";
|
|
421 |
|
|
422 |
val W_def = thm "W_def";
|
|
423 |
|
|
424 |
Goalw [W_def]
|
|
425 |
"[| !b. (b,a) : r --> (!M : W. M+{#b#} : W); M0 : W; \
|
|
426 |
\ !M. (M,M0) : mult1(r) --> M+{#a#} : W |] \
|
|
427 |
\ ==> M0+{#a#} : W";
|
6162
|
428 |
by (rtac accI 1);
|
|
429 |
by (rename_tac "N" 1);
|
|
430 |
by (full_simp_tac (simpset() addsimps [less_add_conv]) 1);
|
|
431 |
by (etac disjE 1);
|
|
432 |
by (Blast_tac 1);
|
|
433 |
by (Clarify_tac 1);
|
|
434 |
by (rotate_tac ~1 1);
|
|
435 |
by (etac rev_mp 1);
|
|
436 |
by (res_inst_tac [("M","K")] multiset_induct 1);
|
|
437 |
by (Asm_simp_tac 1);
|
|
438 |
by (simp_tac (simpset() addsimps [union_assoc RS sym]) 1);
|
|
439 |
by (Blast_tac 1);
|
5628
|
440 |
qed "lemma1";
|
|
441 |
|
|
442 |
Goalw [W_def]
|
|
443 |
"[| !b. (b,a) : r --> (!M : W. M+{#b#} : W); M : W |] ==> M+{#a#} : W";
|
6162
|
444 |
by (etac acc_induct 1);
|
|
445 |
by (blast_tac (claset() addIs [export lemma1]) 1);
|
5628
|
446 |
qed "lemma2";
|
|
447 |
|
|
448 |
Goalw [W_def]
|
|
449 |
"wf(r) ==> !M:W. M+{#a#} : W";
|
6162
|
450 |
by (eres_inst_tac [("a","a")] wf_induct 1);
|
|
451 |
by (blast_tac (claset() addIs [export lemma2]) 1);
|
5628
|
452 |
qed "lemma3";
|
|
453 |
|
|
454 |
Goalw [W_def] "wf(r) ==> M : W";
|
6162
|
455 |
by (res_inst_tac [("M","M")] multiset_induct 1);
|
|
456 |
by (rtac accI 1);
|
|
457 |
by (Asm_full_simp_tac 1);
|
|
458 |
by (blast_tac (claset() addDs [export lemma3]) 1);
|
5628
|
459 |
qed "all_accessible";
|
|
460 |
|
6024
|
461 |
Close_locale "MSOrd";
|
5628
|
462 |
|
|
463 |
Goal "wf(r) ==> wf(mult1 r)";
|
6162
|
464 |
by (blast_tac (claset() addIs [acc_wfI, export all_accessible]) 1);
|
5628
|
465 |
qed "wf_mult1";
|
|
466 |
|
|
467 |
Goalw [mult_def] "wf(r) ==> wf(mult r)";
|
6162
|
468 |
by (blast_tac (claset() addIs [wf_trancl,wf_mult1]) 1);
|
5628
|
469 |
qed "wf_mult";
|
|
470 |
|
5772
|
471 |
(** Equivalence of mult with the usual (closure-free) def **)
|
|
472 |
|
|
473 |
(* Badly needed: a linear arithmetic tactic for multisets *)
|
|
474 |
|
8914
|
475 |
Goal "J :# a ==> I+J - {#a#} = I + (J-{#a#})";
|
6162
|
476 |
by (asm_simp_tac (simpset() addsimps [multiset_eq_conv_count_eq]) 1);
|
5772
|
477 |
qed "diff_union_single_conv";
|
5628
|
478 |
|
5772
|
479 |
(* One direction *)
|
|
480 |
Goalw [mult_def,mult1_def,set_of_def]
|
|
481 |
"trans r ==> \
|
|
482 |
\ (M,N) : mult r ==> (? I J K. N = I+J & M = I+K & J ~= {#} & \
|
|
483 |
\ (!k : set_of K. ? j : set_of J. (k,j) : r))";
|
6162
|
484 |
by (etac converse_trancl_induct 1);
|
|
485 |
by (Clarify_tac 1);
|
|
486 |
by (res_inst_tac [("x","M0")] exI 1);
|
|
487 |
by (Simp_tac 1);
|
|
488 |
by (Clarify_tac 1);
|
8914
|
489 |
by (case_tac "K :# a" 1);
|
6162
|
490 |
by (res_inst_tac [("x","I")] exI 1);
|
|
491 |
by (Simp_tac 1);
|
|
492 |
by (res_inst_tac [("x","(K - {#a#}) + Ka")] exI 1);
|
|
493 |
by (asm_simp_tac (simpset() addsimps [union_assoc RS sym]) 1);
|
|
494 |
by (dres_inst_tac[("f","%M. M-{#a#}")] arg_cong 1);
|
|
495 |
by (asm_full_simp_tac (simpset() addsimps [diff_union_single_conv]) 1);
|
|
496 |
by (full_simp_tac (simpset() addsimps [trans_def]) 1);
|
|
497 |
by (Blast_tac 1);
|
8914
|
498 |
by (subgoal_tac "I :# a" 1);
|
6162
|
499 |
by (res_inst_tac [("x","I-{#a#}")] exI 1);
|
|
500 |
by (res_inst_tac [("x","J+{#a#}")] exI 1);
|
|
501 |
by (res_inst_tac [("x","K + Ka")] exI 1);
|
|
502 |
by (rtac conjI 1);
|
|
503 |
by (asm_simp_tac (simpset() addsimps [multiset_eq_conv_count_eq]
|
5772
|
504 |
addsplits [nat_diff_split]) 1);
|
6162
|
505 |
by (rtac conjI 1);
|
|
506 |
by (dres_inst_tac[("f","%M. M-{#a#}")] arg_cong 1);
|
|
507 |
by (Asm_full_simp_tac 1);
|
|
508 |
by (asm_simp_tac (simpset() addsimps [multiset_eq_conv_count_eq]
|
5772
|
509 |
addsplits [nat_diff_split]) 1);
|
6162
|
510 |
by (full_simp_tac (simpset() addsimps [trans_def]) 1);
|
|
511 |
by (Blast_tac 1);
|
8914
|
512 |
by (subgoal_tac "(M0 +{#a#}) :# a" 1);
|
6162
|
513 |
by (Asm_full_simp_tac 1);
|
|
514 |
by (Simp_tac 1);
|
5772
|
515 |
qed "mult_implies_one_step";
|
8914
|
516 |
|
|
517 |
|
|
518 |
(** Proving that multisets are partially ordered **)
|
|
519 |
|
|
520 |
Goalw [trans_def] "trans {(x',x). x' < (x::'a::order)}";
|
|
521 |
by (blast_tac (claset() addIs [order_less_trans]) 1);
|
|
522 |
qed "trans_base_order";
|
|
523 |
|
|
524 |
Goal "finite A ==> (ALL x: A. EX y : A. x < (y::'a::order)) --> A={}";
|
|
525 |
by (etac finite_induct 1);
|
|
526 |
by Auto_tac;
|
|
527 |
by (blast_tac (claset() addIs [order_less_trans]) 1);
|
|
528 |
qed_spec_mp "mult_irrefl_lemma";
|
|
529 |
|
|
530 |
(*irreflexivity*)
|
|
531 |
Goalw [mult_less_def] "~ M < (M :: ('a::order)multiset)";
|
|
532 |
by Auto_tac;
|
|
533 |
by (dtac (trans_base_order RS mult_implies_one_step) 1);
|
|
534 |
by Auto_tac;
|
|
535 |
by (dtac (finite_set_of RS mult_irrefl_lemma) 1);
|
|
536 |
by (asm_full_simp_tac (simpset() addsimps [set_of_eq_empty_iff]) 1);
|
|
537 |
qed "mult_less_not_refl";
|
|
538 |
|
|
539 |
(* N<N ==> R *)
|
|
540 |
bind_thm ("mult_less_irrefl", mult_less_not_refl RS notE);
|
|
541 |
AddSEs [mult_less_irrefl];
|
|
542 |
|
|
543 |
(*transitivity*)
|
|
544 |
Goalw [mult_less_def, mult_def]
|
|
545 |
"[| K < M; M < N |] ==> K < (N :: ('a::order)multiset)";
|
|
546 |
by (blast_tac (claset() addIs [trancl_trans]) 1);
|
|
547 |
qed "mult_less_trans";
|
|
548 |
|
|
549 |
(*asymmetry*)
|
|
550 |
Goal "M < N ==> ~ N < (M :: ('a::order)multiset)";
|
|
551 |
by Auto_tac;
|
|
552 |
br (mult_less_not_refl RS notE) 1;
|
|
553 |
by (etac mult_less_trans 1);
|
|
554 |
by (assume_tac 1);
|
|
555 |
qed "mult_less_not_sym";
|
|
556 |
|
|
557 |
(* [| M<N; ~P ==> N<M |] ==> P *)
|
|
558 |
bind_thm ("mult_less_asym", mult_less_not_sym RS swap);
|
|
559 |
|
|
560 |
Goalw [mult_le_def] "M <= (M :: ('a::order)multiset)";
|
|
561 |
by Auto_tac;
|
|
562 |
qed "mult_le_refl";
|
|
563 |
|
|
564 |
(*anti-symmetry*)
|
|
565 |
Goalw [mult_le_def] "[| M <= N; N <= M |] ==> M = (N :: ('a::order)multiset)";
|
|
566 |
by (blast_tac (claset() addDs [mult_less_not_sym]) 1);
|
|
567 |
qed "mult_le_antisym";
|
|
568 |
|
|
569 |
(*transitivity*)
|
|
570 |
Goalw [mult_le_def]
|
|
571 |
"[| K <= M; M <= N |] ==> K <= (N :: ('a::order)multiset)";
|
|
572 |
by (blast_tac (claset() addIs [mult_less_trans]) 1);
|
|
573 |
qed "mult_le_trans";
|
|
574 |
|
|
575 |
Goalw [mult_le_def] "M < N = (M <= N & M ~= (N :: ('a::order)multiset))";
|
|
576 |
by Auto_tac;
|
|
577 |
qed "mult_less_le";
|