src/HOLCF/Bifinite.thy
 author huffman Tue Oct 12 06:20:05 2010 -0700 (2010-10-12) changeset 40006 116e94f9543b parent 40002 c5b5f7a3a3b1 child 40012 f13341a45407 permissions -rw-r--r--
remove unneeded lemmas from Fun_Cpo.thy
```     1 (*  Title:      HOLCF/Bifinite.thy
```
```     2     Author:     Brian Huffman
```
```     3 *)
```
```     4
```
```     5 header {* Bifinite domains *}
```
```     6
```
```     7 theory Bifinite
```
```     8 imports Algebraic Cprod Sprod Ssum Up Lift One Tr
```
```     9 begin
```
```    10
```
```    11 subsection {* Class of bifinite domains *}
```
```    12
```
```    13 text {*
```
```    14   We define a bifinite domain as a pcpo that is isomorphic to some
```
```    15   algebraic deflation over the universal domain.
```
```    16 *}
```
```    17
```
```    18 class bifinite = pcpo +
```
```    19   fixes emb :: "'a::pcpo \<rightarrow> udom"
```
```    20   fixes prj :: "udom \<rightarrow> 'a::pcpo"
```
```    21   fixes defl :: "'a itself \<Rightarrow> defl"
```
```    22   assumes ep_pair_emb_prj: "ep_pair emb prj"
```
```    23   assumes cast_DEFL: "cast\<cdot>(defl TYPE('a)) = emb oo prj"
```
```    24
```
```    25 syntax "_DEFL" :: "type \<Rightarrow> defl"  ("(1DEFL/(1'(_')))")
```
```    26 translations "DEFL('t)" \<rightleftharpoons> "CONST defl TYPE('t)"
```
```    27
```
```    28 interpretation bifinite:
```
```    29   pcpo_ep_pair "emb :: 'a::bifinite \<rightarrow> udom" "prj :: udom \<rightarrow> 'a::bifinite"
```
```    30   unfolding pcpo_ep_pair_def
```
```    31   by (rule ep_pair_emb_prj)
```
```    32
```
```    33 lemmas emb_inverse = bifinite.e_inverse
```
```    34 lemmas emb_prj_below = bifinite.e_p_below
```
```    35 lemmas emb_eq_iff = bifinite.e_eq_iff
```
```    36 lemmas emb_strict = bifinite.e_strict
```
```    37 lemmas prj_strict = bifinite.p_strict
```
```    38
```
```    39 subsection {* Bifinite domains have a countable compact basis *}
```
```    40
```
```    41 text {*
```
```    42   Eventually it should be possible to generalize this to an unpointed
```
```    43   variant of the bifinite class.
```
```    44 *}
```
```    45
```
```    46 interpretation compact_basis:
```
```    47   ideal_completion below Rep_compact_basis "approximants::'a::bifinite \<Rightarrow> _"
```
```    48 proof -
```
```    49   obtain Y where Y: "\<forall>i. Y i \<sqsubseteq> Y (Suc i)"
```
```    50   and DEFL: "DEFL('a) = (\<Squnion>i. defl_principal (Y i))"
```
```    51     by (rule defl.obtain_principal_chain)
```
```    52   def approx \<equiv> "\<lambda>i. (prj oo cast\<cdot>(defl_principal (Y i)) oo emb) :: 'a \<rightarrow> 'a"
```
```    53   interpret defl_approx: approx_chain approx
```
```    54   proof (rule approx_chain.intro)
```
```    55     show "chain (\<lambda>i. approx i)"
```
```    56       unfolding approx_def by (simp add: Y)
```
```    57     show "(\<Squnion>i. approx i) = ID"
```
```    58       unfolding approx_def
```
```    59       by (simp add: lub_distribs Y DEFL [symmetric] cast_DEFL cfun_eq_iff)
```
```    60     show "\<And>i. finite_deflation (approx i)"
```
```    61       unfolding approx_def
```
```    62       apply (rule bifinite.finite_deflation_p_d_e)
```
```    63       apply (rule finite_deflation_cast)
```
```    64       apply (rule defl.compact_principal)
```
```    65       apply (rule below_trans [OF monofun_cfun_fun])
```
```    66       apply (rule is_ub_thelub, simp add: Y)
```
```    67       apply (simp add: lub_distribs Y DEFL [symmetric] cast_DEFL)
```
```    68       done
```
```    69   qed
```
```    70   (* FIXME: why does show ?thesis fail here? *)
```
```    71   show "ideal_completion below Rep_compact_basis (approximants::'a \<Rightarrow> _)" ..
```
```    72 qed
```
```    73
```
```    74 subsection {* Type combinators *}
```
```    75
```
```    76 definition
```
```    77   defl_fun1 ::
```
```    78     "(nat \<Rightarrow> 'a \<rightarrow> 'a) \<Rightarrow> ((udom \<rightarrow> udom) \<rightarrow> ('a \<rightarrow> 'a)) \<Rightarrow> (defl \<rightarrow> defl)"
```
```    79 where
```
```    80   "defl_fun1 approx f =
```
```    81     defl.basis_fun (\<lambda>a.
```
```    82       defl_principal (Abs_fin_defl
```
```    83         (udom_emb approx oo f\<cdot>(Rep_fin_defl a) oo udom_prj approx)))"
```
```    84
```
```    85 definition
```
```    86   defl_fun2 ::
```
```    87     "(nat \<Rightarrow> 'a \<rightarrow> 'a) \<Rightarrow> ((udom \<rightarrow> udom) \<rightarrow> (udom \<rightarrow> udom) \<rightarrow> ('a \<rightarrow> 'a))
```
```    88       \<Rightarrow> (defl \<rightarrow> defl \<rightarrow> defl)"
```
```    89 where
```
```    90   "defl_fun2 approx f =
```
```    91     defl.basis_fun (\<lambda>a.
```
```    92       defl.basis_fun (\<lambda>b.
```
```    93         defl_principal (Abs_fin_defl
```
```    94           (udom_emb approx oo
```
```    95             f\<cdot>(Rep_fin_defl a)\<cdot>(Rep_fin_defl b) oo udom_prj approx))))"
```
```    96
```
```    97 lemma cast_defl_fun1:
```
```    98   assumes approx: "approx_chain approx"
```
```    99   assumes f: "\<And>a. finite_deflation a \<Longrightarrow> finite_deflation (f\<cdot>a)"
```
```   100   shows "cast\<cdot>(defl_fun1 approx f\<cdot>A) = udom_emb approx oo f\<cdot>(cast\<cdot>A) oo udom_prj approx"
```
```   101 proof -
```
```   102   have 1: "\<And>a. finite_deflation
```
```   103         (udom_emb approx oo f\<cdot>(Rep_fin_defl a) oo udom_prj approx)"
```
```   104     apply (rule ep_pair.finite_deflation_e_d_p)
```
```   105     apply (rule approx_chain.ep_pair_udom [OF approx])
```
```   106     apply (rule f, rule finite_deflation_Rep_fin_defl)
```
```   107     done
```
```   108   show ?thesis
```
```   109     by (induct A rule: defl.principal_induct, simp)
```
```   110        (simp only: defl_fun1_def
```
```   111                    defl.basis_fun_principal
```
```   112                    defl.basis_fun_mono
```
```   113                    defl.principal_mono
```
```   114                    Abs_fin_defl_mono [OF 1 1]
```
```   115                    monofun_cfun below_refl
```
```   116                    Rep_fin_defl_mono
```
```   117                    cast_defl_principal
```
```   118                    Abs_fin_defl_inverse [unfolded mem_Collect_eq, OF 1])
```
```   119 qed
```
```   120
```
```   121 lemma cast_defl_fun2:
```
```   122   assumes approx: "approx_chain approx"
```
```   123   assumes f: "\<And>a b. finite_deflation a \<Longrightarrow> finite_deflation b \<Longrightarrow>
```
```   124                 finite_deflation (f\<cdot>a\<cdot>b)"
```
```   125   shows "cast\<cdot>(defl_fun2 approx f\<cdot>A\<cdot>B) =
```
```   126     udom_emb approx oo f\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj approx"
```
```   127 proof -
```
```   128   have 1: "\<And>a b. finite_deflation (udom_emb approx oo
```
```   129       f\<cdot>(Rep_fin_defl a)\<cdot>(Rep_fin_defl b) oo udom_prj approx)"
```
```   130     apply (rule ep_pair.finite_deflation_e_d_p)
```
```   131     apply (rule ep_pair_udom [OF approx])
```
```   132     apply (rule f, (rule finite_deflation_Rep_fin_defl)+)
```
```   133     done
```
```   134   show ?thesis
```
```   135     by (induct A B rule: defl.principal_induct2, simp, simp)
```
```   136        (simp only: defl_fun2_def
```
```   137                    defl.basis_fun_principal
```
```   138                    defl.basis_fun_mono
```
```   139                    defl.principal_mono
```
```   140                    Abs_fin_defl_mono [OF 1 1]
```
```   141                    monofun_cfun below_refl
```
```   142                    Rep_fin_defl_mono
```
```   143                    cast_defl_principal
```
```   144                    Abs_fin_defl_inverse [unfolded mem_Collect_eq, OF 1])
```
```   145 qed
```
```   146
```
```   147 subsection {* The universal domain is bifinite *}
```
```   148
```
```   149 instantiation udom :: bifinite
```
```   150 begin
```
```   151
```
```   152 definition [simp]:
```
```   153   "emb = (ID :: udom \<rightarrow> udom)"
```
```   154
```
```   155 definition [simp]:
```
```   156   "prj = (ID :: udom \<rightarrow> udom)"
```
```   157
```
```   158 definition
```
```   159   "defl (t::udom itself) = (\<Squnion>i. defl_principal (Abs_fin_defl (udom_approx i)))"
```
```   160
```
```   161 instance proof
```
```   162   show "ep_pair emb (prj :: udom \<rightarrow> udom)"
```
```   163     by (simp add: ep_pair.intro)
```
```   164 next
```
```   165   show "cast\<cdot>DEFL(udom) = emb oo (prj :: udom \<rightarrow> udom)"
```
```   166     unfolding defl_udom_def
```
```   167     apply (subst contlub_cfun_arg)
```
```   168     apply (rule chainI)
```
```   169     apply (rule defl.principal_mono)
```
```   170     apply (simp add: below_fin_defl_def)
```
```   171     apply (simp add: Abs_fin_defl_inverse finite_deflation_udom_approx)
```
```   172     apply (rule chainE)
```
```   173     apply (rule chain_udom_approx)
```
```   174     apply (subst cast_defl_principal)
```
```   175     apply (simp add: Abs_fin_defl_inverse finite_deflation_udom_approx)
```
```   176     done
```
```   177 qed
```
```   178
```
```   179 end
```
```   180
```
```   181 subsection {* Continuous function space is a bifinite domain *}
```
```   182
```
```   183 definition
```
```   184   cfun_approx :: "nat \<Rightarrow> (udom \<rightarrow> udom) \<rightarrow> (udom \<rightarrow> udom)"
```
```   185 where
```
```   186   "cfun_approx = (\<lambda>i. cfun_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```   187
```
```   188 lemma cfun_approx: "approx_chain cfun_approx"
```
```   189 proof (rule approx_chain.intro)
```
```   190   show "chain (\<lambda>i. cfun_approx i)"
```
```   191     unfolding cfun_approx_def by simp
```
```   192   show "(\<Squnion>i. cfun_approx i) = ID"
```
```   193     unfolding cfun_approx_def
```
```   194     by (simp add: lub_distribs cfun_map_ID)
```
```   195   show "\<And>i. finite_deflation (cfun_approx i)"
```
```   196     unfolding cfun_approx_def
```
```   197     by (intro finite_deflation_cfun_map finite_deflation_udom_approx)
```
```   198 qed
```
```   199
```
```   200 definition cfun_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   201 where "cfun_defl = defl_fun2 cfun_approx cfun_map"
```
```   202
```
```   203 lemma cast_cfun_defl:
```
```   204   "cast\<cdot>(cfun_defl\<cdot>A\<cdot>B) =
```
```   205     udom_emb cfun_approx oo cfun_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj cfun_approx"
```
```   206 unfolding cfun_defl_def
```
```   207 apply (rule cast_defl_fun2 [OF cfun_approx])
```
```   208 apply (erule (1) finite_deflation_cfun_map)
```
```   209 done
```
```   210
```
```   211 instantiation cfun :: (bifinite, bifinite) bifinite
```
```   212 begin
```
```   213
```
```   214 definition
```
```   215   "emb = udom_emb cfun_approx oo cfun_map\<cdot>prj\<cdot>emb"
```
```   216
```
```   217 definition
```
```   218   "prj = cfun_map\<cdot>emb\<cdot>prj oo udom_prj cfun_approx"
```
```   219
```
```   220 definition
```
```   221   "defl (t::('a \<rightarrow> 'b) itself) = cfun_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   222
```
```   223 instance proof
```
```   224   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<rightarrow> 'b)"
```
```   225     unfolding emb_cfun_def prj_cfun_def
```
```   226     using ep_pair_udom [OF cfun_approx]
```
```   227     by (intro ep_pair_comp ep_pair_cfun_map ep_pair_emb_prj)
```
```   228 next
```
```   229   show "cast\<cdot>DEFL('a \<rightarrow> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<rightarrow> 'b)"
```
```   230     unfolding emb_cfun_def prj_cfun_def defl_cfun_def cast_cfun_defl
```
```   231     by (simp add: cast_DEFL oo_def cfun_eq_iff cfun_map_map)
```
```   232 qed
```
```   233
```
```   234 end
```
```   235
```
```   236 lemma DEFL_cfun:
```
```   237   "DEFL('a::bifinite \<rightarrow> 'b::bifinite) = cfun_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   238 by (rule defl_cfun_def)
```
```   239
```
```   240 subsection {* Cartesian product is a bifinite domain *}
```
```   241
```
```   242 definition
```
```   243   prod_approx :: "nat \<Rightarrow> udom \<times> udom \<rightarrow> udom \<times> udom"
```
```   244 where
```
```   245   "prod_approx = (\<lambda>i. cprod_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```   246
```
```   247 lemma prod_approx: "approx_chain prod_approx"
```
```   248 proof (rule approx_chain.intro)
```
```   249   show "chain (\<lambda>i. prod_approx i)"
```
```   250     unfolding prod_approx_def by simp
```
```   251   show "(\<Squnion>i. prod_approx i) = ID"
```
```   252     unfolding prod_approx_def
```
```   253     by (simp add: lub_distribs cprod_map_ID)
```
```   254   show "\<And>i. finite_deflation (prod_approx i)"
```
```   255     unfolding prod_approx_def
```
```   256     by (intro finite_deflation_cprod_map finite_deflation_udom_approx)
```
```   257 qed
```
```   258
```
```   259 definition prod_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   260 where "prod_defl = defl_fun2 prod_approx cprod_map"
```
```   261
```
```   262 lemma cast_prod_defl:
```
```   263   "cast\<cdot>(prod_defl\<cdot>A\<cdot>B) = udom_emb prod_approx oo
```
```   264     cprod_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj prod_approx"
```
```   265 unfolding prod_defl_def
```
```   266 apply (rule cast_defl_fun2 [OF prod_approx])
```
```   267 apply (erule (1) finite_deflation_cprod_map)
```
```   268 done
```
```   269
```
```   270 instantiation prod :: (bifinite, bifinite) bifinite
```
```   271 begin
```
```   272
```
```   273 definition
```
```   274   "emb = udom_emb prod_approx oo cprod_map\<cdot>emb\<cdot>emb"
```
```   275
```
```   276 definition
```
```   277   "prj = cprod_map\<cdot>prj\<cdot>prj oo udom_prj prod_approx"
```
```   278
```
```   279 definition
```
```   280   "defl (t::('a \<times> 'b) itself) = prod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   281
```
```   282 instance proof
```
```   283   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<times> 'b)"
```
```   284     unfolding emb_prod_def prj_prod_def
```
```   285     using ep_pair_udom [OF prod_approx]
```
```   286     by (intro ep_pair_comp ep_pair_cprod_map ep_pair_emb_prj)
```
```   287 next
```
```   288   show "cast\<cdot>DEFL('a \<times> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<times> 'b)"
```
```   289     unfolding emb_prod_def prj_prod_def defl_prod_def cast_prod_defl
```
```   290     by (simp add: cast_DEFL oo_def cfun_eq_iff cprod_map_map)
```
```   291 qed
```
```   292
```
```   293 end
```
```   294
```
```   295 lemma DEFL_prod:
```
```   296   "DEFL('a::bifinite \<times> 'b::bifinite) = prod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   297 by (rule defl_prod_def)
```
```   298
```
```   299 subsection {* Strict product is a bifinite domain *}
```
```   300
```
```   301 definition
```
```   302   sprod_approx :: "nat \<Rightarrow> udom \<otimes> udom \<rightarrow> udom \<otimes> udom"
```
```   303 where
```
```   304   "sprod_approx = (\<lambda>i. sprod_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```   305
```
```   306 lemma sprod_approx: "approx_chain sprod_approx"
```
```   307 proof (rule approx_chain.intro)
```
```   308   show "chain (\<lambda>i. sprod_approx i)"
```
```   309     unfolding sprod_approx_def by simp
```
```   310   show "(\<Squnion>i. sprod_approx i) = ID"
```
```   311     unfolding sprod_approx_def
```
```   312     by (simp add: lub_distribs sprod_map_ID)
```
```   313   show "\<And>i. finite_deflation (sprod_approx i)"
```
```   314     unfolding sprod_approx_def
```
```   315     by (intro finite_deflation_sprod_map finite_deflation_udom_approx)
```
```   316 qed
```
```   317
```
```   318 definition sprod_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   319 where "sprod_defl = defl_fun2 sprod_approx sprod_map"
```
```   320
```
```   321 lemma cast_sprod_defl:
```
```   322   "cast\<cdot>(sprod_defl\<cdot>A\<cdot>B) =
```
```   323     udom_emb sprod_approx oo
```
```   324       sprod_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo
```
```   325         udom_prj sprod_approx"
```
```   326 unfolding sprod_defl_def
```
```   327 apply (rule cast_defl_fun2 [OF sprod_approx])
```
```   328 apply (erule (1) finite_deflation_sprod_map)
```
```   329 done
```
```   330
```
```   331 instantiation sprod :: (bifinite, bifinite) bifinite
```
```   332 begin
```
```   333
```
```   334 definition
```
```   335   "emb = udom_emb sprod_approx oo sprod_map\<cdot>emb\<cdot>emb"
```
```   336
```
```   337 definition
```
```   338   "prj = sprod_map\<cdot>prj\<cdot>prj oo udom_prj sprod_approx"
```
```   339
```
```   340 definition
```
```   341   "defl (t::('a \<otimes> 'b) itself) = sprod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   342
```
```   343 instance proof
```
```   344   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<otimes> 'b)"
```
```   345     unfolding emb_sprod_def prj_sprod_def
```
```   346     using ep_pair_udom [OF sprod_approx]
```
```   347     by (intro ep_pair_comp ep_pair_sprod_map ep_pair_emb_prj)
```
```   348 next
```
```   349   show "cast\<cdot>DEFL('a \<otimes> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<otimes> 'b)"
```
```   350     unfolding emb_sprod_def prj_sprod_def defl_sprod_def cast_sprod_defl
```
```   351     by (simp add: cast_DEFL oo_def cfun_eq_iff sprod_map_map)
```
```   352 qed
```
```   353
```
```   354 end
```
```   355
```
```   356 lemma DEFL_sprod:
```
```   357   "DEFL('a::bifinite \<otimes> 'b::bifinite) = sprod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   358 by (rule defl_sprod_def)
```
```   359
```
```   360 subsection {* Lifted cpo is a bifinite domain *}
```
```   361
```
```   362 definition u_approx :: "nat \<Rightarrow> udom\<^sub>\<bottom> \<rightarrow> udom\<^sub>\<bottom>"
```
```   363 where "u_approx = (\<lambda>i. u_map\<cdot>(udom_approx i))"
```
```   364
```
```   365 lemma u_approx: "approx_chain u_approx"
```
```   366 proof (rule approx_chain.intro)
```
```   367   show "chain (\<lambda>i. u_approx i)"
```
```   368     unfolding u_approx_def by simp
```
```   369   show "(\<Squnion>i. u_approx i) = ID"
```
```   370     unfolding u_approx_def
```
```   371     by (simp add: lub_distribs u_map_ID)
```
```   372   show "\<And>i. finite_deflation (u_approx i)"
```
```   373     unfolding u_approx_def
```
```   374     by (intro finite_deflation_u_map finite_deflation_udom_approx)
```
```   375 qed
```
```   376
```
```   377 definition u_defl :: "defl \<rightarrow> defl"
```
```   378 where "u_defl = defl_fun1 u_approx u_map"
```
```   379
```
```   380 lemma cast_u_defl:
```
```   381   "cast\<cdot>(u_defl\<cdot>A) =
```
```   382     udom_emb u_approx oo u_map\<cdot>(cast\<cdot>A) oo udom_prj u_approx"
```
```   383 unfolding u_defl_def
```
```   384 apply (rule cast_defl_fun1 [OF u_approx])
```
```   385 apply (erule finite_deflation_u_map)
```
```   386 done
```
```   387
```
```   388 instantiation u :: (bifinite) bifinite
```
```   389 begin
```
```   390
```
```   391 definition
```
```   392   "emb = udom_emb u_approx oo u_map\<cdot>emb"
```
```   393
```
```   394 definition
```
```   395   "prj = u_map\<cdot>prj oo udom_prj u_approx"
```
```   396
```
```   397 definition
```
```   398   "defl (t::'a u itself) = u_defl\<cdot>DEFL('a)"
```
```   399
```
```   400 instance proof
```
```   401   show "ep_pair emb (prj :: udom \<rightarrow> 'a u)"
```
```   402     unfolding emb_u_def prj_u_def
```
```   403     using ep_pair_udom [OF u_approx]
```
```   404     by (intro ep_pair_comp ep_pair_u_map ep_pair_emb_prj)
```
```   405 next
```
```   406   show "cast\<cdot>DEFL('a u) = emb oo (prj :: udom \<rightarrow> 'a u)"
```
```   407     unfolding emb_u_def prj_u_def defl_u_def cast_u_defl
```
```   408     by (simp add: cast_DEFL oo_def cfun_eq_iff u_map_map)
```
```   409 qed
```
```   410
```
```   411 end
```
```   412
```
```   413 lemma DEFL_u: "DEFL('a::bifinite u) = u_defl\<cdot>DEFL('a)"
```
```   414 by (rule defl_u_def)
```
```   415
```
```   416 subsection {* Lifted countable types are bifinite domains *}
```
```   417
```
```   418 definition
```
```   419   lift_approx :: "nat \<Rightarrow> 'a::countable lift \<rightarrow> 'a lift"
```
```   420 where
```
```   421   "lift_approx = (\<lambda>i. FLIFT x. if to_nat x < i then Def x else \<bottom>)"
```
```   422
```
```   423 lemma chain_lift_approx [simp]: "chain lift_approx"
```
```   424   unfolding lift_approx_def
```
```   425   by (rule chainI, simp add: FLIFT_mono)
```
```   426
```
```   427 lemma lub_lift_approx [simp]: "(\<Squnion>i. lift_approx i) = ID"
```
```   428 apply (rule cfun_eqI)
```
```   429 apply (simp add: contlub_cfun_fun)
```
```   430 apply (simp add: lift_approx_def)
```
```   431 apply (case_tac x, simp)
```
```   432 apply (rule thelubI)
```
```   433 apply (rule is_lubI)
```
```   434 apply (rule ub_rangeI, simp)
```
```   435 apply (drule ub_rangeD)
```
```   436 apply (erule rev_below_trans)
```
```   437 apply simp
```
```   438 apply (rule lessI)
```
```   439 done
```
```   440
```
```   441 lemma finite_deflation_lift_approx: "finite_deflation (lift_approx i)"
```
```   442 proof
```
```   443   fix x
```
```   444   show "lift_approx i\<cdot>x \<sqsubseteq> x"
```
```   445     unfolding lift_approx_def
```
```   446     by (cases x, simp, simp)
```
```   447   show "lift_approx i\<cdot>(lift_approx i\<cdot>x) = lift_approx i\<cdot>x"
```
```   448     unfolding lift_approx_def
```
```   449     by (cases x, simp, simp)
```
```   450   show "finite {x::'a lift. lift_approx i\<cdot>x = x}"
```
```   451   proof (rule finite_subset)
```
```   452     let ?S = "insert (\<bottom>::'a lift) (Def ` to_nat -` {..<i})"
```
```   453     show "{x::'a lift. lift_approx i\<cdot>x = x} \<subseteq> ?S"
```
```   454       unfolding lift_approx_def
```
```   455       by (rule subsetI, case_tac x, simp, simp split: split_if_asm)
```
```   456     show "finite ?S"
```
```   457       by (simp add: finite_vimageI)
```
```   458   qed
```
```   459 qed
```
```   460
```
```   461 lemma lift_approx: "approx_chain lift_approx"
```
```   462 using chain_lift_approx lub_lift_approx finite_deflation_lift_approx
```
```   463 by (rule approx_chain.intro)
```
```   464
```
```   465 instantiation lift :: (countable) bifinite
```
```   466 begin
```
```   467
```
```   468 definition
```
```   469   "emb = udom_emb lift_approx"
```
```   470
```
```   471 definition
```
```   472   "prj = udom_prj lift_approx"
```
```   473
```
```   474 definition
```
```   475   "defl (t::'a lift itself) =
```
```   476     (\<Squnion>i. defl_principal (Abs_fin_defl (emb oo lift_approx i oo prj)))"
```
```   477
```
```   478 instance proof
```
```   479   show ep: "ep_pair emb (prj :: udom \<rightarrow> 'a lift)"
```
```   480     unfolding emb_lift_def prj_lift_def
```
```   481     by (rule ep_pair_udom [OF lift_approx])
```
```   482   show "cast\<cdot>DEFL('a lift) = emb oo (prj :: udom \<rightarrow> 'a lift)"
```
```   483     unfolding defl_lift_def
```
```   484     apply (subst contlub_cfun_arg)
```
```   485     apply (rule chainI)
```
```   486     apply (rule defl.principal_mono)
```
```   487     apply (simp add: below_fin_defl_def)
```
```   488     apply (simp add: Abs_fin_defl_inverse finite_deflation_lift_approx
```
```   489                      ep_pair.finite_deflation_e_d_p [OF ep])
```
```   490     apply (intro monofun_cfun below_refl)
```
```   491     apply (rule chainE)
```
```   492     apply (rule chain_lift_approx)
```
```   493     apply (subst cast_defl_principal)
```
```   494     apply (simp add: Abs_fin_defl_inverse finite_deflation_lift_approx
```
```   495                      ep_pair.finite_deflation_e_d_p [OF ep] lub_distribs)
```
```   496     done
```
```   497 qed
```
```   498
```
```   499 end
```
```   500
```
```   501 subsection {* Strict sum is a bifinite domain *}
```
```   502
```
```   503 definition
```
```   504   ssum_approx :: "nat \<Rightarrow> udom \<oplus> udom \<rightarrow> udom \<oplus> udom"
```
```   505 where
```
```   506   "ssum_approx = (\<lambda>i. ssum_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))"
```
```   507
```
```   508 lemma ssum_approx: "approx_chain ssum_approx"
```
```   509 proof (rule approx_chain.intro)
```
```   510   show "chain (\<lambda>i. ssum_approx i)"
```
```   511     unfolding ssum_approx_def by simp
```
```   512   show "(\<Squnion>i. ssum_approx i) = ID"
```
```   513     unfolding ssum_approx_def
```
```   514     by (simp add: lub_distribs ssum_map_ID)
```
```   515   show "\<And>i. finite_deflation (ssum_approx i)"
```
```   516     unfolding ssum_approx_def
```
```   517     by (intro finite_deflation_ssum_map finite_deflation_udom_approx)
```
```   518 qed
```
```   519
```
```   520 definition ssum_defl :: "defl \<rightarrow> defl \<rightarrow> defl"
```
```   521 where "ssum_defl = defl_fun2 ssum_approx ssum_map"
```
```   522
```
```   523 lemma cast_ssum_defl:
```
```   524   "cast\<cdot>(ssum_defl\<cdot>A\<cdot>B) =
```
```   525     udom_emb ssum_approx oo ssum_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj ssum_approx"
```
```   526 unfolding ssum_defl_def
```
```   527 apply (rule cast_defl_fun2 [OF ssum_approx])
```
```   528 apply (erule (1) finite_deflation_ssum_map)
```
```   529 done
```
```   530
```
```   531 instantiation ssum :: (bifinite, bifinite) bifinite
```
```   532 begin
```
```   533
```
```   534 definition
```
```   535   "emb = udom_emb ssum_approx oo ssum_map\<cdot>emb\<cdot>emb"
```
```   536
```
```   537 definition
```
```   538   "prj = ssum_map\<cdot>prj\<cdot>prj oo udom_prj ssum_approx"
```
```   539
```
```   540 definition
```
```   541   "defl (t::('a \<oplus> 'b) itself) = ssum_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   542
```
```   543 instance proof
```
```   544   show "ep_pair emb (prj :: udom \<rightarrow> 'a \<oplus> 'b)"
```
```   545     unfolding emb_ssum_def prj_ssum_def
```
```   546     using ep_pair_udom [OF ssum_approx]
```
```   547     by (intro ep_pair_comp ep_pair_ssum_map ep_pair_emb_prj)
```
```   548 next
```
```   549   show "cast\<cdot>DEFL('a \<oplus> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<oplus> 'b)"
```
```   550     unfolding emb_ssum_def prj_ssum_def defl_ssum_def cast_ssum_defl
```
```   551     by (simp add: cast_DEFL oo_def cfun_eq_iff ssum_map_map)
```
```   552 qed
```
```   553
```
```   554 end
```
```   555
```
```   556 lemma DEFL_ssum:
```
```   557   "DEFL('a::bifinite \<oplus> 'b::bifinite) = ssum_defl\<cdot>DEFL('a)\<cdot>DEFL('b)"
```
```   558 by (rule defl_ssum_def)
```
```   559
```
```   560 end
```