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 |