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