src/HOL/Finite.ML
changeset 3708 56facaebf3e3
parent 3517 2547f33fa33a
child 3724 f33e301a89f5
equal deleted inserted replaced
3707:40856b593501 3708:56facaebf3e3
   129 AddIffs [finite_Diff_singleton];
   129 AddIffs [finite_Diff_singleton];
   130 
   130 
   131 goal Finite.thy "!!A. finite B ==> !A. f``A = B --> inj_onto f A --> finite A";
   131 goal Finite.thy "!!A. finite B ==> !A. f``A = B --> inj_onto f A --> finite A";
   132 by (etac finite_induct 1);
   132 by (etac finite_induct 1);
   133  by (ALLGOALS Asm_simp_tac);
   133  by (ALLGOALS Asm_simp_tac);
   134 by (Step_tac 1);
   134 by (Clarify_tac 1);
   135 by (subgoal_tac "EX y:A. f y = x & F = f``(A-{y})" 1);
   135 by (subgoal_tac "EX y:A. f y = x & F = f``(A-{y})" 1);
   136  by (Step_tac 1);
   136  by (Clarify_tac 1);
   137  by (rewtac inj_onto_def);
   137  by (rewtac inj_onto_def);
   138  by (Blast_tac 1);
   138  by (Blast_tac 1);
   139 by (thin_tac "ALL A. ?PP(A)" 1);
   139 by (thin_tac "ALL A. ?PP(A)" 1);
   140 by (forward_tac [[equalityD2, insertI1] MRS subsetD] 1);
   140 by (forward_tac [[equalityD2, insertI1] MRS subsetD] 1);
   141 by (Step_tac 1);
   141 by (Clarify_tac 1);
   142 by (res_inst_tac [("x","xa")] bexI 1);
   142 by (res_inst_tac [("x","xa")] bexI 1);
   143 by (ALLGOALS Asm_simp_tac);
   143 by (ALLGOALS Asm_simp_tac);
   144 by (etac equalityE 1);
   144 by (blast_tac (!claset addEs [equalityE]) 1);
   145 by (rtac equalityI 1);
       
   146 by (Blast_tac 2);
       
   147 by (Best_tac 1);
       
   148 val lemma = result();
   145 val lemma = result();
   149 
   146 
   150 goal Finite.thy "!!A. [| finite(f``A);  inj_onto f A |] ==> finite A";
   147 goal Finite.thy "!!A. [| finite(f``A);  inj_onto f A |] ==> finite A";
   151 by (dtac lemma 1);
   148 by (dtac lemma 1);
   152 by (Blast_tac 1);
   149 by (Blast_tac 1);
   316 Addsimps [card_insert_disjoint];
   313 Addsimps [card_insert_disjoint];
   317 
   314 
   318 goal Finite.thy  "!!A. finite A ==> !B. B <= A --> card(B) <= card(A)";
   315 goal Finite.thy  "!!A. finite A ==> !B. B <= A --> card(B) <= card(A)";
   319 by (etac finite_induct 1);
   316 by (etac finite_induct 1);
   320 by (Simp_tac 1);
   317 by (Simp_tac 1);
   321 by (strip_tac 1);
   318 by (Clarify_tac 1);
   322 by (case_tac "x:B" 1);
   319 by (case_tac "x:B" 1);
   323  by (dres_inst_tac [("A","B")] mk_disjoint_insert 1);
   320  by (dres_inst_tac [("A","B")] mk_disjoint_insert 1);
   324  by (SELECT_GOAL(safe_tac (!claset))1);
   321  by (SELECT_GOAL(safe_tac (!claset))1);
   325  by (rotate_tac ~1 1);
   322  by (rotate_tac ~1 1);
   326  by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   323  by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   407 goalw Finite.thy [psubset_def]
   404 goalw Finite.thy [psubset_def]
   408 "!!B. finite B ==> !A. A < B --> card(A) < card(B)";
   405 "!!B. finite B ==> !A. A < B --> card(A) < card(B)";
   409 by (etac finite_induct 1);
   406 by (etac finite_induct 1);
   410 by (Simp_tac 1);
   407 by (Simp_tac 1);
   411 by (Blast_tac 1);
   408 by (Blast_tac 1);
   412 by (strip_tac 1);
   409 by (Clarify_tac 1);
   413 by (etac conjE 1);
       
   414 by (case_tac "x:A" 1);
   410 by (case_tac "x:A" 1);
   415 (*1*)
   411 (*1*)
   416 by (dres_inst_tac [("A","A")]mk_disjoint_insert 1);
   412 by (dres_inst_tac [("A","A")]mk_disjoint_insert 1);
   417 by (etac exE 1);
   413 by (etac exE 1);
   418 by (etac conjE 1);
   414 by (etac conjE 1);
   419 by (hyp_subst_tac 1);
   415 by (hyp_subst_tac 1);
   420 by (rotate_tac ~1 1);
   416 by (rotate_tac ~1 1);
   421 by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   417 by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   422 by (dtac insert_lim 1);
   418 by (Blast_tac 1);
   423 by (Asm_full_simp_tac 1);
       
   424 (*2*)
   419 (*2*)
   425 by (rotate_tac ~1 1);
   420 by (rotate_tac ~1 1);
       
   421 by (eres_inst_tac [("P","?a<?b")] notE 1);
   426 by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   422 by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   427 by (case_tac "A=F" 1);
   423 by (case_tac "A=F" 1);
   428 by (Asm_simp_tac 1);
   424 by (ALLGOALS Asm_simp_tac);
   429 by (Asm_simp_tac 1);
       
   430 qed_spec_mp "psubset_card" ;
   425 qed_spec_mp "psubset_card" ;
   431 
   426 
   432 
   427 
   433 (*Relates to equivalence classes.   Based on a theorem of F. Kammueller's.
   428 (*Relates to equivalence classes.   Based on a theorem of F. Kammueller's.
   434   The "finite C" premise is redundant*)
   429   The "finite C" premise is redundant*)
   436 \          (! c : C. k dvd card c) -->  \
   431 \          (! c : C. k dvd card c) -->  \
   437 \          (! c1: C. ! c2: C. c1 ~= c2 --> c1 Int c2 = {}) \
   432 \          (! c1: C. ! c2: C. c1 ~= c2 --> c1 Int c2 = {}) \
   438 \          --> k dvd card(Union C)";
   433 \          --> k dvd card(Union C)";
   439 by (etac finite_induct 1);
   434 by (etac finite_induct 1);
   440 by (ALLGOALS Asm_simp_tac);
   435 by (ALLGOALS Asm_simp_tac);
   441 by (strip_tac 1);
   436 by (Clarify_tac 1);
   442 by (REPEAT (etac conjE 1));
       
   443 by (stac card_Un_disjoint 1);
   437 by (stac card_Un_disjoint 1);
   444 by (ALLGOALS
   438 by (ALLGOALS
   445     (asm_full_simp_tac (!simpset
   439     (asm_full_simp_tac (!simpset
   446 			 addsimps [dvd_add, disjoint_eq_subset_Compl])));
   440 			 addsimps [dvd_add, disjoint_eq_subset_Compl])));
   447 by (thin_tac "?PP-->?QQ" 1);
       
   448 by (thin_tac "!c:F. ?PP(c)" 1);
   441 by (thin_tac "!c:F. ?PP(c)" 1);
   449 by (thin_tac "!c:F. ?PP(c) & ?QQ(c)" 1);
   442 by (thin_tac "!c:F. ?PP(c) & ?QQ(c)" 1);
   450 by (Step_tac 1);
   443 by (Clarify_tac 1);
   451 by (ball_tac 1);
   444 by (ball_tac 1);
   452 by (Blast_tac 1);
   445 by (Blast_tac 1);
   453 qed_spec_mp "dvd_partition";
   446 qed_spec_mp "dvd_partition";
   454 
   447