equal
deleted
inserted
replaced
145 unfolding fix_def2 |
145 unfolding fix_def2 |
146 apply (erule admD) |
146 apply (erule admD) |
147 apply (rule chain_iterate) |
147 apply (rule chain_iterate) |
148 apply (rule nat_induct, simp_all) |
148 apply (rule nat_induct, simp_all) |
149 done |
149 done |
|
150 |
|
151 lemma cont_fix_ind: |
|
152 "\<lbrakk>cont F; adm P; P \<bottom>; \<And>x. P x \<Longrightarrow> P (F x)\<rbrakk> \<Longrightarrow> P (fix\<cdot>(Abs_cfun F))" |
|
153 by (simp add: fix_ind) |
150 |
154 |
151 lemma def_fix_ind: |
155 lemma def_fix_ind: |
152 "\<lbrakk>f \<equiv> fix\<cdot>F; adm P; P \<bottom>; \<And>x. P x \<Longrightarrow> P (F\<cdot>x)\<rbrakk> \<Longrightarrow> P f" |
156 "\<lbrakk>f \<equiv> fix\<cdot>F; adm P; P \<bottom>; \<And>x. P x \<Longrightarrow> P (F\<cdot>x)\<rbrakk> \<Longrightarrow> P f" |
153 by (simp add: fix_ind) |
157 by (simp add: fix_ind) |
154 |
158 |
187 hence "P (\<Squnion>i. iterate i\<cdot>F\<cdot>\<bottom>) (\<Squnion>i. iterate i\<cdot>G\<cdot>\<bottom>)" |
191 hence "P (\<Squnion>i. iterate i\<cdot>F\<cdot>\<bottom>) (\<Squnion>i. iterate i\<cdot>G\<cdot>\<bottom>)" |
188 by simp |
192 by simp |
189 thus "P (fix\<cdot>F) (fix\<cdot>G)" |
193 thus "P (fix\<cdot>F) (fix\<cdot>G)" |
190 by (simp add: fix_def2) |
194 by (simp add: fix_def2) |
191 qed |
195 qed |
|
196 |
|
197 lemma cont_parallel_fix_ind: |
|
198 assumes "cont F" and "cont G" |
|
199 assumes "adm (\<lambda>x. P (fst x) (snd x))" |
|
200 assumes "P \<bottom> \<bottom>" |
|
201 assumes "\<And>x y. P x y \<Longrightarrow> P (F x) (G y)" |
|
202 shows "P (fix\<cdot>(Abs_cfun F)) (fix\<cdot>(Abs_cfun G))" |
|
203 by (rule parallel_fix_ind, simp_all add: assms) |
192 |
204 |
193 subsection {* Fixed-points on product types *} |
205 subsection {* Fixed-points on product types *} |
194 |
206 |
195 text {* |
207 text {* |
196 Bekic's Theorem: Simultaneous fixed points over pairs |
208 Bekic's Theorem: Simultaneous fixed points over pairs |