src/HOL/Finite.ML
changeset 4830 bd73675adbed
parent 4775 66b1a7c42d94
child 5069 3ea049f7979d
equal deleted inserted replaced
4829:aa5ea943f8e3 4830:bd73675adbed
   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