equal
deleted
inserted
replaced
1 (* Title: HOLCF/Deflation.thy |
1 (* Title: HOLCF/Deflation.thy |
2 ID: $Id$ |
|
3 Author: Brian Huffman |
2 Author: Brian Huffman |
4 *) |
3 *) |
5 |
4 |
6 header {* Continuous Deflations and Embedding-Projection Pairs *} |
5 header {* Continuous Deflations and Embedding-Projection Pairs *} |
7 |
6 |
80 lemma deflation_less_comp1: |
79 lemma deflation_less_comp1: |
81 assumes "deflation f" |
80 assumes "deflation f" |
82 assumes "deflation g" |
81 assumes "deflation g" |
83 shows "f \<sqsubseteq> g \<Longrightarrow> f\<cdot>(g\<cdot>x) = f\<cdot>x" |
82 shows "f \<sqsubseteq> g \<Longrightarrow> f\<cdot>(g\<cdot>x) = f\<cdot>x" |
84 proof (rule antisym_less) |
83 proof (rule antisym_less) |
85 interpret g: deflation [g] by fact |
84 interpret g: deflation g by fact |
86 from g.less show "f\<cdot>(g\<cdot>x) \<sqsubseteq> f\<cdot>x" by (rule monofun_cfun_arg) |
85 from g.less show "f\<cdot>(g\<cdot>x) \<sqsubseteq> f\<cdot>x" by (rule monofun_cfun_arg) |
87 next |
86 next |
88 interpret f: deflation [f] by fact |
87 interpret f: deflation f by fact |
89 assume "f \<sqsubseteq> g" hence "f\<cdot>x \<sqsubseteq> g\<cdot>x" by (rule monofun_cfun_fun) |
88 assume "f \<sqsubseteq> g" hence "f\<cdot>x \<sqsubseteq> g\<cdot>x" by (rule monofun_cfun_fun) |
90 hence "f\<cdot>(f\<cdot>x) \<sqsubseteq> f\<cdot>(g\<cdot>x)" by (rule monofun_cfun_arg) |
89 hence "f\<cdot>(f\<cdot>x) \<sqsubseteq> f\<cdot>(g\<cdot>x)" by (rule monofun_cfun_arg) |
91 also have "f\<cdot>(f\<cdot>x) = f\<cdot>x" by (rule f.idem) |
90 also have "f\<cdot>(f\<cdot>x) = f\<cdot>x" by (rule f.idem) |
92 finally show "f\<cdot>x \<sqsubseteq> f\<cdot>(g\<cdot>x)" . |
91 finally show "f\<cdot>x \<sqsubseteq> f\<cdot>(g\<cdot>x)" . |
93 qed |
92 qed |
218 |
217 |
219 lemma deflation_e_d_p: |
218 lemma deflation_e_d_p: |
220 assumes "deflation d" |
219 assumes "deflation d" |
221 shows "deflation (e oo d oo p)" |
220 shows "deflation (e oo d oo p)" |
222 proof |
221 proof |
223 interpret deflation [d] by fact |
222 interpret deflation d by fact |
224 fix x :: 'b |
223 fix x :: 'b |
225 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
224 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
226 by (simp add: idem) |
225 by (simp add: idem) |
227 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
226 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
228 by (simp add: e_less_iff_less_p less) |
227 by (simp add: e_less_iff_less_p less) |
230 |
229 |
231 lemma finite_deflation_e_d_p: |
230 lemma finite_deflation_e_d_p: |
232 assumes "finite_deflation d" |
231 assumes "finite_deflation d" |
233 shows "finite_deflation (e oo d oo p)" |
232 shows "finite_deflation (e oo d oo p)" |
234 proof |
233 proof |
235 interpret finite_deflation [d] by fact |
234 interpret finite_deflation d by fact |
236 fix x :: 'b |
235 fix x :: 'b |
237 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
236 show "(e oo d oo p)\<cdot>((e oo d oo p)\<cdot>x) = (e oo d oo p)\<cdot>x" |
238 by (simp add: idem) |
237 by (simp add: idem) |
239 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
238 show "(e oo d oo p)\<cdot>x \<sqsubseteq> x" |
240 by (simp add: e_less_iff_less_p less) |
239 by (simp add: e_less_iff_less_p less) |
249 lemma deflation_p_d_e: |
248 lemma deflation_p_d_e: |
250 assumes "deflation d" |
249 assumes "deflation d" |
251 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
250 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
252 shows "deflation (p oo d oo e)" |
251 shows "deflation (p oo d oo e)" |
253 proof - |
252 proof - |
254 interpret d: deflation [d] by fact |
253 interpret d: deflation d by fact |
255 { |
254 { |
256 fix x |
255 fix x |
257 have "d\<cdot>(e\<cdot>x) \<sqsubseteq> e\<cdot>x" |
256 have "d\<cdot>(e\<cdot>x) \<sqsubseteq> e\<cdot>x" |
258 by (rule d.less) |
257 by (rule d.less) |
259 hence "p\<cdot>(d\<cdot>(e\<cdot>x)) \<sqsubseteq> p\<cdot>(e\<cdot>x)" |
258 hence "p\<cdot>(d\<cdot>(e\<cdot>x)) \<sqsubseteq> p\<cdot>(e\<cdot>x)" |
286 lemma finite_deflation_p_d_e: |
285 lemma finite_deflation_p_d_e: |
287 assumes "finite_deflation d" |
286 assumes "finite_deflation d" |
288 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
287 assumes d: "\<And>x. d\<cdot>x \<sqsubseteq> e\<cdot>(p\<cdot>x)" |
289 shows "finite_deflation (p oo d oo e)" |
288 shows "finite_deflation (p oo d oo e)" |
290 proof - |
289 proof - |
291 interpret d: finite_deflation [d] by fact |
290 interpret d: finite_deflation d by fact |
292 show ?thesis |
291 show ?thesis |
293 proof (intro_locales) |
292 proof (intro_locales) |
294 have "deflation d" .. |
293 have "deflation d" .. |
295 thus "deflation (p oo d oo e)" |
294 thus "deflation (p oo d oo e)" |
296 using d by (rule deflation_p_d_e) |
295 using d by (rule deflation_p_d_e) |
315 |
314 |
316 lemma ep_pair_unique_e_lemma: |
315 lemma ep_pair_unique_e_lemma: |
317 assumes "ep_pair e1 p" and "ep_pair e2 p" |
316 assumes "ep_pair e1 p" and "ep_pair e2 p" |
318 shows "e1 \<sqsubseteq> e2" |
317 shows "e1 \<sqsubseteq> e2" |
319 proof (rule less_cfun_ext) |
318 proof (rule less_cfun_ext) |
320 interpret e1: ep_pair [e1 p] by fact |
319 interpret e1: ep_pair e1 p by fact |
321 interpret e2: ep_pair [e2 p] by fact |
320 interpret e2: ep_pair e2 p by fact |
322 fix x |
321 fix x |
323 have "e1\<cdot>(p\<cdot>(e2\<cdot>x)) \<sqsubseteq> e2\<cdot>x" |
322 have "e1\<cdot>(p\<cdot>(e2\<cdot>x)) \<sqsubseteq> e2\<cdot>x" |
324 by (rule e1.e_p_less) |
323 by (rule e1.e_p_less) |
325 thus "e1\<cdot>x \<sqsubseteq> e2\<cdot>x" |
324 thus "e1\<cdot>x \<sqsubseteq> e2\<cdot>x" |
326 by (simp only: e2.e_inverse) |
325 by (simp only: e2.e_inverse) |
332 |
331 |
333 lemma ep_pair_unique_p_lemma: |
332 lemma ep_pair_unique_p_lemma: |
334 assumes "ep_pair e p1" and "ep_pair e p2" |
333 assumes "ep_pair e p1" and "ep_pair e p2" |
335 shows "p1 \<sqsubseteq> p2" |
334 shows "p1 \<sqsubseteq> p2" |
336 proof (rule less_cfun_ext) |
335 proof (rule less_cfun_ext) |
337 interpret p1: ep_pair [e p1] by fact |
336 interpret p1: ep_pair e p1 by fact |
338 interpret p2: ep_pair [e p2] by fact |
337 interpret p2: ep_pair e p2 by fact |
339 fix x |
338 fix x |
340 have "e\<cdot>(p1\<cdot>x) \<sqsubseteq> x" |
339 have "e\<cdot>(p1\<cdot>x) \<sqsubseteq> x" |
341 by (rule p1.e_p_less) |
340 by (rule p1.e_p_less) |
342 hence "p2\<cdot>(e\<cdot>(p1\<cdot>x)) \<sqsubseteq> p2\<cdot>x" |
341 hence "p2\<cdot>(e\<cdot>(p1\<cdot>x)) \<sqsubseteq> p2\<cdot>x" |
343 by (rule monofun_cfun_arg) |
342 by (rule monofun_cfun_arg) |
356 |
355 |
357 lemma ep_pair_comp: |
356 lemma ep_pair_comp: |
358 assumes "ep_pair e1 p1" and "ep_pair e2 p2" |
357 assumes "ep_pair e1 p1" and "ep_pair e2 p2" |
359 shows "ep_pair (e2 oo e1) (p1 oo p2)" |
358 shows "ep_pair (e2 oo e1) (p1 oo p2)" |
360 proof |
359 proof |
361 interpret ep1: ep_pair [e1 p1] by fact |
360 interpret ep1: ep_pair e1 p1 by fact |
362 interpret ep2: ep_pair [e2 p2] by fact |
361 interpret ep2: ep_pair e2 p2 by fact |
363 fix x y |
362 fix x y |
364 show "(p1 oo p2)\<cdot>((e2 oo e1)\<cdot>x) = x" |
363 show "(p1 oo p2)\<cdot>((e2 oo e1)\<cdot>x) = x" |
365 by simp |
364 by simp |
366 have "e1\<cdot>(p1\<cdot>(p2\<cdot>y)) \<sqsubseteq> p2\<cdot>y" |
365 have "e1\<cdot>(p1\<cdot>(p2\<cdot>y)) \<sqsubseteq> p2\<cdot>y" |
367 by (rule ep1.e_p_less) |
366 by (rule ep1.e_p_less) |