changeset 4091 | 771b1f6422a8 |
parent 3840 | e0baea4d485a |
child 4152 | 451104c223e2 |
4090:9f1eaab75e8c | 4091:771b1f6422a8 |
---|---|
68 "[| !!x. x:set(D) ==> rel(D,x,x); \ |
68 "[| !!x. x:set(D) ==> rel(D,x,x); \ |
69 \ !!x y z. [| rel(D,x,y); rel(D,y,z); x:set(D); y:set(D); z:set(D)|] ==> \ |
69 \ !!x y z. [| rel(D,x,y); rel(D,y,z); x:set(D); y:set(D); z:set(D)|] ==> \ |
70 \ rel(D,x,z); \ |
70 \ rel(D,x,z); \ |
71 \ !!x y. [| rel(D,x,y); rel(D,y,x); x:set(D); y:set(D)|] ==> x=y |] ==> \ |
71 \ !!x y. [| rel(D,x,y); rel(D,y,x); x:set(D); y:set(D)|] ==> x=y |] ==> \ |
72 \ po(D)"; |
72 \ po(D)"; |
73 by (safe_tac (!claset)); |
73 by (safe_tac (claset())); |
74 brr prems 1; |
74 brr prems 1; |
75 qed "poI"; |
75 qed "poI"; |
76 |
76 |
77 val prems = goalw Limit.thy [cpo_def] |
77 val prems = goalw Limit.thy [cpo_def] |
78 "[| po(D); !!X. chain(D,X) ==> islub(D,X,x(D,X))|] ==> cpo(D)"; |
78 "[| po(D); !!X. chain(D,X) ==> islub(D,X,x(D,X))|] ==> cpo(D)"; |
79 by (safe_tac (!claset addSIs [exI])); |
79 by (safe_tac (claset() addSIs [exI])); |
80 brr prems 1; |
80 brr prems 1; |
81 qed "cpoI"; |
81 qed "cpoI"; |
82 |
82 |
83 val [cpo] = goalw Limit.thy [cpo_def] "cpo(D) ==> po(D)"; |
83 val [cpo] = goalw Limit.thy [cpo_def] "cpo(D) ==> po(D)"; |
84 by (rtac (cpo RS conjunct1) 1); |
84 by (rtac (cpo RS conjunct1) 1); |
114 (* Theorems about isub and islub. *) |
114 (* Theorems about isub and islub. *) |
115 (*----------------------------------------------------------------------*) |
115 (*----------------------------------------------------------------------*) |
116 |
116 |
117 val prems = goalw Limit.thy [islub_def] (* islub_isub *) |
117 val prems = goalw Limit.thy [islub_def] (* islub_isub *) |
118 "islub(D,X,x) ==> isub(D,X,x)"; |
118 "islub(D,X,x) ==> isub(D,X,x)"; |
119 by (simp_tac (!simpset addsimps prems) 1); |
119 by (simp_tac (simpset() addsimps prems) 1); |
120 qed "islub_isub"; |
120 qed "islub_isub"; |
121 |
121 |
122 val prems = goal Limit.thy |
122 val prems = goal Limit.thy |
123 "islub(D,X,x) ==> x:set(D)"; |
123 "islub(D,X,x) ==> x:set(D)"; |
124 by (rtac (rewrite_rule[islub_def,isub_def](hd prems) RS conjunct1 RS conjunct1) 1); |
124 by (rtac (rewrite_rule[islub_def,isub_def](hd prems) RS conjunct1 RS conjunct1) 1); |
137 by (resolve_tac prems 1); |
137 by (resolve_tac prems 1); |
138 qed "islub_least"; |
138 qed "islub_least"; |
139 |
139 |
140 val prems = goalw Limit.thy [islub_def] (* islubI *) |
140 val prems = goalw Limit.thy [islub_def] (* islubI *) |
141 "[|isub(D,X,x); !!y. isub(D,X,y) ==> rel(D,x,y)|] ==> islub(D,X,x)"; |
141 "[|isub(D,X,x); !!y. isub(D,X,y) ==> rel(D,x,y)|] ==> islub(D,X,x)"; |
142 by (safe_tac (!claset)); |
142 by (safe_tac (claset())); |
143 by (REPEAT(ares_tac prems 1)); |
143 by (REPEAT(ares_tac prems 1)); |
144 qed "islubI"; |
144 qed "islubI"; |
145 |
145 |
146 val prems = goalw Limit.thy [isub_def] (* isubI *) |
146 val prems = goalw Limit.thy [isub_def] (* isubI *) |
147 "[|x:set(D); !!n. n:nat ==> rel(D,X`n,x)|] ==> isub(D,X,x)"; |
147 "[|x:set(D); !!n. n:nat ==> rel(D,X`n,x)|] ==> isub(D,X,x)"; |
148 by (safe_tac (!claset)); |
148 by (safe_tac (claset())); |
149 by (REPEAT(ares_tac prems 1)); |
149 by (REPEAT(ares_tac prems 1)); |
150 qed "isubI"; |
150 qed "isubI"; |
151 |
151 |
152 val prems = goalw Limit.thy [isub_def] (* isubE *) |
152 val prems = goalw Limit.thy [isub_def] (* isubE *) |
153 "!!z.[|isub(D,X,x);[|x:set(D); !!n. n:nat==>rel(D,X`n,x)|] ==> P|] ==> P"; |
153 "!!z.[|isub(D,X,x);[|x:set(D); !!n. n:nat==>rel(D,X`n,x)|] ==> P|] ==> P"; |
154 by (safe_tac (!claset)); |
154 by (safe_tac (claset())); |
155 by (Asm_simp_tac 1); |
155 by (Asm_simp_tac 1); |
156 qed "isubE"; |
156 qed "isubE"; |
157 |
157 |
158 val prems = goalw Limit.thy [isub_def] (* isubD1 *) |
158 val prems = goalw Limit.thy [isub_def] (* isubD1 *) |
159 "isub(D,X,x) ==> x:set(D)"; |
159 "isub(D,X,x) ==> x:set(D)"; |
160 by (simp_tac (!simpset addsimps prems) 1); |
160 by (simp_tac (simpset() addsimps prems) 1); |
161 qed "isubD1"; |
161 qed "isubD1"; |
162 |
162 |
163 val prems = goalw Limit.thy [isub_def] (* isubD2 *) |
163 val prems = goalw Limit.thy [isub_def] (* isubD2 *) |
164 "[|isub(D,X,x); n:nat|]==>rel(D,X`n,x)"; |
164 "[|isub(D,X,x); n:nat|]==>rel(D,X`n,x)"; |
165 by (simp_tac (!simpset addsimps prems) 1); |
165 by (simp_tac (simpset() addsimps prems) 1); |
166 qed "isubD2"; |
166 qed "isubD2"; |
167 |
167 |
168 val prems = goal Limit.thy |
168 val prems = goal Limit.thy |
169 "!!z. [|islub(D,X,x); islub(D,X,y); cpo(D)|] ==> x = y"; |
169 "!!z. [|islub(D,X,x); islub(D,X,y); cpo(D)|] ==> x = y"; |
170 by (etac cpo_antisym 1); |
170 by (etac cpo_antisym 1); |
196 "!!z.[|X:nat->set(D); !!n. n:nat ==> rel(D,X`n,X`succ(n))|] ==> chain(D,X)" |
196 "!!z.[|X:nat->set(D); !!n. n:nat ==> rel(D,X`n,X`succ(n))|] ==> chain(D,X)" |
197 (fn prems => [Asm_simp_tac 1]); |
197 (fn prems => [Asm_simp_tac 1]); |
198 |
198 |
199 val prems = goalw Limit.thy [chain_def] |
199 val prems = goalw Limit.thy [chain_def] |
200 "chain(D,X) ==> X : nat -> set(D)"; |
200 "chain(D,X) ==> X : nat -> set(D)"; |
201 by (asm_simp_tac (!simpset addsimps prems) 1); |
201 by (asm_simp_tac (simpset() addsimps prems) 1); |
202 qed "chain_fun"; |
202 qed "chain_fun"; |
203 |
203 |
204 val prems = goalw Limit.thy [chain_def] |
204 val prems = goalw Limit.thy [chain_def] |
205 "[|chain(D,X); n:nat|] ==> X`n : set(D)"; |
205 "[|chain(D,X); n:nat|] ==> X`n : set(D)"; |
206 by (rtac ((hd prems)RS conjunct1 RS apply_type) 1); |
206 by (rtac ((hd prems)RS conjunct1 RS apply_type) 1); |
234 "[|n le m; chain(D,X); cpo(D); n:nat; m:nat|] ==> rel(D,X`n,X`m)"; |
234 "[|n le m; chain(D,X); cpo(D); n:nat; m:nat|] ==> rel(D,X`n,X`m)"; |
235 by (rtac impE 1); (* The first three steps prepare for the induction proof *) |
235 by (rtac impE 1); (* The first three steps prepare for the induction proof *) |
236 by (assume_tac 3); |
236 by (assume_tac 3); |
237 by (rtac (hd prems) 2); |
237 by (rtac (hd prems) 2); |
238 by (res_inst_tac [("n","m")] nat_induct 1); |
238 by (res_inst_tac [("n","m")] nat_induct 1); |
239 by (safe_tac (!claset)); |
239 by (safe_tac (claset())); |
240 by (asm_full_simp_tac (!simpset addsimps prems) 2); |
240 by (asm_full_simp_tac (simpset() addsimps prems) 2); |
241 by (rtac cpo_trans 4); |
241 by (rtac cpo_trans 4); |
242 by (rtac (le_succ_eq RS subst) 3); |
242 by (rtac (le_succ_eq RS subst) 3); |
243 brr(cpo_refl::chain_in::chain_rel::nat_0I::nat_succI::prems) 1; |
243 brr(cpo_refl::chain_in::chain_rel::nat_0I::nat_succI::prems) 1; |
244 qed "chain_rel_gen"; |
244 qed "chain_rel_gen"; |
245 |
245 |
262 |
262 |
263 val prems = goalw Limit.thy [pcpo_def] (* pcpo_bot_ex1 *) |
263 val prems = goalw Limit.thy [pcpo_def] (* pcpo_bot_ex1 *) |
264 "pcpo(D) ==> EX! x. x:set(D) & (ALL y:set(D). rel(D,x,y))"; |
264 "pcpo(D) ==> EX! x. x:set(D) & (ALL y:set(D). rel(D,x,y))"; |
265 by (rtac (hd prems RS conjunct2 RS bexE) 1); |
265 by (rtac (hd prems RS conjunct2 RS bexE) 1); |
266 by (rtac ex1I 1); |
266 by (rtac ex1I 1); |
267 by (safe_tac (!claset)); |
267 by (safe_tac (claset())); |
268 by (assume_tac 1); |
268 by (assume_tac 1); |
269 by (etac bspec 1); |
269 by (etac bspec 1); |
270 by (assume_tac 1); |
270 by (assume_tac 1); |
271 by (rtac cpo_antisym 1); |
271 by (rtac cpo_antisym 1); |
272 by (rtac (hd prems RS conjunct1) 1); |
272 by (rtac (hd prems RS conjunct1) 1); |
309 "[|x:set(D); cpo(D)|] ==> chain(D,(lam n:nat. x))"; |
309 "[|x:set(D); cpo(D)|] ==> chain(D,(lam n:nat. x))"; |
310 by (rtac conjI 1); |
310 by (rtac conjI 1); |
311 by (rtac lam_type 1); |
311 by (rtac lam_type 1); |
312 by (resolve_tac prems 1); |
312 by (resolve_tac prems 1); |
313 by (rtac ballI 1); |
313 by (rtac ballI 1); |
314 by (asm_simp_tac (!simpset addsimps [nat_succI]) 1); |
314 by (asm_simp_tac (simpset() addsimps [nat_succI]) 1); |
315 brr(cpo_refl::prems) 1; |
315 brr(cpo_refl::prems) 1; |
316 qed "chain_const"; |
316 qed "chain_const"; |
317 |
317 |
318 goalw Limit.thy [islub_def,isub_def] (* islub_const *) |
318 goalw Limit.thy [islub_def,isub_def] (* islub_const *) |
319 "!!x D. [|x:set(D); cpo(D)|] ==> islub(D,(lam n:nat. x),x)"; |
319 "!!x D. [|x:set(D); cpo(D)|] ==> islub(D,(lam n:nat. x),x)"; |
335 (* Taking the suffix of chains has no effect on ub's. *) |
335 (* Taking the suffix of chains has no effect on ub's. *) |
336 (*----------------------------------------------------------------------*) |
336 (*----------------------------------------------------------------------*) |
337 |
337 |
338 val prems = goalw Limit.thy [isub_def,suffix_def] (* isub_suffix *) |
338 val prems = goalw Limit.thy [isub_def,suffix_def] (* isub_suffix *) |
339 "[|chain(D,X); cpo(D); n:nat|] ==> isub(D,suffix(X,n),x) <-> isub(D,X,x)"; |
339 "[|chain(D,X); cpo(D); n:nat|] ==> isub(D,suffix(X,n),x) <-> isub(D,X,x)"; |
340 by (simp_tac (!simpset addsimps prems) 1); |
340 by (simp_tac (simpset() addsimps prems) 1); |
341 by (safe_tac (!claset)); |
341 by (safe_tac (claset())); |
342 by (dtac bspec 2); |
342 by (dtac bspec 2); |
343 by (assume_tac 3); (* to instantiate unknowns properly *) |
343 by (assume_tac 3); (* to instantiate unknowns properly *) |
344 by (rtac cpo_trans 1); |
344 by (rtac cpo_trans 1); |
345 by (rtac chain_rel_gen_add 2); |
345 by (rtac chain_rel_gen_add 2); |
346 by (dtac bspec 6); |
346 by (dtac bspec 6); |
348 brr(chain_in::add_type::prems) 1; |
348 brr(chain_in::add_type::prems) 1; |
349 qed "isub_suffix"; |
349 qed "isub_suffix"; |
350 |
350 |
351 val prems = goalw Limit.thy [islub_def] (* islub_suffix *) |
351 val prems = goalw Limit.thy [islub_def] (* islub_suffix *) |
352 "[|chain(D,X); cpo(D); n:nat|] ==> islub(D,suffix(X,n),x) <-> islub(D,X,x)"; |
352 "[|chain(D,X); cpo(D); n:nat|] ==> islub(D,suffix(X,n),x) <-> islub(D,X,x)"; |
353 by (asm_simp_tac (!simpset addsimps isub_suffix::prems) 1); |
353 by (asm_simp_tac (simpset() addsimps isub_suffix::prems) 1); |
354 qed "islub_suffix"; |
354 qed "islub_suffix"; |
355 |
355 |
356 val prems = goalw Limit.thy [lub_def] (* lub_suffix *) |
356 val prems = goalw Limit.thy [lub_def] (* lub_suffix *) |
357 "[|chain(D,X); cpo(D); n:nat|] ==> lub(D,suffix(X,n)) = lub(D,X)"; |
357 "[|chain(D,X); cpo(D); n:nat|] ==> lub(D,suffix(X,n)) = lub(D,X)"; |
358 by (asm_simp_tac (!simpset addsimps islub_suffix::prems) 1); |
358 by (asm_simp_tac (simpset() addsimps islub_suffix::prems) 1); |
359 qed "lub_suffix"; |
359 qed "lub_suffix"; |
360 |
360 |
361 (*----------------------------------------------------------------------*) |
361 (*----------------------------------------------------------------------*) |
362 (* Dominate and subchain. *) |
362 (* Dominate and subchain. *) |
363 (*----------------------------------------------------------------------*) |
363 (*----------------------------------------------------------------------*) |
436 (* Matrix. *) |
436 (* Matrix. *) |
437 (*----------------------------------------------------------------------*) |
437 (*----------------------------------------------------------------------*) |
438 |
438 |
439 val prems = goalw Limit.thy [matrix_def] (* matrix_fun *) |
439 val prems = goalw Limit.thy [matrix_def] (* matrix_fun *) |
440 "matrix(D,M) ==> M : nat -> (nat -> set(D))"; |
440 "matrix(D,M) ==> M : nat -> (nat -> set(D))"; |
441 by (simp_tac (!simpset addsimps prems) 1); |
441 by (simp_tac (simpset() addsimps prems) 1); |
442 qed "matrix_fun"; |
442 qed "matrix_fun"; |
443 |
443 |
444 val prems = goalw Limit.thy [] (* matrix_in_fun *) |
444 val prems = goalw Limit.thy [] (* matrix_in_fun *) |
445 "[|matrix(D,M); n:nat|] ==> M`n : nat -> set(D)"; |
445 "[|matrix(D,M); n:nat|] ==> M`n : nat -> set(D)"; |
446 by (rtac apply_type 1); |
446 by (rtac apply_type 1); |
453 by (REPEAT(resolve_tac(matrix_in_fun::prems) 1)); |
453 by (REPEAT(resolve_tac(matrix_in_fun::prems) 1)); |
454 qed "matrix_in"; |
454 qed "matrix_in"; |
455 |
455 |
456 val prems = goalw Limit.thy [matrix_def] (* matrix_rel_1_0 *) |
456 val prems = goalw Limit.thy [matrix_def] (* matrix_rel_1_0 *) |
457 "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`m)"; |
457 "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`m)"; |
458 by (simp_tac (!simpset addsimps prems) 1); |
458 by (simp_tac (simpset() addsimps prems) 1); |
459 qed "matrix_rel_1_0"; |
459 qed "matrix_rel_1_0"; |
460 |
460 |
461 val prems = goalw Limit.thy [matrix_def] (* matrix_rel_0_1 *) |
461 val prems = goalw Limit.thy [matrix_def] (* matrix_rel_0_1 *) |
462 "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`n`succ(m))"; |
462 "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`n`succ(m))"; |
463 by (simp_tac (!simpset addsimps prems) 1); |
463 by (simp_tac (simpset() addsimps prems) 1); |
464 qed "matrix_rel_0_1"; |
464 qed "matrix_rel_0_1"; |
465 |
465 |
466 val prems = goalw Limit.thy [matrix_def] (* matrix_rel_1_1 *) |
466 val prems = goalw Limit.thy [matrix_def] (* matrix_rel_1_1 *) |
467 "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`succ(m))"; |
467 "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`succ(m))"; |
468 by (simp_tac (!simpset addsimps prems) 1); |
468 by (simp_tac (simpset() addsimps prems) 1); |
469 qed "matrix_rel_1_1"; |
469 qed "matrix_rel_1_1"; |
470 |
470 |
471 val prems = goal Limit.thy (* fun_swap *) |
471 val prems = goal Limit.thy (* fun_swap *) |
472 "f:X->Y->Z ==> (lam y:Y. lam x:X. f`x`y):Y->X->Z"; |
472 "f:X->Y->Z ==> (lam y:Y. lam x:X. f`x`y):Y->X->Z"; |
473 by (rtac lam_type 1); |
473 by (rtac lam_type 1); |
477 by (REPEAT(ares_tac prems 1)); |
477 by (REPEAT(ares_tac prems 1)); |
478 qed "fun_swap"; |
478 qed "fun_swap"; |
479 |
479 |
480 val prems = goalw Limit.thy [matrix_def] (* matrix_sym_axis *) |
480 val prems = goalw Limit.thy [matrix_def] (* matrix_sym_axis *) |
481 "!!z. matrix(D,M) ==> matrix(D,lam m:nat. lam n:nat. M`n`m)"; |
481 "!!z. matrix(D,M) ==> matrix(D,lam m:nat. lam n:nat. M`n`m)"; |
482 by (Simp_tac 1 THEN safe_tac (!claset) THEN |
482 by (Simp_tac 1 THEN safe_tac (claset()) THEN |
483 REPEAT(asm_simp_tac (!simpset addsimps [fun_swap]) 1)); |
483 REPEAT(asm_simp_tac (simpset() addsimps [fun_swap]) 1)); |
484 qed "matrix_sym_axis"; |
484 qed "matrix_sym_axis"; |
485 |
485 |
486 val prems = goalw Limit.thy [chain_def] (* matrix_chain_diag *) |
486 val prems = goalw Limit.thy [chain_def] (* matrix_chain_diag *) |
487 "matrix(D,M) ==> chain(D,lam n:nat. M`n`n)"; |
487 "matrix(D,M) ==> chain(D,lam n:nat. M`n`n)"; |
488 by (safe_tac (!claset)); |
488 by (safe_tac (claset())); |
489 by (rtac lam_type 1); |
489 by (rtac lam_type 1); |
490 by (rtac matrix_in 1); |
490 by (rtac matrix_in 1); |
491 by (REPEAT(ares_tac prems 1)); |
491 by (REPEAT(ares_tac prems 1)); |
492 by (Asm_simp_tac 1); |
492 by (Asm_simp_tac 1); |
493 by (rtac matrix_rel_1_1 1); |
493 by (rtac matrix_rel_1_1 1); |
494 by (REPEAT(ares_tac prems 1)); |
494 by (REPEAT(ares_tac prems 1)); |
495 qed "matrix_chain_diag"; |
495 qed "matrix_chain_diag"; |
496 |
496 |
497 val prems = goalw Limit.thy [chain_def] (* matrix_chain_left *) |
497 val prems = goalw Limit.thy [chain_def] (* matrix_chain_left *) |
498 "[|matrix(D,M); n:nat|] ==> chain(D,M`n)"; |
498 "[|matrix(D,M); n:nat|] ==> chain(D,M`n)"; |
499 by (safe_tac (!claset)); |
499 by (safe_tac (claset())); |
500 by (rtac apply_type 1); |
500 by (rtac apply_type 1); |
501 by (rtac matrix_fun 1); |
501 by (rtac matrix_fun 1); |
502 by (REPEAT(ares_tac prems 1)); |
502 by (REPEAT(ares_tac prems 1)); |
503 by (rtac matrix_rel_0_1 1); |
503 by (rtac matrix_rel_0_1 1); |
504 by (REPEAT(ares_tac prems 1)); |
504 by (REPEAT(ares_tac prems 1)); |
505 qed "matrix_chain_left"; |
505 qed "matrix_chain_left"; |
506 |
506 |
507 val prems = goalw Limit.thy [chain_def] (* matrix_chain_right *) |
507 val prems = goalw Limit.thy [chain_def] (* matrix_chain_right *) |
508 "[|matrix(D,M); m:nat|] ==> chain(D,lam n:nat. M`n`m)"; |
508 "[|matrix(D,M); m:nat|] ==> chain(D,lam n:nat. M`n`m)"; |
509 by (safe_tac (!claset)); |
509 by (safe_tac (claset())); |
510 by (asm_simp_tac(!simpset addsimps prems) 2); |
510 by (asm_simp_tac(simpset() addsimps prems) 2); |
511 brr(lam_type::matrix_in::matrix_rel_1_0::prems) 1; |
511 brr(lam_type::matrix_in::matrix_rel_1_0::prems) 1; |
512 qed "matrix_chain_right"; |
512 qed "matrix_chain_right"; |
513 |
513 |
514 val prems = goalw Limit.thy [matrix_def] (* matrix_chainI *) |
514 val prems = goalw Limit.thy [matrix_def] (* matrix_chainI *) |
515 "[|!!x. x:nat==>chain(D,M`x); !!y. y:nat==>chain(D,lam x:nat. M`x`y); \ |
515 "[|!!x. x:nat==>chain(D,M`x); !!y. y:nat==>chain(D,lam x:nat. M`x`y); \ |
516 \ M:nat->nat->set(D); cpo(D)|] ==> matrix(D,M)"; |
516 \ M:nat->nat->set(D); cpo(D)|] ==> matrix(D,M)"; |
517 by (safe_tac (!claset addSIs [ballI])); |
517 by (safe_tac (claset() addSIs [ballI])); |
518 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 2); |
518 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 2); |
519 by (Asm_full_simp_tac 4); |
519 by (Asm_full_simp_tac 4); |
520 by (rtac cpo_trans 5); |
520 by (rtac cpo_trans 5); |
521 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 6); |
521 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 6); |
522 by (Asm_full_simp_tac 8); |
522 by (Asm_full_simp_tac 8); |
535 |
535 |
536 val prems = goalw Limit.thy [] (* isub_lemma *) |
536 val prems = goalw Limit.thy [] (* isub_lemma *) |
537 "[|isub(D,(lam n:nat. M`n`n),y); matrix(D,M); cpo(D)|] ==> \ |
537 "[|isub(D,(lam n:nat. M`n`n),y); matrix(D,M); cpo(D)|] ==> \ |
538 \ isub(D,(lam n:nat. lub(D,lam m:nat. M`n`m)),y)"; |
538 \ isub(D,(lam n:nat. lub(D,lam m:nat. M`n`m)),y)"; |
539 by (rewtac isub_def); |
539 by (rewtac isub_def); |
540 by (safe_tac (!claset)); |
540 by (safe_tac (claset())); |
541 by (rtac isubD1 1); |
541 by (rtac isubD1 1); |
542 by (resolve_tac prems 1); |
542 by (resolve_tac prems 1); |
543 by (Asm_simp_tac 1); |
543 by (Asm_simp_tac 1); |
544 by (cut_inst_tac[("a","n")](hd(tl prems) RS matrix_fun RS apply_type) 1); |
544 by (cut_inst_tac[("a","n")](hd(tl prems) RS matrix_fun RS apply_type) 1); |
545 by (assume_tac 1); |
545 by (assume_tac 1); |
549 by (rtac matrix_chain_left 1); |
549 by (rtac matrix_chain_left 1); |
550 by (resolve_tac prems 1); |
550 by (resolve_tac prems 1); |
551 by (assume_tac 1); |
551 by (assume_tac 1); |
552 by (resolve_tac prems 1); |
552 by (resolve_tac prems 1); |
553 by (rewtac isub_def); |
553 by (rewtac isub_def); |
554 by (safe_tac (!claset)); |
554 by (safe_tac (claset())); |
555 by (rtac isubD1 1); |
555 by (rtac isubD1 1); |
556 by (resolve_tac prems 1); |
556 by (resolve_tac prems 1); |
557 by (cut_inst_tac[("P","n le na")]excluded_middle 1); |
557 by (cut_inst_tac[("P","n le na")]excluded_middle 1); |
558 by (safe_tac (!claset)); |
558 by (safe_tac (claset())); |
559 by (rtac cpo_trans 1); |
559 by (rtac cpo_trans 1); |
560 by (resolve_tac prems 1); |
560 by (resolve_tac prems 1); |
561 by (rtac (not_le_iff_lt RS iffD1 RS leI RS chain_rel_gen) 1); |
561 by (rtac (not_le_iff_lt RS iffD1 RS leI RS chain_rel_gen) 1); |
562 by (assume_tac 3); |
562 by (assume_tac 3); |
563 by (REPEAT(ares_tac (nat_into_Ord::matrix_chain_left::prems) 1)); |
563 by (REPEAT(ares_tac (nat_into_Ord::matrix_chain_left::prems) 1)); |
573 ([chain_rel_gen,matrix_chain_right,matrix_in,isubD1]@prems) 1)); |
573 ([chain_rel_gen,matrix_chain_right,matrix_in,isubD1]@prems) 1)); |
574 qed "isub_lemma"; |
574 qed "isub_lemma"; |
575 |
575 |
576 val prems = goalw Limit.thy [chain_def] (* matrix_chain_lub *) |
576 val prems = goalw Limit.thy [chain_def] (* matrix_chain_lub *) |
577 "[|matrix(D,M); cpo(D)|] ==> chain(D,lam n:nat. lub(D,lam m:nat. M`n`m))"; |
577 "[|matrix(D,M); cpo(D)|] ==> chain(D,lam n:nat. lub(D,lam m:nat. M`n`m))"; |
578 by (safe_tac (!claset)); |
578 by (safe_tac (claset())); |
579 by (rtac lam_type 1); |
579 by (rtac lam_type 1); |
580 by (rtac islub_in 1); |
580 by (rtac islub_in 1); |
581 by (rtac cpo_lub 1); |
581 by (rtac cpo_lub 1); |
582 by (resolve_tac prems 2); |
582 by (resolve_tac prems 2); |
583 by (Asm_simp_tac 2); |
583 by (Asm_simp_tac 2); |
585 by (rtac lam_type 1); |
585 by (rtac lam_type 1); |
586 by (REPEAT(ares_tac (matrix_in::prems) 1)); |
586 by (REPEAT(ares_tac (matrix_in::prems) 1)); |
587 by (Asm_simp_tac 1); |
587 by (Asm_simp_tac 1); |
588 by (rtac matrix_rel_0_1 1); |
588 by (rtac matrix_rel_0_1 1); |
589 by (REPEAT(ares_tac prems 1)); |
589 by (REPEAT(ares_tac prems 1)); |
590 by (asm_simp_tac (!simpset addsimps |
590 by (asm_simp_tac (simpset() addsimps |
591 [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1); |
591 [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1); |
592 by (rtac dominate_islub 1); |
592 by (rtac dominate_islub 1); |
593 by (rtac cpo_lub 3); |
593 by (rtac cpo_lub 3); |
594 by (rtac cpo_lub 2); |
594 by (rtac cpo_lub 2); |
595 by (rewtac dominate_def); |
595 by (rewtac dominate_def); |
611 by (rewtac dominate_def); |
611 by (rewtac dominate_def); |
612 by (rtac ballI 1); |
612 by (rtac ballI 1); |
613 by (rtac bexI 1); |
613 by (rtac bexI 1); |
614 by (assume_tac 2); |
614 by (assume_tac 2); |
615 by (Asm_simp_tac 1); |
615 by (Asm_simp_tac 1); |
616 by (asm_simp_tac (!simpset addsimps |
616 by (asm_simp_tac (simpset() addsimps |
617 [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1); |
617 [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1); |
618 by (rtac islub_ub 1); |
618 by (rtac islub_ub 1); |
619 by (rtac cpo_lub 1); |
619 by (rtac cpo_lub 1); |
620 by (REPEAT(ares_tac |
620 by (REPEAT(ares_tac |
621 (matrix_chain_left::matrix_chain_diag::chain_fun::matrix_chain_lub::prems) 1)); |
621 (matrix_chain_left::matrix_chain_diag::chain_fun::matrix_chain_lub::prems) 1)); |
635 |
635 |
636 val prems = goalw Limit.thy [] (* lub_matrix_diag *) |
636 val prems = goalw Limit.thy [] (* lub_matrix_diag *) |
637 "[|matrix(D,M); cpo(D)|] ==> \ |
637 "[|matrix(D,M); cpo(D)|] ==> \ |
638 \ lub(D,(lam n:nat. lub(D,lam m:nat. M`n`m))) = \ |
638 \ lub(D,(lam n:nat. lub(D,lam m:nat. M`n`m))) = \ |
639 \ lub(D,(lam n:nat. M`n`n))"; |
639 \ lub(D,(lam n:nat. M`n`n))"; |
640 by (simp_tac (!simpset addsimps [lemma1,lemma2]) 1); |
640 by (simp_tac (simpset() addsimps [lemma1,lemma2]) 1); |
641 by (rewtac islub_def); |
641 by (rewtac islub_def); |
642 by (simp_tac (!simpset addsimps [hd(tl prems) RS (hd prems RS isub_eq)]) 1); |
642 by (simp_tac (simpset() addsimps [hd(tl prems) RS (hd prems RS isub_eq)]) 1); |
643 qed "lub_matrix_diag"; |
643 qed "lub_matrix_diag"; |
644 |
644 |
645 val [matrix,cpo] = goalw Limit.thy [] (* lub_matrix_diag_sym *) |
645 val [matrix,cpo] = goalw Limit.thy [] (* lub_matrix_diag_sym *) |
646 "[|matrix(D,M); cpo(D)|] ==> \ |
646 "[|matrix(D,M); cpo(D)|] ==> \ |
647 \ lub(D,(lam m:nat. lub(D,lam n:nat. M`n`m))) = \ |
647 \ lub(D,(lam m:nat. lub(D,lam n:nat. M`n`m))) = \ |
656 |
656 |
657 val prems = goalw Limit.thy [mono_def] (* monoI *) |
657 val prems = goalw Limit.thy [mono_def] (* monoI *) |
658 "[|f:set(D)->set(E); \ |
658 "[|f:set(D)->set(E); \ |
659 \ !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y)|] ==> \ |
659 \ !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y)|] ==> \ |
660 \ f:mono(D,E)"; |
660 \ f:mono(D,E)"; |
661 by (fast_tac(!claset addSIs prems) 1); |
661 by (fast_tac(claset() addSIs prems) 1); |
662 qed "monoI"; |
662 qed "monoI"; |
663 |
663 |
664 val prems = goal Limit.thy |
664 val prems = goal Limit.thy |
665 "f:mono(D,E) ==> f:set(D)->set(E)"; |
665 "f:mono(D,E) ==> f:set(D)->set(E)"; |
666 by (rtac (rewrite_rule[mono_def](hd prems) RS CollectD1) 1); |
666 by (rtac (rewrite_rule[mono_def](hd prems) RS CollectD1) 1); |
681 val prems = goalw Limit.thy [cont_def,mono_def] (* contI *) |
681 val prems = goalw Limit.thy [cont_def,mono_def] (* contI *) |
682 "[|f:set(D)->set(E); \ |
682 "[|f:set(D)->set(E); \ |
683 \ !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y); \ |
683 \ !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y); \ |
684 \ !!X. chain(D,X) ==> f`lub(D,X) = lub(E,lam n:nat. f`(X`n))|] ==> \ |
684 \ !!X. chain(D,X) ==> f`lub(D,X) = lub(E,lam n:nat. f`(X`n))|] ==> \ |
685 \ f:cont(D,E)"; |
685 \ f:cont(D,E)"; |
686 by (fast_tac(!claset addSIs prems) 1); |
686 by (fast_tac(claset() addSIs prems) 1); |
687 qed "contI"; |
687 qed "contI"; |
688 |
688 |
689 val prems = goal Limit.thy |
689 val prems = goal Limit.thy |
690 "f:cont(D,E) ==> f:mono(D,E)"; |
690 "f:cont(D,E) ==> f:mono(D,E)"; |
691 by (rtac (rewrite_rule[cont_def](hd prems) RS CollectD1) 1); |
691 by (rtac (rewrite_rule[cont_def](hd prems) RS CollectD1) 1); |
720 |
720 |
721 val prems = goalw Limit.thy [] (* mono_chain *) |
721 val prems = goalw Limit.thy [] (* mono_chain *) |
722 "[|f:mono(D,E); chain(D,X)|] ==> chain(E,lam n:nat. f`(X`n))"; |
722 "[|f:mono(D,E); chain(D,X)|] ==> chain(E,lam n:nat. f`(X`n))"; |
723 by (rewtac chain_def); |
723 by (rewtac chain_def); |
724 by (Simp_tac 1); |
724 by (Simp_tac 1); |
725 by (safe_tac (!claset)); |
725 by (safe_tac (claset())); |
726 by (rtac lam_type 1); |
726 by (rtac lam_type 1); |
727 by (rtac mono_map 1); |
727 by (rtac mono_map 1); |
728 by (resolve_tac prems 1); |
728 by (resolve_tac prems 1); |
729 by (rtac chain_in 1); |
729 by (rtac chain_in 1); |
730 by (REPEAT(ares_tac prems 1)); |
730 by (REPEAT(ares_tac prems 1)); |
765 |
765 |
766 val prems = goal Limit.thy |
766 val prems = goal Limit.thy |
767 "[|!!x. x:set(D) ==> rel(E,f`x,g`x); f:cont(D,E); g:cont(D,E)|] ==> \ |
767 "[|!!x. x:set(D) ==> rel(E,f`x,g`x); f:cont(D,E); g:cont(D,E)|] ==> \ |
768 \ rel(cf(D,E),f,g)"; |
768 \ rel(cf(D,E),f,g)"; |
769 by (rtac rel_I 1); |
769 by (rtac rel_I 1); |
770 by (simp_tac (!simpset addsimps [cf_def]) 1); |
770 by (simp_tac (simpset() addsimps [cf_def]) 1); |
771 by (safe_tac (!claset)); |
771 by (safe_tac (claset())); |
772 brr prems 1; |
772 brr prems 1; |
773 qed "rel_cfI"; |
773 qed "rel_cfI"; |
774 |
774 |
775 val prems = goalw Limit.thy [rel_def,cf_def] |
775 val prems = goalw Limit.thy [rel_def,cf_def] |
776 "!!z. [|rel(cf(D,E),f,g); x:set(D)|] ==> rel(E,f`x,g`x)"; |
776 "!!z. [|rel(cf(D,E),f,g); x:set(D)|] ==> rel(E,f`x,g`x)"; |
843 by (Asm_simp_tac 1); |
843 by (Asm_simp_tac 1); |
844 by (REPEAT(ares_tac ((chain_in RS cf_cont RS cont_mono)::prems) 1)); |
844 by (REPEAT(ares_tac ((chain_in RS cf_cont RS cont_mono)::prems) 1)); |
845 by (REPEAT(ares_tac ((chain_cf RS chain_fun)::prems) 1)); |
845 by (REPEAT(ares_tac ((chain_cf RS chain_fun)::prems) 1)); |
846 by (stac beta 1); |
846 by (stac beta 1); |
847 by (REPEAT(ares_tac((cpo_lub RS islub_in)::prems) 1)); |
847 by (REPEAT(ares_tac((cpo_lub RS islub_in)::prems) 1)); |
848 by (asm_simp_tac(!simpset addsimps[hd prems RS chain_in RS cf_cont RS cont_lub]) 1); |
848 by (asm_simp_tac(simpset() addsimps[hd prems RS chain_in RS cf_cont RS cont_lub]) 1); |
849 by (forward_tac[hd prems RS matrix_lemma RS lub_matrix_diag]1); |
849 by (forward_tac[hd prems RS matrix_lemma RS lub_matrix_diag]1); |
850 brr prems 1; |
850 brr prems 1; |
851 by (Asm_full_simp_tac 1); |
851 by (Asm_full_simp_tac 1); |
852 by (asm_simp_tac(!simpset addsimps[chain_in RS beta]) 1); |
852 by (asm_simp_tac(simpset() addsimps[chain_in RS beta]) 1); |
853 by (dtac (hd prems RS matrix_lemma RS lub_matrix_diag_sym) 1); |
853 by (dtac (hd prems RS matrix_lemma RS lub_matrix_diag_sym) 1); |
854 brr prems 1; |
854 brr prems 1; |
855 by (Asm_full_simp_tac 1); |
855 by (Asm_full_simp_tac 1); |
856 qed "chain_cf_lub_cont"; |
856 qed "chain_cf_lub_cont"; |
857 |
857 |
918 val prems = goal Limit.thy (* const_cont *) |
918 val prems = goal Limit.thy (* const_cont *) |
919 "[|y:set(E); cpo(D); cpo(E)|] ==> (lam x:set(D).y) : cont(D,E)"; |
919 "[|y:set(E); cpo(D); cpo(E)|] ==> (lam x:set(D).y) : cont(D,E)"; |
920 by (rtac contI 1); |
920 by (rtac contI 1); |
921 by (Asm_simp_tac 2); |
921 by (Asm_simp_tac 2); |
922 brr(lam_type::cpo_refl::prems) 1; |
922 brr(lam_type::cpo_refl::prems) 1; |
923 by (asm_simp_tac(!simpset addsimps(chain_in::(cpo_lub RS islub_in):: |
923 by (asm_simp_tac(simpset() addsimps(chain_in::(cpo_lub RS islub_in):: |
924 lub_const::prems)) 1); |
924 lub_const::prems)) 1); |
925 qed "const_cont"; |
925 qed "const_cont"; |
926 |
926 |
927 val prems = goal Limit.thy (* cf_least *) |
927 val prems = goal Limit.thy (* cf_least *) |
928 "[|cpo(D); pcpo(E); y:cont(D,E)|]==>rel(cf(D,E),(lam x:set(D).bot(E)),y)"; |
928 "[|cpo(D); pcpo(E); y:cont(D,E)|]==>rel(cf(D,E),(lam x:set(D).bot(E)),y)"; |
949 (*----------------------------------------------------------------------*) |
949 (*----------------------------------------------------------------------*) |
950 (* Identity and composition. *) |
950 (* Identity and composition. *) |
951 (*----------------------------------------------------------------------*) |
951 (*----------------------------------------------------------------------*) |
952 |
952 |
953 val id_thm = prove_goalw Perm.thy [id_def] "x:X ==> (id(X)`x) = x" |
953 val id_thm = prove_goalw Perm.thy [id_def] "x:X ==> (id(X)`x) = x" |
954 (fn prems => [simp_tac(!simpset addsimps prems) 1]); |
954 (fn prems => [simp_tac(simpset() addsimps prems) 1]); |
955 |
955 |
956 val prems = goal Limit.thy (* id_cont *) |
956 val prems = goal Limit.thy (* id_cont *) |
957 "cpo(D) ==> id(set(D)):cont(D,D)"; |
957 "cpo(D) ==> id(set(D)):cont(D,D)"; |
958 by (rtac contI 1); |
958 by (rtac contI 1); |
959 by (rtac id_type 1); |
959 by (rtac id_type 1); |
960 by (asm_simp_tac (!simpset addsimps[id_thm]) 1); |
960 by (asm_simp_tac (simpset() addsimps[id_thm]) 1); |
961 by (asm_simp_tac(!simpset addsimps(id_thm::(cpo_lub RS islub_in):: |
961 by (asm_simp_tac(simpset() addsimps(id_thm::(cpo_lub RS islub_in):: |
962 chain_in::(chain_fun RS eta)::prems)) 1); |
962 chain_in::(chain_fun RS eta)::prems)) 1); |
963 qed "id_cont"; |
963 qed "id_cont"; |
964 |
964 |
965 val comp_cont_apply = cont_fun RSN(2,cont_fun RS comp_fun_apply); |
965 val comp_cont_apply = cont_fun RSN(2,cont_fun RS comp_fun_apply); |
966 |
966 |
973 by (rtac cont_mono 9); (* 15 subgoals *) |
973 by (rtac cont_mono 9); (* 15 subgoals *) |
974 brr(comp_fun::cont_fun::cont_map::prems) 1; (* proves all but the lub case *) |
974 brr(comp_fun::cont_fun::cont_map::prems) 1; (* proves all but the lub case *) |
975 by (stac comp_cont_apply 1); |
975 by (stac comp_cont_apply 1); |
976 by (stac cont_lub 4); |
976 by (stac cont_lub 4); |
977 by (stac cont_lub 6); |
977 by (stac cont_lub 6); |
978 by (asm_full_simp_tac(!simpset addsimps (* RS: new subgoals contain unknowns *) |
978 by (asm_full_simp_tac(simpset() addsimps (* RS: new subgoals contain unknowns *) |
979 [hd prems RS (hd(tl prems) RS comp_cont_apply),chain_in]) 8); |
979 [hd prems RS (hd(tl prems) RS comp_cont_apply),chain_in]) 8); |
980 brr((cpo_lub RS islub_in)::cont_chain::prems) 1; |
980 brr((cpo_lub RS islub_in)::cont_chain::prems) 1; |
981 qed "comp_pres_cont"; |
981 qed "comp_pres_cont"; |
982 |
982 |
983 val prems = goal Limit.thy (* comp_mono *) |
983 val prems = goal Limit.thy (* comp_mono *) |
1012 by (rtac fun_extension 1); |
1012 by (rtac fun_extension 1); |
1013 by (stac lub_cf 3); |
1013 by (stac lub_cf 3); |
1014 brr(comp_fun::(cf_cont RS cont_fun)::(cpo_lub RS islub_in)::cpo_cf:: |
1014 brr(comp_fun::(cf_cont RS cont_fun)::(cpo_lub RS islub_in)::cpo_cf:: |
1015 chain_cf_comp::prems) 1; |
1015 chain_cf_comp::prems) 1; |
1016 by (cut_facts_tac[hd prems,hd(tl prems)]1); |
1016 by (cut_facts_tac[hd prems,hd(tl prems)]1); |
1017 by (asm_simp_tac(!simpset addsimps((chain_in RS cf_cont RSN(3,chain_in RS |
1017 by (asm_simp_tac(simpset() addsimps((chain_in RS cf_cont RSN(3,chain_in RS |
1018 cf_cont RS comp_cont_apply))::(tl(tl prems)))) 1); |
1018 cf_cont RS comp_cont_apply))::(tl(tl prems)))) 1); |
1019 by (stac comp_cont_apply 1); |
1019 by (stac comp_cont_apply 1); |
1020 brr((cpo_lub RS islub_in RS cf_cont)::cpo_cf::prems) 1; |
1020 brr((cpo_lub RS islub_in RS cf_cont)::cpo_cf::prems) 1; |
1021 by (asm_simp_tac(!simpset addsimps(lub_cf:: |
1021 by (asm_simp_tac(simpset() addsimps(lub_cf:: |
1022 (hd(tl prems)RS chain_cf RSN(2,hd prems RS chain_in RS cf_cont RS cont_lub)):: |
1022 (hd(tl prems)RS chain_cf RSN(2,hd prems RS chain_in RS cf_cont RS cont_lub)):: |
1023 (hd(tl prems) RS chain_cf RS cpo_lub RS islub_in)::prems)) 1); |
1023 (hd(tl prems) RS chain_cf RS cpo_lub RS islub_in)::prems)) 1); |
1024 by (cut_inst_tac[("M","lam xa:nat. lam xb:nat. X`xa`(Y`xb`x)")] |
1024 by (cut_inst_tac[("M","lam xa:nat. lam xb:nat. X`xa`(Y`xb`x)")] |
1025 lub_matrix_diag 1); |
1025 lub_matrix_diag 1); |
1026 by (Asm_full_simp_tac 3); |
1026 by (Asm_full_simp_tac 3); |
1048 val prems = goalw Limit.thy [projpair_def] (* projpairE *) |
1048 val prems = goalw Limit.thy [projpair_def] (* projpairE *) |
1049 "[| projpair(D,E,e,p); \ |
1049 "[| projpair(D,E,e,p); \ |
1050 \ [| e:cont(D,E); p:cont(E,D); p O e = id(set(D)); \ |
1050 \ [| e:cont(D,E); p:cont(E,D); p O e = id(set(D)); \ |
1051 \ rel(cf(E,E))(e O p)(id(set(E)))|] ==> Q |] ==> Q"; |
1051 \ rel(cf(E,E))(e O p)(id(set(E)))|] ==> Q |] ==> Q"; |
1052 by (rtac (hd(tl prems)) 1); |
1052 by (rtac (hd(tl prems)) 1); |
1053 by (REPEAT(asm_simp_tac(!simpset addsimps[hd prems]) 1)); |
1053 by (REPEAT(asm_simp_tac(simpset() addsimps[hd prems]) 1)); |
1054 qed "projpairE"; |
1054 qed "projpairE"; |
1055 |
1055 |
1056 val prems = goal Limit.thy (* projpair_e_cont *) |
1056 val prems = goal Limit.thy (* projpair_e_cont *) |
1057 "projpair(D,E,e,p) ==> e:cont(D,E)"; |
1057 "projpair(D,E,e,p) ==> e:cont(D,E)"; |
1058 by (rtac projpairE 1); |
1058 by (rtac projpairE 1); |
1216 (* The identity embedding. *) |
1216 (* The identity embedding. *) |
1217 (*----------------------------------------------------------------------*) |
1217 (*----------------------------------------------------------------------*) |
1218 |
1218 |
1219 val prems = goalw Limit.thy [projpair_def] (* projpair_id *) |
1219 val prems = goalw Limit.thy [projpair_def] (* projpair_id *) |
1220 "cpo(D) ==> projpair(D,D,id(set(D)),id(set(D)))"; |
1220 "cpo(D) ==> projpair(D,D,id(set(D)),id(set(D)))"; |
1221 by (safe_tac (!claset)); |
1221 by (safe_tac (claset())); |
1222 brr(id_cont::id_comp::id_type::prems) 1; |
1222 brr(id_cont::id_comp::id_type::prems) 1; |
1223 by (stac id_comp 1); (* Matches almost anything *) |
1223 by (stac id_comp 1); (* Matches almost anything *) |
1224 brr(id_cont::id_type::cpo_refl::cpo_cf::cont_cf::prems) 1; |
1224 brr(id_cont::id_type::cpo_refl::cpo_cf::cont_cf::prems) 1; |
1225 qed "projpair_id"; |
1225 qed "projpair_id"; |
1226 |
1226 |
1243 (* Proof in Isa/ZF: 23 lines (compared to 56: 60% reduction). *) |
1243 (* Proof in Isa/ZF: 23 lines (compared to 56: 60% reduction). *) |
1244 |
1244 |
1245 val prems = goalw Limit.thy [projpair_def] (* lemma *) |
1245 val prems = goalw Limit.thy [projpair_def] (* lemma *) |
1246 "[|emb(D,D',e); emb(D',E,e'); cpo(D); cpo(D'); cpo(E)|] ==> \ |
1246 "[|emb(D,D',e); emb(D',E,e'); cpo(D); cpo(D'); cpo(E)|] ==> \ |
1247 \ projpair(D,E,e' O e,(Rp(D,D',e)) O (Rp(D',E,e')))"; |
1247 \ projpair(D,E,e' O e,(Rp(D,D',e)) O (Rp(D',E,e')))"; |
1248 by (safe_tac (!claset)); |
1248 by (safe_tac (claset())); |
1249 brr(comp_pres_cont::Rp_cont::emb_cont::prems) 1; |
1249 brr(comp_pres_cont::Rp_cont::emb_cont::prems) 1; |
1250 by (rtac (comp_assoc RS subst) 1); |
1250 by (rtac (comp_assoc RS subst) 1); |
1251 by (res_inst_tac[("t1","e'")](comp_assoc RS ssubst) 1); |
1251 by (res_inst_tac[("t1","e'")](comp_assoc RS ssubst) 1); |
1252 by (stac embRp_eq 1); (* Matches everything due to subst/ssubst. *) |
1252 by (stac embRp_eq 1); (* Matches everything due to subst/ssubst. *) |
1253 brr prems 1; |
1253 brr prems 1; |
1286 |
1286 |
1287 (* Proof with non-reflexive relation approach: |
1287 (* Proof with non-reflexive relation approach: |
1288 by (rtac CollectI 1); |
1288 by (rtac CollectI 1); |
1289 by (rtac domainI 1); |
1289 by (rtac domainI 1); |
1290 by (rtac CollectI 1); |
1290 by (rtac CollectI 1); |
1291 by (simp_tac(!simpset addsimps prems) 1); |
1291 by (simp_tac(simpset() addsimps prems) 1); |
1292 by (rtac (hd prems) 1); |
1292 by (rtac (hd prems) 1); |
1293 by (Simp_tac 1); |
1293 by (Simp_tac 1); |
1294 by (rtac ballI 1); |
1294 by (rtac ballI 1); |
1295 by (dtac ((hd prems) RS apply_type) 1); |
1295 by (dtac ((hd prems) RS apply_type) 1); |
1296 by (etac CollectE 1); |
1296 by (etac CollectE 1); |
1297 by (assume_tac 1); |
1297 by (assume_tac 1); |
1298 by (rtac rel_I 1); |
1298 by (rtac rel_I 1); |
1299 by (rtac CollectI 1); |
1299 by (rtac CollectI 1); |
1300 by (fast_tac(!claset addSIs prems) 1); |
1300 by (fast_tac(claset() addSIs prems) 1); |
1301 by (rtac ballI 1); |
1301 by (rtac ballI 1); |
1302 by (Simp_tac 1); |
1302 by (Simp_tac 1); |
1303 by (dtac ((hd prems) RS apply_type) 1); |
1303 by (dtac ((hd prems) RS apply_type) 1); |
1304 by (etac CollectE 1); |
1304 by (etac CollectE 1); |
1305 by (assume_tac 1); |
1305 by (assume_tac 1); |
1315 val prems = goalw Limit.thy [iprod_def] (* rel_iprodI *) |
1315 val prems = goalw Limit.thy [iprod_def] (* rel_iprodI *) |
1316 "[|!!n. n:nat ==> rel(DD`n,f`n,g`n); f:(PROD n:nat. set(DD`n)); \ |
1316 "[|!!n. n:nat ==> rel(DD`n,f`n,g`n); f:(PROD n:nat. set(DD`n)); \ |
1317 \ g:(PROD n:nat. set(DD`n))|] ==> rel(iprod(DD),f,g)"; |
1317 \ g:(PROD n:nat. set(DD`n))|] ==> rel(iprod(DD),f,g)"; |
1318 by (rtac rel_I 1); |
1318 by (rtac rel_I 1); |
1319 by (Simp_tac 1); |
1319 by (Simp_tac 1); |
1320 by (safe_tac (!claset)); |
1320 by (safe_tac (claset())); |
1321 brr prems 1; |
1321 brr prems 1; |
1322 qed "rel_iprodI"; |
1322 qed "rel_iprodI"; |
1323 |
1323 |
1324 val prems = goalw Limit.thy [iprod_def] (* rel_iprodE *) |
1324 val prems = goalw Limit.thy [iprod_def] (* rel_iprodE *) |
1325 "[|rel(iprod(DD),f,g); n:nat|] ==> rel(DD`n,f`n,g`n)"; |
1325 "[|rel(iprod(DD),f,g); n:nat|] ==> rel(DD`n,f`n,g`n)"; |
1326 by (cut_facts_tac[hd prems RS rel_E]1); |
1326 by (cut_facts_tac[hd prems RS rel_E]1); |
1327 by (Asm_full_simp_tac 1); |
1327 by (Asm_full_simp_tac 1); |
1328 by (safe_tac (!claset)); |
1328 by (safe_tac (claset())); |
1329 by (etac bspec 1); |
1329 by (etac bspec 1); |
1330 by (resolve_tac prems 1); |
1330 by (resolve_tac prems 1); |
1331 qed "rel_iprodE"; |
1331 qed "rel_iprodE"; |
1332 |
1332 |
1333 (* Some special theorems like dProdApIn_cpo and other `_cpo' |
1333 (* Some special theorems like dProdApIn_cpo and other `_cpo' |
1334 probably not needed in Isabelle, wait and see. *) |
1334 probably not needed in Isabelle, wait and see. *) |
1335 |
1335 |
1336 val prems = goalw Limit.thy [chain_def] (* chain_iprod *) |
1336 val prems = goalw Limit.thy [chain_def] (* chain_iprod *) |
1337 "[|chain(iprod(DD),X); !!n. n:nat ==> cpo(DD`n); n:nat|] ==> \ |
1337 "[|chain(iprod(DD),X); !!n. n:nat ==> cpo(DD`n); n:nat|] ==> \ |
1338 \ chain(DD`n,lam m:nat. X`m`n)"; |
1338 \ chain(DD`n,lam m:nat. X`m`n)"; |
1339 by (safe_tac (!claset)); |
1339 by (safe_tac (claset())); |
1340 by (rtac lam_type 1); |
1340 by (rtac lam_type 1); |
1341 by (rtac apply_type 1); |
1341 by (rtac apply_type 1); |
1342 by (rtac iprodE 1); |
1342 by (rtac iprodE 1); |
1343 by (etac (hd prems RS conjunct1 RS apply_type) 1); |
1343 by (etac (hd prems RS conjunct1 RS apply_type) 1); |
1344 by (resolve_tac prems 1); |
1344 by (resolve_tac prems 1); |
1345 by (asm_simp_tac(!simpset addsimps prems) 1); |
1345 by (asm_simp_tac(simpset() addsimps prems) 1); |
1346 by (rtac rel_iprodE 1); |
1346 by (rtac rel_iprodE 1); |
1347 by (asm_simp_tac (!simpset addsimps prems) 1); |
1347 by (asm_simp_tac (simpset() addsimps prems) 1); |
1348 by (resolve_tac prems 1); |
1348 by (resolve_tac prems 1); |
1349 qed "chain_iprod"; |
1349 qed "chain_iprod"; |
1350 |
1350 |
1351 val prems = goalw Limit.thy [islub_def,isub_def] (* islub_iprod *) |
1351 val prems = goalw Limit.thy [islub_def,isub_def] (* islub_iprod *) |
1352 "[|chain(iprod(DD),X); !!n. n:nat ==> cpo(DD`n)|] ==> \ |
1352 "[|chain(iprod(DD),X); !!n. n:nat ==> cpo(DD`n)|] ==> \ |
1353 \ islub(iprod(DD),X,lam n:nat. lub(DD`n,lam m:nat. X`m`n))"; |
1353 \ islub(iprod(DD),X,lam n:nat. lub(DD`n,lam m:nat. X`m`n))"; |
1354 by (safe_tac (!claset)); |
1354 by (safe_tac (claset())); |
1355 by (rtac iprodI 1); |
1355 by (rtac iprodI 1); |
1356 by (rtac lam_type 1); |
1356 by (rtac lam_type 1); |
1357 brr((chain_iprod RS cpo_lub RS islub_in)::prems) 1; |
1357 brr((chain_iprod RS cpo_lub RS islub_in)::prems) 1; |
1358 by (rtac rel_iprodI 1); |
1358 by (rtac rel_iprodI 1); |
1359 by (Asm_simp_tac 1); |
1359 by (Asm_simp_tac 1); |
1364 brr(iprodI::lam_type::(chain_iprod RS cpo_lub RS islub_in)::prems) 1; |
1364 brr(iprodI::lam_type::(chain_iprod RS cpo_lub RS islub_in)::prems) 1; |
1365 by (rtac rel_iprodI 1); |
1365 by (rtac rel_iprodI 1); |
1366 by (Asm_simp_tac 1); |
1366 by (Asm_simp_tac 1); |
1367 brr(islub_least::(chain_iprod RS cpo_lub)::prems) 1; |
1367 brr(islub_least::(chain_iprod RS cpo_lub)::prems) 1; |
1368 by (rewtac isub_def); |
1368 by (rewtac isub_def); |
1369 by (safe_tac (!claset)); |
1369 by (safe_tac (claset())); |
1370 by (etac (iprodE RS apply_type) 1); |
1370 by (etac (iprodE RS apply_type) 1); |
1371 by (assume_tac 1); |
1371 by (assume_tac 1); |
1372 by (Asm_simp_tac 1); |
1372 by (Asm_simp_tac 1); |
1373 by (dtac bspec 1); |
1373 by (dtac bspec 1); |
1374 by (etac rel_iprodE 2); |
1374 by (etac rel_iprodE 2); |
1401 |
1401 |
1402 val prems = goalw Limit.thy [subcpo_def] (* subcpoI *) |
1402 val prems = goalw Limit.thy [subcpo_def] (* subcpoI *) |
1403 "[|set(D)<=set(E); \ |
1403 "[|set(D)<=set(E); \ |
1404 \ !!x y. [|x:set(D); y:set(D)|] ==> rel(D,x,y)<->rel(E,x,y); \ |
1404 \ !!x y. [|x:set(D); y:set(D)|] ==> rel(D,x,y)<->rel(E,x,y); \ |
1405 \ !!X. chain(D,X) ==> lub(E,X) : set(D)|] ==> subcpo(D,E)"; |
1405 \ !!X. chain(D,X) ==> lub(E,X) : set(D)|] ==> subcpo(D,E)"; |
1406 by (safe_tac (!claset)); |
1406 by (safe_tac (claset())); |
1407 by (asm_full_simp_tac(!simpset addsimps prems) 2); |
1407 by (asm_full_simp_tac(simpset() addsimps prems) 2); |
1408 by (asm_simp_tac(!simpset addsimps prems) 2); |
1408 by (asm_simp_tac(simpset() addsimps prems) 2); |
1409 brr(prems@[subsetD]) 1; |
1409 brr(prems@[subsetD]) 1; |
1410 qed "subcpoI"; |
1410 qed "subcpoI"; |
1411 |
1411 |
1412 val subcpo_subset = prove_goalw Limit.thy [subcpo_def] |
1412 val subcpo_subset = prove_goalw Limit.thy [subcpo_def] |
1413 "!!x. subcpo(D,E) ==> set(D)<=set(E)" |
1413 "!!x. subcpo(D,E) ==> set(D)<=set(E)" |
1457 |
1457 |
1458 val prems = goal Limit.thy (* subcpo_cpo *) |
1458 val prems = goal Limit.thy (* subcpo_cpo *) |
1459 "[|subcpo(D,E); cpo(E)|] ==> cpo(D)"; |
1459 "[|subcpo(D,E); cpo(E)|] ==> cpo(D)"; |
1460 brr[cpoI,poI]1; |
1460 brr[cpoI,poI]1; |
1461 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *) |
1461 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *) |
1462 by (asm_full_simp_tac(!simpset addsimps[hd prems RS subcpo_rel_eq]) 1); |
1462 by (asm_full_simp_tac(simpset() addsimps[hd prems RS subcpo_rel_eq]) 1); |
1463 brr(cpo_refl::(hd prems RS subcpo_subset RS subsetD)::prems) 1; |
1463 brr(cpo_refl::(hd prems RS subcpo_subset RS subsetD)::prems) 1; |
1464 by (dtac (imp_refl RS mp) 1); |
1464 by (dtac (imp_refl RS mp) 1); |
1465 by (dtac (imp_refl RS mp) 1); |
1465 by (dtac (imp_refl RS mp) 1); |
1466 by (asm_full_simp_tac(!simpset addsimps[hd prems RS subcpo_rel_eq]) 1); |
1466 by (asm_full_simp_tac(simpset() addsimps[hd prems RS subcpo_rel_eq]) 1); |
1467 brr(cpo_trans::(hd prems RS subcpo_subset RS subsetD)::prems) 1; |
1467 brr(cpo_trans::(hd prems RS subcpo_subset RS subsetD)::prems) 1; |
1468 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *) |
1468 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *) |
1469 by (dtac (imp_refl RS mp) 1); |
1469 by (dtac (imp_refl RS mp) 1); |
1470 by (dtac (imp_refl RS mp) 1); |
1470 by (dtac (imp_refl RS mp) 1); |
1471 by (asm_full_simp_tac(!simpset addsimps[hd prems RS subcpo_rel_eq]) 1); |
1471 by (asm_full_simp_tac(simpset() addsimps[hd prems RS subcpo_rel_eq]) 1); |
1472 brr(cpo_antisym::(hd prems RS subcpo_subset RS subsetD)::prems) 1; |
1472 brr(cpo_antisym::(hd prems RS subcpo_subset RS subsetD)::prems) 1; |
1473 brr(islub_subcpo::prems) 1; |
1473 brr(islub_subcpo::prems) 1; |
1474 qed "subcpo_cpo"; |
1474 qed "subcpo_cpo"; |
1475 |
1475 |
1476 val prems = goal Limit.thy (* lub_subcpo *) |
1476 val prems = goal Limit.thy (* lub_subcpo *) |
1496 (* Now, work on subgoal 2 (and 3) to instantiate unknown. *) |
1496 (* Now, work on subgoal 2 (and 3) to instantiate unknown. *) |
1497 by (Simp_tac 2); |
1497 by (Simp_tac 2); |
1498 by (rtac conjI 2); |
1498 by (rtac conjI 2); |
1499 by (rtac conjI 3); |
1499 by (rtac conjI 3); |
1500 by (resolve_tac prems 3); |
1500 by (resolve_tac prems 3); |
1501 by (simp_tac(!simpset addsimps [rewrite_rule[set_def](hd prems)]) 1); |
1501 by (simp_tac(simpset() addsimps [rewrite_rule[set_def](hd prems)]) 1); |
1502 by (resolve_tac prems 1); |
1502 by (resolve_tac prems 1); |
1503 by (rtac cpo_refl 1); |
1503 by (rtac cpo_refl 1); |
1504 by (resolve_tac prems 1); |
1504 by (resolve_tac prems 1); |
1505 by (rtac rel_I 1); |
1505 by (rtac rel_I 1); |
1506 by (rtac CollectI 1); |
1506 by (rtac CollectI 1); |
1507 by (fast_tac(!claset addSIs [rewrite_rule[set_def](hd prems)]) 1); |
1507 by (fast_tac(claset() addSIs [rewrite_rule[set_def](hd prems)]) 1); |
1508 by (Simp_tac 1); |
1508 by (Simp_tac 1); |
1509 brr(conjI::cpo_refl::prems) 1; |
1509 brr(conjI::cpo_refl::prems) 1; |
1510 *) |
1510 *) |
1511 |
1511 |
1512 val prems = goalw Limit.thy [set_def,mkcpo_def] (* mkcpoD1 *) |
1512 val prems = goalw Limit.thy [set_def,mkcpo_def] (* mkcpoD1 *) |
1562 (*----------------------------------------------------------------------*) |
1562 (*----------------------------------------------------------------------*) |
1563 |
1563 |
1564 val prems = goalw Limit.thy [emb_chain_def] (* emb_chainI *) |
1564 val prems = goalw Limit.thy [emb_chain_def] (* emb_chainI *) |
1565 "[|!!n. n:nat ==> cpo(DD`n); \ |
1565 "[|!!n. n:nat ==> cpo(DD`n); \ |
1566 \ !!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n)|] ==> emb_chain(DD,ee)"; |
1566 \ !!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n)|] ==> emb_chain(DD,ee)"; |
1567 by (safe_tac (!claset)); |
1567 by (safe_tac (claset())); |
1568 brr prems 1; |
1568 brr prems 1; |
1569 qed "emb_chainI"; |
1569 qed "emb_chainI"; |
1570 |
1570 |
1571 val emb_chain_cpo = prove_goalw Limit.thy [emb_chain_def] |
1571 val emb_chain_cpo = prove_goalw Limit.thy [emb_chain_def] |
1572 "!!x. [|emb_chain(DD,ee); n:nat|] ==> cpo(DD`n)" |
1572 "!!x. [|emb_chain(DD,ee); n:nat|] ==> cpo(DD`n)" |
1596 val Dinf_prod = DinfD1; |
1596 val Dinf_prod = DinfD1; |
1597 |
1597 |
1598 val prems = goalw Limit.thy [Dinf_def] (* DinfD2 *) |
1598 val prems = goalw Limit.thy [Dinf_def] (* DinfD2 *) |
1599 "[|x:set(Dinf(DD,ee)); n:nat|] ==> \ |
1599 "[|x:set(Dinf(DD,ee)); n:nat|] ==> \ |
1600 \ Rp(DD`n,DD`succ(n),ee`n)`(x`succ(n)) = x`n"; |
1600 \ Rp(DD`n,DD`succ(n),ee`n)`(x`succ(n)) = x`n"; |
1601 by (asm_simp_tac(!simpset addsimps[(hd prems RS mkcpoD2),hd(tl prems)]) 1); |
1601 by (asm_simp_tac(simpset() addsimps[(hd prems RS mkcpoD2),hd(tl prems)]) 1); |
1602 qed "DinfD2"; |
1602 qed "DinfD2"; |
1603 val Dinf_eq = DinfD2; |
1603 val Dinf_eq = DinfD2; |
1604 |
1604 |
1605 (* At first, rel_DinfI was stated too strongly, because rel_mkcpo was too: |
1605 (* At first, rel_DinfI was stated too strongly, because rel_mkcpo was too: |
1606 val prems = goalw Limit.thy [Dinf_def] (* rel_DinfI *) |
1606 val prems = goalw Limit.thy [Dinf_def] (* rel_DinfI *) |
1639 brr(chain_Dinf::(hd prems RS emb_chain_cpo)::[]) 1; |
1639 brr(chain_Dinf::(hd prems RS emb_chain_cpo)::[]) 1; |
1640 by (Asm_simp_tac 1); |
1640 by (Asm_simp_tac 1); |
1641 by (stac (Rp_cont RS cont_lub) 1); |
1641 by (stac (Rp_cont RS cont_lub) 1); |
1642 brr(emb_chain_cpo::emb_chain_emb::nat_succI::chain_iprod::chain_Dinf::prems) 1; |
1642 brr(emb_chain_cpo::emb_chain_emb::nat_succI::chain_iprod::chain_Dinf::prems) 1; |
1643 (* Useful simplification, ugly in HOL. *) |
1643 (* Useful simplification, ugly in HOL. *) |
1644 by (asm_simp_tac(!simpset addsimps(DinfD2::chain_in::[])) 1); |
1644 by (asm_simp_tac(simpset() addsimps(DinfD2::chain_in::[])) 1); |
1645 brr(cpo_iprod::emb_chain_cpo::prems) 1; |
1645 brr(cpo_iprod::emb_chain_cpo::prems) 1; |
1646 qed "subcpo_Dinf"; |
1646 qed "subcpo_Dinf"; |
1647 |
1647 |
1648 (* Simple example of existential reasoning in Isabelle versus HOL. *) |
1648 (* Simple example of existential reasoning in Isabelle versus HOL. *) |
1649 |
1649 |
1668 (* defined as eps(DD,ee,m,n), via e_less and e_gr. *) |
1668 (* defined as eps(DD,ee,m,n), via e_less and e_gr. *) |
1669 (*----------------------------------------------------------------------*) |
1669 (*----------------------------------------------------------------------*) |
1670 |
1670 |
1671 val prems = goalw Limit.thy [e_less_def] (* e_less_eq *) |
1671 val prems = goalw Limit.thy [e_less_def] (* e_less_eq *) |
1672 "!!x. m:nat ==> e_less(DD,ee,m,m) = id(set(DD`m))"; |
1672 "!!x. m:nat ==> e_less(DD,ee,m,m) = id(set(DD`m))"; |
1673 by (asm_simp_tac (!simpset addsimps[diff_self_eq_0]) 1); |
1673 by (asm_simp_tac (simpset() addsimps[diff_self_eq_0]) 1); |
1674 qed "e_less_eq"; |
1674 qed "e_less_eq"; |
1675 |
1675 |
1676 (* ARITH_CONV proves the following in HOL. Would like something similar |
1676 (* ARITH_CONV proves the following in HOL. Would like something similar |
1677 in Isabelle/ZF. *) |
1677 in Isabelle/ZF. *) |
1678 |
1678 |
1679 goal Arith.thy (* lemma_succ_sub *) |
1679 goal Arith.thy (* lemma_succ_sub *) |
1680 "!!z. [|n:nat; m:nat|] ==> succ(m#+n)#-m = succ(n)"; |
1680 "!!z. [|n:nat; m:nat|] ==> succ(m#+n)#-m = succ(n)"; |
1681 (*Uses add_succ_right the wrong way round!*) |
1681 (*Uses add_succ_right the wrong way round!*) |
1682 by (asm_simp_tac |
1682 by (asm_simp_tac |
1683 (simpset_of"Nat" addsimps [add_succ_right RS sym, diff_add_inverse]) 1); |
1683 (simpset_of Nat.thy addsimps [add_succ_right RS sym, diff_add_inverse]) 1); |
1684 val lemma_succ_sub = result(); |
1684 val lemma_succ_sub = result(); |
1685 |
1685 |
1686 val prems = goalw Limit.thy [e_less_def] (* e_less_add *) |
1686 val prems = goalw Limit.thy [e_less_def] (* e_less_add *) |
1687 "!!x. [|m:nat; k:nat|] ==> \ |
1687 "!!x. [|m:nat; k:nat|] ==> \ |
1688 \ e_less(DD,ee,m,succ(m#+k)) = (ee`(m#+k))O(e_less(DD,ee,m,m#+k))"; |
1688 \ e_less(DD,ee,m,succ(m#+k)) = (ee`(m#+k))O(e_less(DD,ee,m,m#+k))"; |
1689 by (asm_simp_tac (!simpset addsimps [lemma_succ_sub,diff_add_inverse]) 1); |
1689 by (asm_simp_tac (simpset() addsimps [lemma_succ_sub,diff_add_inverse]) 1); |
1690 qed "e_less_add"; |
1690 qed "e_less_add"; |
1691 |
1691 |
1692 (* Again, would like more theorems about arithmetic. *) |
1692 (* Again, would like more theorems about arithmetic. *) |
1693 (* Well, HOL has much better support and automation of natural numbers. *) |
1693 (* Well, HOL has much better support and automation of natural numbers. *) |
1694 |
1694 |
1695 val add1 = prove_goal Limit.thy |
1695 val add1 = prove_goal Limit.thy |
1696 "!!x. n:nat ==> succ(n) = n #+ 1" |
1696 "!!x. n:nat ==> succ(n) = n #+ 1" |
1697 (fn prems => |
1697 (fn prems => |
1698 [asm_simp_tac (!simpset addsimps[add_succ_right,add_0_right]) 1]); |
1698 [asm_simp_tac (simpset() addsimps[add_succ_right,add_0_right]) 1]); |
1699 |
1699 |
1700 val prems = goal Limit.thy (* succ_sub1 *) |
1700 val prems = goal Limit.thy (* succ_sub1 *) |
1701 "x:nat ==> 0 < x --> succ(x#-1)=x"; |
1701 "x:nat ==> 0 < x --> succ(x#-1)=x"; |
1702 by (res_inst_tac[("n","x")]nat_induct 1); |
1702 by (res_inst_tac[("n","x")]nat_induct 1); |
1703 by (resolve_tac prems 1); |
1703 by (resolve_tac prems 1); |
1704 by (Fast_tac 1); |
1704 by (Fast_tac 1); |
1705 by (safe_tac (!claset)); |
1705 by (safe_tac (claset())); |
1706 by (Asm_simp_tac 1); |
1706 by (Asm_simp_tac 1); |
1707 by (Asm_simp_tac 1); |
1707 by (Asm_simp_tac 1); |
1708 qed "succ_sub1"; |
1708 qed "succ_sub1"; |
1709 |
1709 |
1710 val prems = goal Limit.thy (* succ_le_pos *) |
1710 val prems = goal Limit.thy (* succ_le_pos *) |
1711 "[|m:nat; k:nat|] ==> succ(m) le m #+ k --> 0 < k"; |
1711 "[|m:nat; k:nat|] ==> succ(m) le m #+ k --> 0 < k"; |
1712 by (res_inst_tac[("n","m")]nat_induct 1); |
1712 by (res_inst_tac[("n","m")]nat_induct 1); |
1713 by (resolve_tac prems 1); |
1713 by (resolve_tac prems 1); |
1714 by (rtac impI 1); |
1714 by (rtac impI 1); |
1715 by (asm_full_simp_tac(!simpset addsimps prems) 1); |
1715 by (asm_full_simp_tac(simpset() addsimps prems) 1); |
1716 by (safe_tac (!claset)); |
1716 by (safe_tac (claset())); |
1717 by (asm_full_simp_tac(!simpset addsimps prems) 1); (* Surprise, surprise. *) |
1717 by (asm_full_simp_tac(simpset() addsimps prems) 1); (* Surprise, surprise. *) |
1718 qed "succ_le_pos"; |
1718 qed "succ_le_pos"; |
1719 |
1719 |
1720 goal Limit.thy (* lemma_le_exists *) |
1720 goal Limit.thy (* lemma_le_exists *) |
1721 "!!z. [|n:nat; m:nat|] ==> m le n --> (EX k:nat. n = m #+ k)"; |
1721 "!!z. [|n:nat; m:nat|] ==> m le n --> (EX k:nat. n = m #+ k)"; |
1722 by (res_inst_tac[("n","m")]nat_induct 1); |
1722 by (res_inst_tac[("n","m")]nat_induct 1); |
1723 by (assume_tac 1); |
1723 by (assume_tac 1); |
1724 by (safe_tac (!claset)); |
1724 by (safe_tac (claset())); |
1725 by (rtac bexI 1); |
1725 by (rtac bexI 1); |
1726 by (rtac (add_0 RS sym) 1); |
1726 by (rtac (add_0 RS sym) 1); |
1727 by (assume_tac 1); |
1727 by (assume_tac 1); |
1728 by (Asm_full_simp_tac 1); |
1728 by (Asm_full_simp_tac 1); |
1729 (* Great, by luck I found le_cs. Such cs's and ss's should be documented. *) |
1729 (* Great, by luck I found le_cs. Such cs's and ss's should be documented. *) |
1730 by (fast_tac le_cs 1); |
1730 by (fast_tac le_cs 1); |
1731 by (asm_simp_tac |
1731 by (asm_simp_tac |
1732 (simpset_of"Nat" addsimps[add_succ, add_succ_right RS sym]) 1); |
1732 (simpset_of Nat.thy addsimps[add_succ, add_succ_right RS sym]) 1); |
1733 by (rtac bexI 1); |
1733 by (rtac bexI 1); |
1734 by (stac (succ_sub1 RS mp) 1); |
1734 by (stac (succ_sub1 RS mp) 1); |
1735 (* Instantiation. *) |
1735 (* Instantiation. *) |
1736 by (rtac refl 3); |
1736 by (rtac refl 3); |
1737 by (assume_tac 1); |
1737 by (assume_tac 1); |
1752 val prems = goal Limit.thy (* e_less_le *) |
1752 val prems = goal Limit.thy (* e_less_le *) |
1753 "[|m le n; m:nat; n:nat|] ==> \ |
1753 "[|m le n; m:nat; n:nat|] ==> \ |
1754 \ e_less(DD,ee,m,succ(n)) = ee`n O e_less(DD,ee,m,n)"; |
1754 \ e_less(DD,ee,m,succ(n)) = ee`n O e_less(DD,ee,m,n)"; |
1755 by (rtac le_exists 1); |
1755 by (rtac le_exists 1); |
1756 by (resolve_tac prems 1); |
1756 by (resolve_tac prems 1); |
1757 by (asm_simp_tac(!simpset addsimps(e_less_add::prems)) 1); |
1757 by (asm_simp_tac(simpset() addsimps(e_less_add::prems)) 1); |
1758 brr prems 1; |
1758 brr prems 1; |
1759 qed "e_less_le"; |
1759 qed "e_less_le"; |
1760 |
1760 |
1761 (* All theorems assume variables m and n are natural numbers. *) |
1761 (* All theorems assume variables m and n are natural numbers. *) |
1762 |
1762 |
1763 val prems = goal Limit.thy (* e_less_succ *) |
1763 val prems = goal Limit.thy (* e_less_succ *) |
1764 "m:nat ==> e_less(DD,ee,m,succ(m)) = ee`m O id(set(DD`m))"; |
1764 "m:nat ==> e_less(DD,ee,m,succ(m)) = ee`m O id(set(DD`m))"; |
1765 by (asm_simp_tac(!simpset addsimps(e_less_le::e_less_eq::prems)) 1); |
1765 by (asm_simp_tac(simpset() addsimps(e_less_le::e_less_eq::prems)) 1); |
1766 qed "e_less_succ"; |
1766 qed "e_less_succ"; |
1767 |
1767 |
1768 val prems = goal Limit.thy (* e_less_succ_emb *) |
1768 val prems = goal Limit.thy (* e_less_succ_emb *) |
1769 "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==> \ |
1769 "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==> \ |
1770 \ e_less(DD,ee,m,succ(m)) = ee`m"; |
1770 \ e_less(DD,ee,m,succ(m)) = ee`m"; |
1771 by (asm_simp_tac(!simpset addsimps(e_less_succ::prems)) 1); |
1771 by (asm_simp_tac(simpset() addsimps(e_less_succ::prems)) 1); |
1772 by (stac comp_id 1); |
1772 by (stac comp_id 1); |
1773 brr(emb_cont::cont_fun::refl::prems) 1; |
1773 brr(emb_cont::cont_fun::refl::prems) 1; |
1774 qed "e_less_succ_emb"; |
1774 qed "e_less_succ_emb"; |
1775 |
1775 |
1776 (* Compare this proof with the HOL one, here we do type checking. *) |
1776 (* Compare this proof with the HOL one, here we do type checking. *) |
1779 val prems = goal Limit.thy (* emb_e_less_add *) |
1779 val prems = goal Limit.thy (* emb_e_less_add *) |
1780 "[|emb_chain(DD,ee); m:nat; k:nat|] ==> \ |
1780 "[|emb_chain(DD,ee); m:nat; k:nat|] ==> \ |
1781 \ emb(DD`m,DD`(m#+k),e_less(DD,ee,m,m#+k))"; |
1781 \ emb(DD`m,DD`(m#+k),e_less(DD,ee,m,m#+k))"; |
1782 by (res_inst_tac[("n","k")]nat_induct 1); |
1782 by (res_inst_tac[("n","k")]nat_induct 1); |
1783 by (resolve_tac prems 1); |
1783 by (resolve_tac prems 1); |
1784 by (asm_simp_tac(!simpset addsimps(add_0_right::e_less_eq::prems)) 1); |
1784 by (asm_simp_tac(simpset() addsimps(add_0_right::e_less_eq::prems)) 1); |
1785 brr(emb_id::emb_chain_cpo::prems) 1; |
1785 brr(emb_id::emb_chain_cpo::prems) 1; |
1786 by (asm_simp_tac(!simpset addsimps(add_succ_right::e_less_add::prems)) 1); |
1786 by (asm_simp_tac(simpset() addsimps(add_succ_right::e_less_add::prems)) 1); |
1787 brr(emb_comp::emb_chain_emb::emb_chain_cpo::add_type::nat_succI::prems) 1; |
1787 brr(emb_comp::emb_chain_emb::emb_chain_cpo::add_type::nat_succI::prems) 1; |
1788 qed "emb_e_less_add"; |
1788 qed "emb_e_less_add"; |
1789 |
1789 |
1790 val prems = goal Limit.thy (* emb_e_less *) |
1790 val prems = goal Limit.thy (* emb_e_less *) |
1791 "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1791 "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1792 \ emb(DD`m,DD`n,e_less(DD,ee,m,n))"; |
1792 \ emb(DD`m,DD`n,e_less(DD,ee,m,n))"; |
1793 (* same proof as e_less_le *) |
1793 (* same proof as e_less_le *) |
1794 by (rtac le_exists 1); |
1794 by (rtac le_exists 1); |
1795 by (resolve_tac prems 1); |
1795 by (resolve_tac prems 1); |
1796 by (asm_simp_tac(!simpset addsimps(emb_e_less_add::prems)) 1); |
1796 by (asm_simp_tac(simpset() addsimps(emb_e_less_add::prems)) 1); |
1797 brr prems 1; |
1797 brr prems 1; |
1798 qed "emb_e_less"; |
1798 qed "emb_e_less"; |
1799 |
1799 |
1800 val comp_mono_eq = prove_goal Limit.thy |
1800 val comp_mono_eq = prove_goal Limit.thy |
1801 "!!z.[|f=f'; g=g'|] ==> f O g = f' O g'" |
1801 "!!z.[|f=f'; g=g'|] ==> f O g = f' O g'" |
1839 \ e_less(DD,ee,m,m#+k) = e_less(DD,ee,m#+n,m#+k) O e_less(DD,ee,m,m#+n)" |
1839 \ e_less(DD,ee,m,m#+k) = e_less(DD,ee,m#+n,m#+k) O e_less(DD,ee,m,m#+n)" |
1840 (fn prems => [trr((e_less_split_add_lemma RS mp)::prems) 1]); |
1840 (fn prems => [trr((e_less_split_add_lemma RS mp)::prems) 1]); |
1841 |
1841 |
1842 val prems = goalw Limit.thy [e_gr_def] (* e_gr_eq *) |
1842 val prems = goalw Limit.thy [e_gr_def] (* e_gr_eq *) |
1843 "!!x. m:nat ==> e_gr(DD,ee,m,m) = id(set(DD`m))"; |
1843 "!!x. m:nat ==> e_gr(DD,ee,m,m) = id(set(DD`m))"; |
1844 by (asm_simp_tac (!simpset addsimps[diff_self_eq_0]) 1); |
1844 by (asm_simp_tac (simpset() addsimps[diff_self_eq_0]) 1); |
1845 qed "e_gr_eq"; |
1845 qed "e_gr_eq"; |
1846 |
1846 |
1847 val prems = goalw Limit.thy [e_gr_def] (* e_gr_add *) |
1847 val prems = goalw Limit.thy [e_gr_def] (* e_gr_add *) |
1848 "!!x. [|n:nat; k:nat|] ==> \ |
1848 "!!x. [|n:nat; k:nat|] ==> \ |
1849 \ e_gr(DD,ee,succ(n#+k),n) = \ |
1849 \ e_gr(DD,ee,succ(n#+k),n) = \ |
1850 \ e_gr(DD,ee,n#+k,n) O Rp(DD`(n#+k),DD`succ(n#+k),ee`(n#+k))"; |
1850 \ e_gr(DD,ee,n#+k,n) O Rp(DD`(n#+k),DD`succ(n#+k),ee`(n#+k))"; |
1851 by (asm_simp_tac (!simpset addsimps [lemma_succ_sub,diff_add_inverse]) 1); |
1851 by (asm_simp_tac (simpset() addsimps [lemma_succ_sub,diff_add_inverse]) 1); |
1852 qed "e_gr_add"; |
1852 qed "e_gr_add"; |
1853 |
1853 |
1854 val prems = goal Limit.thy (* e_gr_le *) |
1854 val prems = goal Limit.thy (* e_gr_le *) |
1855 "[|n le m; m:nat; n:nat|] ==> \ |
1855 "[|n le m; m:nat; n:nat|] ==> \ |
1856 \ e_gr(DD,ee,succ(m),n) = e_gr(DD,ee,m,n) O Rp(DD`m,DD`succ(m),ee`m)"; |
1856 \ e_gr(DD,ee,succ(m),n) = e_gr(DD,ee,m,n) O Rp(DD`m,DD`succ(m),ee`m)"; |
1857 by (rtac le_exists 1); |
1857 by (rtac le_exists 1); |
1858 by (resolve_tac prems 1); |
1858 by (resolve_tac prems 1); |
1859 by (asm_simp_tac(!simpset addsimps(e_gr_add::prems)) 1); |
1859 by (asm_simp_tac(simpset() addsimps(e_gr_add::prems)) 1); |
1860 brr prems 1; |
1860 brr prems 1; |
1861 qed "e_gr_le"; |
1861 qed "e_gr_le"; |
1862 |
1862 |
1863 val prems = goal Limit.thy (* e_gr_succ *) |
1863 val prems = goal Limit.thy (* e_gr_succ *) |
1864 "m:nat ==> \ |
1864 "m:nat ==> \ |
1865 \ e_gr(DD,ee,succ(m),m) = id(set(DD`m)) O Rp(DD`m,DD`succ(m),ee`m)"; |
1865 \ e_gr(DD,ee,succ(m),m) = id(set(DD`m)) O Rp(DD`m,DD`succ(m),ee`m)"; |
1866 by (asm_simp_tac(!simpset addsimps(e_gr_le::e_gr_eq::prems)) 1); |
1866 by (asm_simp_tac(simpset() addsimps(e_gr_le::e_gr_eq::prems)) 1); |
1867 qed "e_gr_succ"; |
1867 qed "e_gr_succ"; |
1868 |
1868 |
1869 (* Cpo asm's due to THE uniqueness. *) |
1869 (* Cpo asm's due to THE uniqueness. *) |
1870 |
1870 |
1871 val prems = goal Limit.thy (* e_gr_succ_emb *) |
1871 val prems = goal Limit.thy (* e_gr_succ_emb *) |
1872 "[|emb_chain(DD,ee); m:nat|] ==> \ |
1872 "[|emb_chain(DD,ee); m:nat|] ==> \ |
1873 \ e_gr(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)"; |
1873 \ e_gr(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)"; |
1874 by (asm_simp_tac(!simpset addsimps(e_gr_succ::prems)) 1); |
1874 by (asm_simp_tac(simpset() addsimps(e_gr_succ::prems)) 1); |
1875 by (stac id_comp 1); |
1875 by (stac id_comp 1); |
1876 brr(Rp_cont::cont_fun::refl::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1; |
1876 brr(Rp_cont::cont_fun::refl::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1; |
1877 qed "e_gr_succ_emb"; |
1877 qed "e_gr_succ_emb"; |
1878 |
1878 |
1879 val prems = goal Limit.thy (* e_gr_fun_add *) |
1879 val prems = goal Limit.thy (* e_gr_fun_add *) |
1880 "[|emb_chain(DD,ee); n:nat; k:nat|] ==> \ |
1880 "[|emb_chain(DD,ee); n:nat; k:nat|] ==> \ |
1881 \ e_gr(DD,ee,n#+k,n): set(DD`(n#+k))->set(DD`n)"; |
1881 \ e_gr(DD,ee,n#+k,n): set(DD`(n#+k))->set(DD`n)"; |
1882 by (res_inst_tac[("n","k")]nat_induct 1); |
1882 by (res_inst_tac[("n","k")]nat_induct 1); |
1883 by (resolve_tac prems 1); |
1883 by (resolve_tac prems 1); |
1884 by (asm_simp_tac(!simpset addsimps(add_0_right::e_gr_eq::id_type::prems)) 1); |
1884 by (asm_simp_tac(simpset() addsimps(add_0_right::e_gr_eq::id_type::prems)) 1); |
1885 by (asm_simp_tac(!simpset addsimps(add_succ_right::e_gr_add::prems)) 1); |
1885 by (asm_simp_tac(simpset() addsimps(add_succ_right::e_gr_add::prems)) 1); |
1886 brr(comp_fun::Rp_cont::cont_fun::emb_chain_emb::emb_chain_cpo::add_type:: |
1886 brr(comp_fun::Rp_cont::cont_fun::emb_chain_emb::emb_chain_cpo::add_type:: |
1887 nat_succI::prems) 1; |
1887 nat_succI::prems) 1; |
1888 qed "e_gr_fun_add"; |
1888 qed "e_gr_fun_add"; |
1889 |
1889 |
1890 val prems = goal Limit.thy (* e_gr_fun *) |
1890 val prems = goal Limit.thy (* e_gr_fun *) |
1891 "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1891 "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1892 \ e_gr(DD,ee,m,n): set(DD`m)->set(DD`n)"; |
1892 \ e_gr(DD,ee,m,n): set(DD`m)->set(DD`n)"; |
1893 by (rtac le_exists 1); |
1893 by (rtac le_exists 1); |
1894 by (resolve_tac prems 1); |
1894 by (resolve_tac prems 1); |
1895 by (asm_simp_tac(!simpset addsimps(e_gr_fun_add::prems)) 1); |
1895 by (asm_simp_tac(simpset() addsimps(e_gr_fun_add::prems)) 1); |
1896 brr prems 1; |
1896 brr prems 1; |
1897 qed "e_gr_fun"; |
1897 qed "e_gr_fun"; |
1898 |
1898 |
1899 val prems = goal Limit.thy (* e_gr_split_add_lemma *) |
1899 val prems = goal Limit.thy (* e_gr_split_add_lemma *) |
1900 "[| emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
1900 "[| emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
1936 val prems = goal Limit.thy (* e_gr_cont_lemma *) |
1936 val prems = goal Limit.thy (* e_gr_cont_lemma *) |
1937 "[|emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1937 "[|emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1938 \ n le m --> e_gr(DD,ee,m,n):cont(DD`m,DD`n)"; |
1938 \ n le m --> e_gr(DD,ee,m,n):cont(DD`m,DD`n)"; |
1939 by (res_inst_tac[("n","m")]nat_induct 1); |
1939 by (res_inst_tac[("n","m")]nat_induct 1); |
1940 by (resolve_tac prems 1); |
1940 by (resolve_tac prems 1); |
1941 by (asm_full_simp_tac(!simpset addsimps |
1941 by (asm_full_simp_tac(simpset() addsimps |
1942 (le0_iff::e_gr_eq::nat_0I::prems)) 1); |
1942 (le0_iff::e_gr_eq::nat_0I::prems)) 1); |
1943 brr(impI::id_cont::emb_chain_cpo::nat_0I::prems) 1; |
1943 brr(impI::id_cont::emb_chain_cpo::nat_0I::prems) 1; |
1944 by (asm_full_simp_tac(!simpset addsimps[le_succ_iff]) 1); |
1944 by (asm_full_simp_tac(simpset() addsimps[le_succ_iff]) 1); |
1945 by (etac disjE 1); |
1945 by (etac disjE 1); |
1946 by (etac impE 1); |
1946 by (etac impE 1); |
1947 by (assume_tac 1); |
1947 by (assume_tac 1); |
1948 by (asm_simp_tac(!simpset addsimps(e_gr_le::prems)) 1); |
1948 by (asm_simp_tac(simpset() addsimps(e_gr_le::prems)) 1); |
1949 brr(comp_pres_cont::Rp_cont::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1; |
1949 brr(comp_pres_cont::Rp_cont::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1; |
1950 by (asm_simp_tac(!simpset addsimps(e_gr_eq::nat_succI::prems)) 1); |
1950 by (asm_simp_tac(simpset() addsimps(e_gr_eq::nat_succI::prems)) 1); |
1951 brr(id_cont::emb_chain_cpo::nat_succI::prems) 1; |
1951 brr(id_cont::emb_chain_cpo::nat_succI::prems) 1; |
1952 qed "e_gr_cont_lemma"; |
1952 qed "e_gr_cont_lemma"; |
1953 |
1953 |
1954 val prems = goal Limit.thy (* e_gr_cont *) |
1954 val prems = goal Limit.thy (* e_gr_cont *) |
1955 "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1955 "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
1994 (* Use mp to prepare for induction. *) |
1994 (* Use mp to prepare for induction. *) |
1995 by (rtac mp 1); |
1995 by (rtac mp 1); |
1996 by (resolve_tac prems 2); |
1996 by (resolve_tac prems 2); |
1997 by (res_inst_tac[("n","k")]nat_induct 1); |
1997 by (res_inst_tac[("n","k")]nat_induct 1); |
1998 by (resolve_tac prems 1); |
1998 by (resolve_tac prems 1); |
1999 by (asm_full_simp_tac(!simpset addsimps |
1999 by (asm_full_simp_tac(simpset() addsimps |
2000 (add_0_right::e_gr_eq::e_less_eq::(id_type RS id_comp)::prems)) 1); |
2000 (add_0_right::e_gr_eq::e_less_eq::(id_type RS id_comp)::prems)) 1); |
2001 by (simp_tac(ZF_ss addsimps[le_succ_iff]) 1); |
2001 by (simp_tac(ZF_ss addsimps[le_succ_iff]) 1); |
2002 by (rtac impI 1); |
2002 by (rtac impI 1); |
2003 by (etac disjE 1); |
2003 by (etac disjE 1); |
2004 by (etac impE 1); |
2004 by (etac impE 1); |
2019 |
2019 |
2020 |
2020 |
2021 val prems = goalw Limit.thy [eps_def] (* emb_eps *) |
2021 val prems = goalw Limit.thy [eps_def] (* emb_eps *) |
2022 "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
2022 "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
2023 \ emb(DD`m,DD`n,eps(DD,ee,m,n))"; |
2023 \ emb(DD`m,DD`n,eps(DD,ee,m,n))"; |
2024 by (asm_simp_tac(!simpset addsimps prems) 1); |
2024 by (asm_simp_tac(simpset() addsimps prems) 1); |
2025 brr(emb_e_less::prems) 1; |
2025 brr(emb_e_less::prems) 1; |
2026 qed "emb_eps"; |
2026 qed "emb_eps"; |
2027 |
2027 |
2028 val prems = goalw Limit.thy [eps_def] (* eps_fun *) |
2028 val prems = goalw Limit.thy [eps_def] (* eps_fun *) |
2029 "[|emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
2029 "[|emb_chain(DD,ee); m:nat; n:nat|] ==> \ |
2030 \ eps(DD,ee,m,n): set(DD`m)->set(DD`n)"; |
2030 \ eps(DD,ee,m,n): set(DD`m)->set(DD`n)"; |
2031 by (rtac (expand_if RS iffD2) 1); |
2031 by (rtac (expand_if RS iffD2) 1); |
2032 by (safe_tac (!claset)); |
2032 by (safe_tac (claset())); |
2033 brr((e_less_cont RS cont_fun)::prems) 1; |
2033 brr((e_less_cont RS cont_fun)::prems) 1; |
2034 brr((not_le_iff_lt RS iffD1 RS leI)::e_gr_fun::nat_into_Ord::prems) 1; |
2034 brr((not_le_iff_lt RS iffD1 RS leI)::e_gr_fun::nat_into_Ord::prems) 1; |
2035 qed "eps_fun"; |
2035 qed "eps_fun"; |
2036 |
2036 |
2037 val eps_id = prove_goalw Limit.thy [eps_def] |
2037 val eps_id = prove_goalw Limit.thy [eps_def] |
2038 "n:nat ==> eps(DD,ee,n,n) = id(set(DD`n))" |
2038 "n:nat ==> eps(DD,ee,n,n) = id(set(DD`n))" |
2039 (fn prems => [simp_tac(!simpset addsimps(e_less_eq::nat_le_refl::prems)) 1]); |
2039 (fn prems => [simp_tac(simpset() addsimps(e_less_eq::nat_le_refl::prems)) 1]); |
2040 |
2040 |
2041 val eps_e_less_add = prove_goalw Limit.thy [eps_def] |
2041 val eps_e_less_add = prove_goalw Limit.thy [eps_def] |
2042 "[|m:nat; n:nat|] ==> eps(DD,ee,m,m#+n) = e_less(DD,ee,m,m#+n)" |
2042 "[|m:nat; n:nat|] ==> eps(DD,ee,m,m#+n) = e_less(DD,ee,m,m#+n)" |
2043 (fn prems => [simp_tac(!simpset addsimps(add_le_self::prems)) 1]); |
2043 (fn prems => [simp_tac(simpset() addsimps(add_le_self::prems)) 1]); |
2044 |
2044 |
2045 val eps_e_less = prove_goalw Limit.thy [eps_def] |
2045 val eps_e_less = prove_goalw Limit.thy [eps_def] |
2046 "[|m le n; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_less(DD,ee,m,n)" |
2046 "[|m le n; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_less(DD,ee,m,n)" |
2047 (fn prems => [simp_tac(!simpset addsimps prems) 1]); |
2047 (fn prems => [simp_tac(simpset() addsimps prems) 1]); |
2048 |
2048 |
2049 val shift_asm = imp_refl RS mp; |
2049 val shift_asm = imp_refl RS mp; |
2050 |
2050 |
2051 val prems = goalw Limit.thy [eps_def] (* eps_e_gr_add *) |
2051 val prems = goalw Limit.thy [eps_def] (* eps_e_gr_add *) |
2052 "[|n:nat; k:nat|] ==> eps(DD,ee,n#+k,n) = e_gr(DD,ee,n#+k,n)"; |
2052 "[|n:nat; k:nat|] ==> eps(DD,ee,n#+k,n) = e_gr(DD,ee,n#+k,n)"; |
2053 by (rtac (expand_if RS iffD2) 1); |
2053 by (rtac (expand_if RS iffD2) 1); |
2054 by (safe_tac (!claset)); |
2054 by (safe_tac (claset())); |
2055 by (etac leE 1); |
2055 by (etac leE 1); |
2056 (* Must control rewriting by instantiating a variable. *) |
2056 (* Must control rewriting by instantiating a variable. *) |
2057 by (asm_full_simp_tac(!simpset addsimps |
2057 by (asm_full_simp_tac(simpset() addsimps |
2058 ((hd prems RS nat_into_Ord RS not_le_iff_lt RS iff_sym)::nat_into_Ord:: |
2058 ((hd prems RS nat_into_Ord RS not_le_iff_lt RS iff_sym)::nat_into_Ord:: |
2059 add_le_self::prems)) 1); |
2059 add_le_self::prems)) 1); |
2060 by (asm_simp_tac(!simpset addsimps(e_less_eq::e_gr_eq::prems)) 1); |
2060 by (asm_simp_tac(simpset() addsimps(e_less_eq::e_gr_eq::prems)) 1); |
2061 qed "eps_e_gr_add"; |
2061 qed "eps_e_gr_add"; |
2062 |
2062 |
2063 val prems = goalw Limit.thy [] (* eps_e_gr *) |
2063 val prems = goalw Limit.thy [] (* eps_e_gr *) |
2064 "[|n le m; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_gr(DD,ee,m,n)"; |
2064 "[|n le m; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_gr(DD,ee,m,n)"; |
2065 by (rtac le_exists 1); |
2065 by (rtac le_exists 1); |
2066 by (resolve_tac prems 1); |
2066 by (resolve_tac prems 1); |
2067 by (asm_simp_tac(!simpset addsimps(eps_e_gr_add::prems)) 1); |
2067 by (asm_simp_tac(simpset() addsimps(eps_e_gr_add::prems)) 1); |
2068 brr prems 1; |
2068 brr prems 1; |
2069 qed "eps_e_gr"; |
2069 qed "eps_e_gr"; |
2070 |
2070 |
2071 val prems = goal Limit.thy (* eps_succ_ee *) |
2071 val prems = goal Limit.thy (* eps_succ_ee *) |
2072 "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==> \ |
2072 "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==> \ |
2073 \ eps(DD,ee,m,succ(m)) = ee`m"; |
2073 \ eps(DD,ee,m,succ(m)) = ee`m"; |
2074 by (asm_simp_tac(!simpset addsimps(eps_e_less::le_succ_iff::e_less_succ_emb:: |
2074 by (asm_simp_tac(simpset() addsimps(eps_e_less::le_succ_iff::e_less_succ_emb:: |
2075 prems)) 1); |
2075 prems)) 1); |
2076 qed "eps_succ_ee"; |
2076 qed "eps_succ_ee"; |
2077 |
2077 |
2078 val prems = goal Limit.thy (* eps_succ_Rp *) |
2078 val prems = goal Limit.thy (* eps_succ_Rp *) |
2079 "[|emb_chain(DD,ee); m:nat|] ==> \ |
2079 "[|emb_chain(DD,ee); m:nat|] ==> \ |
2080 \ eps(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)"; |
2080 \ eps(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)"; |
2081 by (asm_simp_tac(!simpset addsimps(eps_e_gr::le_succ_iff::e_gr_succ_emb:: |
2081 by (asm_simp_tac(simpset() addsimps(eps_e_gr::le_succ_iff::e_gr_succ_emb:: |
2082 prems)) 1); |
2082 prems)) 1); |
2083 qed "eps_succ_Rp"; |
2083 qed "eps_succ_Rp"; |
2084 |
2084 |
2085 val prems = goal Limit.thy (* eps_cont *) |
2085 val prems = goal Limit.thy (* eps_cont *) |
2086 "[|emb_chain(DD,ee); m:nat; n:nat|] ==> eps(DD,ee,m,n): cont(DD`m,DD`n)"; |
2086 "[|emb_chain(DD,ee); m:nat; n:nat|] ==> eps(DD,ee,m,n): cont(DD`m,DD`n)"; |
2087 by (rtac nat_linear_le 1); |
2087 by (rtac nat_linear_le 1); |
2088 by (resolve_tac prems 1); |
2088 by (resolve_tac prems 1); |
2089 by (rtac (hd(rev prems)) 1); |
2089 by (rtac (hd(rev prems)) 1); |
2090 by (asm_simp_tac(!simpset addsimps(eps_e_less::e_less_cont::prems)) 1); |
2090 by (asm_simp_tac(simpset() addsimps(eps_e_less::e_less_cont::prems)) 1); |
2091 by (asm_simp_tac(!simpset addsimps(eps_e_gr::e_gr_cont::prems)) 1); |
2091 by (asm_simp_tac(simpset() addsimps(eps_e_gr::e_gr_cont::prems)) 1); |
2092 qed "eps_cont"; |
2092 qed "eps_cont"; |
2093 |
2093 |
2094 (* Theorems about splitting. *) |
2094 (* Theorems about splitting. *) |
2095 |
2095 |
2096 val prems = goal Limit.thy (* eps_split_add_left *) |
2096 val prems = goal Limit.thy (* eps_split_add_left *) |
2097 "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2097 "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2098 \ eps(DD,ee,m,m#+k) = eps(DD,ee,m#+n,m#+k) O eps(DD,ee,m,m#+n)"; |
2098 \ eps(DD,ee,m,m#+k) = eps(DD,ee,m#+n,m#+k) O eps(DD,ee,m,m#+n)"; |
2099 by (asm_simp_tac(!simpset addsimps |
2099 by (asm_simp_tac(simpset() addsimps |
2100 (eps_e_less::add_le_self::add_le_mono::prems)) 1); |
2100 (eps_e_less::add_le_self::add_le_mono::prems)) 1); |
2101 brr(e_less_split_add::prems) 1; |
2101 brr(e_less_split_add::prems) 1; |
2102 qed "eps_split_add_left"; |
2102 qed "eps_split_add_left"; |
2103 |
2103 |
2104 val prems = goal Limit.thy (* eps_split_add_left_rev *) |
2104 val prems = goal Limit.thy (* eps_split_add_left_rev *) |
2105 "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2105 "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2106 \ eps(DD,ee,m,m#+n) = eps(DD,ee,m#+k,m#+n) O eps(DD,ee,m,m#+k)"; |
2106 \ eps(DD,ee,m,m#+n) = eps(DD,ee,m#+k,m#+n) O eps(DD,ee,m,m#+k)"; |
2107 by (asm_simp_tac(!simpset addsimps |
2107 by (asm_simp_tac(simpset() addsimps |
2108 (eps_e_less_add::eps_e_gr::add_le_self::add_le_mono::prems)) 1); |
2108 (eps_e_less_add::eps_e_gr::add_le_self::add_le_mono::prems)) 1); |
2109 brr(e_less_e_gr_split_add::prems) 1; |
2109 brr(e_less_e_gr_split_add::prems) 1; |
2110 qed "eps_split_add_left_rev"; |
2110 qed "eps_split_add_left_rev"; |
2111 |
2111 |
2112 val prems = goal Limit.thy (* eps_split_add_right *) |
2112 val prems = goal Limit.thy (* eps_split_add_right *) |
2113 "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2113 "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2114 \ eps(DD,ee,n#+k,n) = eps(DD,ee,n#+m,n) O eps(DD,ee,n#+k,n#+m)"; |
2114 \ eps(DD,ee,n#+k,n) = eps(DD,ee,n#+m,n) O eps(DD,ee,n#+k,n#+m)"; |
2115 by (asm_simp_tac(!simpset addsimps |
2115 by (asm_simp_tac(simpset() addsimps |
2116 (eps_e_gr::add_le_self::add_le_mono::prems)) 1); |
2116 (eps_e_gr::add_le_self::add_le_mono::prems)) 1); |
2117 brr(e_gr_split_add::prems) 1; |
2117 brr(e_gr_split_add::prems) 1; |
2118 qed "eps_split_add_right"; |
2118 qed "eps_split_add_right"; |
2119 |
2119 |
2120 val prems = goal Limit.thy (* eps_split_add_right_rev *) |
2120 val prems = goal Limit.thy (* eps_split_add_right_rev *) |
2121 "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2121 "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==> \ |
2122 \ eps(DD,ee,n#+m,n) = eps(DD,ee,n#+k,n) O eps(DD,ee,n#+m,n#+k)"; |
2122 \ eps(DD,ee,n#+m,n) = eps(DD,ee,n#+k,n) O eps(DD,ee,n#+m,n#+k)"; |
2123 by (asm_simp_tac(!simpset addsimps |
2123 by (asm_simp_tac(simpset() addsimps |
2124 (eps_e_gr_add::eps_e_less::add_le_self::add_le_mono::prems)) 1); |
2124 (eps_e_gr_add::eps_e_less::add_le_self::add_le_mono::prems)) 1); |
2125 brr(e_gr_e_less_split_add::prems) 1; |
2125 brr(e_gr_e_less_split_add::prems) 1; |
2126 qed "eps_split_add_right_rev"; |
2126 qed "eps_split_add_right_rev"; |
2127 |
2127 |
2128 (* Arithmetic, little support in Isabelle/ZF. *) |
2128 (* Arithmetic, little support in Isabelle/ZF. *) |
2229 but since x le y is x<succ(y) simplification does too much with this thm. *) |
2229 but since x le y is x<succ(y) simplification does too much with this thm. *) |
2230 by (stac eps_split_right_le 1); |
2230 by (stac eps_split_right_le 1); |
2231 by (assume_tac 2); |
2231 by (assume_tac 2); |
2232 by (asm_simp_tac(ZF_ss addsimps [add1]) 1); |
2232 by (asm_simp_tac(ZF_ss addsimps [add1]) 1); |
2233 brr(add_le_self::nat_0I::nat_succI::prems) 1; |
2233 brr(add_le_self::nat_0I::nat_succI::prems) 1; |
2234 by (asm_simp_tac(!simpset addsimps(eps_succ_Rp::prems)) 1); |
2234 by (asm_simp_tac(simpset() addsimps(eps_succ_Rp::prems)) 1); |
2235 by (stac comp_fun_apply 1); |
2235 by (stac comp_fun_apply 1); |
2236 brr(eps_fun::nat_succI::(Rp_cont RS cont_fun)::emb_chain_emb:: |
2236 brr(eps_fun::nat_succI::(Rp_cont RS cont_fun)::emb_chain_emb:: |
2237 emb_chain_cpo::refl::prems) 1; |
2237 emb_chain_cpo::refl::prems) 1; |
2238 (* Now the second part of the proof. Slightly different than HOL. *) |
2238 (* Now the second part of the proof. Slightly different than HOL. *) |
2239 by (asm_simp_tac(!simpset addsimps(eps_e_less::nat_succI::prems)) 1); |
2239 by (asm_simp_tac(simpset() addsimps(eps_e_less::nat_succI::prems)) 1); |
2240 by (etac (le_iff RS iffD1 RS disjE) 1); |
2240 by (etac (le_iff RS iffD1 RS disjE) 1); |
2241 by (asm_simp_tac(!simpset addsimps(e_less_le::prems)) 1); |
2241 by (asm_simp_tac(simpset() addsimps(e_less_le::prems)) 1); |
2242 by (stac comp_fun_apply 1); |
2242 by (stac comp_fun_apply 1); |
2243 brr(e_less_cont::cont_fun::emb_chain_emb::emb_cont::prems) 1; |
2243 brr(e_less_cont::cont_fun::emb_chain_emb::emb_cont::prems) 1; |
2244 by (stac embRp_eq_thm 1); |
2244 by (stac embRp_eq_thm 1); |
2245 brr(emb_chain_emb::(e_less_cont RS cont_fun RS apply_type)::emb_chain_cpo:: |
2245 brr(emb_chain_emb::(e_less_cont RS cont_fun RS apply_type)::emb_chain_cpo:: |
2246 nat_succI::prems) 1; |
2246 nat_succI::prems) 1; |
2247 by (asm_simp_tac(!simpset addsimps(eps_e_less::prems)) 1); |
2247 by (asm_simp_tac(simpset() addsimps(eps_e_less::prems)) 1); |
2248 by (dtac shift_asm 1); |
2248 by (dtac shift_asm 1); |
2249 by (asm_full_simp_tac(!simpset addsimps(eps_succ_Rp::e_less_eq::id_apply:: |
2249 by (asm_full_simp_tac(simpset() addsimps(eps_succ_Rp::e_less_eq::id_apply:: |
2250 nat_succI::prems)) 1); |
2250 nat_succI::prems)) 1); |
2251 qed "rho_emb_fun"; |
2251 qed "rho_emb_fun"; |
2252 |
2252 |
2253 val rho_emb_apply1 = prove_goalw Limit.thy [rho_emb_def] |
2253 val rho_emb_apply1 = prove_goalw Limit.thy [rho_emb_def] |
2254 "!!z. x:set(DD`n) ==> rho_emb(DD,ee,n)`x = (lam m:nat. eps(DD,ee,n,m)`x)" |
2254 "!!z. x:set(DD`n) ==> rho_emb(DD,ee,n)`x = (lam m:nat. eps(DD,ee,n,m)`x)" |
2258 "!!z. [|x:set(DD`n); m:nat|] ==> rho_emb(DD,ee,n)`x`m = eps(DD,ee,n,m)`x" |
2258 "!!z. [|x:set(DD`n); m:nat|] ==> rho_emb(DD,ee,n)`x`m = eps(DD,ee,n,m)`x" |
2259 (fn prems => [Asm_simp_tac 1]); |
2259 (fn prems => [Asm_simp_tac 1]); |
2260 |
2260 |
2261 val rho_emb_id = prove_goal Limit.thy |
2261 val rho_emb_id = prove_goal Limit.thy |
2262 "!!z. [| x:set(DD`n); n:nat|] ==> rho_emb(DD,ee,n)`x`n = x" |
2262 "!!z. [| x:set(DD`n); n:nat|] ==> rho_emb(DD,ee,n)`x`n = x" |
2263 (fn prems => [asm_simp_tac(!simpset addsimps[rho_emb_apply2,eps_id,id_thm]) 1]); |
2263 (fn prems => [asm_simp_tac(simpset() addsimps[rho_emb_apply2,eps_id,id_thm]) 1]); |
2264 |
2264 |
2265 (* Shorter proof, 23 against 62. *) |
2265 (* Shorter proof, 23 against 62. *) |
2266 |
2266 |
2267 val prems = goalw Limit.thy [] (* rho_emb_cont *) |
2267 val prems = goalw Limit.thy [] (* rho_emb_cont *) |
2268 "[|emb_chain(DD,ee); n:nat|] ==> \ |
2268 "[|emb_chain(DD,ee); n:nat|] ==> \ |
2277 by (stac lub_Dinf 1); |
2277 by (stac lub_Dinf 1); |
2278 by (rtac chainI 1); |
2278 by (rtac chainI 1); |
2279 brr(lam_type::(rho_emb_fun RS apply_type)::chain_in::prems) 1; |
2279 brr(lam_type::(rho_emb_fun RS apply_type)::chain_in::prems) 1; |
2280 by (Asm_simp_tac 1); |
2280 by (Asm_simp_tac 1); |
2281 by (rtac rel_DinfI 1); |
2281 by (rtac rel_DinfI 1); |
2282 by (asm_simp_tac(!simpset addsimps (rho_emb_apply2::chain_in::[])) 1); |
2282 by (asm_simp_tac(simpset() addsimps (rho_emb_apply2::chain_in::[])) 1); |
2283 brr((eps_cont RS cont_mono)::chain_rel::Dinf_prod:: |
2283 brr((eps_cont RS cont_mono)::chain_rel::Dinf_prod:: |
2284 (rho_emb_fun RS apply_type)::chain_in::nat_succI::prems) 1; |
2284 (rho_emb_fun RS apply_type)::chain_in::nat_succI::prems) 1; |
2285 (* Now, back to the result of applying lub_Dinf *) |
2285 (* Now, back to the result of applying lub_Dinf *) |
2286 by (asm_simp_tac(!simpset addsimps (rho_emb_apply2::chain_in::[])) 1); |
2286 by (asm_simp_tac(simpset() addsimps (rho_emb_apply2::chain_in::[])) 1); |
2287 by (stac rho_emb_apply1 1); |
2287 by (stac rho_emb_apply1 1); |
2288 brr((cpo_lub RS islub_in)::emb_chain_cpo::prems) 1; |
2288 brr((cpo_lub RS islub_in)::emb_chain_cpo::prems) 1; |
2289 by (rtac fun_extension 1); |
2289 by (rtac fun_extension 1); |
2290 brr(lam_type::(eps_cont RS cont_fun RS apply_type)::(cpo_lub RS islub_in):: |
2290 brr(lam_type::(eps_cont RS cont_fun RS apply_type)::(cpo_lub RS islub_in):: |
2291 emb_chain_cpo::prems) 1; |
2291 emb_chain_cpo::prems) 1; |
2292 brr(cont_chain::eps_cont::emb_chain_cpo::prems) 1; |
2292 brr(cont_chain::eps_cont::emb_chain_cpo::prems) 1; |
2293 by (Asm_simp_tac 1); |
2293 by (Asm_simp_tac 1); |
2294 by (asm_simp_tac(!simpset addsimps((eps_cont RS cont_lub)::prems)) 1); |
2294 by (asm_simp_tac(simpset() addsimps((eps_cont RS cont_lub)::prems)) 1); |
2295 qed "rho_emb_cont"; |
2295 qed "rho_emb_cont"; |
2296 |
2296 |
2297 (* 32 vs 61, using safe_tac with imp in asm would be unfortunate (5steps) *) |
2297 (* 32 vs 61, using safe_tac with imp in asm would be unfortunate (5steps) *) |
2298 |
2298 |
2299 val prems = goalw Limit.thy [] (* lemma1 *) |
2299 val prems = goalw Limit.thy [] (* lemma1 *) |
2300 "[|m le n; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==> \ |
2300 "[|m le n; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==> \ |
2301 \ rel(DD`n,e_less(DD,ee,m,n)`(x`m),x`n)"; |
2301 \ rel(DD`n,e_less(DD,ee,m,n)`(x`m),x`n)"; |
2302 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2); (* For induction proof *) |
2302 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2); (* For induction proof *) |
2303 by (res_inst_tac[("n","n")]nat_induct 1); |
2303 by (res_inst_tac[("n","n")]nat_induct 1); |
2304 by (rtac impI 2); |
2304 by (rtac impI 2); |
2305 by (asm_full_simp_tac (!simpset addsimps (e_less_eq::prems)) 2); |
2305 by (asm_full_simp_tac (simpset() addsimps (e_less_eq::prems)) 2); |
2306 by (stac id_thm 2); |
2306 by (stac id_thm 2); |
2307 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1; |
2307 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1; |
2308 by (asm_full_simp_tac (!simpset addsimps [le_succ_iff]) 1); |
2308 by (asm_full_simp_tac (simpset() addsimps [le_succ_iff]) 1); |
2309 by (rtac impI 1); |
2309 by (rtac impI 1); |
2310 by (etac disjE 1); |
2310 by (etac disjE 1); |
2311 by (dtac mp 1 THEN atac 1); |
2311 by (dtac mp 1 THEN atac 1); |
2312 by (rtac cpo_trans 1); |
2312 by (rtac cpo_trans 1); |
2313 by (stac e_less_le 2); |
2313 by (stac e_less_le 2); |
2328 (* Dinf and cont_fun doesn't go well together, both Pi(_,%x._). *) |
2328 (* Dinf and cont_fun doesn't go well together, both Pi(_,%x._). *) |
2329 (* brr solves 11 of 12 subgoals *) |
2329 (* brr solves 11 of 12 subgoals *) |
2330 brr((hd(tl(tl prems)) RS Dinf_prod RS apply_type)::cont_fun::Rp_cont:: |
2330 brr((hd(tl(tl prems)) RS Dinf_prod RS apply_type)::cont_fun::Rp_cont:: |
2331 e_less_cont::emb_cont::emb_chain_emb::emb_chain_cpo::apply_type:: |
2331 e_less_cont::emb_cont::emb_chain_emb::emb_chain_cpo::apply_type:: |
2332 embRp_rel::(disjI1 RS (le_succ_iff RS iffD2))::nat_succI::prems) 1; |
2332 embRp_rel::(disjI1 RS (le_succ_iff RS iffD2))::nat_succI::prems) 1; |
2333 by (asm_full_simp_tac (!simpset addsimps (e_less_eq::prems)) 1); |
2333 by (asm_full_simp_tac (simpset() addsimps (e_less_eq::prems)) 1); |
2334 by (stac id_thm 1); |
2334 by (stac id_thm 1); |
2335 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1; |
2335 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1; |
2336 val lemma1 = result(); |
2336 val lemma1 = result(); |
2337 |
2337 |
2338 (* 18 vs 40 *) |
2338 (* 18 vs 40 *) |
2341 "[|n le m; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==> \ |
2341 "[|n le m; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==> \ |
2342 \ rel(DD`n,e_gr(DD,ee,m,n)`(x`m),x`n)"; |
2342 \ rel(DD`n,e_gr(DD,ee,m,n)`(x`m),x`n)"; |
2343 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2); (* For induction proof *) |
2343 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2); (* For induction proof *) |
2344 by (res_inst_tac[("n","m")]nat_induct 1); |
2344 by (res_inst_tac[("n","m")]nat_induct 1); |
2345 by (rtac impI 2); |
2345 by (rtac impI 2); |
2346 by (asm_full_simp_tac (!simpset addsimps (e_gr_eq::prems)) 2); |
2346 by (asm_full_simp_tac (simpset() addsimps (e_gr_eq::prems)) 2); |
2347 by (stac id_thm 2); |
2347 by (stac id_thm 2); |
2348 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1; |
2348 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1; |
2349 by (asm_full_simp_tac (!simpset addsimps [le_succ_iff]) 1); |
2349 by (asm_full_simp_tac (simpset() addsimps [le_succ_iff]) 1); |
2350 by (rtac impI 1); |
2350 by (rtac impI 1); |
2351 by (etac disjE 1); |
2351 by (etac disjE 1); |
2352 by (dtac mp 1 THEN atac 1); |
2352 by (dtac mp 1 THEN atac 1); |
2353 by (stac e_gr_le 1); |
2353 by (stac e_gr_le 1); |
2354 by (stac comp_fun_apply 4); |
2354 by (stac comp_fun_apply 4); |
2355 by (stac Dinf_eq 7); |
2355 by (stac Dinf_eq 7); |
2356 brr(emb_chain_emb::emb_chain_cpo::Rp_cont::e_gr_cont::cont_fun::emb_cont:: |
2356 brr(emb_chain_emb::emb_chain_cpo::Rp_cont::e_gr_cont::cont_fun::emb_cont:: |
2357 apply_type::Dinf_prod::nat_succI::prems) 1; |
2357 apply_type::Dinf_prod::nat_succI::prems) 1; |
2358 by (asm_full_simp_tac (!simpset addsimps (e_gr_eq::prems)) 1); |
2358 by (asm_full_simp_tac (simpset() addsimps (e_gr_eq::prems)) 1); |
2359 by (stac id_thm 1); |
2359 by (stac id_thm 1); |
2360 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1; |
2360 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1; |
2361 val lemma2 = result(); |
2361 val lemma2 = result(); |
2362 |
2362 |
2363 val prems = goalw Limit.thy [eps_def] (* eps1 *) |
2363 val prems = goalw Limit.thy [eps_def] (* eps1 *) |
2379 brr(lam_type::apply_type::Dinf_prod::prems) 1; |
2379 brr(lam_type::apply_type::Dinf_prod::prems) 1; |
2380 by (Asm_simp_tac 1); |
2380 by (Asm_simp_tac 1); |
2381 brr(rel_Dinf::prems) 1; |
2381 brr(rel_Dinf::prems) 1; |
2382 by (stac beta 1); |
2382 by (stac beta 1); |
2383 brr(cpo_Dinf::islub_in::cpo_lub::prems) 1; |
2383 brr(cpo_Dinf::islub_in::cpo_lub::prems) 1; |
2384 by (asm_simp_tac(!simpset addsimps(chain_in::lub_Dinf::prems)) 1); |
2384 by (asm_simp_tac(simpset() addsimps(chain_in::lub_Dinf::prems)) 1); |
2385 qed "lam_Dinf_cont"; |
2385 qed "lam_Dinf_cont"; |
2386 |
2386 |
2387 val prems = goalw Limit.thy [rho_proj_def] (* rho_projpair *) |
2387 val prems = goalw Limit.thy [rho_proj_def] (* rho_projpair *) |
2388 "[| emb_chain(DD,ee); n:nat |] ==> \ |
2388 "[| emb_chain(DD,ee); n:nat |] ==> \ |
2389 \ projpair(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n),rho_proj(DD,ee,n))"; |
2389 \ projpair(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n),rho_proj(DD,ee,n))"; |
2431 |
2431 |
2432 val prems = goalw Limit.thy [commute_def] (* commuteI *) |
2432 val prems = goalw Limit.thy [commute_def] (* commuteI *) |
2433 "[| !!n. n:nat ==> emb(DD`n,E,r(n)); \ |
2433 "[| !!n. n:nat ==> emb(DD`n,E,r(n)); \ |
2434 \ !!m n. [|m le n; m:nat; n:nat|] ==> r(n) O eps(DD,ee,m,n) = r(m) |] ==> \ |
2434 \ !!m n. [|m le n; m:nat; n:nat|] ==> r(n) O eps(DD,ee,m,n) = r(m) |] ==> \ |
2435 \ commute(DD,ee,E,r)"; |
2435 \ commute(DD,ee,E,r)"; |
2436 by (safe_tac (!claset)); |
2436 by (safe_tac (claset())); |
2437 brr prems 1; |
2437 brr prems 1; |
2438 qed "commuteI"; |
2438 qed "commuteI"; |
2439 |
2439 |
2440 val prems = goalw Limit.thy [commute_def] (* commute_emb *) |
2440 val prems = goalw Limit.thy [commute_def] (* commute_emb *) |
2441 "!!z. [| commute(DD,ee,E,r); n:nat |] ==> emb(DD`n,E,r(n))"; |
2441 "!!z. [| commute(DD,ee,E,r); n:nat |] ==> emb(DD`n,E,r(n))"; |
2457 by (rtac fun_extension 1); (* Manual instantiation in HOL. *) |
2457 by (rtac fun_extension 1); (* Manual instantiation in HOL. *) |
2458 by (stac comp_fun_apply 3); |
2458 by (stac comp_fun_apply 3); |
2459 by (rtac fun_extension 6); (* Next, clean up and instantiate unknowns *) |
2459 by (rtac fun_extension 6); (* Next, clean up and instantiate unknowns *) |
2460 brr(comp_fun::rho_emb_fun::eps_fun::Dinf_prod::apply_type::prems) 1; |
2460 brr(comp_fun::rho_emb_fun::eps_fun::Dinf_prod::apply_type::prems) 1; |
2461 by (asm_simp_tac |
2461 by (asm_simp_tac |
2462 (!simpset addsimps(rho_emb_apply2::(eps_fun RS apply_type)::prems)) 1); |
2462 (simpset() addsimps(rho_emb_apply2::(eps_fun RS apply_type)::prems)) 1); |
2463 by (rtac (comp_fun_apply RS subst) 1); |
2463 by (rtac (comp_fun_apply RS subst) 1); |
2464 by (rtac (eps_split_left RS subst) 4); |
2464 by (rtac (eps_split_left RS subst) 4); |
2465 brr(eps_fun::refl::prems) 1; |
2465 brr(eps_fun::refl::prems) 1; |
2466 qed "rho_emb_commute"; |
2466 qed "rho_emb_commute"; |
2467 |
2467 |
2547 brr(cpo_lub::rho_emb_chain::cpo_cf::cpo_Dinf::isubI::cont_cf::id_cont::prems) 1; |
2547 brr(cpo_lub::rho_emb_chain::cpo_cf::cpo_Dinf::isubI::cont_cf::id_cont::prems) 1; |
2548 by (Asm_simp_tac 1); |
2548 by (Asm_simp_tac 1); |
2549 brr(embRp_rel::emb_rho_emb::emb_chain_cpo::cpo_Dinf::prems) 1; |
2549 brr(embRp_rel::emb_rho_emb::emb_chain_cpo::cpo_Dinf::prems) 1; |
2550 by (rtac rel_cfI 1); |
2550 by (rtac rel_cfI 1); |
2551 by (asm_simp_tac |
2551 by (asm_simp_tac |
2552 (!simpset addsimps(id_thm::lub_cf::rho_emb_chain::cpo_Dinf::prems)) 1); |
2552 (simpset() addsimps(id_thm::lub_cf::rho_emb_chain::cpo_Dinf::prems)) 1); |
2553 by (rtac rel_DinfI 1); (* Addtional assumptions *) |
2553 by (rtac rel_DinfI 1); (* Addtional assumptions *) |
2554 by (stac lub_Dinf 1); |
2554 by (stac lub_Dinf 1); |
2555 brr(rho_emb_chain_apply1::prems) 1; |
2555 brr(rho_emb_chain_apply1::prems) 1; |
2556 brr(Dinf_prod::(cpo_lub RS islub_in)::id_cont::cpo_Dinf::cpo_cf::cf_cont:: |
2556 brr(Dinf_prod::(cpo_lub RS islub_in)::id_cont::cpo_Dinf::cpo_cf::cf_cont:: |
2557 rho_emb_chain::rho_emb_chain_apply1::(id_cont RS cont_cf)::prems) 2; |
2557 rho_emb_chain::rho_emb_chain_apply1::(id_cont RS cont_cf)::prems) 2; |
2647 by (stac id_comp 4); |
2647 by (stac id_comp 4); |
2648 brr(cont_fun::Rp_cont::emb_r::emb_f::emb_chain_cpo::refl::prems) 1; |
2648 brr(cont_fun::Rp_cont::emb_r::emb_f::emb_chain_cpo::refl::prems) 1; |
2649 val lemma = result(); |
2649 val lemma = result(); |
2650 |
2650 |
2651 val lemma_assoc = prove_goal Limit.thy "a O b O c O d = a O (b O c) O d" |
2651 val lemma_assoc = prove_goal Limit.thy "a O b O c O d = a O (b O c) O d" |
2652 (fn prems => [simp_tac (!simpset addsimps[comp_assoc]) 1]); |
2652 (fn prems => [simp_tac (simpset() addsimps[comp_assoc]) 1]); |
2653 |
2653 |
2654 fun elem n l = if n = 1 then hd l else elem(n-1)(tl l); |
2654 fun elem n l = if n = 1 then hd l else elem(n-1)(tl l); |
2655 |
2655 |
2656 (* Shorter proof (but lemmas): 19 vs 79 (103 - 24, due to OAssoc) *) |
2656 (* Shorter proof (but lemmas): 19 vs 79 (103 - 24, due to OAssoc) *) |
2657 |
2657 |
2661 \ emb_chain(DD,ee); cpo(E); cpo(G) |] ==> \ |
2661 \ emb_chain(DD,ee); cpo(E); cpo(G) |] ==> \ |
2662 \ projpair \ |
2662 \ projpair \ |
2663 \ (E,G, \ |
2663 \ (E,G, \ |
2664 \ lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n))), \ |
2664 \ lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n))), \ |
2665 \ lub(cf(G,E), lam n:nat. r(n) O Rp(DD`n,G,f(n))))"; |
2665 \ lub(cf(G,E), lam n:nat. r(n) O Rp(DD`n,G,f(n))))"; |
2666 by (safe_tac (!claset)); |
2666 by (safe_tac (claset())); |
2667 by (stac comp_lubs 3); |
2667 by (stac comp_lubs 3); |
2668 (* The following one line is 15 lines in HOL, and includes existentials. *) |
2668 (* The following one line is 15 lines in HOL, and includes existentials. *) |
2669 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1; |
2669 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1; |
2670 by (simp_tac (!simpset addsimps[comp_assoc]) 1); |
2670 by (simp_tac (simpset() addsimps[comp_assoc]) 1); |
2671 by (simp_tac (!simpset addsimps[(tl prems) MRS lemma]) 1); |
2671 by (simp_tac (simpset() addsimps[(tl prems) MRS lemma]) 1); |
2672 by (stac comp_lubs 2); |
2672 by (stac comp_lubs 2); |
2673 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1; |
2673 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1; |
2674 by (simp_tac (!simpset addsimps[comp_assoc]) 1); |
2674 by (simp_tac (simpset() addsimps[comp_assoc]) 1); |
2675 by (simp_tac (!simpset addsimps[ |
2675 by (simp_tac (simpset() addsimps[ |
2676 [elem 3 prems,elem 2 prems,elem 4 prems,elem 6 prems, elem 5 prems] |
2676 [elem 3 prems,elem 2 prems,elem 4 prems,elem 6 prems, elem 5 prems] |
2677 MRS lemma]) 1); |
2677 MRS lemma]) 1); |
2678 by (rtac dominate_islub 1); |
2678 by (rtac dominate_islub 1); |
2679 by (rtac cpo_lub 2); |
2679 by (rtac cpo_lub 2); |
2680 brr(commute_chain::emb_f::islub_const::cont_cf::id_cont::cpo_cf:: |
2680 brr(commute_chain::emb_f::islub_const::cont_cf::id_cont::cpo_cf:: |
2719 by (stac beta 3); |
2719 by (stac beta 3); |
2720 by (stac beta 4); |
2720 by (stac beta 4); |
2721 by (stac beta 5); |
2721 by (stac beta 5); |
2722 by (rtac lam_type 1); |
2722 by (rtac lam_type 1); |
2723 by (stac beta 1); |
2723 by (stac beta 1); |
2724 by (ALLGOALS(asm_simp_tac (!simpset addsimps prems))); |
2724 by (ALLGOALS(asm_simp_tac (simpset() addsimps prems))); |
2725 brr(lam_type::comp_pres_cont::Rp_cont::emb_cont::emb_r::emb_f:: |
2725 brr(lam_type::comp_pres_cont::Rp_cont::emb_cont::emb_r::emb_f:: |
2726 emb_chain_cpo::prems) 1; |
2726 emb_chain_cpo::prems) 1; |
2727 val lemma = result(); |
2727 val lemma = result(); |
2728 |
2728 |
2729 val prems = goal Limit.thy (* chain_lemma *) |
2729 val prems = goal Limit.thy (* chain_lemma *) |
2740 |
2740 |
2741 val prems = goalw Limit.thy [suffix_def] (* suffix_lemma *) |
2741 val prems = goalw Limit.thy [suffix_def] (* suffix_lemma *) |
2742 "[| commute(DD,ee,E,r); commute(DD,ee,G,f); \ |
2742 "[| commute(DD,ee,E,r); commute(DD,ee,G,f); \ |
2743 \ emb_chain(DD,ee); cpo(E); cpo(G); cpo(DD`x); x:nat |] ==> \ |
2743 \ emb_chain(DD,ee); cpo(E); cpo(G); cpo(DD`x); x:nat |] ==> \ |
2744 \ suffix(lam n:nat. (f(n) O Rp(DD`n,E,r(n))) O r(x),x) = (lam n:nat. f(x))"; |
2744 \ suffix(lam n:nat. (f(n) O Rp(DD`n,E,r(n))) O r(x),x) = (lam n:nat. f(x))"; |
2745 by (simp_tac (!simpset addsimps prems) 1); |
2745 by (simp_tac (simpset() addsimps prems) 1); |
2746 by (rtac fun_extension 1); |
2746 by (rtac fun_extension 1); |
2747 brr(lam_type::comp_fun::cont_fun::Rp_cont::emb_cont::emb_r::emb_f:: |
2747 brr(lam_type::comp_fun::cont_fun::Rp_cont::emb_cont::emb_r::emb_f:: |
2748 add_type::emb_chain_cpo::prems) 1; |
2748 add_type::emb_chain_cpo::prems) 1; |
2749 by (Asm_simp_tac 1); |
2749 by (Asm_simp_tac 1); |
2750 by (res_inst_tac[("r1","r"),("m1","x")](commute_eq RS subst) 1); |
2750 by (res_inst_tac[("r1","r"),("m1","x")](commute_eq RS subst) 1); |
2757 brr(emb_r::add_type::eps_fun::add_le_self::refl::emb_chain_cpo::prems) 1; |
2757 brr(emb_r::add_type::eps_fun::add_le_self::refl::emb_chain_cpo::prems) 1; |
2758 qed "suffix_lemma"; |
2758 qed "suffix_lemma"; |
2759 |
2759 |
2760 val mediatingI = prove_goalw Limit.thy [mediating_def] |
2760 val mediatingI = prove_goalw Limit.thy [mediating_def] |
2761 "[|emb(E,G,t); !!n. n:nat ==> f(n) = t O r(n) |]==>mediating(E,G,r,f,t)" |
2761 "[|emb(E,G,t); !!n. n:nat ==> f(n) = t O r(n) |]==>mediating(E,G,r,f,t)" |
2762 (fn prems => [safe_tac (!claset),trr prems 1]); |
2762 (fn prems => [safe_tac (claset()),trr prems 1]); |
2763 |
2763 |
2764 val mediating_emb = prove_goalw Limit.thy [mediating_def] |
2764 val mediating_emb = prove_goalw Limit.thy [mediating_def] |
2765 "!!z. mediating(E,G,r,f,t) ==> emb(E,G,t)" |
2765 "!!z. mediating(E,G,r,f,t) ==> emb(E,G,t)" |
2766 (fn prems => [Fast_tac 1]); |
2766 (fn prems => [Fast_tac 1]); |
2767 |
2767 |
2795 \ t = lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n)))"; |
2795 \ t = lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n)))"; |
2796 by (res_inst_tac[("b","t")](comp_id RS subst) 1); |
2796 by (res_inst_tac[("b","t")](comp_id RS subst) 1); |
2797 by (rtac (hd(tl prems) RS subst) 2); |
2797 by (rtac (hd(tl prems) RS subst) 2); |
2798 by (res_inst_tac[("b","t")](lub_const RS subst) 2); |
2798 by (res_inst_tac[("b","t")](lub_const RS subst) 2); |
2799 by (stac comp_lubs 4); |
2799 by (stac comp_lubs 4); |
2800 by (simp_tac (!simpset addsimps(comp_assoc::(hd prems RS mediating_eq)::prems)) 9); |
2800 by (simp_tac (simpset() addsimps(comp_assoc::(hd prems RS mediating_eq)::prems)) 9); |
2801 brr(cont_fun::emb_cont::mediating_emb::cont_cf::cpo_cf::chain_const:: |
2801 brr(cont_fun::emb_cont::mediating_emb::cont_cf::cpo_cf::chain_const:: |
2802 commute_chain::emb_chain_cpo::prems) 1; |
2802 commute_chain::emb_chain_cpo::prems) 1; |
2803 qed "lub_universal_unique"; |
2803 qed "lub_universal_unique"; |
2804 |
2804 |
2805 (*---------------------------------------------------------------------*) |
2805 (*---------------------------------------------------------------------*) |
2814 \ lub(cf(Dinf(DD,ee),G), \ |
2814 \ lub(cf(Dinf(DD,ee),G), \ |
2815 \ lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n)))) & \ |
2815 \ lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n)))) & \ |
2816 \ (ALL t. mediating(Dinf(DD,ee),G,rho_emb(DD,ee),f,t) --> \ |
2816 \ (ALL t. mediating(Dinf(DD,ee),G,rho_emb(DD,ee),f,t) --> \ |
2817 \ t = lub(cf(Dinf(DD,ee),G), \ |
2817 \ t = lub(cf(Dinf(DD,ee),G), \ |
2818 \ lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n))))"; |
2818 \ lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n))))"; |
2819 by (safe_tac (!claset)); |
2819 by (safe_tac (claset())); |
2820 brr(lub_universal_mediating::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1; |
2820 brr(lub_universal_mediating::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1; |
2821 brr(lub_universal_unique::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1; |
2821 brr(lub_universal_unique::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1; |
2822 qed "Dinf_universal"; |
2822 qed "Dinf_universal"; |
2823 |
2823 |