src/HOL/Finite.ML
changeset 5148 74919e8f221c
parent 5143 b94cd208f073
child 5183 89f162de39cf
equal deleted inserted replaced
5147:825877190618 5148:74919e8f221c
   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*)