109 by (ALLGOALS Asm_simp_tac); |
109 by (ALLGOALS Asm_simp_tac); |
110 qed "finite_Diff_singleton"; |
110 qed "finite_Diff_singleton"; |
111 AddIffs [finite_Diff_singleton]; |
111 AddIffs [finite_Diff_singleton]; |
112 |
112 |
113 (*Lemma for proving finite_imageD*) |
113 (*Lemma for proving finite_imageD*) |
114 goal Finite.thy "!!A. finite B ==> !A. f``A = B --> inj_onto f A --> finite A"; |
114 goal Finite.thy "!!A. finite B ==> !A. f``A = B --> inj_on f A --> finite A"; |
115 by (etac finite_induct 1); |
115 by (etac finite_induct 1); |
116 by (ALLGOALS Asm_simp_tac); |
116 by (ALLGOALS Asm_simp_tac); |
117 by (Clarify_tac 1); |
117 by (Clarify_tac 1); |
118 by (subgoal_tac "EX y:A. f y = x & F = f``(A-{y})" 1); |
118 by (subgoal_tac "EX y:A. f y = x & F = f``(A-{y})" 1); |
119 by (Clarify_tac 1); |
119 by (Clarify_tac 1); |
120 by (full_simp_tac (simpset() addsimps [inj_onto_def]) 1); |
120 by (full_simp_tac (simpset() addsimps [inj_on_def]) 1); |
121 by (Blast_tac 1); |
121 by (Blast_tac 1); |
122 by (thin_tac "ALL A. ?PP(A)" 1); |
122 by (thin_tac "ALL A. ?PP(A)" 1); |
123 by (forward_tac [[equalityD2, insertI1] MRS subsetD] 1); |
123 by (forward_tac [[equalityD2, insertI1] MRS subsetD] 1); |
124 by (Clarify_tac 1); |
124 by (Clarify_tac 1); |
125 by (res_inst_tac [("x","xa")] bexI 1); |
125 by (res_inst_tac [("x","xa")] bexI 1); |
126 by (ALLGOALS |
126 by (ALLGOALS |
127 (asm_full_simp_tac (simpset() addsimps [inj_onto_image_set_diff]))); |
127 (asm_full_simp_tac (simpset() addsimps [inj_on_image_set_diff]))); |
128 val lemma = result(); |
128 val lemma = result(); |
129 |
129 |
130 goal Finite.thy "!!A. [| finite(f``A); inj_onto f A |] ==> finite A"; |
130 goal Finite.thy "!!A. [| finite(f``A); inj_on f A |] ==> finite A"; |
131 by (dtac lemma 1); |
131 by (dtac lemma 1); |
132 by (Blast_tac 1); |
132 by (Blast_tac 1); |
133 qed "finite_imageD"; |
133 qed "finite_imageD"; |
134 |
134 |
135 (** The finite UNION of finite sets **) |
135 (** The finite UNION of finite sets **) |
154 goal Finite.thy "!!A. finite(Pow A) ==> finite A"; |
154 goal Finite.thy "!!A. finite(Pow A) ==> finite A"; |
155 by (subgoal_tac "finite ((%x.{x})``A)" 1); |
155 by (subgoal_tac "finite ((%x.{x})``A)" 1); |
156 by (rtac finite_subset 2); |
156 by (rtac finite_subset 2); |
157 by (assume_tac 3); |
157 by (assume_tac 3); |
158 by (ALLGOALS |
158 by (ALLGOALS |
159 (fast_tac (claset() addSDs [rewrite_rule [inj_onto_def] finite_imageD]))); |
159 (fast_tac (claset() addSDs [rewrite_rule [inj_on_def] finite_imageD]))); |
160 val lemma = result(); |
160 val lemma = result(); |
161 |
161 |
162 goal Finite.thy "finite(Pow A) = finite A"; |
162 goal Finite.thy "finite(Pow A) = finite A"; |
163 by (rtac iffI 1); |
163 by (rtac iffI 1); |
164 by (etac lemma 1); |
164 by (etac lemma 1); |
172 |
172 |
173 goal Finite.thy "finite(r^-1) = finite r"; |
173 goal Finite.thy "finite(r^-1) = finite r"; |
174 by (subgoal_tac "r^-1 = (%(x,y).(y,x))``r" 1); |
174 by (subgoal_tac "r^-1 = (%(x,y).(y,x))``r" 1); |
175 by (Asm_simp_tac 1); |
175 by (Asm_simp_tac 1); |
176 by (rtac iffI 1); |
176 by (rtac iffI 1); |
177 by (etac (rewrite_rule [inj_onto_def] finite_imageD) 1); |
177 by (etac (rewrite_rule [inj_on_def] finite_imageD) 1); |
178 by (simp_tac (simpset() addsplits [expand_split]) 1); |
178 by (simp_tac (simpset() addsplits [split_split]) 1); |
179 by (etac finite_imageI 1); |
179 by (etac finite_imageI 1); |
180 by (simp_tac (simpset() addsimps [converse_def,image_def]) 1); |
180 by (simp_tac (simpset() addsimps [converse_def,image_def]) 1); |
181 by Auto_tac; |
181 by Auto_tac; |
182 by (rtac bexI 1); |
182 by (rtac bexI 1); |
183 by (assume_tac 2); |
183 by (assume_tac 2); |
368 by (ALLGOALS |
368 by (ALLGOALS |
369 (asm_simp_tac (simpset() addsimps [card_Suc_Diff, insert_absorb]))); |
369 (asm_simp_tac (simpset() addsimps [card_Suc_Diff, insert_absorb]))); |
370 qed "card_insert"; |
370 qed "card_insert"; |
371 Addsimps [card_insert]; |
371 Addsimps [card_insert]; |
372 |
372 |
373 goal Finite.thy "!!A. finite(A) ==> inj_onto f A --> card (f `` A) = card A"; |
373 goal Finite.thy "!!A. finite(A) ==> inj_on f A --> card (f `` A) = card A"; |
374 by (etac finite_induct 1); |
374 by (etac finite_induct 1); |
375 by (ALLGOALS Asm_simp_tac); |
375 by (ALLGOALS Asm_simp_tac); |
376 by Safe_tac; |
376 by Safe_tac; |
377 by (rewtac inj_onto_def); |
377 by (rewtac inj_on_def); |
378 by (Blast_tac 1); |
378 by (Blast_tac 1); |
379 by (stac card_insert_disjoint 1); |
379 by (stac card_insert_disjoint 1); |
380 by (etac finite_imageI 1); |
380 by (etac finite_imageI 1); |
381 by (Blast_tac 1); |
381 by (Blast_tac 1); |
382 by (Blast_tac 1); |
382 by (Blast_tac 1); |
385 goal thy "!!A. finite A ==> card (Pow A) = 2 ^ card A"; |
385 goal thy "!!A. finite A ==> card (Pow A) = 2 ^ card A"; |
386 by (etac finite_induct 1); |
386 by (etac finite_induct 1); |
387 by (ALLGOALS (asm_simp_tac (simpset() addsimps [Pow_insert]))); |
387 by (ALLGOALS (asm_simp_tac (simpset() addsimps [Pow_insert]))); |
388 by (stac card_Un_disjoint 1); |
388 by (stac card_Un_disjoint 1); |
389 by (EVERY (map (blast_tac (claset() addIs [finite_imageI])) [3,2,1])); |
389 by (EVERY (map (blast_tac (claset() addIs [finite_imageI])) [3,2,1])); |
390 by (subgoal_tac "inj_onto (insert x) (Pow F)" 1); |
390 by (subgoal_tac "inj_on (insert x) (Pow F)" 1); |
391 by (asm_simp_tac (simpset() addsimps [card_image, Pow_insert]) 1); |
391 by (asm_simp_tac (simpset() addsimps [card_image, Pow_insert]) 1); |
392 by (rewtac inj_onto_def); |
392 by (rewtac inj_on_def); |
393 by (blast_tac (claset() addSEs [equalityE]) 1); |
393 by (blast_tac (claset() addSEs [equalityE]) 1); |
394 qed "card_Pow"; |
394 qed "card_Pow"; |
395 Addsimps [card_Pow]; |
395 Addsimps [card_Pow]; |
396 |
396 |
397 |
397 |