src/HOLCF/Fix.ML
changeset 3842 b55686a7b22c
parent 3661 1ea4a45b9412
child 4098 71e05eb27fb6
equal deleted inserted replaced
3841:22bbc1676768 3842:b55686a7b22c
    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