equal
deleted
inserted
replaced
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); |