125 Goal "finite(A-{}) = finite A"; |
125 Goal "finite(A-{}) = finite A"; |
126 by (Simp_tac 1); |
126 by (Simp_tac 1); |
127 val lemma = result(); |
127 val lemma = result(); |
128 |
128 |
129 (*Lemma for proving finite_imageD*) |
129 (*Lemma for proving finite_imageD*) |
130 Goal "finite B ==> ALL A. f``A = B --> inj_on f A --> finite A"; |
130 Goal "finite B ==> ALL A. f`A = B --> inj_on f A --> finite A"; |
131 by (etac finite_induct 1); |
131 by (etac finite_induct 1); |
132 by (ALLGOALS Asm_simp_tac); |
132 by (ALLGOALS Asm_simp_tac); |
133 by (Clarify_tac 1); |
133 by (Clarify_tac 1); |
134 by (subgoal_tac "EX y:A. f y = x & F = f``(A-{y})" 1); |
134 by (subgoal_tac "EX y:A. f y = x & F = f`(A-{y})" 1); |
135 by (Clarify_tac 1); |
135 by (Clarify_tac 1); |
136 by (full_simp_tac (simpset() addsimps [inj_on_def]) 1); |
136 by (full_simp_tac (simpset() addsimps [inj_on_def]) 1); |
137 by (blast_tac (claset() addSDs [lemma RS iffD1]) 1); |
137 by (blast_tac (claset() addSDs [lemma RS iffD1]) 1); |
138 by (thin_tac "ALL A. ?PP(A)" 1); |
138 by (thin_tac "ALL A. ?PP(A)" 1); |
139 by (forward_tac [[equalityD2, insertI1] MRS subsetD] 1); |
139 by (forward_tac [[equalityD2, insertI1] MRS subsetD] 1); |
141 by (res_inst_tac [("x","xa")] bexI 1); |
141 by (res_inst_tac [("x","xa")] bexI 1); |
142 by (ALLGOALS |
142 by (ALLGOALS |
143 (asm_full_simp_tac (simpset() addsimps [inj_on_image_set_diff]))); |
143 (asm_full_simp_tac (simpset() addsimps [inj_on_image_set_diff]))); |
144 val lemma = result(); |
144 val lemma = result(); |
145 |
145 |
146 Goal "[| finite(f``A); inj_on f A |] ==> finite A"; |
146 Goal "[| finite(f`A); inj_on f A |] ==> finite A"; |
147 by (dtac lemma 1); |
147 by (dtac lemma 1); |
148 by (Blast_tac 1); |
148 by (Blast_tac 1); |
149 qed "finite_imageD"; |
149 qed "finite_imageD"; |
150 |
150 |
151 (** The finite UNION of finite sets **) |
151 (** The finite UNION of finite sets **) |
193 qed "finite_unit"; |
193 qed "finite_unit"; |
194 |
194 |
195 (** The powerset of a finite set **) |
195 (** The powerset of a finite set **) |
196 |
196 |
197 Goal "finite(Pow A) ==> finite A"; |
197 Goal "finite(Pow A) ==> finite A"; |
198 by (subgoal_tac "finite ((%x.{x})``A)" 1); |
198 by (subgoal_tac "finite ((%x.{x})`A)" 1); |
199 by (rtac finite_subset 2); |
199 by (rtac finite_subset 2); |
200 by (assume_tac 3); |
200 by (assume_tac 3); |
201 by (ALLGOALS |
201 by (ALLGOALS |
202 (fast_tac (claset() addSDs [rewrite_rule [inj_on_def] finite_imageD]))); |
202 (fast_tac (claset() addSDs [rewrite_rule [inj_on_def] finite_imageD]))); |
203 val lemma = result(); |
203 val lemma = result(); |
212 (simpset() addsimps [finite_UnI, finite_imageI, Pow_insert]))); |
212 (simpset() addsimps [finite_UnI, finite_imageI, Pow_insert]))); |
213 qed "finite_Pow_iff"; |
213 qed "finite_Pow_iff"; |
214 AddIffs [finite_Pow_iff]; |
214 AddIffs [finite_Pow_iff]; |
215 |
215 |
216 Goal "finite(r^-1) = finite r"; |
216 Goal "finite(r^-1) = finite r"; |
217 by (subgoal_tac "r^-1 = (%(x,y).(y,x))``r" 1); |
217 by (subgoal_tac "r^-1 = (%(x,y).(y,x))`r" 1); |
218 by (Asm_simp_tac 1); |
218 by (Asm_simp_tac 1); |
219 by (rtac iffI 1); |
219 by (rtac iffI 1); |
220 by (etac (rewrite_rule [inj_on_def] finite_imageD) 1); |
220 by (etac (rewrite_rule [inj_on_def] finite_imageD) 1); |
221 by (simp_tac (simpset() addsplits [split_split]) 1); |
221 by (simp_tac (simpset() addsplits [split_split]) 1); |
222 by (etac finite_imageI 1); |
222 by (etac finite_imageI 1); |
465 by (Blast_tac 1); |
465 by (Blast_tac 1); |
466 qed "card_psubset"; |
466 qed "card_psubset"; |
467 |
467 |
468 (*** Cardinality of image ***) |
468 (*** Cardinality of image ***) |
469 |
469 |
470 Goal "finite A ==> card (f `` A) <= card A"; |
470 Goal "finite A ==> card (f ` A) <= card A"; |
471 by (etac finite_induct 1); |
471 by (etac finite_induct 1); |
472 by (Simp_tac 1); |
472 by (Simp_tac 1); |
473 by (asm_simp_tac (simpset() addsimps [le_SucI, finite_imageI, |
473 by (asm_simp_tac (simpset() addsimps [le_SucI, finite_imageI, |
474 card_insert_if]) 1); |
474 card_insert_if]) 1); |
475 qed "card_image_le"; |
475 qed "card_image_le"; |
476 |
476 |
477 Goal "finite(A) ==> inj_on f A --> card (f `` A) = card A"; |
477 Goal "finite(A) ==> inj_on f A --> card (f ` A) = card A"; |
478 by (etac finite_induct 1); |
478 by (etac finite_induct 1); |
479 by (ALLGOALS Asm_simp_tac); |
479 by (ALLGOALS Asm_simp_tac); |
480 by Safe_tac; |
480 by Safe_tac; |
481 by (rewtac inj_on_def); |
481 by (rewtac inj_on_def); |
482 by (Blast_tac 1); |
482 by (Blast_tac 1); |
484 by (etac finite_imageI 1); |
484 by (etac finite_imageI 1); |
485 by (Blast_tac 1); |
485 by (Blast_tac 1); |
486 by (Blast_tac 1); |
486 by (Blast_tac 1); |
487 qed_spec_mp "card_image"; |
487 qed_spec_mp "card_image"; |
488 |
488 |
489 Goal "[| finite A; f``A <= A; inj_on f A |] ==> f``A = A"; |
489 Goal "[| finite A; f`A <= A; inj_on f A |] ==> f`A = A"; |
490 by (asm_simp_tac (simpset() addsimps [card_seteq, card_image]) 1); |
490 by (asm_simp_tac (simpset() addsimps [card_seteq, card_image]) 1); |
491 qed "endo_inj_surj"; |
491 qed "endo_inj_surj"; |
492 |
492 |
493 (*** Cardinality of the Powerset ***) |
493 (*** Cardinality of the Powerset ***) |
494 |
494 |
851 by Auto_tac; |
851 by Auto_tac; |
852 by (etac rev_mp 1 THEN stac card_Diff_singleton 1); |
852 by (etac rev_mp 1 THEN stac card_Diff_singleton 1); |
853 by (auto_tac (claset() addIs [finite_subset], simpset())); |
853 by (auto_tac (claset() addIs [finite_subset], simpset())); |
854 qed "choose_deconstruct"; |
854 qed "choose_deconstruct"; |
855 |
855 |
856 Goal "[| finite(A); finite(B); f``A <= B; inj_on f A |] \ |
856 Goal "[| finite(A); finite(B); f`A <= B; inj_on f A |] \ |
857 \ ==> card A <= card B"; |
857 \ ==> card A <= card B"; |
858 by (auto_tac (claset() addIs [card_mono], |
858 by (auto_tac (claset() addIs [card_mono], |
859 simpset() addsimps [card_image RS sym])); |
859 simpset() addsimps [card_image RS sym])); |
860 qed "card_inj_on_le"; |
860 qed "card_inj_on_le"; |
861 |
861 |
862 Goal "[| finite A; finite B; \ |
862 Goal "[| finite A; finite B; \ |
863 \ f``A <= B; inj_on f A; g``B <= A; inj_on g B |] \ |
863 \ f`A <= B; inj_on f A; g`B <= A; inj_on g B |] \ |
864 \ ==> card(A) = card(B)"; |
864 \ ==> card(A) = card(B)"; |
865 by (auto_tac (claset() addIs [le_anti_sym,card_inj_on_le], simpset())); |
865 by (auto_tac (claset() addIs [le_anti_sym,card_inj_on_le], simpset())); |
866 qed "card_bij_eq"; |
866 qed "card_bij_eq"; |
867 |
867 |
868 Goal "[| finite A; x ~: A |] \ |
868 Goal "[| finite A; x ~: A |] \ |