src/HOL/ex/set.ML
changeset 4089 96fba19bcbe2
parent 3919 c036caebfc75
child 4109 b131edcfeac3
equal deleted inserted replaced
4088:9be9e39fd862 4089:96fba19bcbe2
    14 (*Nice demonstration of blast_tac--and its overloading problems*)
    14 (*Nice demonstration of blast_tac--and its overloading problems*)
    15 goal Set.thy "!!S::'a set set. ALL x:S. ALL y:S. x<=y ==> EX z. S <= {z}";
    15 goal Set.thy "!!S::'a set set. ALL x:S. ALL y:S. x<=y ==> EX z. S <= {z}";
    16 let val insertCI' = read_instantiate [("'a", "?'a set")] insertCI
    16 let val insertCI' = read_instantiate [("'a", "?'a set")] insertCI
    17 in    (*Type instantiation is required so that blast_tac can apply equalityI
    17 in    (*Type instantiation is required so that blast_tac can apply equalityI
    18         to the subgoal arising from insertCI*)
    18         to the subgoal arising from insertCI*)
    19 by(blast_tac (!claset addSIs [insertCI']) 1)
    19 by(blast_tac (claset() addSIs [insertCI']) 1)
    20 end;
    20 end;
    21 
    21 
    22 (*** A unique fixpoint theorem --- fast/best/meson all fail ***)
    22 (*** A unique fixpoint theorem --- fast/best/meson all fail ***)
    23 
    23 
    24 val [prem] = goal HOL.thy "?!x. f(g(x))=x ==> ?!y. g(f(y))=y";
    24 val [prem] = goal HOL.thy "?!x. f(g(x))=x ==> ?!y. g(f(y))=y";
    28 
    28 
    29 (*** Cantor's Theorem: There is no surjection from a set to its powerset. ***)
    29 (*** Cantor's Theorem: There is no surjection from a set to its powerset. ***)
    30 
    30 
    31 goal Set.thy "~ (? f:: 'a=>'a set. ! S. ? x. f(x) = S)";
    31 goal Set.thy "~ (? f:: 'a=>'a set. ! S. ? x. f(x) = S)";
    32 (*requires best-first search because it is undirectional*)
    32 (*requires best-first search because it is undirectional*)
    33 by (best_tac (!claset addSEs [equalityCE]) 1);
    33 by (best_tac (claset() addSEs [equalityCE]) 1);
    34 qed "cantor1";
    34 qed "cantor1";
    35 
    35 
    36 (*This form displays the diagonal term*)
    36 (*This form displays the diagonal term*)
    37 goal Set.thy "! f:: 'a=>'a set. ! x. f(x) ~= ?S(f)";
    37 goal Set.thy "! f:: 'a=>'a set. ! x. f(x) ~= ?S(f)";
    38 by (best_tac (!claset addSEs [equalityCE]) 1);
    38 by (best_tac (claset() addSEs [equalityCE]) 1);
    39 uresult();
    39 uresult();
    40 
    40 
    41 (*This form exploits the set constructs*)
    41 (*This form exploits the set constructs*)
    42 goal Set.thy "?S ~: range(f :: 'a=>'a set)";
    42 goal Set.thy "?S ~: range(f :: 'a=>'a set)";
    43 by (rtac notI 1);
    43 by (rtac notI 1);
    47 by (contr_tac 1);
    47 by (contr_tac 1);
    48 by (swap_res_tac [CollectI] 1);
    48 by (swap_res_tac [CollectI] 1);
    49 by (assume_tac 1);
    49 by (assume_tac 1);
    50 
    50 
    51 choplev 0;
    51 choplev 0;
    52 by (best_tac (!claset addSEs [equalityCE]) 1);
    52 by (best_tac (claset() addSEs [equalityCE]) 1);
    53 
    53 
    54 (*** The Schroder-Berstein Theorem ***)
    54 (*** The Schroder-Berstein Theorem ***)
    55 
    55 
    56 goalw Lfp.thy [image_def] "!!f. inj(f) ==> inv(f)``(f``X) = X";
    56 goalw Lfp.thy [image_def] "!!f. inj(f) ==> inv(f)``(f``X) = X";
    57 by (rtac equalityI 1);
    57 by (rtac equalityI 1);
    58 by (fast_tac (!claset addEs [inv_f_f RS ssubst]) 1);
    58 by (fast_tac (claset() addEs [inv_f_f RS ssubst]) 1);
    59 by (fast_tac (!claset addEs [inv_f_f RS ssubst]) 1);
    59 by (fast_tac (claset() addEs [inv_f_f RS ssubst]) 1);
    60 qed "inv_image_comp";
    60 qed "inv_image_comp";
    61 
    61 
    62 goal Set.thy "!!f. f(a) ~: (f``X) ==> a~:X";
    62 goal Set.thy "!!f. f(a) ~: (f``X) ==> a~:X";
    63 by (Blast_tac 1);
    63 by (Blast_tac 1);
    64 qed "contra_imageI";
    64 qed "contra_imageI";
    75             rtac imageI, rtac Xa]);
    75             rtac imageI, rtac Xa]);
    76 qed "disj_lemma";
    76 qed "disj_lemma";
    77 
    77 
    78 goalw Lfp.thy [image_def]
    78 goalw Lfp.thy [image_def]
    79     "range(%z. if z:X then f(z) else g(z)) = f``X Un g``Compl(X)";
    79     "range(%z. if z:X then f(z) else g(z)) = f``X Un g``Compl(X)";
    80 by (simp_tac (!simpset addsplits [expand_if]) 1);
    80 by (simp_tac (simpset() addsplits [expand_if]) 1);
    81 by (Blast_tac 1);
    81 by (Blast_tac 1);
    82 qed "range_if_then_else";
    82 qed "range_if_then_else";
    83 
    83 
    84 goal Lfp.thy "a : X Un Compl(X)";
    84 goal Lfp.thy "a : X Un Compl(X)";
    85 by (Blast_tac 1);
    85 by (Blast_tac 1);
    86 qed "X_Un_Compl";
    86 qed "X_Un_Compl";
    87 
    87 
    88 goalw Lfp.thy [surj_def] "surj(f) = (!a. a : range(f))";
    88 goalw Lfp.thy [surj_def] "surj(f) = (!a. a : range(f))";
    89 by (fast_tac (!claset addEs [ssubst]) 1);
    89 by (fast_tac (claset() addEs [ssubst]) 1);
    90 qed "surj_iff_full_range";
    90 qed "surj_iff_full_range";
    91 
    91 
    92 val [compl] = goal Lfp.thy
    92 val [compl] = goal Lfp.thy
    93     "Compl(f``X) = g``Compl(X) ==> surj(%z. if z:X then f(z) else g(z))";
    93     "Compl(f``X) = g``Compl(X) ==> surj(%z. if z:X then f(z) else g(z))";
    94 by (EVERY1[stac surj_iff_full_range, stac range_if_then_else,
    94 by (EVERY1[stac surj_iff_full_range, stac range_if_then_else,
   105 by (rtac conjI 1);
   105 by (rtac conjI 1);
   106 by (rtac (compl RS surj_if_then_else) 2);
   106 by (rtac (compl RS surj_if_then_else) 2);
   107 by (rewtac inj_def);
   107 by (rewtac inj_def);
   108 by (cut_facts_tac [injf,injg] 1);
   108 by (cut_facts_tac [injf,injg] 1);
   109 by (EVERY1 [rtac allI, rtac allI, stac expand_if, rtac conjI, stac expand_if]);
   109 by (EVERY1 [rtac allI, rtac allI, stac expand_if, rtac conjI, stac expand_if]);
   110 by (fast_tac (!claset addEs  [inj_ontoD, sym RS f_eq_gE]) 1);
   110 by (fast_tac (claset() addEs  [inj_ontoD, sym RS f_eq_gE]) 1);
   111 by (stac expand_if 1);
   111 by (stac expand_if 1);
   112 by (fast_tac (!claset addEs  [inj_ontoD, f_eq_gE]) 1);
   112 by (fast_tac (claset() addEs  [inj_ontoD, f_eq_gE]) 1);
   113 qed "bij_if_then_else";
   113 qed "bij_if_then_else";
   114 
   114 
   115 goal Lfp.thy "? X. X = Compl(g``Compl((f:: 'a=>'b)``X))";
   115 goal Lfp.thy "? X. X = Compl(g``Compl((f:: 'a=>'b)``X))";
   116 by (rtac exI 1);
   116 by (rtac exI 1);
   117 by (rtac lfp_Tarski 1);
   117 by (rtac lfp_Tarski 1);