136 addSDs (XH_to_Ds ccl_injs); |
136 addSDs (XH_to_Ds ccl_injs); |
137 |
137 |
138 (****** Facts from gfp Definition of [= and = ******) |
138 (****** Facts from gfp Definition of [= and = ******) |
139 |
139 |
140 val major::prems = goal Set.thy "[| A=B; a:B <-> P |] ==> a:A <-> P"; |
140 val major::prems = goal Set.thy "[| A=B; a:B <-> P |] ==> a:A <-> P"; |
141 brs (prems RL [major RS ssubst]) 1; |
141 by (resolve_tac (prems RL [major RS ssubst]) 1); |
142 val XHlemma1 = result(); |
142 val XHlemma1 = result(); |
143 |
143 |
144 goal CCL.thy "(P(t,t') <-> Q) --> (<t,t'> : {p.EX t t'.p=<t,t'> & P(t,t')} <-> Q)"; |
144 goal CCL.thy "(P(t,t') <-> Q) --> (<t,t'> : {p.EX t t'.p=<t,t'> & P(t,t')} <-> Q)"; |
145 by (fast_tac ccl_cs 1); |
145 by (fast_tac ccl_cs 1); |
146 val XHlemma2 = result() RS mp; |
146 val XHlemma2 = result() RS mp; |
147 |
147 |
148 (*** Pre-Order ***) |
148 (*** Pre-Order ***) |
149 |
149 |
150 goalw CCL.thy [POgen_def,SIM_def] "mono(%X.POgen(X))"; |
150 goalw CCL.thy [POgen_def,SIM_def] "mono(%X.POgen(X))"; |
151 br monoI 1; |
151 by (rtac monoI 1); |
152 by (safe_tac ccl_cs); |
152 by (safe_tac ccl_cs); |
153 by (REPEAT_SOME (resolve_tac [exI,conjI,refl])); |
153 by (REPEAT_SOME (resolve_tac [exI,conjI,refl])); |
154 by (ALLGOALS (simp_tac ccl_ss)); |
154 by (ALLGOALS (simp_tac ccl_ss)); |
155 by (ALLGOALS (fast_tac set_cs)); |
155 by (ALLGOALS (fast_tac set_cs)); |
156 val POgen_mono = result(); |
156 val POgen_mono = result(); |
157 |
157 |
158 goalw CCL.thy [POgen_def,SIM_def] |
158 goalw CCL.thy [POgen_def,SIM_def] |
159 "<t,t'> : POgen(R) <-> t= bot | (t=true & t'=true) | (t=false & t'=false) | \ |
159 "<t,t'> : POgen(R) <-> t= bot | (t=true & t'=true) | (t=false & t'=false) | \ |
160 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & <a,a'> : R & <b,b'> : R) | \ |
160 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & <a,a'> : R & <b,b'> : R) | \ |
161 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))"; |
161 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))"; |
162 br (iff_refl RS XHlemma2) 1; |
162 by (rtac (iff_refl RS XHlemma2) 1); |
163 val POgenXH = result(); |
163 val POgenXH = result(); |
164 |
164 |
165 goal CCL.thy |
165 goal CCL.thy |
166 "t [= t' <-> t=bot | (t=true & t'=true) | (t=false & t'=false) | \ |
166 "t [= t' <-> t=bot | (t=true & t'=true) | (t=false & t'=false) | \ |
167 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & a [= a' & b [= b') | \ |
167 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & a [= a' & b [= b') | \ |
168 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.f(x) [= f'(x)))"; |
168 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.f(x) [= f'(x)))"; |
169 by (simp_tac (ccl_ss addsimps [PO_iff]) 1); |
169 by (simp_tac (ccl_ss addsimps [PO_iff]) 1); |
170 br (rewrite_rule [POgen_def,SIM_def] |
170 br (rewrite_rule [POgen_def,SIM_def] |
171 (POgen_mono RS (PO_def RS def_gfp_Tarski) RS XHlemma1)) 1; |
171 (POgen_mono RS (PO_def RS def_gfp_Tarski) RS XHlemma1)) 1; |
172 br (iff_refl RS XHlemma2) 1; |
172 by (rtac (iff_refl RS XHlemma2) 1); |
173 val poXH = result(); |
173 val poXH = result(); |
174 |
174 |
175 goal CCL.thy "bot [= b"; |
175 goal CCL.thy "bot [= b"; |
176 br (poXH RS iffD2) 1; |
176 by (rtac (poXH RS iffD2) 1); |
177 by (simp_tac ccl_ss 1); |
177 by (simp_tac ccl_ss 1); |
178 val po_bot = result(); |
178 val po_bot = result(); |
179 |
179 |
180 goal CCL.thy "a [= bot --> a=bot"; |
180 goal CCL.thy "a [= bot --> a=bot"; |
181 br impI 1; |
181 by (rtac impI 1); |
182 bd (poXH RS iffD1) 1; |
182 by (dtac (poXH RS iffD1) 1); |
183 be rev_mp 1; |
183 by (etac rev_mp 1); |
184 by (simp_tac ccl_ss 1); |
184 by (simp_tac ccl_ss 1); |
185 val bot_poleast = result() RS mp; |
185 val bot_poleast = result() RS mp; |
186 |
186 |
187 goal CCL.thy "<a,b> [= <a',b'> <-> a [= a' & b [= b'"; |
187 goal CCL.thy "<a,b> [= <a',b'> <-> a [= a' & b [= b'"; |
188 br (poXH RS iff_trans) 1; |
188 by (rtac (poXH RS iff_trans) 1); |
189 by (simp_tac ccl_ss 1); |
189 by (simp_tac ccl_ss 1); |
190 by (fast_tac ccl_cs 1); |
190 by (fast_tac ccl_cs 1); |
191 val po_pair = result(); |
191 val po_pair = result(); |
192 |
192 |
193 goal CCL.thy "lam x.f(x) [= lam x.f'(x) <-> (ALL x. f(x) [= f'(x))"; |
193 goal CCL.thy "lam x.f(x) [= lam x.f'(x) <-> (ALL x. f(x) [= f'(x))"; |
194 br (poXH RS iff_trans) 1; |
194 by (rtac (poXH RS iff_trans) 1); |
195 by (simp_tac ccl_ss 1); |
195 by (simp_tac ccl_ss 1); |
196 by (REPEAT (ares_tac [iffI,allI] 1 ORELSE eresolve_tac [exE,conjE] 1)); |
196 by (REPEAT (ares_tac [iffI,allI] 1 ORELSE eresolve_tac [exE,conjE] 1)); |
197 by (asm_simp_tac ccl_ss 1); |
197 by (asm_simp_tac ccl_ss 1); |
198 by (fast_tac ccl_cs 1); |
198 by (fast_tac ccl_cs 1); |
199 val po_lam = result(); |
199 val po_lam = result(); |
201 val ccl_porews = [po_bot,po_pair,po_lam]; |
201 val ccl_porews = [po_bot,po_pair,po_lam]; |
202 |
202 |
203 val [p1,p2,p3,p4,p5] = goal CCL.thy |
203 val [p1,p2,p3,p4,p5] = goal CCL.thy |
204 "[| t [= t'; a [= a'; b [= b'; !!x y.c(x,y) [= c'(x,y); \ |
204 "[| t [= t'; a [= a'; b [= b'; !!x y.c(x,y) [= c'(x,y); \ |
205 \ !!u.d(u) [= d'(u) |] ==> case(t,a,b,c,d) [= case(t',a',b',c',d')"; |
205 \ !!u.d(u) [= d'(u) |] ==> case(t,a,b,c,d) [= case(t',a',b',c',d')"; |
206 br (p1 RS po_cong RS po_trans) 1; |
206 by (rtac (p1 RS po_cong RS po_trans) 1); |
207 br (p2 RS po_cong RS po_trans) 1; |
207 by (rtac (p2 RS po_cong RS po_trans) 1); |
208 br (p3 RS po_cong RS po_trans) 1; |
208 by (rtac (p3 RS po_cong RS po_trans) 1); |
209 br (p4 RS po_abstractn RS po_abstractn RS po_cong RS po_trans) 1; |
209 by (rtac (p4 RS po_abstractn RS po_abstractn RS po_cong RS po_trans) 1); |
210 by (res_inst_tac [("f1","%d.case(t',a',b',c',d)")] |
210 by (res_inst_tac [("f1","%d.case(t',a',b',c',d)")] |
211 (p5 RS po_abstractn RS po_cong RS po_trans) 1); |
211 (p5 RS po_abstractn RS po_cong RS po_trans) 1); |
212 br po_refl 1; |
212 by (rtac po_refl 1); |
213 val case_pocong = result(); |
213 val case_pocong = result(); |
214 |
214 |
215 val [p1,p2] = goalw CCL.thy ccl_data_defs |
215 val [p1,p2] = goalw CCL.thy ccl_data_defs |
216 "[| f [= f'; a [= a' |] ==> f ` a [= f' ` a'"; |
216 "[| f [= f'; a [= a' |] ==> f ` a [= f' ` a'"; |
217 by (REPEAT (ares_tac [po_refl,case_pocong,p1,p2 RS po_cong] 1)); |
217 by (REPEAT (ares_tac [po_refl,case_pocong,p1,p2 RS po_cong] 1)); |
218 val apply_pocong = result(); |
218 val apply_pocong = result(); |
219 |
219 |
220 |
220 |
221 val prems = goal CCL.thy "~ lam x.b(x) [= bot"; |
221 val prems = goal CCL.thy "~ lam x.b(x) [= bot"; |
222 br notI 1; |
222 by (rtac notI 1); |
223 bd bot_poleast 1; |
223 by (dtac bot_poleast 1); |
224 be (distinctness RS notE) 1; |
224 by (etac (distinctness RS notE) 1); |
225 val npo_lam_bot = result(); |
225 val npo_lam_bot = result(); |
226 |
226 |
227 val eq1::eq2::prems = goal CCL.thy |
227 val eq1::eq2::prems = goal CCL.thy |
228 "[| x=a; y=b; x[=y |] ==> a[=b"; |
228 "[| x=a; y=b; x[=y |] ==> a[=b"; |
229 br (eq1 RS subst) 1; |
229 by (rtac (eq1 RS subst) 1); |
230 br (eq2 RS subst) 1; |
230 by (rtac (eq2 RS subst) 1); |
231 brs prems 1; |
231 by (resolve_tac prems 1); |
232 val po_lemma = result(); |
232 val po_lemma = result(); |
233 |
233 |
234 goal CCL.thy "~ <a,b> [= lam x.f(x)"; |
234 goal CCL.thy "~ <a,b> [= lam x.f(x)"; |
235 br notI 1; |
235 by (rtac notI 1); |
236 br (npo_lam_bot RS notE) 1; |
236 by (rtac (npo_lam_bot RS notE) 1); |
237 be (case_pocong RS (caseBlam RS (caseBpair RS po_lemma))) 1; |
237 by (etac (case_pocong RS (caseBlam RS (caseBpair RS po_lemma))) 1); |
238 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1)); |
238 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1)); |
239 val npo_pair_lam = result(); |
239 val npo_pair_lam = result(); |
240 |
240 |
241 goal CCL.thy "~ lam x.f(x) [= <a,b>"; |
241 goal CCL.thy "~ lam x.f(x) [= <a,b>"; |
242 br notI 1; |
242 by (rtac notI 1); |
243 br (npo_lam_bot RS notE) 1; |
243 by (rtac (npo_lam_bot RS notE) 1); |
244 be (case_pocong RS (caseBpair RS (caseBlam RS po_lemma))) 1; |
244 by (etac (case_pocong RS (caseBpair RS (caseBlam RS po_lemma))) 1); |
245 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1)); |
245 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1)); |
246 val npo_lam_pair = result(); |
246 val npo_lam_pair = result(); |
247 |
247 |
248 fun mk_thm s = prove_goal CCL.thy s (fn _ => |
248 fun mk_thm s = prove_goal CCL.thy s (fn _ => |
249 [rtac notI 1,dtac case_pocong 1,etac rev_mp 5, |
249 [rtac notI 1,dtac case_pocong 1,etac rev_mp 5, |
258 "~ false [= lam x.f(x)","~ lam x.f(x) [= false"]; |
258 "~ false [= lam x.f(x)","~ lam x.f(x) [= false"]; |
259 |
259 |
260 (* Coinduction for [= *) |
260 (* Coinduction for [= *) |
261 |
261 |
262 val prems = goal CCL.thy "[| <t,u> : R; R <= POgen(R) |] ==> t [= u"; |
262 val prems = goal CCL.thy "[| <t,u> : R; R <= POgen(R) |] ==> t [= u"; |
263 br (PO_def RS def_coinduct RS (PO_iff RS iffD2)) 1; |
263 by (rtac (PO_def RS def_coinduct RS (PO_iff RS iffD2)) 1); |
264 by (REPEAT (ares_tac prems 1)); |
264 by (REPEAT (ares_tac prems 1)); |
265 val po_coinduct = result(); |
265 val po_coinduct = result(); |
266 |
266 |
267 fun po_coinduct_tac s i = res_inst_tac [("R",s)] po_coinduct i; |
267 fun po_coinduct_tac s i = res_inst_tac [("R",s)] po_coinduct i; |
268 |
268 |
269 (*************** EQUALITY *******************) |
269 (*************** EQUALITY *******************) |
270 |
270 |
271 goalw CCL.thy [EQgen_def,SIM_def] "mono(%X.EQgen(X))"; |
271 goalw CCL.thy [EQgen_def,SIM_def] "mono(%X.EQgen(X))"; |
272 br monoI 1; |
272 by (rtac monoI 1); |
273 by (safe_tac set_cs); |
273 by (safe_tac set_cs); |
274 by (REPEAT_SOME (resolve_tac [exI,conjI,refl])); |
274 by (REPEAT_SOME (resolve_tac [exI,conjI,refl])); |
275 by (ALLGOALS (simp_tac ccl_ss)); |
275 by (ALLGOALS (simp_tac ccl_ss)); |
276 by (ALLGOALS (fast_tac set_cs)); |
276 by (ALLGOALS (fast_tac set_cs)); |
277 val EQgen_mono = result(); |
277 val EQgen_mono = result(); |
279 goalw CCL.thy [EQgen_def,SIM_def] |
279 goalw CCL.thy [EQgen_def,SIM_def] |
280 "<t,t'> : EQgen(R) <-> (t=bot & t'=bot) | (t=true & t'=true) | \ |
280 "<t,t'> : EQgen(R) <-> (t=bot & t'=bot) | (t=true & t'=true) | \ |
281 \ (t=false & t'=false) | \ |
281 \ (t=false & t'=false) | \ |
282 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & <a,a'> : R & <b,b'> : R) | \ |
282 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & <a,a'> : R & <b,b'> : R) | \ |
283 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))"; |
283 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))"; |
284 br (iff_refl RS XHlemma2) 1; |
284 by (rtac (iff_refl RS XHlemma2) 1); |
285 val EQgenXH = result(); |
285 val EQgenXH = result(); |
286 |
286 |
287 goal CCL.thy |
287 goal CCL.thy |
288 "t=t' <-> (t=bot & t'=bot) | (t=true & t'=true) | (t=false & t'=false) | \ |
288 "t=t' <-> (t=bot & t'=bot) | (t=true & t'=true) | (t=false & t'=false) | \ |
289 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & a=a' & b=b') | \ |
289 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & a=a' & b=b') | \ |
290 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.f(x)=f'(x)))"; |
290 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.f(x)=f'(x)))"; |
291 by (subgoal_tac |
291 by (subgoal_tac |
292 "<t,t'> : EQ <-> (t=bot & t'=bot) | (t=true & t'=true) | (t=false & t'=false) | \ |
292 "<t,t'> : EQ <-> (t=bot & t'=bot) | (t=true & t'=true) | (t=false & t'=false) | \ |
293 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & <a,a'> : EQ & <b,b'> : EQ) | \ |
293 \ (EX a a' b b'.t=<a,b> & t'=<a',b'> & <a,a'> : EQ & <b,b'> : EQ) | \ |
294 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : EQ))" 1); |
294 \ (EX f f'.t=lam x.f(x) & t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : EQ))" 1); |
295 be rev_mp 1; |
295 by (etac rev_mp 1); |
296 by (simp_tac (CCL_ss addsimps [EQ_iff RS iff_sym]) 1); |
296 by (simp_tac (CCL_ss addsimps [EQ_iff RS iff_sym]) 1); |
297 br (rewrite_rule [EQgen_def,SIM_def] |
297 br (rewrite_rule [EQgen_def,SIM_def] |
298 (EQgen_mono RS (EQ_def RS def_gfp_Tarski) RS XHlemma1)) 1; |
298 (EQgen_mono RS (EQ_def RS def_gfp_Tarski) RS XHlemma1)) 1; |
299 br (iff_refl RS XHlemma2) 1; |
299 by (rtac (iff_refl RS XHlemma2) 1); |
300 val eqXH = result(); |
300 val eqXH = result(); |
301 |
301 |
302 val prems = goal CCL.thy "[| <t,u> : R; R <= EQgen(R) |] ==> t = u"; |
302 val prems = goal CCL.thy "[| <t,u> : R; R <= EQgen(R) |] ==> t = u"; |
303 br (EQ_def RS def_coinduct RS (EQ_iff RS iffD2)) 1; |
303 by (rtac (EQ_def RS def_coinduct RS (EQ_iff RS iffD2)) 1); |
304 by (REPEAT (ares_tac prems 1)); |
304 by (REPEAT (ares_tac prems 1)); |
305 val eq_coinduct = result(); |
305 val eq_coinduct = result(); |
306 |
306 |
307 val prems = goal CCL.thy |
307 val prems = goal CCL.thy |
308 "[| <t,u> : R; R <= EQgen(lfp(%x.EQgen(x) Un R Un EQ)) |] ==> t = u"; |
308 "[| <t,u> : R; R <= EQgen(lfp(%x.EQgen(x) Un R Un EQ)) |] ==> t = u"; |
309 br (EQ_def RS def_coinduct3 RS (EQ_iff RS iffD2)) 1; |
309 by (rtac (EQ_def RS def_coinduct3 RS (EQ_iff RS iffD2)) 1); |
310 by (REPEAT (ares_tac (EQgen_mono::prems) 1)); |
310 by (REPEAT (ares_tac (EQgen_mono::prems) 1)); |
311 val eq_coinduct3 = result(); |
311 val eq_coinduct3 = result(); |
312 |
312 |
313 fun eq_coinduct_tac s i = res_inst_tac [("R",s)] eq_coinduct i; |
313 fun eq_coinduct_tac s i = res_inst_tac [("R",s)] eq_coinduct i; |
314 fun eq_coinduct3_tac s i = res_inst_tac [("R",s)] eq_coinduct3 i; |
314 fun eq_coinduct3_tac s i = res_inst_tac [("R",s)] eq_coinduct3 i; |