src/HOLCF/Fix.ML
changeset 1267 bca91b4e1710
parent 1168 74be52691d62
child 1274 ea0668a1c0ba
equal deleted inserted replaced
1266:3ae9fe3c0f68 1267:bca91b4e1710
    22  (fn prems =>
    22  (fn prems =>
    23 	[
    23 	[
    24 	(resolve_tac (nat_recs iterate_def) 1)
    24 	(resolve_tac (nat_recs iterate_def) 1)
    25 	]);
    25 	]);
    26 
    26 
    27 val iterate_ss = Cfun_ss addsimps [iterate_0,iterate_Suc];
    27 Addsimps [iterate_0, iterate_Suc];
    28 
    28 
    29 qed_goal "iterate_Suc2" Fix.thy "iterate (Suc n) F x = iterate n F (F`x)"
    29 qed_goal "iterate_Suc2" Fix.thy "iterate (Suc n) F x = iterate n F (F`x)"
    30  (fn prems =>
    30  (fn prems =>
    31 	[
    31 	[
    32 	(nat_ind_tac "n" 1),
    32 	(nat_ind_tac "n" 1),
    33 	(simp_tac iterate_ss 1),
    33 	(Simp_tac 1),
    34 	(asm_simp_tac iterate_ss 1)
    34 	(Asm_simp_tac 1)
    35 	]);
    35 	]);
    36 
    36 
    37 (* ------------------------------------------------------------------------ *)
    37 (* ------------------------------------------------------------------------ *)
    38 (* the sequence of function itertaions is a chain                           *)
    38 (* the sequence of function itertaions is a chain                           *)
    39 (* This property is essential since monotonicity of iterate makes no sense  *)
    39 (* This property is essential since monotonicity of iterate makes no sense  *)
    43 	" x << F`x ==> is_chain (%i.iterate i F x)"
    43 	" x << F`x ==> is_chain (%i.iterate i F x)"
    44  (fn prems =>
    44  (fn prems =>
    45 	[
    45 	[
    46 	(cut_facts_tac prems 1),
    46 	(cut_facts_tac prems 1),
    47 	(strip_tac 1),
    47 	(strip_tac 1),
    48 	(simp_tac iterate_ss 1),
    48 	(Simp_tac 1),
    49 	(nat_ind_tac "i" 1),
    49 	(nat_ind_tac "i" 1),
    50 	(asm_simp_tac iterate_ss 1),
    50 	(Asm_simp_tac 1),
    51 	(asm_simp_tac iterate_ss 1),
    51 	(Asm_simp_tac 1),
    52 	(etac monofun_cfun_arg 1)
    52 	(etac monofun_cfun_arg 1)
    53 	]);
    53 	]);
    54 
    54 
    55 
    55 
    56 qed_goal "is_chain_iterate" Fix.thy  
    56 qed_goal "is_chain_iterate" Fix.thy  
    99 	(rtac is_lub_thelub 1),
    99 	(rtac is_lub_thelub 1),
   100 	(rtac is_chain_iterate 1),
   100 	(rtac is_chain_iterate 1),
   101 	(rtac ub_rangeI 1),
   101 	(rtac ub_rangeI 1),
   102 	(strip_tac 1),
   102 	(strip_tac 1),
   103 	(nat_ind_tac "i" 1),
   103 	(nat_ind_tac "i" 1),
   104 	(asm_simp_tac iterate_ss 1),
   104 	(Asm_simp_tac 1),
   105 	(asm_simp_tac iterate_ss 1),
   105 	(Asm_simp_tac 1),
   106 	(res_inst_tac [("t","x")] subst 1),
   106 	(res_inst_tac [("t","x")] subst 1),
   107 	(atac 1),
   107 	(atac 1),
   108 	(etac monofun_cfun_arg 1)
   108 	(etac monofun_cfun_arg 1)
   109 	]);
   109 	]);
   110 
   110 
   116 qed_goalw "monofun_iterate" Fix.thy  [monofun] "monofun(iterate(i))"
   116 qed_goalw "monofun_iterate" Fix.thy  [monofun] "monofun(iterate(i))"
   117  (fn prems =>
   117  (fn prems =>
   118 	[
   118 	[
   119 	(strip_tac 1),
   119 	(strip_tac 1),
   120 	(nat_ind_tac "i" 1),
   120 	(nat_ind_tac "i" 1),
   121 	(asm_simp_tac iterate_ss 1),
   121 	(Asm_simp_tac 1),
   122 	(asm_simp_tac iterate_ss 1),
   122 	(Asm_simp_tac 1),
   123 	(rtac (less_fun RS iffD2) 1),
   123 	(rtac (less_fun RS iffD2) 1),
   124 	(rtac allI 1),
   124 	(rtac allI 1),
   125 	(rtac monofun_cfun 1),
   125 	(rtac monofun_cfun 1),
   126 	(atac 1),
   126 	(atac 1),
   127 	(rtac (less_fun RS iffD1 RS spec) 1),
   127 	(rtac (less_fun RS iffD1 RS spec) 1),
   137 qed_goalw "contlub_iterate" Fix.thy  [contlub] "contlub(iterate(i))"
   137 qed_goalw "contlub_iterate" Fix.thy  [contlub] "contlub(iterate(i))"
   138  (fn prems =>
   138  (fn prems =>
   139 	[
   139 	[
   140 	(strip_tac 1),
   140 	(strip_tac 1),
   141 	(nat_ind_tac "i" 1),
   141 	(nat_ind_tac "i" 1),
   142 	(asm_simp_tac iterate_ss 1),
   142 	(Asm_simp_tac 1),
   143 	(rtac (lub_const RS thelubI RS sym) 1),
   143 	(rtac (lub_const RS thelubI RS sym) 1),
   144 	(asm_simp_tac iterate_ss 1),
   144 	(Asm_simp_tac 1),
   145 	(rtac ext 1),
   145 	(rtac ext 1),
   146 	(rtac (thelub_fun RS ssubst) 1),
   146 	(rtac (thelub_fun RS ssubst) 1),
   147 	(rtac is_chainI 1),
   147 	(rtac is_chainI 1),
   148 	(rtac allI 1),
   148 	(rtac allI 1),
   149 	(rtac (less_fun RS iffD2) 1),
   149 	(rtac (less_fun RS iffD2) 1),
   181  (fn prems =>
   181  (fn prems =>
   182 	[
   182 	[
   183 	(rtac monofunI 1),
   183 	(rtac monofunI 1),
   184 	(strip_tac 1),
   184 	(strip_tac 1),
   185 	(nat_ind_tac "n" 1),
   185 	(nat_ind_tac "n" 1),
   186 	(asm_simp_tac iterate_ss 1),
   186 	(Asm_simp_tac 1),
   187 	(asm_simp_tac iterate_ss 1),
   187 	(Asm_simp_tac 1),
   188 	(etac monofun_cfun_arg 1)
   188 	(etac monofun_cfun_arg 1)
   189 	]);
   189 	]);
   190 
   190 
   191 qed_goal "contlub_iterate2" Fix.thy "contlub(iterate n F)"
   191 qed_goal "contlub_iterate2" Fix.thy "contlub(iterate n F)"
   192  (fn prems =>
   192  (fn prems =>
   193 	[
   193 	[
   194 	(rtac contlubI 1),
   194 	(rtac contlubI 1),
   195 	(strip_tac 1),
   195 	(strip_tac 1),
   196 	(nat_ind_tac "n" 1),
   196 	(nat_ind_tac "n" 1),
   197 	(simp_tac iterate_ss 1),
   197 	(Simp_tac 1),
   198 	(simp_tac iterate_ss 1),
   198 	(Simp_tac 1),
   199 	(res_inst_tac [("t","iterate n1 F (lub(range(%u. Y u)))"),
   199 	(res_inst_tac [("t","iterate n1 F (lub(range(%u. Y u)))"),
   200 	("s","lub(range(%i. iterate n1 F (Y i)))")] ssubst 1),
   200 	("s","lub(range(%i. iterate n1 F (Y i)))")] ssubst 1),
   201 	(atac 1),
   201 	(atac 1),
   202 	(rtac contlub_cfun_arg 1),
   202 	(rtac contlub_cfun_arg 1),
   203 	(etac (monofun_iterate2 RS ch2ch_monofun) 1)
   203 	(etac (monofun_iterate2 RS ch2ch_monofun) 1)
   326 (* ------------------------------------------------------------------------ *)
   326 (* ------------------------------------------------------------------------ *)
   327 
   327 
   328 qed_goalw "fix_eq" Fix.thy  [fix_def] "fix`F = F`(fix`F)"
   328 qed_goalw "fix_eq" Fix.thy  [fix_def] "fix`F = F`(fix`F)"
   329  (fn prems =>
   329  (fn prems =>
   330 	[
   330 	[
   331 	(asm_simp_tac (Cfun_ss addsimps [cont_Ifix]) 1),
   331 	(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1),
   332 	(rtac Ifix_eq 1)
   332 	(rtac Ifix_eq 1)
   333 	]);
   333 	]);
   334 
   334 
   335 qed_goalw "fix_least" Fix.thy [fix_def] "F`x = x ==> fix`F << x"
   335 qed_goalw "fix_least" Fix.thy [fix_def] "F`x = x ==> fix`F << x"
   336  (fn prems =>
   336  (fn prems =>
   337 	[
   337 	[
   338 	(cut_facts_tac prems 1),
   338 	(cut_facts_tac prems 1),
   339 	(asm_simp_tac (Cfun_ss addsimps [cont_Ifix]) 1),
   339 	(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1),
   340 	(etac Ifix_least 1)
   340 	(etac Ifix_least 1)
   341 	]);
   341 	]);
   342 
   342 
   343 
   343 
   344 qed_goal "fix_eq2" Fix.thy "f == fix`F ==> f = F`f"
   344 qed_goal "fix_eq2" Fix.thy "f == fix`F ==> f = F`f"
   419 qed_goalw "fix_def2" Fix.thy [fix_def]
   419 qed_goalw "fix_def2" Fix.thy [fix_def]
   420  "fix`F = lub(range(%i. iterate i F UU))"
   420  "fix`F = lub(range(%i. iterate i F UU))"
   421  (fn prems =>
   421  (fn prems =>
   422 	[
   422 	[
   423 	(fold_goals_tac [Ifix_def]),
   423 	(fold_goals_tac [Ifix_def]),
   424 	(asm_simp_tac (Cfun_ss addsimps [cont_Ifix]) 1)
   424 	(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1)
   425 	]);
   425 	]);
   426 
   426 
   427 
   427 
   428 (* ------------------------------------------------------------------------ *)
   428 (* ------------------------------------------------------------------------ *)
   429 (* Lemmas about admissibility and fixed point induction                     *)
   429 (* Lemmas about admissibility and fixed point induction                     *)
   565 	(rtac refl_less 1),
   565 	(rtac refl_less 1),
   566 	(res_inst_tac [("P","Y(Suc(x)) = UU")] notE 1),
   566 	(res_inst_tac [("P","Y(Suc(x)) = UU")] notE 1),
   567 	(atac 2),
   567 	(atac 2),
   568 	(rtac mp 1),
   568 	(rtac mp 1),
   569 	(etac spec 1),
   569 	(etac spec 1),
   570 	(asm_simp_tac nat_ss 1)
   570 	(Asm_simp_tac 1)
   571 	]);
   571 	]);
   572 
   572 
   573 
   573 
   574 val adm_flat = flat_imp_chain_finite RS adm_chain_finite;
   574 val adm_flat = flat_imp_chain_finite RS adm_chain_finite;
   575 (* flat(?x::?'a) ==> adm(?P::?'a => bool) *)
   575 (* flat(?x::?'a) ==> adm(?P::?'a => bool) *)
   834 
   834 
   835 qed_goal "adm_UU_not_less"  Fix.thy "adm(%x.~ UU << t(x))"
   835 qed_goal "adm_UU_not_less"  Fix.thy "adm(%x.~ UU << t(x))"
   836  (fn prems =>
   836  (fn prems =>
   837 	[
   837 	[
   838 	(res_inst_tac [("P2","%x.False")] (adm_cong RS iffD1) 1),
   838 	(res_inst_tac [("P2","%x.False")] (adm_cong RS iffD1) 1),
   839 	(asm_simp_tac Cfun_ss 1),
   839 	(Asm_simp_tac 1),
   840 	(rtac adm_not_free 1)
   840 	(rtac adm_not_free 1)
   841 	]);
   841 	]);
   842 
   842 
   843 qed_goalw "adm_not_UU"  Fix.thy [adm_def] 
   843 qed_goalw "adm_not_UU"  Fix.thy [adm_def] 
   844 	"cont(t)==> adm(%x.~ (t x) = UU)"
   844 	"cont(t)==> adm(%x.~ (t x) = UU)"
   925 	(rtac notE 1),
   925 	(rtac notE 1),
   926 	(rtac (not_less_eq RS iffD2) 1),
   926 	(rtac (not_less_eq RS iffD2) 1),
   927 	(atac 1),
   927 	(atac 1),
   928 	(atac 1),
   928 	(atac 1),
   929 	(res_inst_tac [("s","False"),("t","Suc(ia) < Suc(i)")] ssubst 1),
   929 	(res_inst_tac [("s","False"),("t","Suc(ia) < Suc(i)")] ssubst 1),
   930 	(asm_simp_tac nat_ss  1),
   930 	(Asm_simp_tac  1),
   931 	(rtac iffI 1),
   931 	(rtac iffI 1),
   932 	(etac FalseE 2),
   932 	(etac FalseE 2),
   933 	(rtac notE 1),
   933 	(rtac notE 1),
   934 	(etac less_not_sym 1),	
   934 	(etac less_not_sym 1),	
   935 	(atac 1),
   935 	(atac 1),
   936 	(asm_simp_tac Cfun_ss  1),
   936 	(Asm_simp_tac 1),
   937 	(etac (is_chainE RS spec) 1),
   937 	(etac (is_chainE RS spec) 1),
   938 	(hyp_subst_tac 1),
   938 	(hyp_subst_tac 1),
   939 	(asm_simp_tac nat_ss 1),
   939 	(Asm_simp_tac 1),
   940 	(rtac refl_less 1),
   940 	(Asm_simp_tac 1)
   941 	(asm_simp_tac nat_ss 1),
       
   942 	(rtac refl_less 1)
       
   943 	]);
   941 	]);
   944 
   942 
   945 qed_goal "adm_disj_lemma4"  Fix.thy
   943 qed_goal "adm_disj_lemma4"  Fix.thy
   946 "[| ! j. i < j --> Q(Y(j)) |] ==>\
   944 "[| ! j. i < j --> Q(Y(j)) |] ==>\
   947 \	 ! n. Q( if n < Suc i then Y(Suc i) else Y n)"
   945 \	 ! n. Q( if n < Suc i then Y(Suc i) else Y n)"
   949 	[
   947 	[
   950 	(cut_facts_tac prems 1),
   948 	(cut_facts_tac prems 1),
   951 	(rtac allI 1),
   949 	(rtac allI 1),
   952 	(res_inst_tac [("m","n"),("n","Suc(i)")] nat_less_cases 1),
   950 	(res_inst_tac [("m","n"),("n","Suc(i)")] nat_less_cases 1),
   953 	(res_inst_tac[("s","Y(Suc(i))"),("t","if n<Suc(i) then Y(Suc(i)) else Y n")] ssubst 1),
   951 	(res_inst_tac[("s","Y(Suc(i))"),("t","if n<Suc(i) then Y(Suc(i)) else Y n")] ssubst 1),
   954 	(asm_simp_tac nat_ss 1),
   952 	(Asm_simp_tac 1),
   955 	(etac allE 1),
   953 	(etac allE 1),
   956 	(rtac mp 1),
   954 	(rtac mp 1),
   957 	(atac 1),
   955 	(atac 1),
   958 	(asm_simp_tac nat_ss 1),
   956 	(Asm_simp_tac 1),
   959 	(res_inst_tac[("s","Y(n)"),("t","if n<Suc(i) then Y(Suc(i)) else Y(n)")] ssubst 1),
   957 	(res_inst_tac[("s","Y(n)"),("t","if n<Suc(i) then Y(Suc(i)) else Y(n)")] ssubst 1),
   960 	(asm_simp_tac nat_ss 1),
   958 	(Asm_simp_tac 1),
   961 	(hyp_subst_tac 1),
   959 	(hyp_subst_tac 1),
   962 	(dtac spec 1),
   960 	(dtac spec 1),
   963 	(rtac mp 1),
   961 	(rtac mp 1),
   964 	(atac 1),
   962 	(atac 1),
   965 	(asm_simp_tac nat_ss 1),
   963 	(Asm_simp_tac 1),
   966 	(res_inst_tac [("s","Y(n)"),("t","if n < Suc(i) then Y(Suc(i)) else Y(n)")] ssubst 1),
   964 	(res_inst_tac [("s","Y(n)"),("t","if n < Suc(i) then Y(Suc(i)) else Y(n)")] ssubst 1),
   967 	(res_inst_tac [("s","False"),("t","n < Suc(i)")] ssubst 1),
   965 	(res_inst_tac [("s","False"),("t","n < Suc(i)")] ssubst 1),
   968 	(rtac iffI 1),
   966 	(rtac iffI 1),
   969 	(etac FalseE 2),
   967 	(etac FalseE 2),
   970 	(rtac notE 1),
   968 	(rtac notE 1),
   971 	(etac less_not_sym 1),	
   969 	(etac less_not_sym 1),	
   972 	(atac 1),
   970 	(atac 1),
   973 	(asm_simp_tac nat_ss 1),
   971 	(Asm_simp_tac 1),
   974 	(dtac spec 1),
   972 	(dtac spec 1),
   975 	(rtac mp 1),
   973 	(rtac mp 1),
   976 	(atac 1),
   974 	(atac 1),
   977 	(etac Suc_lessD 1)
   975 	(etac Suc_lessD 1)
   978 	]);
   976 	]);