src/HOL/Finite.ML
changeset 1786 8a31d85d27b8
parent 1782 ab45b881fa62
child 2031 03a843f0f447
equal deleted inserted replaced
1785:0a2414dd696b 1786:8a31d85d27b8
    47 by (EVERY1 [subgoal_tac "ALL C. C<=B --> C: Fin(M)",
    47 by (EVERY1 [subgoal_tac "ALL C. C<=B --> C: Fin(M)",
    48             rtac mp, etac spec,
    48             rtac mp, etac spec,
    49             rtac subs]);
    49             rtac subs]);
    50 by (rtac (fin RS Fin_induct) 1);
    50 by (rtac (fin RS Fin_induct) 1);
    51 by (simp_tac (!simpset addsimps [subset_Un_eq]) 1);
    51 by (simp_tac (!simpset addsimps [subset_Un_eq]) 1);
    52 by (safe_tac (set_cs addSDs [subset_insert_iff RS iffD1]));
    52 by (safe_tac (!claset addSDs [subset_insert_iff RS iffD1]));
    53 by (eres_inst_tac [("t","C")] (insert_Diff RS subst) 2);
    53 by (eres_inst_tac [("t","C")] (insert_Diff RS subst) 2);
    54 by (ALLGOALS Asm_simp_tac);
    54 by (ALLGOALS Asm_simp_tac);
    55 qed "Fin_subset";
    55 qed "Fin_subset";
    56 
    56 
    57 goal Finite.thy "(F Un G : Fin(A)) = (F: Fin(A) & G: Fin(A))";
    57 goal Finite.thy "(F Un G : Fin(A)) = (F: Fin(A) & G: Fin(A))";
   203 by (rtac exI 1);
   203 by (rtac exI 1);
   204 by (rtac (refl RS disjI2 RS conjI) 1);
   204 by (rtac (refl RS disjI2 RS conjI) 1);
   205 by (etac equalityE 1);
   205 by (etac equalityE 1);
   206 by (asm_full_simp_tac
   206 by (asm_full_simp_tac
   207      (!simpset addsimps [subset_insert,Collect_conv_insert, less_Suc_eq]) 1);
   207      (!simpset addsimps [subset_insert,Collect_conv_insert, less_Suc_eq]) 1);
   208 by (SELECT_GOAL(safe_tac eq_cs)1);
   208 by (SELECT_GOAL(safe_tac (!claset))1);
   209   by (Asm_full_simp_tac 1);
   209   by (Asm_full_simp_tac 1);
   210   by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   210   by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   211   by (SELECT_GOAL(safe_tac eq_cs)1);
   211   by (SELECT_GOAL(safe_tac (!claset))1);
   212    by (subgoal_tac "x ~= f m" 1);
   212    by (subgoal_tac "x ~= f m" 1);
   213     by (Fast_tac 2);
   213     by (Fast_tac 2);
   214    by (subgoal_tac "? k. f k = x & k<m" 1);
   214    by (subgoal_tac "? k. f k = x & k<m" 1);
   215     by (best_tac set_cs 2);
   215     by (best_tac (!claset) 2);
   216    by (SELECT_GOAL(safe_tac HOL_cs)1);
   216    by (SELECT_GOAL(safe_tac (!claset))1);
   217    by (res_inst_tac [("x","k")] exI 1);
   217    by (res_inst_tac [("x","k")] exI 1);
   218    by (Asm_simp_tac 1);
   218    by (Asm_simp_tac 1);
   219   by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   219   by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   220   by (best_tac set_cs 1);
   220   by (best_tac (!claset) 1);
   221  bd sym 1;
   221  bd sym 1;
   222  by (rotate_tac ~1 1);
   222  by (rotate_tac ~1 1);
   223  by (Asm_full_simp_tac 1);
   223  by (Asm_full_simp_tac 1);
   224  by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   224  by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   225  by (SELECT_GOAL(safe_tac eq_cs)1);
   225  by (SELECT_GOAL(safe_tac (!claset))1);
   226   by (subgoal_tac "x ~= f m" 1);
   226   by (subgoal_tac "x ~= f m" 1);
   227    by (Fast_tac 2);
   227    by (Fast_tac 2);
   228   by (subgoal_tac "? k. f k = x & k<m" 1);
   228   by (subgoal_tac "? k. f k = x & k<m" 1);
   229    by (best_tac set_cs 2);
   229    by (best_tac (!claset) 2);
   230   by (SELECT_GOAL(safe_tac HOL_cs)1);
   230   by (SELECT_GOAL(safe_tac (!claset))1);
   231   by (res_inst_tac [("x","k")] exI 1);
   231   by (res_inst_tac [("x","k")] exI 1);
   232   by (Asm_simp_tac 1);
   232   by (Asm_simp_tac 1);
   233  by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   233  by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   234  by (best_tac set_cs 1);
   234  by (best_tac (!claset) 1);
   235 by (res_inst_tac [("x","%j. if f j = f i then f m else f j")] exI 1);
   235 by (res_inst_tac [("x","%j. if f j = f i then f m else f j")] exI 1);
   236 by (SELECT_GOAL(safe_tac eq_cs)1);
   236 by (SELECT_GOAL(safe_tac (!claset))1);
   237  by (subgoal_tac "x ~= f i" 1);
   237  by (subgoal_tac "x ~= f i" 1);
   238   by (Fast_tac 2);
   238   by (Fast_tac 2);
   239  by (case_tac "x = f m" 1);
   239  by (case_tac "x = f m" 1);
   240   by (res_inst_tac [("x","i")] exI 1);
   240   by (res_inst_tac [("x","i")] exI 1);
   241   by (Asm_simp_tac 1);
   241   by (Asm_simp_tac 1);
   242  by (subgoal_tac "? k. f k = x & k<m" 1);
   242  by (subgoal_tac "? k. f k = x & k<m" 1);
   243   by (best_tac set_cs 2);
   243   by (best_tac (!claset) 2);
   244  by (SELECT_GOAL(safe_tac HOL_cs)1);
   244  by (SELECT_GOAL(safe_tac (!claset))1);
   245  by (res_inst_tac [("x","k")] exI 1);
   245  by (res_inst_tac [("x","k")] exI 1);
   246  by (Asm_simp_tac 1);
   246  by (Asm_simp_tac 1);
   247 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   247 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   248 by (best_tac set_cs 1);
   248 by (best_tac (!claset) 1);
   249 val lemma = result();
   249 val lemma = result();
   250 
   250 
   251 goal Finite.thy "!!A. [| finite A; x ~: A |] ==> \
   251 goal Finite.thy "!!A. [| finite A; x ~: A |] ==> \
   252 \ (LEAST n. ? f. insert x A = {f i|i.i<n}) = Suc(LEAST n. ? f. A={f i|i.i<n})";
   252 \ (LEAST n. ? f. insert x A = {f i|i.i<n}) = Suc(LEAST n. ? f. A={f i|i.i<n})";
   253 by (rtac Least_equality 1);
   253 by (rtac Least_equality 1);
   314 by (etac finite_induct 1);
   314 by (etac finite_induct 1);
   315 by (Simp_tac 1);
   315 by (Simp_tac 1);
   316 by (strip_tac 1);
   316 by (strip_tac 1);
   317 by (case_tac "x:B" 1);
   317 by (case_tac "x:B" 1);
   318  by (dtac mk_disjoint_insert 1);
   318  by (dtac mk_disjoint_insert 1);
   319  by (SELECT_GOAL(safe_tac HOL_cs)1);
   319  by (SELECT_GOAL(safe_tac (!claset))1);
   320  by (rotate_tac ~1 1);
   320  by (rotate_tac ~1 1);
   321  by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   321  by (asm_full_simp_tac (!simpset addsimps [subset_insert_iff,finite_subset]) 1);
   322 by (rotate_tac ~1 1);
   322 by (rotate_tac ~1 1);
   323 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);
   324 qed_spec_mp "card_mono";
   324 qed_spec_mp "card_mono";