76 The composition of two deflations is equal to |
76 The composition of two deflations is equal to |
77 the lesser of the two (if they are comparable). |
77 the lesser of the two (if they are comparable). |
78 *} |
78 *} |
79 |
79 |
80 lemma deflation_less_comp1: |
80 lemma deflation_less_comp1: |
81 includes deflation f |
81 assumes "deflation f" |
82 includes deflation g |
82 assumes "deflation g" |
83 shows "f \<sqsubseteq> g \<Longrightarrow> f\<cdot>(g\<cdot>x) = f\<cdot>x" |
83 shows "f \<sqsubseteq> g \<Longrightarrow> f\<cdot>(g\<cdot>x) = f\<cdot>x" |
84 proof (rule antisym_less) |
84 proof (rule antisym_less) |
|
85 interpret g: deflation [g] by fact |
85 from g.less show "f\<cdot>(g\<cdot>x) \<sqsubseteq> f\<cdot>x" by (rule monofun_cfun_arg) |
86 from g.less show "f\<cdot>(g\<cdot>x) \<sqsubseteq> f\<cdot>x" by (rule monofun_cfun_arg) |
86 next |
87 next |
|
88 interpret f: deflation [f] by fact |
87 assume "f \<sqsubseteq> g" hence "f\<cdot>x \<sqsubseteq> g\<cdot>x" by (rule monofun_cfun_fun) |
89 assume "f \<sqsubseteq> g" hence "f\<cdot>x \<sqsubseteq> g\<cdot>x" by (rule monofun_cfun_fun) |
88 hence "f\<cdot>(f\<cdot>x) \<sqsubseteq> f\<cdot>(g\<cdot>x)" by (rule monofun_cfun_arg) |
90 hence "f\<cdot>(f\<cdot>x) \<sqsubseteq> f\<cdot>(g\<cdot>x)" by (rule monofun_cfun_arg) |
89 also have "f\<cdot>(f\<cdot>x) = f\<cdot>x" by (rule f.idem) |
91 also have "f\<cdot>(f\<cdot>x) = f\<cdot>x" by (rule f.idem) |
90 finally show "f\<cdot>x \<sqsubseteq> f\<cdot>(g\<cdot>x)" . |
92 finally show "f\<cdot>x \<sqsubseteq> f\<cdot>(g\<cdot>x)" . |
91 qed |
93 qed |
213 |
215 |
214 lemma deflation_e_p: "deflation (e oo p)" |
216 lemma deflation_e_p: "deflation (e oo p)" |
215 by (simp add: deflation.intro e_p_less) |
217 by (simp add: deflation.intro e_p_less) |
216 |
218 |
217 lemma deflation_e_d_p: |
219 lemma deflation_e_d_p: |
218 includes deflation d |
220 assumes "deflation d" |
219 shows "deflation (e oo d oo p)" |
221 shows "deflation (e oo d oo p)" |
220 proof |
222 proof |
|
223 interpret deflation [d] by fact |
221 fix x :: 'b |
224 fix x :: 'b |
222 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
225 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
223 by (simp add: idem) |
226 by (simp add: idem) |
224 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
227 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
225 by (simp add: e_less_iff_less_p less) |
228 by (simp add: e_less_iff_less_p less) |
226 qed |
229 qed |
227 |
230 |
228 lemma finite_deflation_e_d_p: |
231 lemma finite_deflation_e_d_p: |
229 includes finite_deflation d |
232 assumes "finite_deflation d" |
230 shows "finite_deflation (e oo d oo p)" |
233 shows "finite_deflation (e oo d oo p)" |
231 proof |
234 proof |
|
235 interpret finite_deflation [d] by fact |
232 fix x :: 'b |
236 fix x :: 'b |
233 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
237 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
234 by (simp add: idem) |
238 by (simp add: idem) |
235 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
239 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
236 by (simp add: e_less_iff_less_p less) |
240 by (simp add: e_less_iff_less_p less) |
241 thus "finite {x. (e oo d oo p)\<cdot>x = x}" |
245 thus "finite {x. (e oo d oo p)\<cdot>x = x}" |
242 by (rule finite_range_imp_finite_fixes) |
246 by (rule finite_range_imp_finite_fixes) |
243 qed |
247 qed |
244 |
248 |
245 lemma deflation_p_d_e: |
249 lemma deflation_p_d_e: |
246 includes deflation d |
250 assumes "deflation d" |
247 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
251 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
248 shows "deflation (p oo d oo e)" |
252 shows "deflation (p oo d oo e)" |
249 apply (default, simp_all) |
253 proof - |
250 apply (rule antisym_less) |
254 interpret d: deflation [d] by fact |
251 apply (rule monofun_cfun_arg) |
255 show ?thesis |
252 apply (rule trans_less [OF d]) |
256 apply (default, simp_all) |
253 apply (simp add: e_p_less) |
257 apply (rule antisym_less) |
254 apply (rule monofun_cfun_arg) |
258 apply (rule monofun_cfun_arg) |
255 apply (rule rev_trans_less) |
259 apply (rule trans_less [OF d]) |
256 apply (rule monofun_cfun_arg) |
260 apply (simp add: e_p_less) |
257 apply (rule d) |
261 apply (rule monofun_cfun_arg) |
258 apply (simp add: d.idem) |
262 apply (rule rev_trans_less) |
259 apply (rule sq_ord_less_eq_trans) |
263 apply (rule monofun_cfun_arg) |
260 apply (rule monofun_cfun_arg) |
264 apply (rule d) |
261 apply (rule d.less) |
265 apply (simp add: d.idem) |
262 apply (rule e_inverse) |
266 apply (rule sq_ord_less_eq_trans) |
263 done |
267 apply (rule monofun_cfun_arg) |
|
268 apply (rule d.less) |
|
269 apply (rule e_inverse) |
|
270 done |
|
271 qed |
264 |
272 |
265 lemma finite_deflation_p_d_e: |
273 lemma finite_deflation_p_d_e: |
266 includes finite_deflation d |
274 assumes "finite_deflation d" |
267 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
275 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
268 shows "finite_deflation (p oo d oo e)" |
276 shows "finite_deflation (p oo d oo e)" |
269 apply (rule finite_deflation.intro) |
277 proof - |
270 apply (rule deflation_p_d_e) |
278 interpret d: finite_deflation [d] by fact |
271 apply (rule `deflation d`) |
279 show ?thesis |
272 apply (rule d) |
280 apply (rule finite_deflation.intro) |
273 apply (rule finite_deflation_axioms.intro) |
281 apply (rule deflation_p_d_e) |
274 apply (rule finite_range_imp_finite_fixes) |
282 apply (rule `finite_deflation d` [THEN finite_deflation.axioms(1)]) |
275 apply (simp add: range_composition [where f="\<lambda>x. p\<cdot>x"]) |
283 apply (rule d) |
276 apply (simp add: range_composition [where f="\<lambda>x. d\<cdot>x"]) |
284 apply (rule finite_deflation_axioms.intro) |
277 apply (simp add: d.finite_image) |
285 apply (rule finite_range_imp_finite_fixes) |
278 done |
286 apply (simp add: range_composition [where f="\<lambda>x. p\<cdot>x"]) |
|
287 apply (simp add: range_composition [where f="\<lambda>x. d\<cdot>x"]) |
|
288 apply (simp add: d.finite_image) |
|
289 done |
|
290 qed |
279 |
291 |
280 end |
292 end |
281 |
293 |
282 subsection {* Uniqueness of ep-pairs *} |
294 subsection {* Uniqueness of ep-pairs *} |
283 |
295 |