src/HOLCF/Pcpo.thy
author huffman
Tue Oct 12 06:20:05 2010 -0700 (2010-10-12)
changeset 40006 116e94f9543b
parent 39969 0b8e19f588a4
child 40045 e0f372e18f3e
permissions -rw-r--r--
remove unneeded lemmas from Fun_Cpo.thy
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@16626
    39
lemma lub_range_mono:
haftmann@31071
    40
  "\<lbrakk>range X \<subseteq> range Y; chain Y; chain X\<rbrakk>
huffman@16626
    41
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
huffman@15563
    42
apply (erule is_lub_thelub)
huffman@15563
    43
apply (rule ub_rangeI)
huffman@16626
    44
apply (subgoal_tac "\<exists>j. X i = Y j")
huffman@15563
    45
apply  clarsimp
huffman@15563
    46
apply  (erule is_ub_thelub)
huffman@15563
    47
apply auto
huffman@15563
    48
done
huffman@15563
    49
huffman@16626
    50
lemma lub_range_shift:
haftmann@31071
    51
  "chain Y \<Longrightarrow> (\<Squnion>i. Y (i + j)) = (\<Squnion>i. Y i)"
huffman@31076
    52
apply (rule below_antisym)
huffman@15563
    53
apply (rule lub_range_mono)
huffman@15563
    54
apply    fast
huffman@15563
    55
apply   assumption
huffman@15563
    56
apply (erule chain_shift)
huffman@15563
    57
apply (rule is_lub_thelub)
huffman@15563
    58
apply assumption
huffman@15563
    59
apply (rule ub_rangeI)
huffman@31076
    60
apply (rule_tac y="Y (i + j)" in below_trans)
huffman@25922
    61
apply (erule chain_mono)
huffman@15563
    62
apply (rule le_add1)
huffman@17813
    63
apply (rule is_ub_thelub)
huffman@17813
    64
apply (erule chain_shift)
huffman@15563
    65
done
huffman@15563
    66
huffman@16626
    67
lemma maxinch_is_thelub:
haftmann@31071
    68
  "chain Y \<Longrightarrow> max_in_chain i Y = ((\<Squnion>i. Y i) = Y i)"
huffman@15563
    69
apply (rule iffI)
huffman@15563
    70
apply (fast intro!: thelubI lub_finch1)
huffman@15563
    71
apply (unfold max_in_chain_def)
huffman@31076
    72
apply (safe intro!: below_antisym)
huffman@25922
    73
apply (fast elim!: chain_mono)
huffman@15563
    74
apply (drule sym)
huffman@15563
    75
apply (force elim!: is_ub_thelub)
huffman@15563
    76
done
huffman@15563
    77
huffman@16626
    78
text {* the @{text "\<sqsubseteq>"} relation between two chains is preserved by their lubs *}
huffman@15563
    79
huffman@16626
    80
lemma lub_mono:
haftmann@31071
    81
  "\<lbrakk>chain X; chain Y; \<And>i. X i \<sqsubseteq> Y i\<rbrakk> 
huffman@16626
    82
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
huffman@15563
    83
apply (erule is_lub_thelub)
huffman@15563
    84
apply (rule ub_rangeI)
huffman@31076
    85
apply (rule below_trans)
huffman@25923
    86
apply (erule meta_spec)
huffman@15563
    87
apply (erule is_ub_thelub)
huffman@15563
    88
done
huffman@15563
    89
huffman@15588
    90
text {* the = relation between two chains is preserved by their lubs *}
huffman@15563
    91
huffman@16626
    92
lemma lub_equal:
haftmann@31071
    93
  "\<lbrakk>chain X; chain Y; \<forall>k. X k = Y k\<rbrakk>
huffman@16626
    94
    \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
nipkow@39302
    95
  by (simp only: fun_eq_iff [symmetric])
huffman@15563
    96
huffman@35492
    97
lemma lub_eq:
huffman@35492
    98
  "(\<And>i. X i = Y i) \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
huffman@35492
    99
  by simp
huffman@35492
   100
huffman@15588
   101
text {* more results about mono and = of lubs of chains *}
slotosch@3326
   102
huffman@16626
   103
lemma lub_mono2:
haftmann@31071
   104
  "\<lbrakk>\<exists>j. \<forall>i>j. X i = Y i; chain X; chain Y\<rbrakk>
huffman@16626
   105
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
huffman@15563
   106
apply (erule exE)
huffman@17813
   107
apply (subgoal_tac "(\<Squnion>i. X (i + Suc j)) \<sqsubseteq> (\<Squnion>i. Y (i + Suc j))")
huffman@17813
   108
apply (thin_tac "\<forall>i>j. X i = Y i")
huffman@17813
   109
apply (simp only: lub_range_shift)
huffman@16626
   110
apply simp
huffman@15563
   111
done
huffman@15563
   112
huffman@16626
   113
lemma lub_equal2:
haftmann@31071
   114
  "\<lbrakk>\<exists>j. \<forall>i>j. X i = Y i; chain X; chain Y\<rbrakk>
huffman@16626
   115
    \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
huffman@31076
   116
  by (blast intro: below_antisym lub_mono2 sym)
huffman@15563
   117
huffman@16626
   118
lemma lub_mono3:
haftmann@31071
   119
  "\<lbrakk>chain Y; chain X; \<forall>i. \<exists>j. Y i \<sqsubseteq> X j\<rbrakk>
huffman@16626
   120
    \<Longrightarrow> (\<Squnion>i. Y i) \<sqsubseteq> (\<Squnion>i. X i)"
huffman@17813
   121
apply (erule is_lub_thelub)
huffman@15563
   122
apply (rule ub_rangeI)
huffman@15563
   123
apply (erule allE)
huffman@15563
   124
apply (erule exE)
huffman@31076
   125
apply (erule below_trans)
huffman@16626
   126
apply (erule is_ub_thelub)
huffman@15563
   127
done
huffman@15563
   128
huffman@16203
   129
lemma ch2ch_lub:
huffman@16203
   130
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
huffman@16203
   131
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
huffman@16203
   132
  shows "chain (\<lambda>i. \<Squnion>j. Y i j)"
huffman@16203
   133
apply (rule chainI)
huffman@25923
   134
apply (rule lub_mono [OF 2 2])
huffman@16203
   135
apply (rule chainE [OF 1])
huffman@16203
   136
done
huffman@16203
   137
huffman@16201
   138
lemma diag_lub:
huffman@16201
   139
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
huffman@16201
   140
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
huffman@16201
   141
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>i. Y i i)"
huffman@31076
   142
proof (rule below_antisym)
huffman@16201
   143
  have 3: "chain (\<lambda>i. Y i i)"
huffman@16201
   144
    apply (rule chainI)
huffman@31076
   145
    apply (rule below_trans)
huffman@16201
   146
    apply (rule chainE [OF 1])
huffman@16201
   147
    apply (rule chainE [OF 2])
huffman@16201
   148
    done
huffman@16201
   149
  have 4: "chain (\<lambda>i. \<Squnion>j. Y i j)"
huffman@16203
   150
    by (rule ch2ch_lub [OF 1 2])
huffman@16201
   151
  show "(\<Squnion>i. \<Squnion>j. Y i j) \<sqsubseteq> (\<Squnion>i. Y i i)"
huffman@16201
   152
    apply (rule is_lub_thelub [OF 4])
huffman@16201
   153
    apply (rule ub_rangeI)
huffman@16203
   154
    apply (rule lub_mono3 [rule_format, OF 2 3])
huffman@16201
   155
    apply (rule exI)
huffman@31076
   156
    apply (rule below_trans)
huffman@25922
   157
    apply (rule chain_mono [OF 1 le_maxI1])
huffman@25922
   158
    apply (rule chain_mono [OF 2 le_maxI2])
huffman@16201
   159
    done
huffman@16201
   160
  show "(\<Squnion>i. Y i i) \<sqsubseteq> (\<Squnion>i. \<Squnion>j. Y i j)"
huffman@25923
   161
    apply (rule lub_mono [OF 3 4])
huffman@16201
   162
    apply (rule is_ub_thelub [OF 2])
huffman@16201
   163
    done
huffman@16201
   164
qed
huffman@16201
   165
huffman@16201
   166
lemma ex_lub:
huffman@16201
   167
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
huffman@16201
   168
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
huffman@16201
   169
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>j. \<Squnion>i. Y i j)"
haftmann@31071
   170
  by (simp add: diag_lub 1 2)
huffman@16201
   171
haftmann@31071
   172
end
huffman@16201
   173
huffman@15588
   174
subsection {* Pointed cpos *}
huffman@15588
   175
huffman@15588
   176
text {* The class pcpo of pointed cpos *}
huffman@15588
   177
haftmann@29614
   178
class pcpo = cpo +
haftmann@29614
   179
  assumes least: "\<exists>x. \<forall>y. x \<sqsubseteq> y"
haftmann@31071
   180
begin
huffman@25723
   181
haftmann@31071
   182
definition UU :: 'a where
huffman@25723
   183
  "UU = (THE x. \<forall>y. x \<sqsubseteq> y)"
huffman@25723
   184
huffman@25723
   185
notation (xsymbols)
huffman@25723
   186
  UU  ("\<bottom>")
huffman@25723
   187
huffman@25723
   188
text {* derive the old rule minimal *}
huffman@25723
   189
 
huffman@25723
   190
lemma UU_least: "\<forall>z. \<bottom> \<sqsubseteq> z"
huffman@25723
   191
apply (unfold UU_def)
huffman@25723
   192
apply (rule theI')
huffman@25723
   193
apply (rule ex_ex1I)
huffman@25723
   194
apply (rule least)
huffman@31076
   195
apply (blast intro: below_antisym)
huffman@25723
   196
done
huffman@25723
   197
huffman@25723
   198
lemma minimal [iff]: "\<bottom> \<sqsubseteq> x"
huffman@25723
   199
by (rule UU_least [THEN spec])
huffman@25723
   200
haftmann@31071
   201
end
haftmann@31071
   202
huffman@31024
   203
text {* Simproc to rewrite @{term "\<bottom> = x"} to @{term "x = \<bottom>"}. *}
huffman@16739
   204
huffman@31024
   205
setup {*
wenzelm@33523
   206
  Reorient_Proc.add
huffman@31024
   207
    (fn Const(@{const_name UU}, _) => true | _ => false)
huffman@31024
   208
*}
huffman@25723
   209
wenzelm@33523
   210
simproc_setup reorient_bottom ("\<bottom> = x") = Reorient_Proc.proc
huffman@25723
   211
haftmann@31071
   212
context pcpo
haftmann@31071
   213
begin
haftmann@31071
   214
huffman@25723
   215
text {* useful lemmas about @{term \<bottom>} *}
huffman@25723
   216
huffman@31076
   217
lemma below_UU_iff [simp]: "(x \<sqsubseteq> \<bottom>) = (x = \<bottom>)"
huffman@25723
   218
by (simp add: po_eq_conv)
huffman@25723
   219
huffman@25723
   220
lemma eq_UU_iff: "(x = \<bottom>) = (x \<sqsubseteq> \<bottom>)"
huffman@25723
   221
by simp
huffman@25723
   222
huffman@25723
   223
lemma UU_I: "x \<sqsubseteq> \<bottom> \<Longrightarrow> x = \<bottom>"
huffman@25723
   224
by (subst eq_UU_iff)
huffman@25723
   225
huffman@25723
   226
lemma chain_UU_I: "\<lbrakk>chain Y; (\<Squnion>i. Y i) = \<bottom>\<rbrakk> \<Longrightarrow> \<forall>i. Y i = \<bottom>"
huffman@15563
   227
apply (rule allI)
huffman@16626
   228
apply (rule UU_I)
huffman@15563
   229
apply (erule subst)
huffman@15563
   230
apply (erule is_ub_thelub)
huffman@15563
   231
done
huffman@15563
   232
huffman@16626
   233
lemma chain_UU_I_inverse: "\<forall>i::nat. Y i = \<bottom> \<Longrightarrow> (\<Squnion>i. Y i) = \<bottom>"
huffman@15563
   234
apply (rule lub_chain_maxelem)
huffman@15563
   235
apply (erule spec)
huffman@15588
   236
apply simp
huffman@15563
   237
done
huffman@15563
   238
huffman@16626
   239
lemma chain_UU_I_inverse2: "(\<Squnion>i. Y i) \<noteq> \<bottom> \<Longrightarrow> \<exists>i::nat. Y i \<noteq> \<bottom>"
haftmann@31071
   240
  by (blast intro: chain_UU_I_inverse)
huffman@15563
   241
huffman@16626
   242
lemma notUU_I: "\<lbrakk>x \<sqsubseteq> y; x \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> y \<noteq> \<bottom>"
haftmann@31071
   243
  by (blast intro: UU_I)
huffman@15563
   244
huffman@16627
   245
lemma chain_mono2: "\<lbrakk>\<exists>j. Y j \<noteq> \<bottom>; chain Y\<rbrakk> \<Longrightarrow> \<exists>j. \<forall>i>j. Y i \<noteq> \<bottom>"
haftmann@31071
   246
  by (blast dest: notUU_I chain_mono_less)
haftmann@31071
   247
haftmann@31071
   248
end
huffman@15588
   249
huffman@15588
   250
subsection {* Chain-finite and flat cpos *}
huffman@15563
   251
huffman@15588
   252
text {* further useful classes for HOLCF domains *}
huffman@15588
   253
haftmann@31071
   254
class chfin = po +
haftmann@31071
   255
  assumes chfin: "chain Y \<Longrightarrow> \<exists>n. max_in_chain n Y"
haftmann@31071
   256
begin
huffman@25814
   257
haftmann@31071
   258
subclass cpo
haftmann@31071
   259
apply default
haftmann@31071
   260
apply (frule chfin)
haftmann@31071
   261
apply (blast intro: lub_finch1)
haftmann@31071
   262
done
huffman@15563
   263
haftmann@31071
   264
lemma chfin2finch: "chain Y \<Longrightarrow> finite_chain Y"
haftmann@31071
   265
  by (simp add: chfin finite_chain_def)
haftmann@31071
   266
haftmann@31071
   267
end
huffman@15588
   268
haftmann@31071
   269
class finite_po = finite + po
haftmann@31071
   270
begin
huffman@25814
   271
haftmann@31071
   272
subclass chfin
haftmann@31071
   273
apply default
huffman@25814
   274
apply (drule finite_range_imp_finch)
huffman@25814
   275
apply (rule finite)
huffman@25814
   276
apply (simp add: finite_chain_def)
huffman@25814
   277
done
huffman@25814
   278
haftmann@31071
   279
end
huffman@15640
   280
haftmann@31071
   281
class flat = pcpo +
haftmann@31071
   282
  assumes ax_flat: "x \<sqsubseteq> y \<Longrightarrow> x = \<bottom> \<or> x = y"
haftmann@31071
   283
begin
huffman@15640
   284
haftmann@31071
   285
subclass chfin
haftmann@31071
   286
apply default
huffman@15563
   287
apply (unfold max_in_chain_def)
huffman@16626
   288
apply (case_tac "\<forall>i. Y i = \<bottom>")
huffman@15588
   289
apply simp
huffman@15563
   290
apply simp
huffman@15563
   291
apply (erule exE)
huffman@16626
   292
apply (rule_tac x="i" in exI)
huffman@15588
   293
apply clarify
huffman@25922
   294
apply (blast dest: chain_mono ax_flat)
huffman@15563
   295
done
huffman@15563
   296
huffman@31076
   297
lemma flat_below_iff:
huffman@25826
   298
  shows "(x \<sqsubseteq> y) = (x = \<bottom> \<or> x = y)"
haftmann@31071
   299
  by (safe dest!: ax_flat)
huffman@25826
   300
haftmann@31071
   301
lemma flat_eq: "a \<noteq> \<bottom> \<Longrightarrow> a \<sqsubseteq> b = (a = b)"
haftmann@31071
   302
  by (safe dest!: ax_flat)
huffman@15563
   303
haftmann@31071
   304
end
huffman@15563
   305
huffman@26023
   306
text {* Discrete cpos *}
huffman@26023
   307
huffman@31076
   308
class discrete_cpo = below +
haftmann@29614
   309
  assumes discrete_cpo [simp]: "x \<sqsubseteq> y \<longleftrightarrow> x = y"
haftmann@31071
   310
begin
huffman@26023
   311
haftmann@31071
   312
subclass po
haftmann@29614
   313
proof qed simp_all
huffman@26023
   314
huffman@26023
   315
text {* In a discrete cpo, every chain is constant *}
huffman@26023
   316
huffman@26023
   317
lemma discrete_chain_const:
haftmann@31071
   318
  assumes S: "chain S"
huffman@26023
   319
  shows "\<exists>x. S = (\<lambda>i. x)"
huffman@26023
   320
proof (intro exI ext)
huffman@26023
   321
  fix i :: nat
huffman@26023
   322
  have "S 0 \<sqsubseteq> S i" using S le0 by (rule chain_mono)
huffman@26023
   323
  hence "S 0 = S i" by simp
huffman@26023
   324
  thus "S i = S 0" by (rule sym)
huffman@26023
   325
qed
huffman@26023
   326
haftmann@31071
   327
subclass cpo
huffman@26023
   328
proof
huffman@26023
   329
  fix S :: "nat \<Rightarrow> 'a"
huffman@26023
   330
  assume S: "chain S"
huffman@26023
   331
  hence "\<exists>x. S = (\<lambda>i. x)"
huffman@26023
   332
    by (rule discrete_chain_const)
huffman@26023
   333
  thus "\<exists>x. range S <<| x"
huffman@26023
   334
    by (fast intro: lub_const)
huffman@26023
   335
qed
huffman@26023
   336
haftmann@31071
   337
end
huffman@15576
   338
huffman@16626
   339
end