equal
deleted
inserted
replaced
41 (* the sequence of function itertaions is a chain *) |
41 (* the sequence of function itertaions is a chain *) |
42 (* This property is essential since monotonicity of iterate makes no sense *) |
42 (* This property is essential since monotonicity of iterate makes no sense *) |
43 (* ------------------------------------------------------------------------ *) |
43 (* ------------------------------------------------------------------------ *) |
44 |
44 |
45 qed_goalw "is_chain_iterate2" thy [is_chain] |
45 qed_goalw "is_chain_iterate2" thy [is_chain] |
46 " x << F`x ==> is_chain (%i.iterate i F x)" |
46 " x << F`x ==> is_chain (%i. iterate i F x)" |
47 (fn prems => |
47 (fn prems => |
48 [ |
48 [ |
49 (cut_facts_tac prems 1), |
49 (cut_facts_tac prems 1), |
50 (strip_tac 1), |
50 (strip_tac 1), |
51 (Simp_tac 1), |
51 (Simp_tac 1), |
55 (etac monofun_cfun_arg 1) |
55 (etac monofun_cfun_arg 1) |
56 ]); |
56 ]); |
57 |
57 |
58 |
58 |
59 qed_goal "is_chain_iterate" thy |
59 qed_goal "is_chain_iterate" thy |
60 "is_chain (%i.iterate i F UU)" |
60 "is_chain (%i. iterate i F UU)" |
61 (fn prems => |
61 (fn prems => |
62 [ |
62 [ |
63 (rtac is_chain_iterate2 1), |
63 (rtac is_chain_iterate2 1), |
64 (rtac minimal 1) |
64 (rtac minimal 1) |
65 ]); |
65 ]); |
450 (* ------------------------------------------------------------------------ *) |
450 (* ------------------------------------------------------------------------ *) |
451 (* access to definitions *) |
451 (* access to definitions *) |
452 (* ------------------------------------------------------------------------ *) |
452 (* ------------------------------------------------------------------------ *) |
453 |
453 |
454 qed_goalw "admI" thy [adm_def] |
454 qed_goalw "admI" thy [adm_def] |
455 "(!!Y. [| is_chain(Y); !i.P(Y(i)) |] ==> P(lub(range(Y)))) ==> adm(P)" |
455 "(!!Y. [| is_chain(Y); !i. P(Y(i)) |] ==> P(lub(range(Y)))) ==> adm(P)" |
456 (fn prems => [fast_tac (HOL_cs addIs prems) 1]); |
456 (fn prems => [fast_tac (HOL_cs addIs prems) 1]); |
457 |
457 |
458 qed_goalw "admD" thy [adm_def] |
458 qed_goalw "admD" thy [adm_def] |
459 "!!P. [| adm(P); is_chain(Y); !i.P(Y(i)) |] ==> P(lub(range(Y)))" |
459 "!!P. [| adm(P); is_chain(Y); !i. P(Y(i)) |] ==> P(lub(range(Y)))" |
460 (fn prems => [fast_tac HOL_cs 1]); |
460 (fn prems => [fast_tac HOL_cs 1]); |
461 |
461 |
462 qed_goalw "admw_def2" thy [admw_def] |
462 qed_goalw "admw_def2" thy [admw_def] |
463 "admw(P) = (!F.(!n.P(iterate n F UU)) -->\ |
463 "admw(P) = (!F.(!n. P(iterate n F UU)) -->\ |
464 \ P (lub(range(%i.iterate i F UU))))" |
464 \ P (lub(range(%i. iterate i F UU))))" |
465 (fn prems => |
465 (fn prems => |
466 [ |
466 [ |
467 (rtac refl 1) |
467 (rtac refl 1) |
468 ]); |
468 ]); |
469 |
469 |
535 (* ------------------------------------------------------------------------ *) |
535 (* ------------------------------------------------------------------------ *) |
536 (* for chain-finite (easy) types every formula is admissible *) |
536 (* for chain-finite (easy) types every formula is admissible *) |
537 (* ------------------------------------------------------------------------ *) |
537 (* ------------------------------------------------------------------------ *) |
538 |
538 |
539 qed_goalw "adm_max_in_chain" thy [adm_def] |
539 qed_goalw "adm_max_in_chain" thy [adm_def] |
540 "!Y. is_chain(Y::nat=>'a) --> (? n.max_in_chain n Y) ==> adm(P::'a=>bool)" |
540 "!Y. is_chain(Y::nat=>'a) --> (? n. max_in_chain n Y) ==> adm(P::'a=>bool)" |
541 (fn prems => |
541 (fn prems => |
542 [ |
542 [ |
543 (cut_facts_tac prems 1), |
543 (cut_facts_tac prems 1), |
544 (strip_tac 1), |
544 (strip_tac 1), |
545 (rtac exE 1), |
545 (rtac exE 1), |
583 (* ------------------------------------------------------------------------ *) |
583 (* ------------------------------------------------------------------------ *) |
584 (* admissibility of special formulae and propagation *) |
584 (* admissibility of special formulae and propagation *) |
585 (* ------------------------------------------------------------------------ *) |
585 (* ------------------------------------------------------------------------ *) |
586 |
586 |
587 qed_goalw "adm_less" thy [adm_def] |
587 qed_goalw "adm_less" thy [adm_def] |
588 "[|cont u;cont v|]==> adm(%x.u x << v x)" |
588 "[|cont u;cont v|]==> adm(%x. u x << v x)" |
589 (fn prems => |
589 (fn prems => |
590 [ |
590 [ |
591 (cut_facts_tac prems 1), |
591 (cut_facts_tac prems 1), |
592 (strip_tac 1), |
592 (strip_tac 1), |
593 (etac (cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
593 (etac (cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
608 qed_goal "adm_conj" thy |
608 qed_goal "adm_conj" thy |
609 "!!P. [| adm P; adm Q |] ==> adm(%x. P x & Q x)" |
609 "!!P. [| adm P; adm Q |] ==> adm(%x. P x & Q x)" |
610 (fn prems => [fast_tac (HOL_cs addEs [admD] addIs [admI]) 1]); |
610 (fn prems => [fast_tac (HOL_cs addEs [admD] addIs [admI]) 1]); |
611 Addsimps [adm_conj]; |
611 Addsimps [adm_conj]; |
612 |
612 |
613 qed_goalw "adm_not_free" thy [adm_def] "adm(%x.t)" |
613 qed_goalw "adm_not_free" thy [adm_def] "adm(%x. t)" |
614 (fn prems => [fast_tac HOL_cs 1]); |
614 (fn prems => [fast_tac HOL_cs 1]); |
615 Addsimps [adm_not_free]; |
615 Addsimps [adm_not_free]; |
616 |
616 |
617 qed_goalw "adm_not_less" thy [adm_def] |
617 qed_goalw "adm_not_less" thy [adm_def] |
618 "!!t. cont t ==> adm(%x.~ (t x) << u)" |
618 "!!t. cont t ==> adm(%x.~ (t x) << u)" |
627 (rtac is_ub_thelub 1), |
627 (rtac is_ub_thelub 1), |
628 (atac 1) |
628 (atac 1) |
629 ]); |
629 ]); |
630 |
630 |
631 qed_goal "adm_all" thy |
631 qed_goal "adm_all" thy |
632 "!!P. !y.adm(P y) ==> adm(%x.!y.P y x)" |
632 "!!P. !y. adm(P y) ==> adm(%x.!y. P y x)" |
633 (fn prems => [fast_tac (HOL_cs addIs [admI] addEs [admD]) 1]); |
633 (fn prems => [fast_tac (HOL_cs addIs [admI] addEs [admD]) 1]); |
634 |
634 |
635 bind_thm ("adm_all2", allI RS adm_all); |
635 bind_thm ("adm_all2", allI RS adm_all); |
636 |
636 |
637 qed_goal "adm_subst" thy |
637 qed_goal "adm_subst" thy |
679 (* ------------------------------------------------------------------------ *) |
679 (* ------------------------------------------------------------------------ *) |
680 |
680 |
681 local |
681 local |
682 |
682 |
683 val adm_disj_lemma1 = prove_goal HOL.thy |
683 val adm_disj_lemma1 = prove_goal HOL.thy |
684 "!n.P(Y n)|Q(Y n) ==> (? i.!j.R i j --> Q(Y(j))) | (!i.? j.R i j & P(Y(j)))" |
684 "!n. P(Y n)|Q(Y n) ==> (? i.!j. R i j --> Q(Y(j))) | (!i.? j. R i j & P(Y(j)))" |
685 (fn prems => |
685 (fn prems => |
686 [ |
686 [ |
687 (cut_facts_tac prems 1), |
687 (cut_facts_tac prems 1), |
688 (fast_tac HOL_cs 1) |
688 (fast_tac HOL_cs 1) |
689 ]); |
689 ]); |
690 |
690 |
691 val adm_disj_lemma2 = prove_goal thy |
691 val adm_disj_lemma2 = prove_goal thy |
692 "!!Q. [| adm(Q); ? X.is_chain(X) & (!n.Q(X(n))) &\ |
692 "!!Q. [| adm(Q); ? X. is_chain(X) & (!n. Q(X(n))) &\ |
693 \ lub(range(Y))=lub(range(X))|] ==> Q(lub(range(Y)))" |
693 \ lub(range(Y))=lub(range(X))|] ==> Q(lub(range(Y)))" |
694 (fn _ => [fast_tac (!claset addEs [admD] addss !simpset) 1]); |
694 (fn _ => [fast_tac (!claset addEs [admD] addss !simpset) 1]); |
695 |
695 |
696 val adm_disj_lemma3 = prove_goalw thy [is_chain] |
696 val adm_disj_lemma3 = prove_goalw thy [is_chain] |
697 "!!Q. is_chain(Y) ==> is_chain(%m. if m < Suc i then Y(Suc i) else Y m)" |
697 "!!Q. is_chain(Y) ==> is_chain(%m. if m < Suc i then Y(Suc i) else Y m)" |
733 \ ? X. is_chain(X) & (! n. Q(X(n))) & lub(range(Y)) = lub(range(X))" |
733 \ ? X. is_chain(X) & (! n. Q(X(n))) & lub(range(Y)) = lub(range(X))" |
734 (fn prems => |
734 (fn prems => |
735 [ |
735 [ |
736 (cut_facts_tac prems 1), |
736 (cut_facts_tac prems 1), |
737 (etac exE 1), |
737 (etac exE 1), |
738 (res_inst_tac [("x","%m.if m<Suc(i) then Y(Suc(i)) else Y m")] exI 1), |
738 (res_inst_tac [("x","%m. if m<Suc(i) then Y(Suc(i)) else Y m")] exI 1), |
739 (rtac conjI 1), |
739 (rtac conjI 1), |
740 (rtac adm_disj_lemma3 1), |
740 (rtac adm_disj_lemma3 1), |
741 (atac 1), |
741 (atac 1), |
742 (rtac conjI 1), |
742 (rtac conjI 1), |
743 (rtac adm_disj_lemma4 1), |
743 (rtac adm_disj_lemma4 1), |
852 (etac adm_disj_lemma10 1), |
852 (etac adm_disj_lemma10 1), |
853 (atac 1) |
853 (atac 1) |
854 ]); |
854 ]); |
855 |
855 |
856 val adm_disj = prove_goal thy |
856 val adm_disj = prove_goal thy |
857 "!!P. [| adm P; adm Q |] ==> adm(%x.P x | Q x)" |
857 "!!P. [| adm P; adm Q |] ==> adm(%x. P x | Q x)" |
858 (fn prems => |
858 (fn prems => |
859 [ |
859 [ |
860 (rtac admI 1), |
860 (rtac admI 1), |
861 (rtac (adm_disj_lemma1 RS disjE) 1), |
861 (rtac (adm_disj_lemma1 RS disjE) 1), |
862 (atac 1), |
862 (atac 1), |
874 |
874 |
875 bind_thm("adm_lemma11",adm_lemma11); |
875 bind_thm("adm_lemma11",adm_lemma11); |
876 bind_thm("adm_disj",adm_disj); |
876 bind_thm("adm_disj",adm_disj); |
877 |
877 |
878 qed_goal "adm_imp" thy |
878 qed_goal "adm_imp" thy |
879 "!!P. [| adm(%x.~(P x)); adm Q |] ==> adm(%x.P x --> Q x)" |
879 "!!P. [| adm(%x.~(P x)); adm Q |] ==> adm(%x. P x --> Q x)" |
880 (fn prems => |
880 (fn prems => |
881 [ |
881 [ |
882 (subgoal_tac "(%x.P x --> Q x) = (%x. ~P x | Q x)" 1), |
882 (subgoal_tac "(%x. P x --> Q x) = (%x. ~P x | Q x)" 1), |
883 (Asm_simp_tac 1), |
883 (Asm_simp_tac 1), |
884 (etac adm_disj 1), |
884 (etac adm_disj 1), |
885 (atac 1), |
885 (atac 1), |
886 (rtac ext 1), |
886 (rtac ext 1), |
887 (fast_tac HOL_cs 1) |
887 (fast_tac HOL_cs 1) |
888 ]); |
888 ]); |
889 |
889 |
890 goal Fix.thy "!! P. [| adm (%x. P x --> Q x); adm (%x.Q x --> P x) |] \ |
890 goal Fix.thy "!! P. [| adm (%x. P x --> Q x); adm (%x. Q x --> P x) |] \ |
891 \ ==> adm (%x. P x = Q x)"; |
891 \ ==> adm (%x. P x = Q x)"; |
892 by(subgoal_tac "(%x.P x = Q x) = (%x. (P x --> Q x) & (Q x --> P x))" 1); |
892 by(subgoal_tac "(%x. P x = Q x) = (%x. (P x --> Q x) & (Q x --> P x))" 1); |
893 by (Asm_simp_tac 1); |
893 by (Asm_simp_tac 1); |
894 by (rtac ext 1); |
894 by (rtac ext 1); |
895 by (fast_tac HOL_cs 1); |
895 by (fast_tac HOL_cs 1); |
896 qed"adm_iff"; |
896 qed"adm_iff"; |
897 |
897 |