14 by (rtac lfp_mono 1); |
14 by (rtac lfp_mono 1); |
15 by (REPEAT (ares_tac basic_monos 1)); |
15 by (REPEAT (ares_tac basic_monos 1)); |
16 qed "Fin_mono"; |
16 qed "Fin_mono"; |
17 |
17 |
18 goalw Finite.thy Fin.defs "Fin(A) <= Pow(A)"; |
18 goalw Finite.thy Fin.defs "Fin(A) <= Pow(A)"; |
19 by (fast_tac (set_cs addSIs [lfp_lowerbound]) 1); |
19 by (fast_tac (!claset addSIs [lfp_lowerbound]) 1); |
20 qed "Fin_subset_Pow"; |
20 qed "Fin_subset_Pow"; |
21 |
21 |
22 (* A : Fin(B) ==> A <= B *) |
22 (* A : Fin(B) ==> A <= B *) |
23 val FinD = Fin_subset_Pow RS subsetD RS PowD; |
23 val FinD = Fin_subset_Pow RS subsetD RS PowD; |
24 |
24 |
53 by (eres_inst_tac [("t","C")] (insert_Diff RS subst) 2); |
53 by (eres_inst_tac [("t","C")] (insert_Diff RS subst) 2); |
54 by (ALLGOALS Asm_simp_tac); |
54 by (ALLGOALS Asm_simp_tac); |
55 qed "Fin_subset"; |
55 qed "Fin_subset"; |
56 |
56 |
57 goal Finite.thy "(F Un G : Fin(A)) = (F: Fin(A) & G: Fin(A))"; |
57 goal Finite.thy "(F Un G : Fin(A)) = (F: Fin(A) & G: Fin(A))"; |
58 by (fast_tac (set_cs addIs [Fin_UnI] addDs |
58 by (fast_tac (!claset addIs [Fin_UnI] addDs |
59 [Un_upper1 RS Fin_subset, Un_upper2 RS Fin_subset]) 1); |
59 [Un_upper1 RS Fin_subset, Un_upper2 RS Fin_subset]) 1); |
60 qed "subset_Fin"; |
60 qed "subset_Fin"; |
61 Addsimps[subset_Fin]; |
61 Addsimps[subset_Fin]; |
62 |
62 |
63 goal Finite.thy "(insert a A : Fin M) = (a:M & A : Fin M)"; |
63 goal Finite.thy "(insert a A : Fin M) = (a:M & A : Fin M)"; |
64 by (stac insert_is_Un 1); |
64 by (stac insert_is_Un 1); |
65 by (Simp_tac 1); |
65 by (Simp_tac 1); |
66 by (fast_tac (set_cs addSIs Fin.intrs addDs [FinD]) 1); |
66 by (fast_tac (!claset addSIs Fin.intrs addDs [FinD]) 1); |
67 qed "insert_Fin"; |
67 qed "insert_Fin"; |
68 Addsimps[insert_Fin]; |
68 Addsimps[insert_Fin]; |
69 |
69 |
70 (*The image of a finite set is finite*) |
70 (*The image of a finite set is finite*) |
71 val major::_ = goal Finite.thy |
71 val major::_ = goal Finite.thy |
161 |
161 |
162 |
162 |
163 section "Finite cardinality -- 'card'"; |
163 section "Finite cardinality -- 'card'"; |
164 |
164 |
165 goal Set.thy "{f i |i. P i | i=n} = insert (f n) {f i|i. P i}"; |
165 goal Set.thy "{f i |i. P i | i=n} = insert (f n) {f i|i. P i}"; |
166 by (fast_tac eq_cs 1); |
166 by (Fast_tac 1); |
167 val Collect_conv_insert = result(); |
167 val Collect_conv_insert = result(); |
168 |
168 |
169 goalw Finite.thy [card_def] "card {} = 0"; |
169 goalw Finite.thy [card_def] "card {} = 0"; |
170 by (rtac Least_equality 1); |
170 by (rtac Least_equality 1); |
171 by (ALLGOALS Asm_full_simp_tac); |
171 by (ALLGOALS Asm_full_simp_tac); |
195 by (rename_tac "m" 1); |
195 by (rename_tac "m" 1); |
196 by (hyp_subst_tac 1); |
196 by (hyp_subst_tac 1); |
197 by (case_tac "? a. a:A" 1); |
197 by (case_tac "? a. a:A" 1); |
198 by (res_inst_tac [("x","0")] exI 2); |
198 by (res_inst_tac [("x","0")] exI 2); |
199 by (Simp_tac 2); |
199 by (Simp_tac 2); |
200 by (fast_tac eq_cs 2); |
200 by (Fast_tac 2); |
201 by (etac exE 1); |
201 by (etac exE 1); |
202 by (simp_tac (!simpset addsimps [less_Suc_eq]) 1); |
202 by (simp_tac (!simpset addsimps [less_Suc_eq]) 1); |
203 by (rtac exI 1); |
203 by (rtac exI 1); |
204 by (rtac conjI 1); |
204 by (rtac conjI 1); |
205 br disjI2 1; |
205 br disjI2 1; |
210 by (SELECT_GOAL(safe_tac eq_cs)1); |
210 by (SELECT_GOAL(safe_tac eq_cs)1); |
211 by (Asm_full_simp_tac 1); |
211 by (Asm_full_simp_tac 1); |
212 by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1); |
212 by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1); |
213 by (SELECT_GOAL(safe_tac eq_cs)1); |
213 by (SELECT_GOAL(safe_tac eq_cs)1); |
214 by (subgoal_tac "x ~= f m" 1); |
214 by (subgoal_tac "x ~= f m" 1); |
215 by (fast_tac set_cs 2); |
215 by (Fast_tac 2); |
216 by (subgoal_tac "? k. f k = x & k<m" 1); |
216 by (subgoal_tac "? k. f k = x & k<m" 1); |
217 by (best_tac set_cs 2); |
217 by (best_tac set_cs 2); |
218 by (SELECT_GOAL(safe_tac HOL_cs)1); |
218 by (SELECT_GOAL(safe_tac HOL_cs)1); |
219 by (res_inst_tac [("x","k")] exI 1); |
219 by (res_inst_tac [("x","k")] exI 1); |
220 by (Asm_simp_tac 1); |
220 by (Asm_simp_tac 1); |
224 by (rotate_tac ~1 1); |
224 by (rotate_tac ~1 1); |
225 by (Asm_full_simp_tac 1); |
225 by (Asm_full_simp_tac 1); |
226 by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1); |
226 by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1); |
227 by (SELECT_GOAL(safe_tac eq_cs)1); |
227 by (SELECT_GOAL(safe_tac eq_cs)1); |
228 by (subgoal_tac "x ~= f m" 1); |
228 by (subgoal_tac "x ~= f m" 1); |
229 by (fast_tac set_cs 2); |
229 by (Fast_tac 2); |
230 by (subgoal_tac "? k. f k = x & k<m" 1); |
230 by (subgoal_tac "? k. f k = x & k<m" 1); |
231 by (best_tac set_cs 2); |
231 by (best_tac set_cs 2); |
232 by (SELECT_GOAL(safe_tac HOL_cs)1); |
232 by (SELECT_GOAL(safe_tac HOL_cs)1); |
233 by (res_inst_tac [("x","k")] exI 1); |
233 by (res_inst_tac [("x","k")] exI 1); |
234 by (Asm_simp_tac 1); |
234 by (Asm_simp_tac 1); |
235 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
235 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
236 by (best_tac set_cs 1); |
236 by (best_tac set_cs 1); |
237 by (res_inst_tac [("x","%j. if f j = f i then f m else f j")] exI 1); |
237 by (res_inst_tac [("x","%j. if f j = f i then f m else f j")] exI 1); |
238 by (SELECT_GOAL(safe_tac eq_cs)1); |
238 by (SELECT_GOAL(safe_tac eq_cs)1); |
239 by (subgoal_tac "x ~= f i" 1); |
239 by (subgoal_tac "x ~= f i" 1); |
240 by (fast_tac set_cs 2); |
240 by (Fast_tac 2); |
241 by (case_tac "x = f m" 1); |
241 by (case_tac "x = f m" 1); |
242 by (res_inst_tac [("x","i")] exI 1); |
242 by (res_inst_tac [("x","i")] exI 1); |
243 by (Asm_simp_tac 1); |
243 by (Asm_simp_tac 1); |
244 by (subgoal_tac "? k. f k = x & k<m" 1); |
244 by (subgoal_tac "? k. f k = x & k<m" 1); |
245 by (best_tac set_cs 2); |
245 by (best_tac set_cs 2); |
303 by (dtac mk_disjoint_insert 1); |
303 by (dtac mk_disjoint_insert 1); |
304 by (etac exE 1); |
304 by (etac exE 1); |
305 by (Asm_simp_tac 1); |
305 by (Asm_simp_tac 1); |
306 by (rtac card_insert_disjoint 1); |
306 by (rtac card_insert_disjoint 1); |
307 by (rtac (major RSN (2,finite_subset)) 1); |
307 by (rtac (major RSN (2,finite_subset)) 1); |
308 by (fast_tac set_cs 1); |
308 by (Fast_tac 1); |
309 by (fast_tac HOL_cs 1); |
309 by (Fast_tac 1); |
310 by (asm_simp_tac (!simpset addsimps [major RS card_insert_disjoint]) 1); |
310 by (asm_simp_tac (!simpset addsimps [major RS card_insert_disjoint]) 1); |
311 qed "card_insert"; |
311 qed "card_insert"; |
312 Addsimps [card_insert]; |
312 Addsimps [card_insert]; |
313 |
313 |
314 |
314 |