src/HOLCF/Deflation.thy
changeset 29237 e90d9d51106b
parent 28613 15a41d3fa959
child 29252 ea97aa6aeba2
equal deleted inserted replaced
29236:51526dd8da8e 29237:e90d9d51106b
     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)