src/HOLCF/Pcpo.thy
author huffman
Wed Nov 10 17:56:08 2010 -0800 (2010-11-10)
changeset 40502 8e92772bc0e8
parent 40500 ee9c8d36318e
child 40771 1c6f7d4b110e
permissions -rw-r--r--
move map functions to new theory file Map_Functions; add theory file Plain_HOLCF
slotosch@2640
     1
(*  Title:      HOLCF/Pcpo.thy
slotosch@2640
     2
    Author:     Franz Regensburger
slotosch@2640
     3
*)
huffman@15576
     4
huffman@15576
     5
header {* Classes cpo and pcpo *}
huffman@15576
     6
huffman@15577
     7
theory Pcpo
huffman@15577
     8
imports Porder
huffman@15577
     9
begin
nipkow@243
    10
huffman@15588
    11
subsection {* Complete partial orders *}
huffman@15588
    12
huffman@15588
    13
text {* The class cpo of chain complete partial orders *}
huffman@15588
    14
haftmann@29614
    15
class cpo = po +
haftmann@31071
    16
  assumes cpo: "chain S \<Longrightarrow> \<exists>x. range S <<| x"
haftmann@31071
    17
begin
oheimb@2394
    18
huffman@15588
    19
text {* in cpo's everthing equal to THE lub has lub properties for every chain *}
huffman@15563
    20
haftmann@31071
    21
lemma cpo_lubI: "chain S \<Longrightarrow> range S <<| (\<Squnion>i. S i)"
haftmann@31071
    22
  by (fast dest: cpo elim: lubI)
huffman@26026
    23
haftmann@31071
    24
lemma thelubE: "\<lbrakk>chain S; (\<Squnion>i. S i) = l\<rbrakk> \<Longrightarrow> range S <<| l"
haftmann@31071
    25
  by (blast dest: cpo intro: lubI)
huffman@15563
    26
huffman@15588
    27
text {* Properties of the lub *}
huffman@15563
    28
haftmann@31071
    29
lemma is_ub_thelub: "chain S \<Longrightarrow> S x \<sqsubseteq> (\<Squnion>i. S i)"
haftmann@31071
    30
  by (blast dest: cpo intro: lubI [THEN is_ub_lub])
huffman@15563
    31
huffman@16626
    32
lemma is_lub_thelub:
haftmann@31071
    33
  "\<lbrakk>chain S; range S <| x\<rbrakk> \<Longrightarrow> (\<Squnion>i. S i) \<sqsubseteq> x"
haftmann@31071
    34
  by (blast dest: cpo intro: lubI [THEN is_lub_lub])
huffman@15563
    35
huffman@39969
    36
lemma lub_below_iff: "chain S \<Longrightarrow> (\<Squnion>i. S i) \<sqsubseteq> x \<longleftrightarrow> (\<forall>i. S i \<sqsubseteq> x)"
huffman@39969
    37
  by (simp add: is_lub_below_iff [OF cpo_lubI] is_ub_def)
huffman@39969
    38
huffman@40500
    39
lemma lub_below: "\<lbrakk>chain S; \<And>i. S i \<sqsubseteq> x\<rbrakk> \<Longrightarrow> (\<Squnion>i. S i) \<sqsubseteq> x"
huffman@40500
    40
  by (simp add: lub_below_iff)
huffman@40500
    41
huffman@40500
    42
lemma below_lub: "\<lbrakk>chain S; x \<sqsubseteq> S i\<rbrakk> \<Longrightarrow> x \<sqsubseteq> (\<Squnion>i. S i)"
huffman@40500
    43
  by (erule below_trans, erule is_ub_thelub)
huffman@40500
    44
huffman@16626
    45
lemma lub_range_mono:
haftmann@31071
    46
  "\<lbrakk>range X \<subseteq> range Y; chain Y; chain X\<rbrakk>
huffman@16626
    47
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
huffman@40500
    48
apply (erule lub_below)
huffman@16626
    49
apply (subgoal_tac "\<exists>j. X i = Y j")
huffman@15563
    50
apply  clarsimp
huffman@15563
    51
apply  (erule is_ub_thelub)
huffman@15563
    52
apply auto
huffman@15563
    53
done
huffman@15563
    54
huffman@16626
    55
lemma lub_range_shift:
haftmann@31071
    56
  "chain Y \<Longrightarrow> (\<Squnion>i. Y (i + j)) = (\<Squnion>i. Y i)"
huffman@31076
    57
apply (rule below_antisym)
huffman@15563
    58
apply (rule lub_range_mono)
huffman@15563
    59
apply    fast
huffman@15563
    60
apply   assumption
huffman@15563
    61
apply (erule chain_shift)
huffman@40500
    62
apply (rule lub_below)
huffman@15563
    63
apply assumption
huffman@40500
    64
apply (rule_tac i="i" in below_lub)
huffman@40500
    65
apply (erule chain_shift)
huffman@25922
    66
apply (erule chain_mono)
huffman@15563
    67
apply (rule le_add1)
huffman@15563
    68
done
huffman@15563
    69
huffman@16626
    70
lemma maxinch_is_thelub:
haftmann@31071
    71
  "chain Y \<Longrightarrow> max_in_chain i Y = ((\<Squnion>i. Y i) = Y i)"
huffman@15563
    72
apply (rule iffI)
huffman@15563
    73
apply (fast intro!: thelubI lub_finch1)
huffman@15563
    74
apply (unfold max_in_chain_def)
huffman@31076
    75
apply (safe intro!: below_antisym)
huffman@25922
    76
apply (fast elim!: chain_mono)
huffman@15563
    77
apply (drule sym)
huffman@15563
    78
apply (force elim!: is_ub_thelub)
huffman@15563
    79
done
huffman@15563
    80
huffman@16626
    81
text {* the @{text "\<sqsubseteq>"} relation between two chains is preserved by their lubs *}
huffman@15563
    82
huffman@16626
    83
lemma lub_mono:
haftmann@31071
    84
  "\<lbrakk>chain X; chain Y; \<And>i. X i \<sqsubseteq> Y i\<rbrakk> 
huffman@16626
    85
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
huffman@40500
    86
by (fast elim: lub_below below_lub)
huffman@15563
    87
huffman@15588
    88
text {* the = relation between two chains is preserved by their lubs *}
huffman@15563
    89
huffman@35492
    90
lemma lub_eq:
huffman@35492
    91
  "(\<And>i. X i = Y i) \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
huffman@35492
    92
  by simp
huffman@35492
    93
huffman@16203
    94
lemma ch2ch_lub:
huffman@16203
    95
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
huffman@16203
    96
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
huffman@16203
    97
  shows "chain (\<lambda>i. \<Squnion>j. Y i j)"
huffman@16203
    98
apply (rule chainI)
huffman@25923
    99
apply (rule lub_mono [OF 2 2])
huffman@16203
   100
apply (rule chainE [OF 1])
huffman@16203
   101
done
huffman@16203
   102
huffman@16201
   103
lemma diag_lub:
huffman@16201
   104
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
huffman@16201
   105
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
huffman@16201
   106
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>i. Y i i)"
huffman@31076
   107
proof (rule below_antisym)
huffman@16201
   108
  have 3: "chain (\<lambda>i. Y i i)"
huffman@16201
   109
    apply (rule chainI)
huffman@31076
   110
    apply (rule below_trans)
huffman@16201
   111
    apply (rule chainE [OF 1])
huffman@16201
   112
    apply (rule chainE [OF 2])
huffman@16201
   113
    done
huffman@16201
   114
  have 4: "chain (\<lambda>i. \<Squnion>j. Y i j)"
huffman@16203
   115
    by (rule ch2ch_lub [OF 1 2])
huffman@16201
   116
  show "(\<Squnion>i. \<Squnion>j. Y i j) \<sqsubseteq> (\<Squnion>i. Y i i)"
huffman@40500
   117
    apply (rule lub_below [OF 4])
huffman@40500
   118
    apply (rule lub_below [OF 2])
huffman@40500
   119
    apply (rule below_lub [OF 3])
huffman@31076
   120
    apply (rule below_trans)
huffman@25922
   121
    apply (rule chain_mono [OF 1 le_maxI1])
huffman@25922
   122
    apply (rule chain_mono [OF 2 le_maxI2])
huffman@16201
   123
    done
huffman@16201
   124
  show "(\<Squnion>i. Y i i) \<sqsubseteq> (\<Squnion>i. \<Squnion>j. Y i j)"
huffman@25923
   125
    apply (rule lub_mono [OF 3 4])
huffman@16201
   126
    apply (rule is_ub_thelub [OF 2])
huffman@16201
   127
    done
huffman@16201
   128
qed
huffman@16201
   129
huffman@16201
   130
lemma ex_lub:
huffman@16201
   131
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
huffman@16201
   132
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
huffman@16201
   133
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>j. \<Squnion>i. Y i j)"
haftmann@31071
   134
  by (simp add: diag_lub 1 2)
huffman@16201
   135
haftmann@31071
   136
end
huffman@16201
   137
huffman@15588
   138
subsection {* Pointed cpos *}
huffman@15588
   139
huffman@15588
   140
text {* The class pcpo of pointed cpos *}
huffman@15588
   141
haftmann@29614
   142
class pcpo = cpo +
haftmann@29614
   143
  assumes least: "\<exists>x. \<forall>y. x \<sqsubseteq> y"
haftmann@31071
   144
begin
huffman@25723
   145
haftmann@31071
   146
definition UU :: 'a where
huffman@25723
   147
  "UU = (THE x. \<forall>y. x \<sqsubseteq> y)"
huffman@25723
   148
huffman@25723
   149
notation (xsymbols)
huffman@25723
   150
  UU  ("\<bottom>")
huffman@25723
   151
huffman@25723
   152
text {* derive the old rule minimal *}
huffman@25723
   153
 
huffman@25723
   154
lemma UU_least: "\<forall>z. \<bottom> \<sqsubseteq> z"
huffman@25723
   155
apply (unfold UU_def)
huffman@25723
   156
apply (rule theI')
huffman@25723
   157
apply (rule ex_ex1I)
huffman@25723
   158
apply (rule least)
huffman@31076
   159
apply (blast intro: below_antisym)
huffman@25723
   160
done
huffman@25723
   161
huffman@25723
   162
lemma minimal [iff]: "\<bottom> \<sqsubseteq> x"
huffman@25723
   163
by (rule UU_least [THEN spec])
huffman@25723
   164
haftmann@31071
   165
end
haftmann@31071
   166
huffman@31024
   167
text {* Simproc to rewrite @{term "\<bottom> = x"} to @{term "x = \<bottom>"}. *}
huffman@16739
   168
huffman@31024
   169
setup {*
wenzelm@33523
   170
  Reorient_Proc.add
huffman@31024
   171
    (fn Const(@{const_name UU}, _) => true | _ => false)
huffman@31024
   172
*}
huffman@25723
   173
wenzelm@33523
   174
simproc_setup reorient_bottom ("\<bottom> = x") = Reorient_Proc.proc
huffman@25723
   175
haftmann@31071
   176
context pcpo
haftmann@31071
   177
begin
haftmann@31071
   178
huffman@25723
   179
text {* useful lemmas about @{term \<bottom>} *}
huffman@25723
   180
huffman@31076
   181
lemma below_UU_iff [simp]: "(x \<sqsubseteq> \<bottom>) = (x = \<bottom>)"
huffman@25723
   182
by (simp add: po_eq_conv)
huffman@25723
   183
huffman@25723
   184
lemma eq_UU_iff: "(x = \<bottom>) = (x \<sqsubseteq> \<bottom>)"
huffman@25723
   185
by simp
huffman@25723
   186
huffman@25723
   187
lemma UU_I: "x \<sqsubseteq> \<bottom> \<Longrightarrow> x = \<bottom>"
huffman@25723
   188
by (subst eq_UU_iff)
huffman@25723
   189
huffman@40045
   190
lemma lub_eq_bottom_iff: "chain Y \<Longrightarrow> (\<Squnion>i. Y i) = \<bottom> \<longleftrightarrow> (\<forall>i. Y i = \<bottom>)"
huffman@40045
   191
by (simp only: eq_UU_iff lub_below_iff)
huffman@40045
   192
huffman@25723
   193
lemma chain_UU_I: "\<lbrakk>chain Y; (\<Squnion>i. Y i) = \<bottom>\<rbrakk> \<Longrightarrow> \<forall>i. Y i = \<bottom>"
huffman@40045
   194
by (simp add: lub_eq_bottom_iff)
huffman@15563
   195
huffman@16626
   196
lemma chain_UU_I_inverse: "\<forall>i::nat. Y i = \<bottom> \<Longrightarrow> (\<Squnion>i. Y i) = \<bottom>"
huffman@40045
   197
by simp
huffman@15563
   198
huffman@16626
   199
lemma chain_UU_I_inverse2: "(\<Squnion>i. Y i) \<noteq> \<bottom> \<Longrightarrow> \<exists>i::nat. Y i \<noteq> \<bottom>"
haftmann@31071
   200
  by (blast intro: chain_UU_I_inverse)
huffman@15563
   201
huffman@16626
   202
lemma notUU_I: "\<lbrakk>x \<sqsubseteq> y; x \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> y \<noteq> \<bottom>"
haftmann@31071
   203
  by (blast intro: UU_I)
huffman@15563
   204
haftmann@31071
   205
end
huffman@15588
   206
huffman@15588
   207
subsection {* Chain-finite and flat cpos *}
huffman@15563
   208
huffman@15588
   209
text {* further useful classes for HOLCF domains *}
huffman@15588
   210
haftmann@31071
   211
class chfin = po +
haftmann@31071
   212
  assumes chfin: "chain Y \<Longrightarrow> \<exists>n. max_in_chain n Y"
haftmann@31071
   213
begin
huffman@25814
   214
haftmann@31071
   215
subclass cpo
haftmann@31071
   216
apply default
haftmann@31071
   217
apply (frule chfin)
haftmann@31071
   218
apply (blast intro: lub_finch1)
haftmann@31071
   219
done
huffman@15563
   220
haftmann@31071
   221
lemma chfin2finch: "chain Y \<Longrightarrow> finite_chain Y"
haftmann@31071
   222
  by (simp add: chfin finite_chain_def)
haftmann@31071
   223
haftmann@31071
   224
end
huffman@15588
   225
haftmann@31071
   226
class flat = pcpo +
haftmann@31071
   227
  assumes ax_flat: "x \<sqsubseteq> y \<Longrightarrow> x = \<bottom> \<or> x = y"
haftmann@31071
   228
begin
huffman@15640
   229
haftmann@31071
   230
subclass chfin
haftmann@31071
   231
apply default
huffman@15563
   232
apply (unfold max_in_chain_def)
huffman@16626
   233
apply (case_tac "\<forall>i. Y i = \<bottom>")
huffman@15588
   234
apply simp
huffman@15563
   235
apply simp
huffman@15563
   236
apply (erule exE)
huffman@16626
   237
apply (rule_tac x="i" in exI)
huffman@15588
   238
apply clarify
huffman@25922
   239
apply (blast dest: chain_mono ax_flat)
huffman@15563
   240
done
huffman@15563
   241
huffman@31076
   242
lemma flat_below_iff:
huffman@25826
   243
  shows "(x \<sqsubseteq> y) = (x = \<bottom> \<or> x = y)"
haftmann@31071
   244
  by (safe dest!: ax_flat)
huffman@25826
   245
haftmann@31071
   246
lemma flat_eq: "a \<noteq> \<bottom> \<Longrightarrow> a \<sqsubseteq> b = (a = b)"
haftmann@31071
   247
  by (safe dest!: ax_flat)
huffman@15563
   248
haftmann@31071
   249
end
huffman@15563
   250
huffman@40091
   251
subsection {* Discrete cpos *}
huffman@26023
   252
huffman@31076
   253
class discrete_cpo = below +
haftmann@29614
   254
  assumes discrete_cpo [simp]: "x \<sqsubseteq> y \<longleftrightarrow> x = y"
haftmann@31071
   255
begin
huffman@26023
   256
haftmann@31071
   257
subclass po
haftmann@29614
   258
proof qed simp_all
huffman@26023
   259
huffman@26023
   260
text {* In a discrete cpo, every chain is constant *}
huffman@26023
   261
huffman@26023
   262
lemma discrete_chain_const:
haftmann@31071
   263
  assumes S: "chain S"
huffman@26023
   264
  shows "\<exists>x. S = (\<lambda>i. x)"
huffman@26023
   265
proof (intro exI ext)
huffman@26023
   266
  fix i :: nat
huffman@26023
   267
  have "S 0 \<sqsubseteq> S i" using S le0 by (rule chain_mono)
huffman@26023
   268
  hence "S 0 = S i" by simp
huffman@26023
   269
  thus "S i = S 0" by (rule sym)
huffman@26023
   270
qed
huffman@26023
   271
huffman@40091
   272
subclass chfin
huffman@26023
   273
proof
huffman@26023
   274
  fix S :: "nat \<Rightarrow> 'a"
huffman@26023
   275
  assume S: "chain S"
huffman@40091
   276
  hence "\<exists>x. S = (\<lambda>i. x)" by (rule discrete_chain_const)
huffman@40091
   277
  hence "max_in_chain 0 S"
huffman@40091
   278
    unfolding max_in_chain_def by auto
huffman@40091
   279
  thus "\<exists>i. max_in_chain i S" ..
huffman@26023
   280
qed
huffman@26023
   281
haftmann@31071
   282
end
huffman@15576
   283
huffman@16626
   284
end