118 |
118 |
119 (* ------------------------------------------------------------------------ *) |
119 (* ------------------------------------------------------------------------ *) |
120 (* first a lemma about binary chains *) |
120 (* first a lemma about binary chains *) |
121 (* ------------------------------------------------------------------------ *) |
121 (* ------------------------------------------------------------------------ *) |
122 |
122 |
123 qed_goal "binchain_contX" Cont.thy |
123 qed_goal "binchain_cont" Cont.thy |
124 "[| contX(f); x << y |] ==> range(%i. f(if(i = 0,x,y))) <<| f(y)" |
124 "[| cont(f); x << y |] ==> range(%i. f(if i = 0 then x else y)) <<| f(y)" |
125 (fn prems => |
125 (fn prems => |
126 [ |
126 [ |
127 (cut_facts_tac prems 1), |
127 (cut_facts_tac prems 1), |
128 (rtac subst 1), |
128 (rtac subst 1), |
129 (etac (contXE RS spec RS mp) 2), |
129 (etac (contE RS spec RS mp) 2), |
130 (etac bin_chain 2), |
130 (etac bin_chain 2), |
131 (res_inst_tac [("y","y")] arg_cong 1), |
131 (res_inst_tac [("y","y")] arg_cong 1), |
132 (etac (lub_bin_chain RS thelubI) 1) |
132 (etac (lub_bin_chain RS thelubI) 1) |
133 ]); |
133 ]); |
134 |
134 |
135 (* ------------------------------------------------------------------------ *) |
135 (* ------------------------------------------------------------------------ *) |
136 (* right to left: contX(f) ==> monofun(f) & contlub(f) *) |
136 (* right to left: cont(f) ==> monofun(f) & contlub(f) *) |
137 (* part1: contX(f) ==> monofun(f *) |
137 (* part1: cont(f) ==> monofun(f *) |
138 (* ------------------------------------------------------------------------ *) |
138 (* ------------------------------------------------------------------------ *) |
139 |
139 |
140 qed_goalw "contX2mono" Cont.thy [monofun] |
140 qed_goalw "cont2mono" Cont.thy [monofun] |
141 "contX(f) ==> monofun(f)" |
141 "cont(f) ==> monofun(f)" |
142 (fn prems => |
142 (fn prems => |
143 [ |
143 [ |
144 (cut_facts_tac prems 1), |
144 (cut_facts_tac prems 1), |
145 (strip_tac 1), |
145 (strip_tac 1), |
146 (res_inst_tac [("s","if(0 = 0,x,y)")] subst 1), |
146 (res_inst_tac [("s","if 0 = 0 then x else y")] subst 1), |
147 (rtac (binchain_contX RS is_ub_lub) 2), |
147 (rtac (binchain_cont RS is_ub_lub) 2), |
148 (atac 2), |
148 (atac 2), |
149 (atac 2), |
149 (atac 2), |
150 (simp_tac nat_ss 1) |
150 (simp_tac nat_ss 1) |
151 ]); |
151 ]); |
152 |
152 |
153 (* ------------------------------------------------------------------------ *) |
153 (* ------------------------------------------------------------------------ *) |
154 (* right to left: contX(f) ==> monofun(f) & contlub(f) *) |
154 (* right to left: cont(f) ==> monofun(f) & contlub(f) *) |
155 (* part2: contX(f) ==> contlub(f) *) |
155 (* part2: cont(f) ==> contlub(f) *) |
156 (* ------------------------------------------------------------------------ *) |
156 (* ------------------------------------------------------------------------ *) |
157 |
157 |
158 qed_goalw "contX2contlub" Cont.thy [contlub] |
158 qed_goalw "cont2contlub" Cont.thy [contlub] |
159 "contX(f) ==> contlub(f)" |
159 "cont(f) ==> contlub(f)" |
160 (fn prems => |
160 (fn prems => |
161 [ |
161 [ |
162 (cut_facts_tac prems 1), |
162 (cut_facts_tac prems 1), |
163 (strip_tac 1), |
163 (strip_tac 1), |
164 (rtac (thelubI RS sym) 1), |
164 (rtac (thelubI RS sym) 1), |
165 (etac (contXE RS spec RS mp) 1), |
165 (etac (contE RS spec RS mp) 1), |
166 (atac 1) |
166 (atac 1) |
167 ]); |
167 ]); |
168 |
168 |
169 (* ------------------------------------------------------------------------ *) |
169 (* ------------------------------------------------------------------------ *) |
170 (* The following results are about a curried function that is monotone *) |
170 (* The following results are about a curried function that is monotone *) |
171 (* in both arguments *) |
171 (* in both arguments *) |
172 (* ------------------------------------------------------------------------ *) |
172 (* ------------------------------------------------------------------------ *) |
173 |
173 |
174 qed_goal "ch2ch_MF2L" Cont.thy |
174 qed_goal "ch2ch_MF2L" Cont.thy |
175 "[|monofun(MF2); is_chain(F)|] ==> is_chain(%i. MF2(F(i),x))" |
175 "[|monofun(MF2); is_chain(F)|] ==> is_chain(%i. MF2 (F i) x)" |
176 (fn prems => |
176 (fn prems => |
177 [ |
177 [ |
178 (cut_facts_tac prems 1), |
178 (cut_facts_tac prems 1), |
179 (etac (ch2ch_monofun RS ch2ch_fun) 1), |
179 (etac (ch2ch_monofun RS ch2ch_fun) 1), |
180 (atac 1) |
180 (atac 1) |
181 ]); |
181 ]); |
182 |
182 |
183 |
183 |
184 qed_goal "ch2ch_MF2R" Cont.thy |
184 qed_goal "ch2ch_MF2R" Cont.thy |
185 "[|monofun(MF2(f)); is_chain(Y)|] ==> is_chain(%i. MF2(f,Y(i)))" |
185 "[|monofun(MF2(f)); is_chain(Y)|] ==> is_chain(%i. MF2 f (Y i))" |
186 (fn prems => |
186 (fn prems => |
187 [ |
187 [ |
188 (cut_facts_tac prems 1), |
188 (cut_facts_tac prems 1), |
189 (etac ch2ch_monofun 1), |
189 (etac ch2ch_monofun 1), |
190 (atac 1) |
190 (atac 1) |
268 |
268 |
269 qed_goal "ex_lubMF2" Cont.thy |
269 qed_goal "ex_lubMF2" Cont.thy |
270 "[|monofun(MF2::('a::po=>'b::po=>'c::pcpo));\ |
270 "[|monofun(MF2::('a::po=>'b::po=>'c::pcpo));\ |
271 \ !f.monofun(MF2(f)::('b::po=>'c::pcpo));\ |
271 \ !f.monofun(MF2(f)::('b::po=>'c::pcpo));\ |
272 \ is_chain(F); is_chain(Y)|] ==> \ |
272 \ is_chain(F); is_chain(Y)|] ==> \ |
273 \ lub(range(%j. lub(range(%i. MF2(F(j),Y(i)))))) =\ |
273 \ lub(range(%j. lub(range(%i. MF2(F j) (Y i))))) =\ |
274 \ lub(range(%i. lub(range(%j. MF2(F(j),Y(i))))))" |
274 \ lub(range(%i. lub(range(%j. MF2(F j) (Y i)))))" |
275 (fn prems => |
275 (fn prems => |
276 [ |
276 [ |
277 (cut_facts_tac prems 1), |
277 (cut_facts_tac prems 1), |
278 (rtac antisym_less 1), |
278 (rtac antisym_less 1), |
279 (rtac (ub_rangeI RSN (2,is_lub_thelub)) 1), |
279 (rtac (ub_rangeI RSN (2,is_lub_thelub)) 1), |
372 (* The following results are about a curried function that is continuous *) |
372 (* The following results are about a curried function that is continuous *) |
373 (* in both arguments *) |
373 (* in both arguments *) |
374 (* ------------------------------------------------------------------------ *) |
374 (* ------------------------------------------------------------------------ *) |
375 |
375 |
376 qed_goal "contlub_CF2" Cont.thy |
376 qed_goal "contlub_CF2" Cont.thy |
377 "[|contX(CF2);!f.contX(CF2(f));is_chain(FY);is_chain(TY)|] ==>\ |
377 "[|cont(CF2);!f.cont(CF2(f));is_chain(FY);is_chain(TY)|] ==>\ |
378 \ CF2(lub(range(FY)))(lub(range(TY))) = lub(range(%i.CF2(FY(i))(TY(i))))" |
378 \ CF2(lub(range(FY)))(lub(range(TY))) = lub(range(%i.CF2(FY(i))(TY(i))))" |
379 (fn prems => |
379 (fn prems => |
380 [ |
380 [ |
381 (cut_facts_tac prems 1), |
381 (cut_facts_tac prems 1), |
382 (rtac ((hd prems) RS contX2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
382 (rtac ((hd prems) RS cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
383 (atac 1), |
383 (atac 1), |
384 (rtac (thelub_fun RS ssubst) 1), |
384 (rtac (thelub_fun RS ssubst) 1), |
385 (rtac ((hd prems) RS contX2mono RS ch2ch_monofun) 1), |
385 (rtac ((hd prems) RS cont2mono RS ch2ch_monofun) 1), |
386 (atac 1), |
386 (atac 1), |
387 (rtac trans 1), |
387 (rtac trans 1), |
388 (rtac (((hd (tl prems)) RS spec RS contX2contlub) RS contlubE RS spec RS mp RS ext RS arg_cong RS arg_cong) 1), |
388 (rtac (((hd (tl prems)) RS spec RS cont2contlub) RS contlubE RS spec RS mp RS ext RS arg_cong RS arg_cong) 1), |
389 (atac 1), |
389 (atac 1), |
390 (rtac diag_lubMF2_2 1), |
390 (rtac diag_lubMF2_2 1), |
391 (etac contX2mono 1), |
391 (etac cont2mono 1), |
392 (rtac allI 1), |
392 (rtac allI 1), |
393 (etac allE 1), |
393 (etac allE 1), |
394 (etac contX2mono 1), |
394 (etac cont2mono 1), |
395 (REPEAT (atac 1)) |
395 (REPEAT (atac 1)) |
396 ]); |
396 ]); |
397 |
397 |
398 (* ------------------------------------------------------------------------ *) |
398 (* ------------------------------------------------------------------------ *) |
399 (* The following results are about application for functions in 'a=>'b *) |
399 (* The following results are about application for functions in 'a=>'b *) |
432 (* The following results are about the propagation of monotonicity and *) |
432 (* The following results are about the propagation of monotonicity and *) |
433 (* continuity *) |
433 (* continuity *) |
434 (* ------------------------------------------------------------------------ *) |
434 (* ------------------------------------------------------------------------ *) |
435 |
435 |
436 qed_goal "mono2mono_MF1L" Cont.thy |
436 qed_goal "mono2mono_MF1L" Cont.thy |
437 "[|monofun(c1)|] ==> monofun(%x. c1(x,y))" |
437 "[|monofun(c1)|] ==> monofun(%x. c1 x y)" |
438 (fn prems => |
438 (fn prems => |
439 [ |
439 [ |
440 (cut_facts_tac prems 1), |
440 (cut_facts_tac prems 1), |
441 (rtac monofunI 1), |
441 (rtac monofunI 1), |
442 (strip_tac 1), |
442 (strip_tac 1), |
443 (etac (monofun_fun_arg RS monofun_fun_fun) 1), |
443 (etac (monofun_fun_arg RS monofun_fun_fun) 1), |
444 (atac 1) |
444 (atac 1) |
445 ]); |
445 ]); |
446 |
446 |
447 qed_goal "contX2contX_CF1L" Cont.thy |
447 qed_goal "cont2cont_CF1L" Cont.thy |
448 "[|contX(c1)|] ==> contX(%x. c1(x,y))" |
448 "[|cont(c1)|] ==> cont(%x. c1 x y)" |
449 (fn prems => |
449 (fn prems => |
450 [ |
450 [ |
451 (cut_facts_tac prems 1), |
451 (cut_facts_tac prems 1), |
452 (rtac monocontlub2contX 1), |
452 (rtac monocontlub2cont 1), |
453 (etac (contX2mono RS mono2mono_MF1L) 1), |
453 (etac (cont2mono RS mono2mono_MF1L) 1), |
454 (rtac contlubI 1), |
454 (rtac contlubI 1), |
455 (strip_tac 1), |
455 (strip_tac 1), |
456 (rtac ((hd prems) RS contX2contlub RS |
456 (rtac ((hd prems) RS cont2contlub RS |
457 contlubE RS spec RS mp RS ssubst) 1), |
457 contlubE RS spec RS mp RS ssubst) 1), |
458 (atac 1), |
458 (atac 1), |
459 (rtac (thelub_fun RS ssubst) 1), |
459 (rtac (thelub_fun RS ssubst) 1), |
460 (rtac ch2ch_monofun 1), |
460 (rtac ch2ch_monofun 1), |
461 (etac contX2mono 1), |
461 (etac cont2mono 1), |
462 (atac 1), |
462 (atac 1), |
463 (rtac refl 1) |
463 (rtac refl 1) |
464 ]); |
464 ]); |
465 |
465 |
466 (********* Note "(%x.%y.c1(x,y)) = c1" ***********) |
466 (********* Note "(%x.%y.c1 x y) = c1" ***********) |
467 |
467 |
468 qed_goal "mono2mono_MF1L_rev" Cont.thy |
468 qed_goal "mono2mono_MF1L_rev" Cont.thy |
469 "!y.monofun(%x.c1(x,y)) ==> monofun(c1)" |
469 "!y.monofun(%x.c1 x y) ==> monofun(c1)" |
470 (fn prems => |
470 (fn prems => |
471 [ |
471 [ |
472 (cut_facts_tac prems 1), |
472 (cut_facts_tac prems 1), |
473 (rtac monofunI 1), |
473 (rtac monofunI 1), |
474 (strip_tac 1), |
474 (strip_tac 1), |
476 (strip_tac 1), |
476 (strip_tac 1), |
477 (rtac ((hd prems) RS spec RS monofunE RS spec RS spec RS mp) 1), |
477 (rtac ((hd prems) RS spec RS monofunE RS spec RS spec RS mp) 1), |
478 (atac 1) |
478 (atac 1) |
479 ]); |
479 ]); |
480 |
480 |
481 qed_goal "contX2contX_CF1L_rev" Cont.thy |
481 qed_goal "cont2cont_CF1L_rev" Cont.thy |
482 "!y.contX(%x.c1(x,y)) ==> contX(c1)" |
482 "!y.cont(%x.c1 x y) ==> cont(c1)" |
483 (fn prems => |
483 (fn prems => |
484 [ |
484 [ |
485 (cut_facts_tac prems 1), |
485 (cut_facts_tac prems 1), |
486 (rtac monocontlub2contX 1), |
486 (rtac monocontlub2cont 1), |
487 (rtac (contX2mono RS allI RS mono2mono_MF1L_rev ) 1), |
487 (rtac (cont2mono RS allI RS mono2mono_MF1L_rev ) 1), |
488 (etac spec 1), |
488 (etac spec 1), |
489 (rtac contlubI 1), |
489 (rtac contlubI 1), |
490 (strip_tac 1), |
490 (strip_tac 1), |
491 (rtac ext 1), |
491 (rtac ext 1), |
492 (rtac (thelub_fun RS ssubst) 1), |
492 (rtac (thelub_fun RS ssubst) 1), |
493 (rtac (contX2mono RS allI RS mono2mono_MF1L_rev RS ch2ch_monofun) 1), |
493 (rtac (cont2mono RS allI RS mono2mono_MF1L_rev RS ch2ch_monofun) 1), |
494 (etac spec 1), |
494 (etac spec 1), |
495 (atac 1), |
495 (atac 1), |
496 (rtac |
496 (rtac |
497 ((hd prems) RS spec RS contX2contlub RS contlubE RS spec RS mp) 1), |
497 ((hd prems) RS spec RS cont2contlub RS contlubE RS spec RS mp) 1), |
498 (atac 1) |
498 (atac 1) |
499 ]); |
499 ]); |
500 |
500 |
501 |
501 |
502 (* ------------------------------------------------------------------------ *) |
502 (* ------------------------------------------------------------------------ *) |
503 (* What D.A.Schmidt calls continuity of abstraction *) |
503 (* What D.A.Schmidt calls continuity of abstraction *) |
504 (* never used here *) |
504 (* never used here *) |
505 (* ------------------------------------------------------------------------ *) |
505 (* ------------------------------------------------------------------------ *) |
506 |
506 |
507 qed_goal "contlub_abstraction" Cont.thy |
507 qed_goal "contlub_abstraction" Cont.thy |
508 "[|is_chain(Y::nat=>'a);!y.contX(%x.(c::'a=>'b=>'c)(x,y))|] ==>\ |
508 "[|is_chain(Y::nat=>'a);!y.cont(%x.(c::'a=>'b=>'c) x y)|] ==>\ |
509 \ (%y.lub(range(%i.c(Y(i),y)))) = (lub(range(%i.%y.c(Y(i),y))))" |
509 \ (%y.lub(range(%i.c (Y i) y))) = (lub(range(%i.%y.c (Y i) y)))" |
510 (fn prems => |
510 (fn prems => |
511 [ |
511 [ |
512 (cut_facts_tac prems 1), |
512 (cut_facts_tac prems 1), |
513 (rtac trans 1), |
513 (rtac trans 1), |
514 (rtac (contX2contlub RS contlubE RS spec RS mp) 2), |
514 (rtac (cont2contlub RS contlubE RS spec RS mp) 2), |
515 (atac 3), |
515 (atac 3), |
516 (etac contX2contX_CF1L_rev 2), |
516 (etac cont2cont_CF1L_rev 2), |
517 (rtac ext 1), |
517 (rtac ext 1), |
518 (rtac (contX2contlub RS contlubE RS spec RS mp RS sym) 1), |
518 (rtac (cont2contlub RS contlubE RS spec RS mp RS sym) 1), |
519 (etac spec 1), |
519 (etac spec 1), |
520 (atac 1) |
520 (atac 1) |
521 ]); |
521 ]); |
522 |
522 |
523 |
523 |
537 (etac (monofunE RS spec RS spec RS mp) 1), |
537 (etac (monofunE RS spec RS spec RS mp) 1), |
538 (atac 1) |
538 (atac 1) |
539 ]); |
539 ]); |
540 |
540 |
541 |
541 |
542 qed_goal "contX2contlub_app" Cont.thy |
542 qed_goal "cont2contlub_app" Cont.thy |
543 "[|contX(ft);!x.contX(ft(x));contX(tt)|] ==> contlub(%x.(ft(x))(tt(x)))" |
543 "[|cont(ft);!x.cont(ft(x));cont(tt)|] ==> contlub(%x.(ft(x))(tt(x)))" |
544 (fn prems => |
544 (fn prems => |
545 [ |
545 [ |
546 (cut_facts_tac prems 1), |
546 (cut_facts_tac prems 1), |
547 (rtac contlubI 1), |
547 (rtac contlubI 1), |
548 (strip_tac 1), |
548 (strip_tac 1), |
549 (res_inst_tac [("f3","tt")] (contlubE RS spec RS mp RS ssubst) 1), |
549 (res_inst_tac [("f3","tt")] (contlubE RS spec RS mp RS ssubst) 1), |
550 (etac contX2contlub 1), |
550 (etac cont2contlub 1), |
551 (atac 1), |
551 (atac 1), |
552 (rtac contlub_CF2 1), |
552 (rtac contlub_CF2 1), |
553 (REPEAT (atac 1)), |
553 (REPEAT (atac 1)), |
554 (etac (contX2mono RS ch2ch_monofun) 1), |
554 (etac (cont2mono RS ch2ch_monofun) 1), |
555 (atac 1) |
555 (atac 1) |
556 ]); |
556 ]); |
557 |
557 |
558 |
558 |
559 qed_goal "contX2contX_app" Cont.thy |
559 qed_goal "cont2cont_app" Cont.thy |
560 "[|contX(ft);!x.contX(ft(x));contX(tt)|] ==>\ |
560 "[|cont(ft);!x.cont(ft(x));cont(tt)|] ==>\ |
561 \ contX(%x.(ft(x))(tt(x)))" |
561 \ cont(%x.(ft(x))(tt(x)))" |
562 (fn prems => |
562 (fn prems => |
563 [ |
563 [ |
564 (rtac monocontlub2contX 1), |
564 (rtac monocontlub2cont 1), |
565 (rtac mono2mono_app 1), |
565 (rtac mono2mono_app 1), |
566 (rtac contX2mono 1), |
566 (rtac cont2mono 1), |
567 (resolve_tac prems 1), |
567 (resolve_tac prems 1), |
568 (strip_tac 1), |
568 (strip_tac 1), |
569 (rtac contX2mono 1), |
569 (rtac cont2mono 1), |
570 (cut_facts_tac prems 1), |
570 (cut_facts_tac prems 1), |
571 (etac spec 1), |
571 (etac spec 1), |
572 (rtac contX2mono 1), |
572 (rtac cont2mono 1), |
573 (resolve_tac prems 1), |
573 (resolve_tac prems 1), |
574 (rtac contX2contlub_app 1), |
574 (rtac cont2contlub_app 1), |
575 (resolve_tac prems 1), |
575 (resolve_tac prems 1), |
576 (resolve_tac prems 1), |
576 (resolve_tac prems 1), |
577 (resolve_tac prems 1) |
577 (resolve_tac prems 1) |
578 ]); |
578 ]); |
579 |
579 |
580 |
580 |
581 val contX2contX_app2 = (allI RSN (2,contX2contX_app)); |
581 val cont2cont_app2 = (allI RSN (2,cont2cont_app)); |
582 (* [| contX(?ft); !!x. contX(?ft(x)); contX(?tt) |] ==> *) |
582 (* [| cont ?ft; !!x. cont (?ft x); cont ?tt |] ==> *) |
583 (* contX(%x. ?ft(x,?tt(x))) *) |
583 (* cont (%x. ?ft x (?tt x)) *) |
584 |
584 |
585 |
585 |
586 (* ------------------------------------------------------------------------ *) |
586 (* ------------------------------------------------------------------------ *) |
587 (* The identity function is continuous *) |
587 (* The identity function is continuous *) |
588 (* ------------------------------------------------------------------------ *) |
588 (* ------------------------------------------------------------------------ *) |
589 |
589 |
590 qed_goal "contX_id" Cont.thy "contX(% x.x)" |
590 qed_goal "cont_id" Cont.thy "cont(% x.x)" |
591 (fn prems => |
591 (fn prems => |
592 [ |
592 [ |
593 (rtac contXI 1), |
593 (rtac contI 1), |
594 (strip_tac 1), |
594 (strip_tac 1), |
595 (etac thelubE 1), |
595 (etac thelubE 1), |
596 (rtac refl 1) |
596 (rtac refl 1) |
597 ]); |
597 ]); |
598 |
598 |