31 by (rtac Card_cardinal 1); |
31 by (rtac Card_cardinal 1); |
32 by (resolve_tac [Card_nat RS (Card_def RS def_imp_iff RS iffD1 RS ssubst)] 1); |
32 by (resolve_tac [Card_nat RS (Card_def RS def_imp_iff RS iffD1 RS ssubst)] 1); |
33 by (resolve_tac [nat_le_infinite_Ord RS le_imp_lepoll |
33 by (resolve_tac [nat_le_infinite_Ord RS le_imp_lepoll |
34 RSN (2, well_ord_Memrel RS well_ord_lepoll_imp_Card_le)] 1 |
34 RSN (2, well_ord_Memrel RS well_ord_lepoll_imp_Card_le)] 1 |
35 THEN REPEAT (assume_tac 1)); |
35 THEN REPEAT (assume_tac 1)); |
36 val Inf_Ord_imp_InfCard_cardinal = result(); |
36 qed "Inf_Ord_imp_InfCard_cardinal"; |
37 |
37 |
38 val sum_lepoll_prod = [sum_eq_2_times RS equalityD1 RS subset_imp_lepoll, |
38 val sum_lepoll_prod = [sum_eq_2_times RS equalityD1 RS subset_imp_lepoll, |
39 asm_rl, lepoll_refl] MRS (prod_lepoll_mono RSN (2, lepoll_trans)) |
39 asm_rl, lepoll_refl] MRS (prod_lepoll_mono RSN (2, lepoll_trans)) |
40 |> standard; |
40 |> standard; |
41 |
41 |
42 goal thy "!!A. [| A lepoll B; 2 lepoll A |] ==> A+B lepoll A*B"; |
42 goal thy "!!A. [| A lepoll B; 2 lepoll A |] ==> A+B lepoll A*B"; |
43 by (REPEAT (ares_tac [[sum_lepoll_mono, sum_lepoll_prod] |
43 by (REPEAT (ares_tac [[sum_lepoll_mono, sum_lepoll_prod] |
44 MRS lepoll_trans, lepoll_refl] 1)); |
44 MRS lepoll_trans, lepoll_refl] 1)); |
45 val lepoll_imp_sum_lepoll_prod = result(); |
45 qed "lepoll_imp_sum_lepoll_prod"; |
46 |
46 |
47 goal thy "!!A. [| A eqpoll i; B eqpoll i; ~Finite(i); Ord(i) |] \ |
47 goal thy "!!A. [| A eqpoll i; B eqpoll i; ~Finite(i); Ord(i) |] \ |
48 \ ==> A Un B eqpoll i"; |
48 \ ==> A Un B eqpoll i"; |
49 by (rtac eqpollI 1); |
49 by (rtac eqpollI 1); |
50 by (eresolve_tac [subset_imp_lepoll RSN (2, eqpoll_sym RS eqpoll_imp_lepoll |
50 by (eresolve_tac [subset_imp_lepoll RSN (2, eqpoll_sym RS eqpoll_imp_lepoll |
61 by (eresolve_tac [prod_eqpoll_cong RS eqpoll_imp_lepoll RS lepoll_trans] 1 |
61 by (eresolve_tac [prod_eqpoll_cong RS eqpoll_imp_lepoll RS lepoll_trans] 1 |
62 THEN (assume_tac 1)); |
62 THEN (assume_tac 1)); |
63 by (resolve_tac [Inf_Ord_imp_InfCard_cardinal RSN (2, well_ord_Memrel RS |
63 by (resolve_tac [Inf_Ord_imp_InfCard_cardinal RSN (2, well_ord_Memrel RS |
64 well_ord_InfCard_square_eq) RS eqpoll_imp_lepoll] 1 |
64 well_ord_InfCard_square_eq) RS eqpoll_imp_lepoll] 1 |
65 THEN REPEAT (assume_tac 1)); |
65 THEN REPEAT (assume_tac 1)); |
66 val Un_eqpoll_Inf_Ord = result(); |
66 qed "Un_eqpoll_Inf_Ord"; |
67 |
67 |
68 val ss = (!simpset) addsimps [inj_is_fun RS apply_type, left_inverse] |
68 val ss = (!simpset) addsimps [inj_is_fun RS apply_type, left_inverse] |
69 setloop (split_tac [expand_if] ORELSE' etac UnE); |
69 setloop (split_tac [expand_if] ORELSE' etac UnE); |
70 |
70 |
71 goal ZF.thy "{x, y} - {y} = {x} - {y}"; |
71 goal ZF.thy "{x, y} - {y} = {x} - {y}"; |
72 by (Fast_tac 1); |
72 by (Fast_tac 1); |
73 val double_Diff_sing = result(); |
73 qed "double_Diff_sing"; |
74 |
74 |
75 goal ZF.thy "if({y,z}-{z}=0, z, THE w. {y,z}-{z}={w}) = y"; |
75 goal ZF.thy "if({y,z}-{z}=0, z, THE w. {y,z}-{z}={w}) = y"; |
76 by (split_tac [expand_if] 1); |
76 by (split_tac [expand_if] 1); |
77 by (asm_full_simp_tac (!simpset addsimps [double_Diff_sing, Diff_eq_0_iff]) 1); |
77 by (asm_full_simp_tac (!simpset addsimps [double_Diff_sing, Diff_eq_0_iff]) 1); |
78 by (fast_tac (!claset addSIs [the_equality] addEs [equalityE]) 1); |
78 by (fast_tac (!claset addSIs [the_equality] addEs [equalityE]) 1); |
79 val paired_bij_lemma = result(); |
79 qed "paired_bij_lemma"; |
80 |
80 |
81 goal thy "(lam y:{{y,z}. y:x}. if(y-{z}=0, z, THE w. y-{z}={w})) \ |
81 goal thy "(lam y:{{y,z}. y:x}. if(y-{z}=0, z, THE w. y-{z}={w})) \ |
82 \ : bij({{y,z}. y:x}, x)"; |
82 \ : bij({{y,z}. y:x}, x)"; |
83 by (res_inst_tac [("d","%a. {a,z}")] lam_bijective 1); |
83 by (res_inst_tac [("d","%a. {a,z}")] lam_bijective 1); |
84 by (TRYALL (fast_tac (!claset addSEs [RepFunE] addSIs [RepFunI] |
84 by (TRYALL (fast_tac (!claset addSEs [RepFunE] addSIs [RepFunI] |
85 addss (!simpset addsimps [paired_bij_lemma])))); |
85 addss (!simpset addsimps [paired_bij_lemma])))); |
86 val paired_bij = result(); |
86 qed "paired_bij"; |
87 |
87 |
88 goalw thy [eqpoll_def] "{{y,z}. y:x} eqpoll x"; |
88 goalw thy [eqpoll_def] "{{y,z}. y:x} eqpoll x"; |
89 by (fast_tac (!claset addSIs [paired_bij]) 1); |
89 by (fast_tac (!claset addSIs [paired_bij]) 1); |
90 val paired_eqpoll = result(); |
90 qed "paired_eqpoll"; |
91 |
91 |
92 goal thy "!!A. EX B. B eqpoll A & B Int C = 0"; |
92 goal thy "!!A. EX B. B eqpoll A & B Int C = 0"; |
93 by (fast_tac (!claset addSIs [paired_eqpoll, equals0I] addEs [mem_asym]) 1); |
93 by (fast_tac (!claset addSIs [paired_eqpoll, equals0I] addEs [mem_asym]) 1); |
94 val ex_eqpoll_disjoint = result(); |
94 qed "ex_eqpoll_disjoint"; |
95 |
95 |
96 goal thy "!!A. [| A lepoll i; B lepoll i; ~Finite(i); Ord(i) |] \ |
96 goal thy "!!A. [| A lepoll i; B lepoll i; ~Finite(i); Ord(i) |] \ |
97 \ ==> A Un B lepoll i"; |
97 \ ==> A Un B lepoll i"; |
98 by (res_inst_tac [("A1","i"), ("C1","i")] (ex_eqpoll_disjoint RS exE) 1); |
98 by (res_inst_tac [("A1","i"), ("C1","i")] (ex_eqpoll_disjoint RS exE) 1); |
99 by (etac conjE 1); |
99 by (etac conjE 1); |
101 by (assume_tac 1); |
101 by (assume_tac 1); |
102 by (resolve_tac [Un_lepoll_Un RS lepoll_trans] 1 THEN (REPEAT (assume_tac 1))); |
102 by (resolve_tac [Un_lepoll_Un RS lepoll_trans] 1 THEN (REPEAT (assume_tac 1))); |
103 by (eresolve_tac [eqpoll_refl RSN (2, Un_eqpoll_Inf_Ord) RS |
103 by (eresolve_tac [eqpoll_refl RSN (2, Un_eqpoll_Inf_Ord) RS |
104 eqpoll_imp_lepoll] 1 |
104 eqpoll_imp_lepoll] 1 |
105 THEN (REPEAT (assume_tac 1))); |
105 THEN (REPEAT (assume_tac 1))); |
106 val Un_lepoll_Inf_Ord = result(); |
106 qed "Un_lepoll_Inf_Ord"; |
107 |
107 |
108 goal thy "!!P. [| P(i); i:j; Ord(j) |] ==> (LEAST i. P(i)) : j"; |
108 goal thy "!!P. [| P(i); i:j; Ord(j) |] ==> (LEAST i. P(i)) : j"; |
109 by (eresolve_tac [Least_le RS leE] 1); |
109 by (eresolve_tac [Least_le RS leE] 1); |
110 by (etac Ord_in_Ord 1 THEN (assume_tac 1)); |
110 by (etac Ord_in_Ord 1 THEN (assume_tac 1)); |
111 by (etac ltE 1); |
111 by (etac ltE 1); |
112 by (fast_tac (!claset addDs [OrdmemD]) 1); |
112 by (fast_tac (!claset addDs [OrdmemD]) 1); |
113 by (etac subst_elem 1 THEN (assume_tac 1)); |
113 by (etac subst_elem 1 THEN (assume_tac 1)); |
114 val Least_in_Ord = result(); |
114 qed "Least_in_Ord"; |
115 |
115 |
116 goal thy "!!x. [| well_ord(x,r); y<=x; y lepoll succ(n); n:nat |] \ |
116 goal thy "!!x. [| well_ord(x,r); y<=x; y lepoll succ(n); n:nat |] \ |
117 \ ==> y-{THE b. first(b,y,r)} lepoll n"; |
117 \ ==> y-{THE b. first(b,y,r)} lepoll n"; |
118 by (res_inst_tac [("Q","y=0")] (excluded_middle RS disjE) 1); |
118 by (res_inst_tac [("Q","y=0")] (excluded_middle RS disjE) 1); |
119 by (fast_tac (!claset addSIs [Diff_sing_lepoll, the_first_in]) 1); |
119 by (fast_tac (!claset addSIs [Diff_sing_lepoll, the_first_in]) 1); |
120 by (res_inst_tac [("b","y-{THE b. first(b, y, r)}")] subst 1); |
120 by (res_inst_tac [("b","y-{THE b. first(b, y, r)}")] subst 1); |
121 by (rtac empty_lepollI 2); |
121 by (rtac empty_lepollI 2); |
122 by (Fast_tac 1); |
122 by (Fast_tac 1); |
123 val Diff_first_lepoll = result(); |
123 qed "Diff_first_lepoll"; |
124 |
124 |
125 goal thy "(UN x:X. P(x)) <= (UN x:X. P(x)-Q(x)) Un (UN x:X. Q(x))"; |
125 goal thy "(UN x:X. P(x)) <= (UN x:X. P(x)-Q(x)) Un (UN x:X. Q(x))"; |
126 by (Fast_tac 1); |
126 by (Fast_tac 1); |
127 val UN_subset_split = result(); |
127 qed "UN_subset_split"; |
128 |
128 |
129 goalw thy [lepoll_def] "!!a. Ord(a) ==> (UN x:a. {P(x)}) lepoll a"; |
129 goalw thy [lepoll_def] "!!a. Ord(a) ==> (UN x:a. {P(x)}) lepoll a"; |
130 by (res_inst_tac [("x","lam z:(UN x:a. {P(x)}). (LEAST i. P(i)=z)")] exI 1); |
130 by (res_inst_tac [("x","lam z:(UN x:a. {P(x)}). (LEAST i. P(i)=z)")] exI 1); |
131 by (res_inst_tac [("d","%z. P(z)")] lam_injective 1); |
131 by (res_inst_tac [("d","%z. P(z)")] lam_injective 1); |
132 by (fast_tac (!claset addSIs [Least_in_Ord]) 1); |
132 by (fast_tac (!claset addSIs [Least_in_Ord]) 1); |
133 by (fast_tac (!claset addIs [LeastI] addSEs [Ord_in_Ord]) 1); |
133 by (fast_tac (!claset addIs [LeastI] addSEs [Ord_in_Ord]) 1); |
134 val UN_sing_lepoll = result(); |
134 qed "UN_sing_lepoll"; |
135 |
135 |
136 goal thy "!!a T. [| well_ord(T, R); ~Finite(a); Ord(a); n:nat |] ==> \ |
136 goal thy "!!a T. [| well_ord(T, R); ~Finite(a); Ord(a); n:nat |] ==> \ |
137 \ ALL f. (ALL b:a. f`b lepoll n & f`b <= T) --> (UN b:a. f`b) lepoll a"; |
137 \ ALL f. (ALL b:a. f`b lepoll n & f`b <= T) --> (UN b:a. f`b) lepoll a"; |
138 by (etac nat_induct 1); |
138 by (etac nat_induct 1); |
139 by (rtac allI 1); |
139 by (rtac allI 1); |
151 by (fast_tac (!claset addSIs [Diff_first_lepoll]) 1); |
151 by (fast_tac (!claset addSIs [Diff_first_lepoll]) 1); |
152 by (Asm_full_simp_tac 1); |
152 by (Asm_full_simp_tac 1); |
153 by (resolve_tac [UN_subset_split RS subset_imp_lepoll RS lepoll_trans] 1); |
153 by (resolve_tac [UN_subset_split RS subset_imp_lepoll RS lepoll_trans] 1); |
154 by (rtac Un_lepoll_Inf_Ord 1 THEN (REPEAT_FIRST assume_tac)); |
154 by (rtac Un_lepoll_Inf_Ord 1 THEN (REPEAT_FIRST assume_tac)); |
155 by (etac UN_sing_lepoll 1); |
155 by (etac UN_sing_lepoll 1); |
156 val UN_fun_lepoll_lemma = result(); |
156 qed "UN_fun_lepoll_lemma"; |
157 |
157 |
158 goal thy "!!a f. [| ALL b:a. f`b lepoll n & f`b <= T; well_ord(T, R); \ |
158 goal thy "!!a f. [| ALL b:a. f`b lepoll n & f`b <= T; well_ord(T, R); \ |
159 \ ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. f`b) lepoll a"; |
159 \ ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. f`b) lepoll a"; |
160 by (eresolve_tac [UN_fun_lepoll_lemma RS allE] 1 THEN (REPEAT (assume_tac 1))); |
160 by (eresolve_tac [UN_fun_lepoll_lemma RS allE] 1 THEN (REPEAT (assume_tac 1))); |
161 by (Fast_tac 1); |
161 by (Fast_tac 1); |
162 val UN_fun_lepoll = result(); |
162 qed "UN_fun_lepoll"; |
163 |
163 |
164 goal thy "!!a f. [| ALL b:a. F(b) lepoll n & F(b) <= T; well_ord(T, R); \ |
164 goal thy "!!a f. [| ALL b:a. F(b) lepoll n & F(b) <= T; well_ord(T, R); \ |
165 \ ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. F(b)) lepoll a"; |
165 \ ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. F(b)) lepoll a"; |
166 by (rtac impE 1 THEN (assume_tac 3)); |
166 by (rtac impE 1 THEN (assume_tac 3)); |
167 by (res_inst_tac [("f","lam b:a. F(b)")] (UN_fun_lepoll) 2 |
167 by (res_inst_tac [("f","lam b:a. F(b)")] (UN_fun_lepoll) 2 |
168 THEN (TRYALL assume_tac)); |
168 THEN (TRYALL assume_tac)); |
169 by (Simp_tac 2); |
169 by (Simp_tac 2); |
170 by (Asm_full_simp_tac 1); |
170 by (Asm_full_simp_tac 1); |
171 val UN_lepoll = result(); |
171 qed "UN_lepoll"; |
172 |
172 |
173 goal thy "!!a. Ord(a) ==> (UN b:a. F(b)) = (UN b:a. F(b) - (UN c:b. F(c)))"; |
173 goal thy "!!a. Ord(a) ==> (UN b:a. F(b)) = (UN b:a. F(b) - (UN c:b. F(c)))"; |
174 by (rtac equalityI 1); |
174 by (rtac equalityI 1); |
175 by (Fast_tac 2); |
175 by (Fast_tac 2); |
176 by (rtac subsetI 1); |
176 by (rtac subsetI 1); |
181 by (resolve_tac [Ord_in_Ord RSN (2, LeastI)] 1 THEN (REPEAT (assume_tac 1))); |
181 by (resolve_tac [Ord_in_Ord RSN (2, LeastI)] 1 THEN (REPEAT (assume_tac 1))); |
182 by (rtac notI 1); |
182 by (rtac notI 1); |
183 by (etac UN_E 1); |
183 by (etac UN_E 1); |
184 by (eres_inst_tac [("P","%z. x:F(z)"),("i","c")] less_LeastE 1); |
184 by (eres_inst_tac [("P","%z. x:F(z)"),("i","c")] less_LeastE 1); |
185 by (eresolve_tac [Ord_Least RSN (2, ltI)] 1); |
185 by (eresolve_tac [Ord_Least RSN (2, ltI)] 1); |
186 val UN_eq_UN_Diffs = result(); |
186 qed "UN_eq_UN_Diffs"; |
187 |
187 |
188 goalw thy [eqpoll_def] "!!A B. A Int B = 0 ==> A Un B eqpoll A + B"; |
188 goalw thy [eqpoll_def] "!!A B. A Int B = 0 ==> A Un B eqpoll A + B"; |
189 by (res_inst_tac [("x","lam a:A Un B. if(a:A,Inl(a),Inr(a))")] exI 1); |
189 by (res_inst_tac [("x","lam a:A Un B. if(a:A,Inl(a),Inr(a))")] exI 1); |
190 by (res_inst_tac [("d","%z. case(%x.x, %x.x, z)")] lam_bijective 1); |
190 by (res_inst_tac [("d","%z. case(%x.x, %x.x, z)")] lam_bijective 1); |
191 by (fast_tac (!claset addSIs [if_type, InlI, InrI]) 1); |
191 by (fast_tac (!claset addSIs [if_type, InlI, InrI]) 1); |
192 by (TRYALL (etac sumE )); |
192 by (TRYALL (etac sumE )); |
193 by (TRYALL (split_tac [expand_if])); |
193 by (TRYALL (split_tac [expand_if])); |
194 by (TRYALL Asm_simp_tac); |
194 by (TRYALL Asm_simp_tac); |
195 by (fast_tac (!claset addDs [equals0D]) 1); |
195 by (fast_tac (!claset addDs [equals0D]) 1); |
196 val disj_Un_eqpoll_sum = result(); |
196 qed "disj_Un_eqpoll_sum"; |
197 |
197 |
198 goalw thy [lepoll_def, eqpoll_def] |
198 goalw thy [lepoll_def, eqpoll_def] |
199 "!!X a. a lepoll X ==> EX Y. Y<=X & a eqpoll Y"; |
199 "!!X a. a lepoll X ==> EX Y. Y<=X & a eqpoll Y"; |
200 by (etac exE 1); |
200 by (etac exE 1); |
201 by (forward_tac [subset_refl RSN (2, restrict_bij)] 1); |
201 by (forward_tac [subset_refl RSN (2, restrict_bij)] 1); |
202 by (res_inst_tac [("x","f``a")] exI 1); |
202 by (res_inst_tac [("x","f``a")] exI 1); |
203 by (fast_tac (!claset addSEs [inj_is_fun RS fun_is_rel RS image_subset]) 1); |
203 by (fast_tac (!claset addSEs [inj_is_fun RS fun_is_rel RS image_subset]) 1); |
204 val lepoll_imp_eqpoll_subset = result(); |
204 qed "lepoll_imp_eqpoll_subset"; |
205 |
205 |
206 (* ********************************************************************** *) |
206 (* ********************************************************************** *) |
207 (* Diff_lesspoll_eqpoll_Card *) |
207 (* Diff_lesspoll_eqpoll_Card *) |
208 (* ********************************************************************** *) |
208 (* ********************************************************************** *) |
209 |
209 |
233 by (fast_tac (!claset addSEs [ltE, Ord_in_Ord]) 1); |
233 by (fast_tac (!claset addSEs [ltE, Ord_in_Ord]) 1); |
234 by (dresolve_tac [subset_Un_Diff RS subset_imp_lepoll RS lepoll_trans RSN |
234 by (dresolve_tac [subset_Un_Diff RS subset_imp_lepoll RS lepoll_trans RSN |
235 (3, lt_Card_imp_lesspoll RS lepoll_lesspoll_lesspoll)] 1 |
235 (3, lt_Card_imp_lesspoll RS lepoll_lesspoll_lesspoll)] 1 |
236 THEN (TRYALL assume_tac)); |
236 THEN (TRYALL assume_tac)); |
237 by (fast_tac (!claset addSDs [lesspoll_def RS def_imp_iff RS iffD1]) 1); |
237 by (fast_tac (!claset addSDs [lesspoll_def RS def_imp_iff RS iffD1]) 1); |
238 val Diff_lesspoll_eqpoll_Card_lemma = result(); |
238 qed "Diff_lesspoll_eqpoll_Card_lemma"; |
239 |
239 |
240 goal thy "!!A. [| A eqpoll a; ~Finite(a); Card(a); B lesspoll a |] \ |
240 goal thy "!!A. [| A eqpoll a; ~Finite(a); Card(a); B lesspoll a |] \ |
241 \ ==> A - B eqpoll a"; |
241 \ ==> A - B eqpoll a"; |
242 by (rtac swap 1 THEN (Fast_tac 1)); |
242 by (rtac swap 1 THEN (Fast_tac 1)); |
243 by (rtac Diff_lesspoll_eqpoll_Card_lemma 1 THEN (REPEAT (assume_tac 1))); |
243 by (rtac Diff_lesspoll_eqpoll_Card_lemma 1 THEN (REPEAT (assume_tac 1))); |
244 by (fast_tac (!claset addSIs [lesspoll_def RS def_imp_iff RS iffD2, |
244 by (fast_tac (!claset addSIs [lesspoll_def RS def_imp_iff RS iffD2, |
245 subset_imp_lepoll RS (eqpoll_imp_lepoll RSN (2, lepoll_trans))]) 1); |
245 subset_imp_lepoll RS (eqpoll_imp_lepoll RSN (2, lepoll_trans))]) 1); |
246 val Diff_lesspoll_eqpoll_Card = result(); |
246 qed "Diff_lesspoll_eqpoll_Card"; |
247 |
247 |