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