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