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