7 Union and Intersection as lattice operations |
7 Union and Intersection as lattice operations |
8 *) |
8 *) |
9 |
9 |
10 (*** cons ***) |
10 (*** cons ***) |
11 |
11 |
12 qed_goal "cons_subsetI" thy "!!a. [| a:C; B<=C |] ==> cons(a,B) <= C" |
12 qed_goal "cons_subsetI" ZF.thy "!!a. [| a:C; B<=C |] ==> cons(a,B) <= C" |
13 (fn _ => [ Fast_tac 1 ]); |
13 (fn _ => [ Blast_tac 1 ]); |
14 |
14 |
15 qed_goal "subset_consI" thy "B <= cons(a,B)" |
15 qed_goal "subset_consI" ZF.thy "B <= cons(a,B)" |
16 (fn _ => [ Fast_tac 1 ]); |
16 (fn _ => [ Blast_tac 1 ]); |
17 |
17 |
18 qed_goal "cons_subset_iff" thy "cons(a,B)<=C <-> a:C & B<=C" |
18 qed_goal "cons_subset_iff" ZF.thy "cons(a,B)<=C <-> a:C & B<=C" |
19 (fn _ => [ Fast_tac 1 ]); |
19 (fn _ => [ Blast_tac 1 ]); |
20 |
20 |
21 (*A safe special case of subset elimination, adding no new variables |
21 (*A safe special case of subset elimination, adding no new variables |
22 [| cons(a,B) <= C; [| a : C; B <= C |] ==> R |] ==> R *) |
22 [| cons(a,B) <= C; [| a : C; B <= C |] ==> R |] ==> R *) |
23 bind_thm ("cons_subsetE", cons_subset_iff RS iffD1 RS conjE); |
23 bind_thm ("cons_subsetE", cons_subset_iff RS iffD1 RS conjE); |
24 |
24 |
25 qed_goal "subset_empty_iff" thy "A<=0 <-> A=0" |
25 qed_goal "subset_empty_iff" ZF.thy "A<=0 <-> A=0" |
26 (fn _=> [ (Fast_tac 1) ]); |
26 (fn _=> [ (Blast_tac 1) ]); |
27 |
27 |
28 qed_goal "subset_cons_iff" thy |
28 qed_goal "subset_cons_iff" ZF.thy |
29 "C<=cons(a,B) <-> C<=B | (a:C & C-{a} <= B)" |
29 "C<=cons(a,B) <-> C<=B | (a:C & C-{a} <= B)" |
30 (fn _=> [ (Fast_tac 1) ]); |
30 (fn _=> [ (Blast_tac 1) ]); |
31 |
31 |
32 (*** succ ***) |
32 (*** succ ***) |
33 |
33 |
34 qed_goal "subset_succI" thy "i <= succ(i)" |
34 qed_goal "subset_succI" ZF.thy "i <= succ(i)" |
35 (fn _=> [ (Fast_tac 1) ]); |
35 (fn _=> [ (Blast_tac 1) ]); |
36 |
36 |
37 (*But if j is an ordinal or is transitive, then i:j implies i<=j! |
37 (*But if j is an ordinal or is transitive, then i:j implies i<=j! |
38 See ordinal/Ord_succ_subsetI*) |
38 See ordinal/Ord_succ_subsetI*) |
39 qed_goalw "succ_subsetI" thy [succ_def] |
39 qed_goalw "succ_subsetI" ZF.thy [succ_def] |
40 "!!i j. [| i:j; i<=j |] ==> succ(i)<=j" |
40 "!!i j. [| i:j; i<=j |] ==> succ(i)<=j" |
41 (fn _=> [ (Fast_tac 1) ]); |
41 (fn _=> [ (Blast_tac 1) ]); |
42 |
42 |
43 qed_goalw "succ_subsetE" thy [succ_def] |
43 qed_goalw "succ_subsetE" ZF.thy [succ_def] |
44 "[| succ(i) <= j; [| i:j; i<=j |] ==> P \ |
44 "[| succ(i) <= j; [| i:j; i<=j |] ==> P \ |
45 \ |] ==> P" |
45 \ |] ==> P" |
46 (fn major::prems=> |
46 (fn major::prems=> |
47 [ (rtac (major RS cons_subsetE) 1), |
47 [ (rtac (major RS cons_subsetE) 1), |
48 (REPEAT (ares_tac prems 1)) ]); |
48 (REPEAT (ares_tac prems 1)) ]); |
49 |
49 |
50 (*** singletons ***) |
50 (*** singletons ***) |
51 |
51 |
52 qed_goal "singleton_subsetI" thy "!!a c. a:C ==> {a} <= C" |
52 qed_goal "singleton_subsetI" ZF.thy "!!a c. a:C ==> {a} <= C" |
53 (fn _=> [ (Fast_tac 1) ]); |
53 (fn _=> [ (Blast_tac 1) ]); |
54 |
54 |
55 qed_goal "singleton_subsetD" thy "!!a C. {a} <= C ==> a:C" |
55 qed_goal "singleton_subsetD" ZF.thy "!!a C. {a} <= C ==> a:C" |
56 (fn _=> [ (Fast_tac 1) ]); |
56 (fn _=> [ (Blast_tac 1) ]); |
57 |
57 |
58 (*** Big Union -- least upper bound of a set ***) |
58 (*** Big Union -- least upper bound of a set ***) |
59 |
59 |
60 qed_goal "Union_subset_iff" thy "Union(A) <= C <-> (ALL x:A. x <= C)" |
60 qed_goal "Union_subset_iff" ZF.thy "Union(A) <= C <-> (ALL x:A. x <= C)" |
61 (fn _ => [ Fast_tac 1 ]); |
61 (fn _ => [ Blast_tac 1 ]); |
62 |
62 |
63 qed_goal "Union_upper" thy |
63 qed_goal "Union_upper" ZF.thy |
64 "!!B A. B:A ==> B <= Union(A)" |
64 "!!B A. B:A ==> B <= Union(A)" |
65 (fn _ => [ Fast_tac 1 ]); |
65 (fn _ => [ Blast_tac 1 ]); |
66 |
66 |
67 qed_goal "Union_least" thy |
67 qed_goal "Union_least" ZF.thy |
68 "[| !!x. x:A ==> x<=C |] ==> Union(A) <= C" |
68 "[| !!x. x:A ==> x<=C |] ==> Union(A) <= C" |
69 (fn [prem]=> |
69 (fn [prem]=> |
70 [ (rtac (ballI RS (Union_subset_iff RS iffD2)) 1), |
70 [ (rtac (ballI RS (Union_subset_iff RS iffD2)) 1), |
71 (etac prem 1) ]); |
71 (etac prem 1) ]); |
72 |
72 |
73 (*** Union of a family of sets ***) |
73 (*** Union of a family of sets ***) |
74 |
74 |
75 goal thy "A <= (UN i:I. B(i)) <-> A = (UN i:I. A Int B(i))"; |
75 goal ZF.thy "A <= (UN i:I. B(i)) <-> A = (UN i:I. A Int B(i))"; |
76 by (fast_tac (!claset addSEs [equalityE]) 1); |
76 by (blast_tac (!claset addSEs [equalityE]) 1); |
77 qed "subset_UN_iff_eq"; |
77 qed "subset_UN_iff_eq"; |
78 |
78 |
79 qed_goal "UN_subset_iff" thy |
79 qed_goal "UN_subset_iff" ZF.thy |
80 "(UN x:A.B(x)) <= C <-> (ALL x:A. B(x) <= C)" |
80 "(UN x:A.B(x)) <= C <-> (ALL x:A. B(x) <= C)" |
81 (fn _ => [ Fast_tac 1 ]); |
81 (fn _ => [ Blast_tac 1 ]); |
82 |
82 |
83 qed_goal "UN_upper" thy |
83 qed_goal "UN_upper" ZF.thy |
84 "!!x A. x:A ==> B(x) <= (UN x:A.B(x))" |
84 "!!x A. x:A ==> B(x) <= (UN x:A.B(x))" |
85 (fn _ => [ etac (RepFunI RS Union_upper) 1 ]); |
85 (fn _ => [ etac (RepFunI RS Union_upper) 1 ]); |
86 |
86 |
87 qed_goal "UN_least" thy |
87 qed_goal "UN_least" ZF.thy |
88 "[| !!x. x:A ==> B(x)<=C |] ==> (UN x:A.B(x)) <= C" |
88 "[| !!x. x:A ==> B(x)<=C |] ==> (UN x:A.B(x)) <= C" |
89 (fn [prem]=> |
89 (fn [prem]=> |
90 [ (rtac (ballI RS (UN_subset_iff RS iffD2)) 1), |
90 [ (rtac (ballI RS (UN_subset_iff RS iffD2)) 1), |
91 (etac prem 1) ]); |
91 (etac prem 1) ]); |
92 |
92 |
93 |
93 |
94 (*** Big Intersection -- greatest lower bound of a nonempty set ***) |
94 (*** Big Intersection -- greatest lower bound of a nonempty set ***) |
95 |
95 |
96 qed_goal "Inter_subset_iff" thy |
96 qed_goal "Inter_subset_iff" ZF.thy |
97 "!!a A. a: A ==> C <= Inter(A) <-> (ALL x:A. C <= x)" |
97 "!!a A. a: A ==> C <= Inter(A) <-> (ALL x:A. C <= x)" |
98 (fn _ => [ Fast_tac 1 ]); |
98 (fn _ => [ Blast_tac 1 ]); |
99 |
99 |
100 qed_goal "Inter_lower" thy "!!B A. B:A ==> Inter(A) <= B" |
100 qed_goal "Inter_lower" ZF.thy "!!B A. B:A ==> Inter(A) <= B" |
101 (fn _ => [ Fast_tac 1 ]); |
101 (fn _ => [ Blast_tac 1 ]); |
102 |
102 |
103 qed_goal "Inter_greatest" thy |
103 qed_goal "Inter_greatest" ZF.thy |
104 "[| a:A; !!x. x:A ==> C<=x |] ==> C <= Inter(A)" |
104 "[| a:A; !!x. x:A ==> C<=x |] ==> C <= Inter(A)" |
105 (fn [prem1,prem2]=> |
105 (fn [prem1,prem2]=> |
106 [ (rtac ([prem1, ballI] MRS (Inter_subset_iff RS iffD2)) 1), |
106 [ (rtac ([prem1, ballI] MRS (Inter_subset_iff RS iffD2)) 1), |
107 (etac prem2 1) ]); |
107 (etac prem2 1) ]); |
108 |
108 |
109 (*** Intersection of a family of sets ***) |
109 (*** Intersection of a family of sets ***) |
110 |
110 |
111 qed_goal "INT_lower" thy |
111 qed_goal "INT_lower" ZF.thy |
112 "!!x. x:A ==> (INT x:A.B(x)) <= B(x)" |
112 "!!x. x:A ==> (INT x:A.B(x)) <= B(x)" |
113 (fn _ => [ Fast_tac 1 ]); |
113 (fn _ => [ Blast_tac 1 ]); |
114 |
114 |
115 qed_goal "INT_greatest" thy |
115 qed_goal "INT_greatest" ZF.thy |
116 "[| a:A; !!x. x:A ==> C<=B(x) |] ==> C <= (INT x:A.B(x))" |
116 "[| a:A; !!x. x:A ==> C<=B(x) |] ==> C <= (INT x:A.B(x))" |
117 (fn [nonempty,prem] => |
117 (fn [nonempty,prem] => |
118 [ rtac (nonempty RS RepFunI RS Inter_greatest) 1, |
118 [ rtac (nonempty RS RepFunI RS Inter_greatest) 1, |
119 REPEAT (eresolve_tac [RepFunE, prem, ssubst] 1) ]); |
119 REPEAT (eresolve_tac [RepFunE, prem, ssubst] 1) ]); |
120 |
120 |
121 |
121 |
122 (*** Finite Union -- the least upper bound of 2 sets ***) |
122 (*** Finite Union -- the least upper bound of 2 sets ***) |
123 |
123 |
124 qed_goal "Un_subset_iff" thy "A Un B <= C <-> A <= C & B <= C" |
124 qed_goal "Un_subset_iff" ZF.thy "A Un B <= C <-> A <= C & B <= C" |
125 (fn _ => [ Fast_tac 1 ]); |
125 (fn _ => [ Blast_tac 1 ]); |
126 |
126 |
127 qed_goal "Un_upper1" thy "A <= A Un B" |
127 qed_goal "Un_upper1" ZF.thy "A <= A Un B" |
128 (fn _ => [ Fast_tac 1 ]); |
128 (fn _ => [ Blast_tac 1 ]); |
129 |
129 |
130 qed_goal "Un_upper2" thy "B <= A Un B" |
130 qed_goal "Un_upper2" ZF.thy "B <= A Un B" |
131 (fn _ => [ Fast_tac 1 ]); |
131 (fn _ => [ Blast_tac 1 ]); |
132 |
132 |
133 qed_goal "Un_least" thy "!!A B C. [| A<=C; B<=C |] ==> A Un B <= C" |
133 qed_goal "Un_least" ZF.thy "!!A B C. [| A<=C; B<=C |] ==> A Un B <= C" |
134 (fn _ => [ Fast_tac 1 ]); |
134 (fn _ => [ Blast_tac 1 ]); |
135 |
135 |
136 |
136 |
137 (*** Finite Intersection -- the greatest lower bound of 2 sets *) |
137 (*** Finite Intersection -- the greatest lower bound of 2 sets *) |
138 |
138 |
139 qed_goal "Int_subset_iff" thy "C <= A Int B <-> C <= A & C <= B" |
139 qed_goal "Int_subset_iff" ZF.thy "C <= A Int B <-> C <= A & C <= B" |
140 (fn _ => [ Fast_tac 1 ]); |
140 (fn _ => [ Blast_tac 1 ]); |
141 |
141 |
142 qed_goal "Int_lower1" thy "A Int B <= A" |
142 qed_goal "Int_lower1" ZF.thy "A Int B <= A" |
143 (fn _ => [ Fast_tac 1 ]); |
143 (fn _ => [ Blast_tac 1 ]); |
144 |
144 |
145 qed_goal "Int_lower2" thy "A Int B <= B" |
145 qed_goal "Int_lower2" ZF.thy "A Int B <= B" |
146 (fn _ => [ Fast_tac 1 ]); |
146 (fn _ => [ Blast_tac 1 ]); |
147 |
147 |
148 qed_goal "Int_greatest" thy "!!A B C. [| C<=A; C<=B |] ==> C <= A Int B" |
148 qed_goal "Int_greatest" ZF.thy "!!A B C. [| C<=A; C<=B |] ==> C <= A Int B" |
149 (fn _ => [ Fast_tac 1 ]); |
149 (fn _ => [ Blast_tac 1 ]); |
150 |
150 |
151 |
151 |
152 (*** Set difference *) |
152 (*** Set difference *) |
153 |
153 |
154 qed_goal "Diff_subset" thy "A-B <= A" |
154 qed_goal "Diff_subset" ZF.thy "A-B <= A" |
155 (fn _ => [ Fast_tac 1 ]); |
155 (fn _ => [ Blast_tac 1 ]); |
156 |
156 |
157 qed_goal "Diff_contains" thy |
157 qed_goal "Diff_contains" ZF.thy |
158 "!!C. [| C<=A; C Int B = 0 |] ==> C <= A-B" |
158 "!!C. [| C<=A; C Int B = 0 |] ==> C <= A-B" |
159 (fn _ => [ (fast_tac (!claset addSEs [equalityE]) 1) ]); |
159 (fn _ => [ (blast_tac (!claset addSEs [equalityE]) 1) ]); |
160 |
160 |
161 |
161 |
162 (** Collect **) |
162 (** Collect **) |
163 |
163 |
164 qed_goal "Collect_subset" thy "Collect(A,P) <= A" |
164 qed_goal "Collect_subset" ZF.thy "Collect(A,P) <= A" |
165 (fn _ => [ Fast_tac 1 ]); |
165 (fn _ => [ Blast_tac 1 ]); |
166 |
166 |
167 |
167 |
168 (** RepFun **) |
168 (** RepFun **) |
169 |
169 |
170 val prems = goal thy "[| !!x. x:A ==> f(x): B |] ==> {f(x). x:A} <= B"; |
170 val prems = goal ZF.thy "[| !!x. x:A ==> f(x): B |] ==> {f(x). x:A} <= B"; |
171 by (fast_tac (!claset addIs prems) 1); |
171 by (blast_tac (!claset addIs prems) 1); |
172 qed "RepFun_subset"; |
172 qed "RepFun_subset"; |
173 |
173 |
174 val subset_SIs = |
174 val subset_SIs = |
175 [subset_refl, cons_subsetI, subset_consI, |
175 [subset_refl, cons_subsetI, subset_consI, |
176 Union_least, UN_least, Un_least, |
176 Union_least, UN_least, Un_least, |