src/HOLCF/Deflation.thy
changeset 28611 983c1855a7af
parent 27681 8cedebf55539
child 28613 15a41d3fa959
equal deleted inserted replaced
28610:2ededdda7294 28611:983c1855a7af
    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