src/HOLCF/Bifinite.thy
 author huffman Wed Nov 10 17:56:08 2010 -0800 (2010-11-10) changeset 40502 8e92772bc0e8 parent 40497 d2e876d6da8c child 40506 4c5363173f88 permissions -rw-r--r--
move map functions to new theory file Map_Functions; add theory file Plain_HOLCF
```     1 (*  Title:      HOLCF/Bifinite.thy
```
```     2     Author:     Brian Huffman
```
```     3 *)
```
```     4
```
```     5 header {* Bifinite domains *}
```
```     6
```
```     7 theory Bifinite
```
```     8 imports Algebraic Map_Functions Countable
```
```     9 begin
```
```    10
```
```    11 subsection {* Class of bifinite domains *}
```
```    12
```
```    13 text {*
```
```    14   We define a ``domain'' as a pcpo that is isomorphic to some
```
```    15   algebraic deflation over the universal domain; this is equivalent
```
```    16   to being omega-bifinite.
```
```    17
```
```    18   A predomain is a cpo that, when lifted, becomes a domain.
```
```    19 *}
```
```    20
```
```    21 class predomain = cpo +
```
```    22   fixes liftdefl :: "('a::cpo) itself \<Rightarrow> defl"
```
```    23   fixes liftemb :: "'a\<^sub>\<bottom> \<rightarrow> udom"
```
```    24   fixes liftprj :: "udom \<rightarrow> 'a\<^sub>\<bottom>"
```
```    25   assumes predomain_ep: "ep_pair liftemb liftprj"
```
```    26   assumes cast_liftdefl: "cast\<cdot>(liftdefl TYPE('a::cpo)) = liftemb oo liftprj"
```
```    27
```
```    28 syntax "_LIFTDEFL" :: "type \<Rightarrow> logic"  ("(1LIFTDEFL/(1'(_')))")
```
```    29 translations "LIFTDEFL('t)" \<rightleftharpoons> "CONST liftdefl TYPE('t)"
```
```    30
```
```    31 class "domain" = predomain + pcpo +
```
```    32   fixes emb :: "'a::cpo \<rightarrow> udom"
```
```    33   fixes prj :: "udom \<rightarrow> 'a::cpo"
```
```    34   fixes defl :: "'a itself \<Rightarrow> defl"
```
```    35   assumes ep_pair_emb_prj: "ep_pair emb prj"
```
```    36   assumes cast_DEFL: "cast\<cdot>(defl TYPE('a)) = emb oo prj"
```
```    37
```
```    38 syntax "_DEFL" :: "type \<Rightarrow> defl"  ("(1DEFL/(1'(_')))")
```
```    39 translations "DEFL('t)" \<rightleftharpoons> "CONST defl TYPE('t)"
```
```    40
```
```    41 interpretation "domain": pcpo_ep_pair emb prj
```
```    42   unfolding pcpo_ep_pair_def
```
```    43   by (rule ep_pair_emb_prj)
```
```    44
```
```    45 lemmas emb_inverse = domain.e_inverse
```
```    46 lemmas emb_prj_below = domain.e_p_below
```
```    47 lemmas emb_eq_iff = domain.e_eq_iff
```
```    48 lemmas emb_strict = domain.e_strict
```
```    49 lemmas prj_strict = domain.p_strict
```
```    50
```
```    51 subsection {* Domains have a countable compact basis *}
```
```    52
```
```    53 text {*
```
```    54   Eventually it should be possible to generalize this to an unpointed
```
```    55   variant of the domain class.
```
```    56 *}
```
```    57
```
```    58 interpretation compact_basis:
```
```    59   ideal_completion below Rep_compact_basis "approximants::'a::domain \<Rightarrow> _"
```
```    60 proof -
```
```    61   obtain Y where Y: "\<forall>i. Y i \<sqsubseteq> Y (Suc i)"
```
```    62   and DEFL: "DEFL('a) = (\<Squnion>i. defl_principal (Y i))"
```
```    63     by (rule defl.obtain_principal_chain)
```
```    64   def approx \<equiv> "\<lambda>i. (prj oo cast\<cdot>(defl_principal (Y i)) oo emb) :: 'a \<rightarrow> 'a"
```
```    65   interpret defl_approx: approx_chain approx
```
```    66   proof (rule approx_chain.intro)
```
```    67     show "chain (\<lambda>i. approx i)"
```
```    68       unfolding approx_def by (simp add: Y)
```
```    69     show "(\<Squnion>i. approx i) = ID"
```
```    70       unfolding approx_def
```
```    71       by (simp add: lub_distribs Y DEFL [symmetric] cast_DEFL cfun_eq_iff)
```
```    72     show "\<And>i. finite_deflation (approx i)"
```
```    73       unfolding approx_def
```
```    74       apply (rule domain.finite_deflation_p_d_e)
```
```    75       apply (rule finite_deflation_cast)
```
```    76       apply (rule defl.compact_principal)
```
```    77       apply (rule below_trans [OF monofun_cfun_fun])
```
```    78       apply (rule is_ub_thelub, simp add: Y)
```
```    79       apply (simp add: lub_distribs Y DEFL [symmetric] cast_DEFL)
```
```    80       done
```
```    81   qed
```
```    82   (* FIXME: why does show ?thesis fail here? *)
```
```    83   show "ideal_completion below Rep_compact_basis (approximants::'a \<Rightarrow> _)" ..
```
```    84 qed
```
```    85
```
```    86 subsection {* Chains of approx functions *}
```
```    87
```
```    88 definition u_approx :: "nat \<Rightarrow> udom\<^sub>\<bottom> \<rightarrow> udom\<^sub>\<bottom>"
```
```    89   where "u_approx = (\<lambda>i. u_map\<cdot>(udom_approx i))"
```
```    90
```
```    91 definition cfun_approx :: "nat \<Rightarrow> (udom \<rightarrow> udom) \<rightarrow> (udom \<rightarrow> udom)"
```
```    92   where "cfun_approx = (\<lambda>i. cfun_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```    93
```
```    94 definition prod_approx :: "nat \<Rightarrow> udom \<times> udom \<rightarrow> udom \<times> udom"
```
```    95   where "prod_approx = (\<lambda>i. cprod_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```    96
```
```    97 definition sprod_approx :: "nat \<Rightarrow> udom \<otimes> udom \<rightarrow> udom \<otimes> udom"
```
```    98   where "sprod_approx = (\<lambda>i. sprod_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```    99
```
```   100 definition ssum_approx :: "nat \<Rightarrow> udom \<oplus> udom \<rightarrow> udom \<oplus> udom"
```
```   101   where "ssum_approx = (\<lambda>i. ssum_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```   102
```
```   103 lemma approx_chain_lemma1:
```
```   104   assumes "m\<cdot>ID = ID"
```
```   105   assumes "\<And>d. finite_deflation d \<Longrightarrow> finite_deflation (m\<cdot>d)"
```
```   106   shows "approx_chain (\<lambda>i. m\<cdot>(udom_approx i))"
```
```   107 by (rule approx_chain.intro)
```
```   108    (simp_all add: lub_distribs finite_deflation_udom_approx assms)
```
```   109
```
```   110 lemma approx_chain_lemma2:
```
```   111   assumes "m\<cdot>ID\<cdot>ID = ID"
```
```   112   assumes "\<And>a b. \<lbrakk>finite_deflation a; finite_deflation b\<rbrakk>
```
```   113     \<Longrightarrow> finite_deflation (m\<cdot>a\<cdot>b)"
```
```   114   shows "approx_chain (\<lambda>i. m\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```   115 by (rule approx_chain.intro)
```
```   116    (simp_all add: lub_distribs finite_deflation_udom_approx assms)
```
```   117
```
```   118 lemma u_approx: "approx_chain u_approx"
```
```   119 using u_map_ID finite_deflation_u_map
```
```   120 unfolding u_approx_def by (rule approx_chain_lemma1)
```
```   121
```
```   122 lemma cfun_approx: "approx_chain cfun_approx"
```
```   123 using cfun_map_ID finite_deflation_cfun_map
```
```   124 unfolding cfun_approx_def by (rule approx_chain_lemma2)
```
```   125
```
```   126 lemma prod_approx: "approx_chain prod_approx"
```
```   127 using cprod_map_ID finite_deflation_cprod_map
```
```   128 unfolding prod_approx_def by (rule approx_chain_lemma2)
```
```   129
```
```   130 lemma sprod_approx: "approx_chain sprod_approx"
```
```   131 using sprod_map_ID finite_deflation_sprod_map
```
```   132 unfolding sprod_approx_def by (rule approx_chain_lemma2)
```
```   133
```
```   134 lemma ssum_approx: "approx_chain ssum_approx"
```
```   135 using ssum_map_ID finite_deflation_ssum_map
```
```   136 unfolding ssum_approx_def by (rule approx_chain_lemma2)
```
```   137
```
```   138 subsection {* Type combinators *}
```
```   139
```
```   140 definition
```
```   141   defl_fun1 ::
```
```   142     "(nat \<Rightarrow> 'a \<rightarrow> 'a) \<Rightarrow> ((udom \<rightarrow> udom) \<rightarrow> ('a \<rightarrow> 'a)) \<Rightarrow> (defl \<rightarrow> defl)"
```
```   143 where
```
```   144   "defl_fun1 approx f =
```
```   145     defl.basis_fun (\<lambda>a.
```
```   146       defl_principal (Abs_fin_defl
```
```   147         (udom_emb approx oo f\<cdot>(Rep_fin_defl a) oo udom_prj approx)))"
```
```   148
```
```   149 definition
```
```   150   defl_fun2 ::
```
```   151     "(nat \<Rightarrow> 'a \<rightarrow> 'a) \<Rightarrow> ((udom \<rightarrow> udom) \<rightarrow> (udom \<rightarrow> udom) \<rightarrow> ('a \<rightarrow> 'a))
```
```   152       \<Rightarrow> (defl \<rightarrow> defl \<rightarrow> defl)"
```
```   153 where
```
```   154   "defl_fun2 approx f =
```
```   155     defl.basis_fun (\<lambda>a.
```
```   156       defl.basis_fun (\<lambda>b.
```
```   157         defl_principal (Abs_fin_defl
```
```   158           (udom_emb approx oo
```
```   159             f\<cdot>(Rep_fin_defl a)\<cdot>(Rep_fin_defl b) oo udom_prj approx))))"
```
```   160
```
```   161 lemma cast_defl_fun1:
```
```   162   assumes approx: "approx_chain approx"
```
```   163   assumes f: "\<And>a. finite_deflation a \<Longrightarrow> finite_deflation (f\<cdot>a)"
```
```   164   shows "cast\<cdot>(defl_fun1 approx f\<cdot>A) = udom_emb approx oo f\<cdot>(cast\<cdot>A) oo udom_prj approx"
```
```   165 proof -
```
```   166   have 1: "\<And>a. finite_deflation
```
```   167         (udom_emb approx oo f\<cdot>(Rep_fin_defl a) oo udom_prj approx)"
```
```   168     apply (rule ep_pair.finite_deflation_e_d_p)
```
```   169     apply (rule approx_chain.ep_pair_udom [OF approx])
```
```   170     apply (rule f, rule finite_deflation_Rep_fin_defl)
```
```   171     done
```
```   172   show ?thesis
```
```   173     by (induct A rule: defl.principal_induct, simp)
```
```   174        (simp only: defl_fun1_def
```
```   175                    defl.basis_fun_principal
```
```   176                    defl.basis_fun_mono
```
```   177                    defl.principal_mono
```
```   178                    Abs_fin_defl_mono [OF 1 1]
```
```   179                    monofun_cfun below_refl
```
```   180                    Rep_fin_defl_mono
```
```   181                    cast_defl_principal
```
```   182                    Abs_fin_defl_inverse [unfolded mem_Collect_eq, OF 1])
```
```   183 qed
```
```   184
```
```   185 lemma cast_defl_fun2:
```
```   186   assumes approx: "approx_chain approx"
```
```   187   assumes f: "\<And>a b. finite_deflation a \<Longrightarrow> finite_deflation b \<Longrightarrow>
```
```   188                 finite_deflation (f\<cdot>a\<cdot>b)"
```
```   189   shows "cast\<cdot>(defl_fun2 approx f\<cdot>A\<cdot>B) =
```
```   190     udom_emb approx oo f\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj approx"
```
```   191 proof -
```
```   192   have 1: "\<And>a b. finite_deflation (udom_emb approx oo
```
```   193       f\<cdot>(Rep_fin_defl a)\<cdot>(Rep_fin_defl b) oo udom_prj approx)"
```
```   194     apply (rule ep_pair.finite_deflation_e_d_p)
```
```   195     apply (rule ep_pair_udom [OF approx])
```
```   196     apply (rule f, (rule finite_deflation_Rep_fin_defl)+)
```
```   197     done
```
```   198   show ?thesis
```
```   199     by (induct A B rule: defl.principal_induct2, simp, simp)
```
```   200        (simp only: defl_fun2_def
```
```   201                    defl.basis_fun_principal
```
```   202                    defl.basis_fun_mono
```
```   203                    defl.principal_mono
```
```   204                    Abs_fin_defl_mono [OF 1 1]
```
```   205                    monofun_cfun below_refl
```
```   206                    Rep_fin_defl_mono
```
```   207                    cast_defl_principal
```
```   208                    Abs_fin_defl_inverse [unfolded mem_Collect_eq, OF 1])
```
```   209 qed
```
```   210
```
```   211 definition u_defl :: "defl \<rightarrow> defl"
```
```   212   where "u_defl = defl_fun1 u_approx u_map"
```
```   213
```
```   214 definition cfun_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   215   where "cfun_defl = defl_fun2 cfun_approx cfun_map"
```
```   216
```
```   217 definition prod_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   218   where "prod_defl = defl_fun2 prod_approx cprod_map"
```
```   219
```
```   220 definition sprod_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   221   where "sprod_defl = defl_fun2 sprod_approx sprod_map"
```
```   222
```
```   223 definition ssum_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   224 where "ssum_defl = defl_fun2 ssum_approx ssum_map"
```
```   225
```
```   226 lemma cast_u_defl:
```
```   227   "cast\<cdot>(u_defl\<cdot>A) =
```
```   228     udom_emb u_approx oo u_map\<cdot>(cast\<cdot>A) oo udom_prj u_approx"
```
```   229 using u_approx finite_deflation_u_map
```
```   230 unfolding u_defl_def by (rule cast_defl_fun1)
```
```   231
```
```   232 lemma cast_cfun_defl:
```
```   233   "cast\<cdot>(cfun_defl\<cdot>A\<cdot>B) =
```
```   234     udom_emb cfun_approx oo cfun_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj cfun_approx"
```
```   235 using cfun_approx finite_deflation_cfun_map
```
```   236 unfolding cfun_defl_def by (rule cast_defl_fun2)
```
```   237
```
```   238 lemma cast_prod_defl:
```
```   239   "cast\<cdot>(prod_defl\<cdot>A\<cdot>B) = udom_emb prod_approx oo
```
```   240     cprod_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj prod_approx"
```
```   241 using prod_approx finite_deflation_cprod_map
```
```   242 unfolding prod_defl_def by (rule cast_defl_fun2)
```
```   243
```
```   244 lemma cast_sprod_defl:
```
```   245   "cast\<cdot>(sprod_defl\<cdot>A\<cdot>B) =
```
```   246     udom_emb sprod_approx oo
```
```   247       sprod_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo
```
```   248         udom_prj sprod_approx"
```
```   249 using sprod_approx finite_deflation_sprod_map
```
```   250 unfolding sprod_defl_def by (rule cast_defl_fun2)
```
```   251
```
```   252 lemma cast_ssum_defl:
```
```   253   "cast\<cdot>(ssum_defl\<cdot>A\<cdot>B) =
```
```   254     udom_emb ssum_approx oo ssum_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj ssum_approx"
```
```   255 using ssum_approx finite_deflation_ssum_map
```
```   256 unfolding ssum_defl_def by (rule cast_defl_fun2)
```
```   257
```
```   258 subsection {* Lemma for proving domain instances *}
```
```   259
```
```   260 text {*
```
```   261   A class of domains where @{const liftemb}, @{const liftprj},
```
```   262   and @{const liftdefl} are all defined in the standard way.
```
```   263 *}
```
```   264
```
```   265 class liftdomain = "domain" +
```
```   266   assumes liftemb_eq: "liftemb = udom_emb u_approx oo u_map\<cdot>emb"
```
```   267   assumes liftprj_eq: "liftprj = u_map\<cdot>prj oo udom_prj u_approx"
```
```   268   assumes liftdefl_eq: "liftdefl TYPE('a::cpo) = u_defl\<cdot>DEFL('a)"
```
```   269
```
```   270 text {* Temporarily relax type constraints. *}
```
```   271
```
```   272 setup {*
```
```   273   fold Sign.add_const_constraint
```
```   274   [ (@{const_name defl}, SOME @{typ "'a::pcpo itself \<Rightarrow> defl"})
```
```   275   , (@{const_name emb}, SOME @{typ "'a::pcpo \<rightarrow> udom"})
```
```   276   , (@{const_name prj}, SOME @{typ "udom \<rightarrow> 'a::pcpo"})
```
```   277   , (@{const_name liftdefl}, SOME @{typ "'a::pcpo itself \<Rightarrow> defl"})
```
```   278   , (@{const_name liftemb}, SOME @{typ "'a::pcpo u \<rightarrow> udom"})
```
```   279   , (@{const_name liftprj}, SOME @{typ "udom \<rightarrow> 'a::pcpo u"}) ]
```
```   280 *}
```
```   281
```
```   282 lemma liftdomain_class_intro:
```
```   283   assumes liftemb: "(liftemb :: 'a u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb"
```
```   284   assumes liftprj: "(liftprj :: udom \<rightarrow> 'a u) = u_map\<cdot>prj oo udom_prj u_approx"
```
```   285   assumes liftdefl: "liftdefl TYPE('a) = u_defl\<cdot>DEFL('a)"
```
```   286   assumes ep_pair: "ep_pair emb (prj :: udom \<rightarrow> 'a)"
```
```   287   assumes cast_defl: "cast\<cdot>DEFL('a) = emb oo (prj :: udom \<rightarrow> 'a)"
```
```   288   shows "OFCLASS('a, liftdomain_class)"
```
```   289 proof
```
```   290   show "ep_pair liftemb (liftprj :: udom \<rightarrow> 'a u)"
```
```   291     unfolding liftemb liftprj
```
```   292     by (intro ep_pair_comp ep_pair_u_map ep_pair ep_pair_udom u_approx)
```
```   293   show "cast\<cdot>LIFTDEFL('a) = liftemb oo (liftprj :: udom \<rightarrow> 'a u)"
```
```   294     unfolding liftemb liftprj liftdefl
```
```   295     by (simp add: cfcomp1 cast_u_defl cast_defl u_map_map)
```
```   296 next
```
```   297 qed fact+
```
```   298
```
```   299 text {* Restore original type constraints. *}
```
```   300
```
```   301 setup {*
```
```   302   fold Sign.add_const_constraint
```
```   303   [ (@{const_name defl}, SOME @{typ "'a::domain itself \<Rightarrow> defl"})
```
```   304   , (@{const_name emb}, SOME @{typ "'a::domain \<rightarrow> udom"})
```
```   305   , (@{const_name prj}, SOME @{typ "udom \<rightarrow> 'a::domain"})
```
```   306   , (@{const_name liftdefl}, SOME @{typ "'a::predomain itself \<Rightarrow> defl"})
```
```   307   , (@{const_name liftemb}, SOME @{typ "'a::predomain u \<rightarrow> udom"})
```
```   308   , (@{const_name liftprj}, SOME @{typ "udom \<rightarrow> 'a::predomain u"}) ]
```
```   309 *}
```
```   310
```
```   311 subsection {* The universal domain is a domain *}
```
```   312
```
```   313 instantiation udom :: liftdomain
```
```   314 begin
```
```   315
```
```   316 definition [simp]:
```
```   317   "emb = (ID :: udom \<rightarrow> udom)"
```
```   318
```
```   319 definition [simp]:
```
```   320   "prj = (ID :: udom \<rightarrow> udom)"
```
```   321
```
```   322 definition
```
```   323   "defl (t::udom itself) = (\<Squnion>i. defl_principal (Abs_fin_defl (udom_approx i)))"
```
```   324
```
```   325 definition
```
```   326   "(liftemb :: udom u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb"
```
```   327
```
```   328 definition
```
```   329   "(liftprj :: udom \<rightarrow> udom u) = u_map\<cdot>prj oo udom_prj u_approx"
```
```   330
```
```   331 definition
```
```   332   "liftdefl (t::udom itself) = u_defl\<cdot>DEFL(udom)"
```
```   333
```
```   334 instance
```
```   335 using liftemb_udom_def liftprj_udom_def liftdefl_udom_def
```
```   336 proof (rule liftdomain_class_intro)
```
```   337   show "ep_pair emb (prj :: udom \<rightarrow> udom)"
```
```   338     by (simp add: ep_pair.intro)
```
```   339   show "cast\<cdot>DEFL(udom) = emb oo (prj :: udom \<rightarrow> udom)"
```
```   340     unfolding defl_udom_def
```
```   341     apply (subst contlub_cfun_arg)
```
```   342     apply (rule chainI)
```
```   343     apply (rule defl.principal_mono)
```
```   344     apply (simp add: below_fin_defl_def)
```
```   345     apply (simp add: Abs_fin_defl_inverse finite_deflation_udom_approx)
```
```   346     apply (rule chainE)
```
```   347     apply (rule chain_udom_approx)
```
```   348     apply (subst cast_defl_principal)
```
```   349     apply (simp add: Abs_fin_defl_inverse finite_deflation_udom_approx)
```
```   350     done
```
```   351 qed
```
```   352
```
```   353 end
```
```   354
```
```   355 subsection {* Lifted predomains are domains *}
```
```   356
```
```   357 instantiation u :: (predomain) liftdomain
```
```   358 begin
```
```   359
```
```   360 definition
```
```   361   "emb = liftemb"
```
```   362
```
```   363 definition
```
```   364   "prj = liftprj"
```
```   365
```
```   366 definition
```
```   367   "defl (t::'a u itself) = LIFTDEFL('a)"
```
```   368
```
```   369 definition
```
```   370   "(liftemb :: 'a u u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb"
```
```   371
```
```   372 definition
```
```   373   "(liftprj :: udom \<rightarrow> 'a u u) = u_map\<cdot>prj oo udom_prj u_approx"
```
```   374
```
```   375 definition
```
```   376   "liftdefl (t::'a u itself) = u_defl\<cdot>DEFL('a u)"
```
```   377
```
```   378 instance
```
```   379 using liftemb_u_def liftprj_u_def liftdefl_u_def
```
```   380 proof (rule liftdomain_class_intro)
```
```   381   show "ep_pair emb (prj :: udom \<rightarrow> 'a u)"
```
```   382     unfolding emb_u_def prj_u_def
```
```   383     by (rule predomain_ep)
```
```   384   show "cast\<cdot>DEFL('a u) = emb oo (prj :: udom \<rightarrow> 'a u)"
```
```   385     unfolding emb_u_def prj_u_def defl_u_def
```
```   386     by (rule cast_liftdefl)
```
```   387 qed
```
```   388
```
```   389 end
```
```   390
```
```   391 lemma DEFL_u: "DEFL('a::predomain u) = LIFTDEFL('a)"
```
```   392 by (rule defl_u_def)
```
```   393
```
```   394 subsection {* Continuous function space is a domain *}
```
```   395
```
```   396 text {* TODO: Allow argument type to be a predomain. *}
```
```   397
```
```   398 instantiation cfun :: ("domain", "domain") liftdomain
```
```   399 begin
```
```   400
```
```   401 definition
```
```   402   "emb = udom_emb cfun_approx oo cfun_map\<cdot>prj\<cdot>emb"
```
```   403
```
```   404 definition
```
```   405   "prj = cfun_map\<cdot>emb\<cdot>prj oo udom_prj cfun_approx"
```
```   406
```
```   407 definition
```
```   408   "defl (t::('a \<rightarrow> 'b) itself) = cfun_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   409
```
```   410 definition
```
```   411   "(liftemb :: ('a \<rightarrow> 'b) u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb"
```
```   412
```
```   413 definition
```
```   414   "(liftprj :: udom \<rightarrow> ('a \<rightarrow> 'b) u) = u_map\<cdot>prj oo udom_prj u_approx"
```
```   415
```
```   416 definition
```
```   417   "liftdefl (t::('a \<rightarrow> 'b) itself) = u_defl\<cdot>DEFL('a \<rightarrow> 'b)"
```
```   418
```
```   419 instance
```
```   420 using liftemb_cfun_def liftprj_cfun_def liftdefl_cfun_def
```
```   421 proof (rule liftdomain_class_intro)
```
```   422   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<rightarrow> 'b)"
```
```   423     unfolding emb_cfun_def prj_cfun_def
```
```   424     using ep_pair_udom [OF cfun_approx]
```
```   425     by (intro ep_pair_comp ep_pair_cfun_map ep_pair_emb_prj)
```
```   426   show "cast\<cdot>DEFL('a \<rightarrow> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<rightarrow> 'b)"
```
```   427     unfolding emb_cfun_def prj_cfun_def defl_cfun_def cast_cfun_defl
```
```   428     by (simp add: cast_DEFL oo_def cfun_eq_iff cfun_map_map)
```
```   429 qed
```
```   430
```
```   431 end
```
```   432
```
```   433 lemma DEFL_cfun:
```
```   434   "DEFL('a::domain \<rightarrow> 'b::domain) = cfun_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   435 by (rule defl_cfun_def)
```
```   436
```
```   437 subsection {* Cartesian product is a domain *}
```
```   438
```
```   439 text {*
```
```   440   Types @{typ "('a * 'b) u"} and @{typ "'a u \<otimes> 'b u"} are isomorphic.
```
```   441 *}
```
```   442
```
```   443 definition
```
```   444   "encode_prod_u = (\<Lambda>(up\<cdot>(x, y)). (:up\<cdot>x, up\<cdot>y:))"
```
```   445
```
```   446 definition
```
```   447   "decode_prod_u = (\<Lambda>(:up\<cdot>x, up\<cdot>y:). up\<cdot>(x, y))"
```
```   448
```
```   449 lemma decode_encode_prod_u [simp]: "decode_prod_u\<cdot>(encode_prod_u\<cdot>x) = x"
```
```   450 unfolding encode_prod_u_def decode_prod_u_def
```
```   451 by (case_tac x, simp, rename_tac y, case_tac y, simp)
```
```   452
```
```   453 lemma encode_decode_prod_u [simp]: "encode_prod_u\<cdot>(decode_prod_u\<cdot>y) = y"
```
```   454 unfolding encode_prod_u_def decode_prod_u_def
```
```   455 apply (case_tac y, simp, rename_tac a b)
```
```   456 apply (case_tac a, simp, case_tac b, simp, simp)
```
```   457 done
```
```   458
```
```   459 instantiation prod :: (predomain, predomain) predomain
```
```   460 begin
```
```   461
```
```   462 definition
```
```   463   "liftemb =
```
```   464     (udom_emb sprod_approx oo sprod_map\<cdot>emb\<cdot>emb) oo encode_prod_u"
```
```   465
```
```   466 definition
```
```   467   "liftprj =
```
```   468     decode_prod_u oo (sprod_map\<cdot>prj\<cdot>prj oo udom_prj sprod_approx)"
```
```   469
```
```   470 definition
```
```   471   "liftdefl (t::('a \<times> 'b) itself) = sprod_defl\<cdot>DEFL('a u)\<cdot>DEFL('b u)"
```
```   472
```
```   473 instance proof
```
```   474   have "ep_pair encode_prod_u decode_prod_u"
```
```   475     by (rule ep_pair.intro, simp_all)
```
```   476   thus "ep_pair liftemb (liftprj :: udom \<rightarrow> ('a \<times> 'b) u)"
```
```   477     unfolding liftemb_prod_def liftprj_prod_def
```
```   478     apply (rule ep_pair_comp)
```
```   479     apply (rule ep_pair_comp)
```
```   480     apply (intro ep_pair_sprod_map ep_pair_emb_prj)
```
```   481     apply (rule ep_pair_udom [OF sprod_approx])
```
```   482     done
```
```   483   show "cast\<cdot>LIFTDEFL('a \<times> 'b) = liftemb oo (liftprj :: udom \<rightarrow> ('a \<times> 'b) u)"
```
```   484     unfolding liftemb_prod_def liftprj_prod_def liftdefl_prod_def
```
```   485     by (simp add: cast_sprod_defl cast_DEFL cfcomp1 sprod_map_map)
```
```   486 qed
```
```   487
```
```   488 end
```
```   489
```
```   490 instantiation prod :: ("domain", "domain") "domain"
```
```   491 begin
```
```   492
```
```   493 definition
```
```   494   "emb = udom_emb prod_approx oo cprod_map\<cdot>emb\<cdot>emb"
```
```   495
```
```   496 definition
```
```   497   "prj = cprod_map\<cdot>prj\<cdot>prj oo udom_prj prod_approx"
```
```   498
```
```   499 definition
```
```   500   "defl (t::('a \<times> 'b) itself) = prod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   501
```
```   502 instance proof
```
```   503   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<times> 'b)"
```
```   504     unfolding emb_prod_def prj_prod_def
```
```   505     using ep_pair_udom [OF prod_approx]
```
```   506     by (intro ep_pair_comp ep_pair_cprod_map ep_pair_emb_prj)
```
```   507 next
```
```   508   show "cast\<cdot>DEFL('a \<times> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<times> 'b)"
```
```   509     unfolding emb_prod_def prj_prod_def defl_prod_def cast_prod_defl
```
```   510     by (simp add: cast_DEFL oo_def cfun_eq_iff cprod_map_map)
```
```   511 qed
```
```   512
```
```   513 end
```
```   514
```
```   515 lemma DEFL_prod:
```
```   516   "DEFL('a::domain \<times> 'b::domain) = prod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   517 by (rule defl_prod_def)
```
```   518
```
```   519 lemma LIFTDEFL_prod:
```
```   520   "LIFTDEFL('a::predomain \<times> 'b::predomain) = sprod_defl\<cdot>DEFL('a u)\<cdot>DEFL('b u)"
```
```   521 by (rule liftdefl_prod_def)
```
```   522
```
```   523 subsection {* Strict product is a domain *}
```
```   524
```
```   525 instantiation sprod :: ("domain", "domain") liftdomain
```
```   526 begin
```
```   527
```
```   528 definition
```
```   529   "emb = udom_emb sprod_approx oo sprod_map\<cdot>emb\<cdot>emb"
```
```   530
```
```   531 definition
```
```   532   "prj = sprod_map\<cdot>prj\<cdot>prj oo udom_prj sprod_approx"
```
```   533
```
```   534 definition
```
```   535   "defl (t::('a \<otimes> 'b) itself) = sprod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   536
```
```   537 definition
```
```   538   "(liftemb :: ('a \<otimes> 'b) u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb"
```
```   539
```
```   540 definition
```
```   541   "(liftprj :: udom \<rightarrow> ('a \<otimes> 'b) u) = u_map\<cdot>prj oo udom_prj u_approx"
```
```   542
```
```   543 definition
```
```   544   "liftdefl (t::('a \<otimes> 'b) itself) = u_defl\<cdot>DEFL('a \<otimes> 'b)"
```
```   545
```
```   546 instance
```
```   547 using liftemb_sprod_def liftprj_sprod_def liftdefl_sprod_def
```
```   548 proof (rule liftdomain_class_intro)
```
```   549   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<otimes> 'b)"
```
```   550     unfolding emb_sprod_def prj_sprod_def
```
```   551     using ep_pair_udom [OF sprod_approx]
```
```   552     by (intro ep_pair_comp ep_pair_sprod_map ep_pair_emb_prj)
```
```   553 next
```
```   554   show "cast\<cdot>DEFL('a \<otimes> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<otimes> 'b)"
```
```   555     unfolding emb_sprod_def prj_sprod_def defl_sprod_def cast_sprod_defl
```
```   556     by (simp add: cast_DEFL oo_def cfun_eq_iff sprod_map_map)
```
```   557 qed
```
```   558
```
```   559 end
```
```   560
```
```   561 lemma DEFL_sprod:
```
```   562   "DEFL('a::domain \<otimes> 'b::domain) = sprod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   563 by (rule defl_sprod_def)
```
```   564
```
```   565 subsection {* Countable discrete cpos are predomains *}
```
```   566
```
```   567 definition discr_approx :: "nat \<Rightarrow> 'a::countable discr u \<rightarrow> 'a discr u"
```
```   568   where "discr_approx = (\<lambda>i. \<Lambda>(up\<cdot>x). if to_nat (undiscr x) < i then up\<cdot>x else \<bottom>)"
```
```   569
```
```   570 lemma chain_discr_approx [simp]: "chain discr_approx"
```
```   571 unfolding discr_approx_def
```
```   572 by (rule chainI, simp add: monofun_cfun monofun_LAM)
```
```   573
```
```   574 lemma lub_discr_approx [simp]: "(\<Squnion>i. discr_approx i) = ID"
```
```   575 apply (rule cfun_eqI)
```
```   576 apply (simp add: contlub_cfun_fun)
```
```   577 apply (simp add: discr_approx_def)
```
```   578 apply (case_tac x, simp)
```
```   579 apply (rule thelubI)
```
```   580 apply (rule is_lubI)
```
```   581 apply (rule ub_rangeI, simp)
```
```   582 apply (drule ub_rangeD)
```
```   583 apply (erule rev_below_trans)
```
```   584 apply simp
```
```   585 apply (rule lessI)
```
```   586 done
```
```   587
```
```   588 lemma inj_on_undiscr [simp]: "inj_on undiscr A"
```
```   589 using Discr_undiscr by (rule inj_on_inverseI)
```
```   590
```
```   591 lemma finite_deflation_discr_approx: "finite_deflation (discr_approx i)"
```
```   592 proof
```
```   593   fix x :: "'a discr u"
```
```   594   show "discr_approx i\<cdot>x \<sqsubseteq> x"
```
```   595     unfolding discr_approx_def
```
```   596     by (cases x, simp, simp)
```
```   597   show "discr_approx i\<cdot>(discr_approx i\<cdot>x) = discr_approx i\<cdot>x"
```
```   598     unfolding discr_approx_def
```
```   599     by (cases x, simp, simp)
```
```   600   show "finite {x::'a discr u. discr_approx i\<cdot>x = x}"
```
```   601   proof (rule finite_subset)
```
```   602     let ?S = "insert (\<bottom>::'a discr u) ((\<lambda>x. up\<cdot>x) ` undiscr -` to_nat -` {..<i})"
```
```   603     show "{x::'a discr u. discr_approx i\<cdot>x = x} \<subseteq> ?S"
```
```   604       unfolding discr_approx_def
```
```   605       by (rule subsetI, case_tac x, simp, simp split: split_if_asm)
```
```   606     show "finite ?S"
```
```   607       by (simp add: finite_vimageI)
```
```   608   qed
```
```   609 qed
```
```   610
```
```   611 lemma discr_approx: "approx_chain discr_approx"
```
```   612 using chain_discr_approx lub_discr_approx finite_deflation_discr_approx
```
```   613 by (rule approx_chain.intro)
```
```   614
```
```   615 instantiation discr :: (countable) predomain
```
```   616 begin
```
```   617
```
```   618 definition
```
```   619   "liftemb = udom_emb discr_approx"
```
```   620
```
```   621 definition
```
```   622   "liftprj = udom_prj discr_approx"
```
```   623
```
```   624 definition
```
```   625   "liftdefl (t::'a discr itself) =
```
```   626     (\<Squnion>i. defl_principal (Abs_fin_defl (liftemb oo discr_approx i oo liftprj)))"
```
```   627
```
```   628 instance proof
```
```   629   show "ep_pair liftemb (liftprj :: udom \<rightarrow> 'a discr u)"
```
```   630     unfolding liftemb_discr_def liftprj_discr_def
```
```   631     by (rule ep_pair_udom [OF discr_approx])
```
```   632   show "cast\<cdot>LIFTDEFL('a discr) = liftemb oo (liftprj :: udom \<rightarrow> 'a discr u)"
```
```   633     unfolding liftemb_discr_def liftprj_discr_def liftdefl_discr_def
```
```   634     apply (subst contlub_cfun_arg)
```
```   635     apply (rule chainI)
```
```   636     apply (rule defl.principal_mono)
```
```   637     apply (simp add: below_fin_defl_def)
```
```   638     apply (simp add: Abs_fin_defl_inverse
```
```   639         ep_pair.finite_deflation_e_d_p [OF ep_pair_udom [OF discr_approx]]
```
```   640         approx_chain.finite_deflation_approx [OF discr_approx])
```
```   641     apply (intro monofun_cfun below_refl)
```
```   642     apply (rule chainE)
```
```   643     apply (rule chain_discr_approx)
```
```   644     apply (subst cast_defl_principal)
```
```   645     apply (simp add: Abs_fin_defl_inverse
```
```   646         ep_pair.finite_deflation_e_d_p [OF ep_pair_udom [OF discr_approx]]
```
```   647         approx_chain.finite_deflation_approx [OF discr_approx])
```
```   648     apply (simp add: lub_distribs)
```
```   649     done
```
```   650 qed
```
```   651
```
```   652 end
```
```   653
```
```   654 subsection {* Strict sum is a domain *}
```
```   655
```
```   656 instantiation ssum :: ("domain", "domain") liftdomain
```
```   657 begin
```
```   658
```
```   659 definition
```
```   660   "emb = udom_emb ssum_approx oo ssum_map\<cdot>emb\<cdot>emb"
```
```   661
```
```   662 definition
```
```   663   "prj = ssum_map\<cdot>prj\<cdot>prj oo udom_prj ssum_approx"
```
```   664
```
```   665 definition
```
```   666   "defl (t::('a \<oplus> 'b) itself) = ssum_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   667
```
```   668 definition
```
```   669   "(liftemb :: ('a \<oplus> 'b) u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb"
```
```   670
```
```   671 definition
```
```   672   "(liftprj :: udom \<rightarrow> ('a \<oplus> 'b) u) = u_map\<cdot>prj oo udom_prj u_approx"
```
```   673
```
```   674 definition
```
```   675   "liftdefl (t::('a \<oplus> 'b) itself) = u_defl\<cdot>DEFL('a \<oplus> 'b)"
```
```   676
```
```   677 instance
```
```   678 using liftemb_ssum_def liftprj_ssum_def liftdefl_ssum_def
```
```   679 proof (rule liftdomain_class_intro)
```
```   680   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<oplus> 'b)"
```
```   681     unfolding emb_ssum_def prj_ssum_def
```
```   682     using ep_pair_udom [OF ssum_approx]
```
```   683     by (intro ep_pair_comp ep_pair_ssum_map ep_pair_emb_prj)
```
```   684   show "cast\<cdot>DEFL('a \<oplus> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<oplus> 'b)"
```
```   685     unfolding emb_ssum_def prj_ssum_def defl_ssum_def cast_ssum_defl
```
```   686     by (simp add: cast_DEFL oo_def cfun_eq_iff ssum_map_map)
```
```   687 qed
```
```   688
```
```   689 end
```
```   690
```
```   691 lemma DEFL_ssum:
```
```   692   "DEFL('a::domain \<oplus> 'b::domain) = ssum_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   693 by (rule defl_ssum_def)
```
```   694
```
```   695 subsection {* Lifted countable types are bifinite domains *}
```
```   696
```
```   697 instantiation lift :: (countable) liftdomain
```
```   698 begin
```
```   699
```
```   700 definition
```
```   701   "emb = emb oo (\<Lambda> x. Rep_lift x)"
```
```   702
```
```   703 definition
```
```   704   "prj = (\<Lambda> y. Abs_lift y) oo prj"
```
```   705
```
```   706 definition
```
```   707   "defl (t::'a lift itself) = DEFL('a discr u)"
```
```   708
```
```   709 definition
```
```   710   "(liftemb :: 'a lift u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb"
```
```   711
```
```   712 definition
```
```   713   "(liftprj :: udom \<rightarrow> 'a lift u) = u_map\<cdot>prj oo udom_prj u_approx"
```
```   714
```
```   715 definition
```
```   716   "liftdefl (t::'a lift itself) = u_defl\<cdot>DEFL('a lift)"
```
```   717
```
```   718 instance
```
```   719 using liftemb_lift_def liftprj_lift_def liftdefl_lift_def
```
```   720 proof (rule liftdomain_class_intro)
```
```   721   note [simp] = cont_Rep_lift cont_Abs_lift Rep_lift_inverse Abs_lift_inverse
```
```   722   have "ep_pair (\<Lambda>(x::'a lift). Rep_lift x) (\<Lambda> y. Abs_lift y)"
```
```   723     by (simp add: ep_pair_def)
```
```   724   thus "ep_pair emb (prj :: udom \<rightarrow> 'a lift)"
```
```   725     unfolding emb_lift_def prj_lift_def
```
```   726     using ep_pair_emb_prj by (rule ep_pair_comp)
```
```   727   show "cast\<cdot>DEFL('a lift) = emb oo (prj :: udom \<rightarrow> 'a lift)"
```
```   728     unfolding emb_lift_def prj_lift_def defl_lift_def cast_DEFL
```
```   729     by (simp add: cfcomp1)
```
```   730 qed
```
```   731
```
```   732 end
```
```   733
```
```   734 end
```