equal
deleted
inserted
replaced
142 Addsimps [finite_UnionI]; |
142 Addsimps [finite_UnionI]; |
143 |
143 |
144 (** Sigma of finite sets **) |
144 (** Sigma of finite sets **) |
145 |
145 |
146 Goalw [Sigma_def] |
146 Goalw [Sigma_def] |
147 "!!A. [| finite A; !a:A. finite(B a) |] ==> finite(SIGMA a:A. B a)"; |
147 "[| finite A; !a:A. finite(B a) |] ==> finite(SIGMA a:A. B a)"; |
148 by (blast_tac (claset() addSIs [finite_UnionI]) 1); |
148 by (blast_tac (claset() addSIs [finite_UnionI]) 1); |
149 bind_thm("finite_SigmaI", ballI RSN (2,result())); |
149 bind_thm("finite_SigmaI", ballI RSN (2,result())); |
150 Addsimps [finite_SigmaI]; |
150 Addsimps [finite_SigmaI]; |
151 |
151 |
152 (** The powerset of a finite set **) |
152 (** The powerset of a finite set **) |
210 by (asm_simp_tac (simpset() addsimps [Collect_conv_insert, less_Suc_eq] |
210 by (asm_simp_tac (simpset() addsimps [Collect_conv_insert, less_Suc_eq] |
211 addcongs [rev_conj_cong]) 1); |
211 addcongs [rev_conj_cong]) 1); |
212 qed "finite_has_card"; |
212 qed "finite_has_card"; |
213 |
213 |
214 Goal |
214 Goal |
215 "!!A.[| x ~: A; insert x A = {f i|i. i<n} |] ==> \ |
215 "[| x ~: A; insert x A = {f i|i. i<n} |] ==> \ |
216 \ ? m::nat. m<n & (? g. A = {g i|i. i<m})"; |
216 \ ? m::nat. m<n & (? g. A = {g i|i. i<m})"; |
217 by (res_inst_tac [("n","n")] natE 1); |
217 by (res_inst_tac [("n","n")] natE 1); |
218 by (hyp_subst_tac 1); |
218 by (hyp_subst_tac 1); |
219 by (Asm_full_simp_tac 1); |
219 by (Asm_full_simp_tac 1); |
220 by (rename_tac "m" 1); |
220 by (rename_tac "m" 1); |
301 by (hyp_subst_tac 1); |
301 by (hyp_subst_tac 1); |
302 by (Asm_full_simp_tac 1); |
302 by (Asm_full_simp_tac 1); |
303 val lemma = result(); |
303 val lemma = result(); |
304 |
304 |
305 Goalw [card_def] |
305 Goalw [card_def] |
306 "!!A. [| finite A; x ~: A |] ==> card(insert x A) = Suc(card A)"; |
306 "[| finite A; x ~: A |] ==> card(insert x A) = Suc(card A)"; |
307 by (etac lemma 1); |
307 by (etac lemma 1); |
308 by (assume_tac 1); |
308 by (assume_tac 1); |
309 qed "card_insert_disjoint"; |
309 qed "card_insert_disjoint"; |
310 Addsimps [card_insert_disjoint]; |
310 Addsimps [card_insert_disjoint]; |
311 |
311 |
394 qed "card_Pow"; |
394 qed "card_Pow"; |
395 Addsimps [card_Pow]; |
395 Addsimps [card_Pow]; |
396 |
396 |
397 |
397 |
398 (*Proper subsets*) |
398 (*Proper subsets*) |
399 Goalw [psubset_def] |
399 Goalw [psubset_def] "finite B ==> !A. A < B --> card(A) < card(B)"; |
400 "!!B. finite B ==> !A. A < B --> card(A) < card(B)"; |
|
401 by (etac finite_induct 1); |
400 by (etac finite_induct 1); |
402 by (Simp_tac 1); |
401 by (Simp_tac 1); |
403 by (Clarify_tac 1); |
402 by (Clarify_tac 1); |
404 by (case_tac "x:A" 1); |
403 by (case_tac "x:A" 1); |
405 (*1*) |
404 (*1*) |