src/HOL/Finite.ML
changeset 1760 6f41a494f3b1
parent 1660 8cb42cd97579
child 1782 ab45b881fa62
equal deleted inserted replaced
1759:a42d6c537f4a 1760:6f41a494f3b1
    14 by (rtac lfp_mono 1);
    14 by (rtac lfp_mono 1);
    15 by (REPEAT (ares_tac basic_monos 1));
    15 by (REPEAT (ares_tac basic_monos 1));
    16 qed "Fin_mono";
    16 qed "Fin_mono";
    17 
    17 
    18 goalw Finite.thy Fin.defs "Fin(A) <= Pow(A)";
    18 goalw Finite.thy Fin.defs "Fin(A) <= Pow(A)";
    19 by (fast_tac (set_cs addSIs [lfp_lowerbound]) 1);
    19 by (fast_tac (!claset addSIs [lfp_lowerbound]) 1);
    20 qed "Fin_subset_Pow";
    20 qed "Fin_subset_Pow";
    21 
    21 
    22 (* A : Fin(B) ==> A <= B *)
    22 (* A : Fin(B) ==> A <= B *)
    23 val FinD = Fin_subset_Pow RS subsetD RS PowD;
    23 val FinD = Fin_subset_Pow RS subsetD RS PowD;
    24 
    24 
    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))";
    58 by (fast_tac (set_cs addIs [Fin_UnI] addDs
    58 by (fast_tac (!claset addIs [Fin_UnI] addDs
    59                 [Un_upper1 RS Fin_subset, Un_upper2 RS Fin_subset]) 1);
    59                 [Un_upper1 RS Fin_subset, Un_upper2 RS Fin_subset]) 1);
    60 qed "subset_Fin";
    60 qed "subset_Fin";
    61 Addsimps[subset_Fin];
    61 Addsimps[subset_Fin];
    62 
    62 
    63 goal Finite.thy "(insert a A : Fin M) = (a:M & A : Fin M)";
    63 goal Finite.thy "(insert a A : Fin M) = (a:M & A : Fin M)";
    64 by (stac insert_is_Un 1);
    64 by (stac insert_is_Un 1);
    65 by (Simp_tac 1);
    65 by (Simp_tac 1);
    66 by (fast_tac (set_cs addSIs Fin.intrs addDs [FinD]) 1);
    66 by (fast_tac (!claset addSIs Fin.intrs addDs [FinD]) 1);
    67 qed "insert_Fin";
    67 qed "insert_Fin";
    68 Addsimps[insert_Fin];
    68 Addsimps[insert_Fin];
    69 
    69 
    70 (*The image of a finite set is finite*)
    70 (*The image of a finite set is finite*)
    71 val major::_ = goal Finite.thy
    71 val major::_ = goal Finite.thy
   161 
   161 
   162 
   162 
   163 section "Finite cardinality -- 'card'";
   163 section "Finite cardinality -- 'card'";
   164 
   164 
   165 goal Set.thy "{f i |i. P i | i=n} = insert (f n) {f i|i. P i}";
   165 goal Set.thy "{f i |i. P i | i=n} = insert (f n) {f i|i. P i}";
   166 by (fast_tac eq_cs 1);
   166 by (Fast_tac 1);
   167 val Collect_conv_insert = result();
   167 val Collect_conv_insert = result();
   168 
   168 
   169 goalw Finite.thy [card_def] "card {} = 0";
   169 goalw Finite.thy [card_def] "card {} = 0";
   170 by (rtac Least_equality 1);
   170 by (rtac Least_equality 1);
   171 by (ALLGOALS Asm_full_simp_tac);
   171 by (ALLGOALS Asm_full_simp_tac);
   195 by (rename_tac "m" 1);
   195 by (rename_tac "m" 1);
   196 by (hyp_subst_tac 1);
   196 by (hyp_subst_tac 1);
   197 by (case_tac "? a. a:A" 1);
   197 by (case_tac "? a. a:A" 1);
   198  by (res_inst_tac [("x","0")] exI 2);
   198  by (res_inst_tac [("x","0")] exI 2);
   199  by (Simp_tac 2);
   199  by (Simp_tac 2);
   200  by (fast_tac eq_cs 2);
   200  by (Fast_tac 2);
   201 by (etac exE 1);
   201 by (etac exE 1);
   202 by (simp_tac (!simpset addsimps [less_Suc_eq]) 1);
   202 by (simp_tac (!simpset addsimps [less_Suc_eq]) 1);
   203 by (rtac exI 1);
   203 by (rtac exI 1);
   204 by (rtac conjI 1);
   204 by (rtac conjI 1);
   205  br disjI2 1;
   205  br disjI2 1;
   210 by (SELECT_GOAL(safe_tac eq_cs)1);
   210 by (SELECT_GOAL(safe_tac eq_cs)1);
   211   by (Asm_full_simp_tac 1);
   211   by (Asm_full_simp_tac 1);
   212   by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   212   by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   213   by (SELECT_GOAL(safe_tac eq_cs)1);
   213   by (SELECT_GOAL(safe_tac eq_cs)1);
   214    by (subgoal_tac "x ~= f m" 1);
   214    by (subgoal_tac "x ~= f m" 1);
   215     by (fast_tac set_cs 2);
   215     by (Fast_tac 2);
   216    by (subgoal_tac "? k. f k = x & k<m" 1);
   216    by (subgoal_tac "? k. f k = x & k<m" 1);
   217     by (best_tac set_cs 2);
   217     by (best_tac set_cs 2);
   218    by (SELECT_GOAL(safe_tac HOL_cs)1);
   218    by (SELECT_GOAL(safe_tac HOL_cs)1);
   219    by (res_inst_tac [("x","k")] exI 1);
   219    by (res_inst_tac [("x","k")] exI 1);
   220    by (Asm_simp_tac 1);
   220    by (Asm_simp_tac 1);
   224  by (rotate_tac ~1 1);
   224  by (rotate_tac ~1 1);
   225  by (Asm_full_simp_tac 1);
   225  by (Asm_full_simp_tac 1);
   226  by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   226  by (res_inst_tac [("x","%i. if f i = f m then a else f i")] exI 1);
   227  by (SELECT_GOAL(safe_tac eq_cs)1);
   227  by (SELECT_GOAL(safe_tac eq_cs)1);
   228   by (subgoal_tac "x ~= f m" 1);
   228   by (subgoal_tac "x ~= f m" 1);
   229    by (fast_tac set_cs 2);
   229    by (Fast_tac 2);
   230   by (subgoal_tac "? k. f k = x & k<m" 1);
   230   by (subgoal_tac "? k. f k = x & k<m" 1);
   231    by (best_tac set_cs 2);
   231    by (best_tac set_cs 2);
   232   by (SELECT_GOAL(safe_tac HOL_cs)1);
   232   by (SELECT_GOAL(safe_tac HOL_cs)1);
   233   by (res_inst_tac [("x","k")] exI 1);
   233   by (res_inst_tac [("x","k")] exI 1);
   234   by (Asm_simp_tac 1);
   234   by (Asm_simp_tac 1);
   235  by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   235  by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   236  by (best_tac set_cs 1);
   236  by (best_tac set_cs 1);
   237 by (res_inst_tac [("x","%j. if f j = f i then f m else f j")] exI 1);
   237 by (res_inst_tac [("x","%j. if f j = f i then f m else f j")] exI 1);
   238 by (SELECT_GOAL(safe_tac eq_cs)1);
   238 by (SELECT_GOAL(safe_tac eq_cs)1);
   239  by (subgoal_tac "x ~= f i" 1);
   239  by (subgoal_tac "x ~= f i" 1);
   240   by (fast_tac set_cs 2);
   240   by (Fast_tac 2);
   241  by (case_tac "x = f m" 1);
   241  by (case_tac "x = f m" 1);
   242   by (res_inst_tac [("x","i")] exI 1);
   242   by (res_inst_tac [("x","i")] exI 1);
   243   by (Asm_simp_tac 1);
   243   by (Asm_simp_tac 1);
   244  by (subgoal_tac "? k. f k = x & k<m" 1);
   244  by (subgoal_tac "? k. f k = x & k<m" 1);
   245   by (best_tac set_cs 2);
   245   by (best_tac set_cs 2);
   303 by (dtac mk_disjoint_insert 1);
   303 by (dtac mk_disjoint_insert 1);
   304 by (etac exE 1);
   304 by (etac exE 1);
   305 by (Asm_simp_tac 1);
   305 by (Asm_simp_tac 1);
   306 by (rtac card_insert_disjoint 1);
   306 by (rtac card_insert_disjoint 1);
   307 by (rtac (major RSN (2,finite_subset)) 1);
   307 by (rtac (major RSN (2,finite_subset)) 1);
   308 by (fast_tac set_cs 1);
   308 by (Fast_tac 1);
   309 by (fast_tac HOL_cs 1);
   309 by (Fast_tac 1);
   310 by (asm_simp_tac (!simpset addsimps [major RS card_insert_disjoint]) 1);
   310 by (asm_simp_tac (!simpset addsimps [major RS card_insert_disjoint]) 1);
   311 qed "card_insert";
   311 qed "card_insert";
   312 Addsimps [card_insert];
   312 Addsimps [card_insert];
   313 
   313 
   314 
   314