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 *) |
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 ]); |