src/HOL/Finite.ML
changeset 10832 e33b47e4246d
parent 10785 53547a02f2a1
child 11092 69c1abb9a129
equal deleted inserted replaced
10831:024bdf8e52a4 10832:e33b47e4246d
    72 by (Blast_tac 1);
    72 by (Blast_tac 1);
    73 qed "finite_insert";
    73 qed "finite_insert";
    74 Addsimps[finite_insert];
    74 Addsimps[finite_insert];
    75 
    75 
    76 (*The image of a finite set is finite *)
    76 (*The image of a finite set is finite *)
    77 Goal  "finite F ==> finite(h``F)";
    77 Goal  "finite F ==> finite(h`F)";
    78 by (etac finite_induct 1);
    78 by (etac finite_induct 1);
    79 by (Simp_tac 1);
    79 by (Simp_tac 1);
    80 by (Asm_simp_tac 1);
    80 by (Asm_simp_tac 1);
    81 qed "finite_imageI";
    81 qed "finite_imageI";
    82 
    82 
   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 |]  \