src/HOLCF/Pcpo.thy
author paulson
Fri, 05 Oct 2007 09:59:03 +0200
changeset 24854 0ebcd575d3c6
parent 22577 1a08fce38565
child 25131 2c8caac48ade
permissions -rw-r--r--
filtering out some package theorems
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     1
(*  Title:      HOLCF/Pcpo.thy
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     2
    ID:         $Id$
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     3
    Author:     Franz Regensburger
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     4
*)
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
     5
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
     6
header {* Classes cpo and pcpo *}
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
     7
15577
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
     8
theory Pcpo
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
     9
imports Porder
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
    10
begin
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    11
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    12
subsection {* Complete partial orders *}
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    13
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    14
text {* The class cpo of chain complete partial orders *}
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    15
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    16
axclass cpo < po
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    17
        -- {* class axiom: *}
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    18
  cpo:   "chain S \<Longrightarrow> \<exists>x. range S <<| x" 
2394
91d8abf108be adaptions for symbol font
oheimb
parents: 2291
diff changeset
    19
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    20
text {* in cpo's everthing equal to THE lub has lub properties for every chain *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    21
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    22
lemma thelubE: "\<lbrakk>chain S; (\<Squnion>i. S i) = (l::'a::cpo)\<rbrakk> \<Longrightarrow> range S <<| l"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    23
by (blast dest: cpo intro: lubI)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    24
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    25
text {* Properties of the lub *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    26
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    27
lemma is_ub_thelub: "chain (S::nat \<Rightarrow> 'a::cpo) \<Longrightarrow> S x \<sqsubseteq> (\<Squnion>i. S i)"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    28
by (blast dest: cpo intro: lubI [THEN is_ub_lub])
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    29
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    30
lemma is_lub_thelub:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    31
  "\<lbrakk>chain (S::nat \<Rightarrow> 'a::cpo); range S <| x\<rbrakk> \<Longrightarrow> (\<Squnion>i. S i) \<sqsubseteq> x"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    32
by (blast dest: cpo intro: lubI [THEN is_lub_lub])
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    33
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    34
lemma lub_range_mono:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    35
  "\<lbrakk>range X \<subseteq> range Y; chain Y; chain (X::nat \<Rightarrow> 'a::cpo)\<rbrakk>
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    36
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    37
apply (erule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    38
apply (rule ub_rangeI)
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    39
apply (subgoal_tac "\<exists>j. X i = Y j")
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    40
apply  clarsimp
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    41
apply  (erule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    42
apply auto
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    43
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    44
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    45
lemma lub_range_shift:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    46
  "chain (Y::nat \<Rightarrow> 'a::cpo) \<Longrightarrow> (\<Squnion>i. Y (i + j)) = (\<Squnion>i. Y i)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    47
apply (rule antisym_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    48
apply (rule lub_range_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    49
apply    fast
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    50
apply   assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    51
apply (erule chain_shift)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    52
apply (rule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    53
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    54
apply (rule ub_rangeI)
17813
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
    55
apply (rule_tac y="Y (i + j)" in trans_less)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    56
apply (erule chain_mono3)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    57
apply (rule le_add1)
17813
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
    58
apply (rule is_ub_thelub)
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
    59
apply (erule chain_shift)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    60
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    61
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    62
lemma maxinch_is_thelub:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    63
  "chain Y \<Longrightarrow> max_in_chain i Y = ((\<Squnion>i. Y i) = ((Y i)::'a::cpo))"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    64
apply (rule iffI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    65
apply (fast intro!: thelubI lub_finch1)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    66
apply (unfold max_in_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    67
apply (safe intro!: antisym_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    68
apply (fast elim!: chain_mono3)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    69
apply (drule sym)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    70
apply (force elim!: is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    71
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    72
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    73
text {* the @{text "\<sqsubseteq>"} relation between two chains is preserved by their lubs *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    74
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    75
lemma lub_mono:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    76
  "\<lbrakk>chain (X::nat \<Rightarrow> 'a::cpo); chain Y; \<forall>k. X k \<sqsubseteq> Y k\<rbrakk> 
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    77
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    78
apply (erule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    79
apply (rule ub_rangeI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    80
apply (rule trans_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    81
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    82
apply (erule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    83
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    84
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    85
text {* the = relation between two chains is preserved by their lubs *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    86
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    87
lemma lub_equal:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    88
  "\<lbrakk>chain (X::nat \<Rightarrow> 'a::cpo); chain Y; \<forall>k. X k = Y k\<rbrakk>
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    89
    \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    90
by (simp only: expand_fun_eq [symmetric])
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    91
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
    92
text {* more results about mono and = of lubs of chains *}
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    93
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    94
lemma lub_mono2:
17813
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
    95
  "\<lbrakk>\<exists>j. \<forall>i>j. X i = Y i; chain (X::nat \<Rightarrow> 'a::cpo); chain Y\<rbrakk>
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
    96
    \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    97
apply (erule exE)
17813
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
    98
apply (subgoal_tac "(\<Squnion>i. X (i + Suc j)) \<sqsubseteq> (\<Squnion>i. Y (i + Suc j))")
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
    99
apply (thin_tac "\<forall>i>j. X i = Y i")
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
   100
apply (simp only: lub_range_shift)
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   101
apply simp
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   102
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   103
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   104
lemma lub_equal2:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   105
  "\<lbrakk>\<exists>j. \<forall>i>j. X i = Y i; chain (X::nat \<Rightarrow> 'a::cpo); chain Y\<rbrakk>
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   106
    \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   107
by (blast intro: antisym_less lub_mono2 sym)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   108
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   109
lemma lub_mono3:
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   110
  "\<lbrakk>chain (Y::nat \<Rightarrow> 'a::cpo); chain X; \<forall>i. \<exists>j. Y i \<sqsubseteq> X j\<rbrakk>
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   111
    \<Longrightarrow> (\<Squnion>i. Y i) \<sqsubseteq> (\<Squnion>i. X i)"
17813
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
   112
apply (erule is_lub_thelub)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   113
apply (rule ub_rangeI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   114
apply (erule allE)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   115
apply (erule exE)
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   116
apply (erule trans_less)
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   117
apply (erule is_ub_thelub)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   118
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   119
16203
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   120
lemma ch2ch_lub:
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   121
  fixes Y :: "nat \<Rightarrow> nat \<Rightarrow> 'a::cpo"
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   122
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   123
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   124
  shows "chain (\<lambda>i. \<Squnion>j. Y i j)"
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   125
apply (rule chainI)
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   126
apply (rule lub_mono [rule_format, OF 2 2])
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   127
apply (rule chainE [OF 1])
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   128
done
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   129
16201
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   130
lemma diag_lub:
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   131
  fixes Y :: "nat \<Rightarrow> nat \<Rightarrow> 'a::cpo"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   132
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   133
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   134
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>i. Y i i)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   135
proof (rule antisym_less)
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   136
  have 3: "chain (\<lambda>i. Y i i)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   137
    apply (rule chainI)
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   138
    apply (rule trans_less)
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   139
    apply (rule chainE [OF 1])
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   140
    apply (rule chainE [OF 2])
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   141
    done
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   142
  have 4: "chain (\<lambda>i. \<Squnion>j. Y i j)"
16203
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   143
    by (rule ch2ch_lub [OF 1 2])
16201
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   144
  show "(\<Squnion>i. \<Squnion>j. Y i j) \<sqsubseteq> (\<Squnion>i. Y i i)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   145
    apply (rule is_lub_thelub [OF 4])
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   146
    apply (rule ub_rangeI)
16203
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   147
    apply (rule lub_mono3 [rule_format, OF 2 3])
16201
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   148
    apply (rule exI)
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   149
    apply (rule trans_less)
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   150
    apply (rule chain_mono3 [OF 1 le_maxI1])
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   151
    apply (rule chain_mono3 [OF 2 le_maxI2])
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   152
    done
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   153
  show "(\<Squnion>i. Y i i) \<sqsubseteq> (\<Squnion>i. \<Squnion>j. Y i j)"
16203
b3268fe39838 added theorem ch2ch_lub
huffman
parents: 16201
diff changeset
   154
    apply (rule lub_mono [rule_format, OF 3 4])
16201
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   155
    apply (rule is_ub_thelub [OF 2])
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   156
    done
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   157
qed
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   158
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   159
lemma ex_lub:
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   160
  fixes Y :: "nat \<Rightarrow> nat \<Rightarrow> 'a::cpo"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   161
  assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   162
  assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   163
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>j. \<Squnion>i. Y i j)"
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   164
by (simp add: diag_lub 1 2)
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   165
7bb51c8196cb added theorems diag_lub and ex_lub
huffman
parents: 16070
diff changeset
   166
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   167
subsection {* Pointed cpos *}
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   168
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   169
text {* The class pcpo of pointed cpos *}
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   170
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   171
axclass pcpo < cpo
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   172
  least: "\<exists>x. \<forall>y. x \<sqsubseteq> y"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   173
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   174
constdefs
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   175
  UU :: "'a::pcpo"
17813
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
   176
  "UU \<equiv> THE x. \<forall>y. x \<sqsubseteq> y"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   177
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   178
syntax (xsymbols)
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   179
  UU :: "'a::pcpo" ("\<bottom>")
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   180
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   181
text {* derive the old rule minimal *}
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   182
 
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   183
lemma UU_least: "\<forall>z. \<bottom> \<sqsubseteq> z"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   184
apply (unfold UU_def)
15930
145651bc64a8 Replaced all unnecessary uses of SOME with THE or LEAST
huffman
parents: 15640
diff changeset
   185
apply (rule theI')
145651bc64a8 Replaced all unnecessary uses of SOME with THE or LEAST
huffman
parents: 15640
diff changeset
   186
apply (rule ex_ex1I)
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   187
apply (rule least)
15930
145651bc64a8 Replaced all unnecessary uses of SOME with THE or LEAST
huffman
parents: 15640
diff changeset
   188
apply (blast intro: antisym_less)
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   189
done
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   190
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   191
lemma minimal [iff]: "\<bottom> \<sqsubseteq> x"
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   192
by (rule UU_least [THEN spec])
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   193
16739
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   194
lemma UU_reorient: "(\<bottom> = x) = (x = \<bottom>)"
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   195
by auto
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   196
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   197
ML_setup {*
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   198
local
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   199
  val meta_UU_reorient = thm "UU_reorient" RS eq_reflection;
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   200
  fun reorient_proc sg _ (_ $ t $ u) =
18924
83acd39b1bab UU_reorient_simproc no longer rewrites UU = numeral
huffman
parents: 17813
diff changeset
   201
    case u of
83acd39b1bab UU_reorient_simproc no longer rewrites UU = numeral
huffman
parents: 17813
diff changeset
   202
        Const("Pcpo.UU",_) => NONE
20713
823967ef47f1 renamed 0 and 1 to HOL.zero and HOL.one respectivly; introduced corresponding syntactic classes
haftmann
parents: 19440
diff changeset
   203
      | Const("HOL.zero", _) => NONE
823967ef47f1 renamed 0 and 1 to HOL.zero and HOL.one respectivly; introduced corresponding syntactic classes
haftmann
parents: 19440
diff changeset
   204
      | Const("HOL.one", _) => NONE
18924
83acd39b1bab UU_reorient_simproc no longer rewrites UU = numeral
huffman
parents: 17813
diff changeset
   205
      | Const("Numeral.number_of", _) $ _ => NONE
83acd39b1bab UU_reorient_simproc no longer rewrites UU = numeral
huffman
parents: 17813
diff changeset
   206
      | _ => SOME meta_UU_reorient;
16739
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   207
in
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   208
  val UU_reorient_simproc = 
22577
1a08fce38565 ML antiquotes;
wenzelm
parents: 20713
diff changeset
   209
    Simplifier.simproc @{theory} "UU_reorient_simproc" ["UU=x"] reorient_proc
16739
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   210
end;
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   211
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   212
Addsimprocs [UU_reorient_simproc];
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   213
*}
9ffd706ae402 add UU_reorient_simproc
huffman
parents: 16627
diff changeset
   214
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   215
text {* useful lemmas about @{term \<bottom>} *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   216
19440
b2877e230b07 add lemma less_UU_iff as default simp rule
huffman
parents: 18924
diff changeset
   217
lemma less_UU_iff [simp]: "(x \<sqsubseteq> \<bottom>) = (x = \<bottom>)"
b2877e230b07 add lemma less_UU_iff as default simp rule
huffman
parents: 18924
diff changeset
   218
by (simp add: po_eq_conv)
b2877e230b07 add lemma less_UU_iff as default simp rule
huffman
parents: 18924
diff changeset
   219
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   220
lemma eq_UU_iff: "(x = \<bottom>) = (x \<sqsubseteq> \<bottom>)"
19440
b2877e230b07 add lemma less_UU_iff as default simp rule
huffman
parents: 18924
diff changeset
   221
by simp
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   222
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   223
lemma UU_I: "x \<sqsubseteq> \<bottom> \<Longrightarrow> x = \<bottom>"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   224
by (subst eq_UU_iff)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   225
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   226
lemma not_less2not_eq: "\<not> (x::'a::po) \<sqsubseteq> y \<Longrightarrow> x \<noteq> y"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   227
by auto
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   228
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   229
lemma chain_UU_I: "\<lbrakk>chain Y; (\<Squnion>i. Y i) = \<bottom>\<rbrakk> \<Longrightarrow> \<forall>i. Y i = \<bottom>"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   230
apply (rule allI)
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   231
apply (rule UU_I)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   232
apply (erule subst)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   233
apply (erule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   234
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   235
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   236
lemma chain_UU_I_inverse: "\<forall>i::nat. Y i = \<bottom> \<Longrightarrow> (\<Squnion>i. Y i) = \<bottom>"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   237
apply (rule lub_chain_maxelem)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   238
apply (erule spec)
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   239
apply simp
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   240
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   241
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   242
lemma chain_UU_I_inverse2: "(\<Squnion>i. Y i) \<noteq> \<bottom> \<Longrightarrow> \<exists>i::nat. Y i \<noteq> \<bottom>"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   243
by (blast intro: chain_UU_I_inverse)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   244
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   245
lemma notUU_I: "\<lbrakk>x \<sqsubseteq> y; x \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> y \<noteq> \<bottom>"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   246
by (blast intro: UU_I)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   247
16627
a2844e212da4 cleaned up
huffman
parents: 16626
diff changeset
   248
lemma chain_mono2: "\<lbrakk>\<exists>j. Y j \<noteq> \<bottom>; chain Y\<rbrakk> \<Longrightarrow> \<exists>j. \<forall>i>j. Y i \<noteq> \<bottom>"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   249
by (blast dest: notUU_I chain_mono)
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   250
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   251
subsection {* Chain-finite and flat cpos *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   252
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   253
text {* further useful classes for HOLCF domains *}
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   254
15640
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   255
axclass chfin < po
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   256
  chfin: "\<forall>Y. chain Y \<longrightarrow> (\<exists>n. max_in_chain n Y)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   257
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   258
axclass flat < pcpo
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   259
  ax_flat: "\<forall>x y. x \<sqsubseteq> y \<longrightarrow> (x = \<bottom>) \<or> (x = y)"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   260
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   261
text {* some properties for chfin and flat *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   262
15640
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   263
text {* chfin types are cpo *}
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   264
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   265
lemma chfin_imp_cpo:
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   266
  "chain (S::nat \<Rightarrow> 'a::chfin) \<Longrightarrow> \<exists>x. range S <<| x"
15640
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   267
apply (frule chfin [rule_format])
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   268
apply (blast intro: lub_finch1)
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   269
done
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   270
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   271
instance chfin < cpo
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   272
by intro_classes (rule chfin_imp_cpo)
2d1d6ea579a1 chfin now a subclass of po, proved instance chfin < cpo
huffman
parents: 15588
diff changeset
   273
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   274
text {* flat types are chfin *}
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   275
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   276
lemma flat_imp_chfin: 
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   277
     "\<forall>Y::nat \<Rightarrow> 'a::flat. chain Y \<longrightarrow> (\<exists>n. max_in_chain n Y)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   278
apply (unfold max_in_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   279
apply clarify
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   280
apply (case_tac "\<forall>i. Y i = \<bottom>")
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   281
apply simp
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   282
apply simp
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   283
apply (erule exE)
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   284
apply (rule_tac x="i" in exI)
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   285
apply clarify
17813
03133f6606a1 cleaned up
huffman
parents: 16739
diff changeset
   286
apply (blast dest: chain_mono3 ax_flat [rule_format])
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   287
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   288
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   289
instance flat < chfin
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   290
by intro_classes (rule flat_imp_chfin)
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   291
16627
a2844e212da4 cleaned up
huffman
parents: 16626
diff changeset
   292
text {* flat subclass of chfin; @{text adm_flat} not needed *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   293
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   294
lemma flat_eq: "(a::'a::flat) \<noteq> \<bottom> \<Longrightarrow> a \<sqsubseteq> b = (a = b)"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   295
by (safe dest!: ax_flat [rule_format])
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   296
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   297
lemma chfin2finch: "chain (Y::nat \<Rightarrow> 'a::chfin) \<Longrightarrow> finite_chain Y"
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   298
by (simp add: chfin finite_chain_def)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   299
15588
14e3228f18cc arranged for document generation, cleaned up some proofs
huffman
parents: 15577
diff changeset
   300
text {* lemmata for improved admissibility introdution rule *}
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   301
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   302
lemma infinite_chain_adm_lemma:
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   303
  "\<lbrakk>chain Y; \<forall>i. P (Y i);  
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   304
    \<And>Y. \<lbrakk>chain Y; \<forall>i. P (Y i); \<not> finite_chain Y\<rbrakk> \<Longrightarrow> P (\<Squnion>i. Y i)\<rbrakk>
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   305
      \<Longrightarrow> P (\<Squnion>i. Y i)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   306
apply (case_tac "finite_chain Y")
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   307
prefer 2 apply fast
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   308
apply (unfold finite_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   309
apply safe
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   310
apply (erule lub_finch1 [THEN thelubI, THEN ssubst])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   311
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   312
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   313
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   314
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   315
lemma increasing_chain_adm_lemma:
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   316
  "\<lbrakk>chain Y;  \<forall>i. P (Y i); \<And>Y. \<lbrakk>chain Y; \<forall>i. P (Y i);
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   317
    \<forall>i. \<exists>j>i. Y i \<noteq> Y j \<and> Y i \<sqsubseteq> Y j\<rbrakk> \<Longrightarrow> P (\<Squnion>i. Y i)\<rbrakk>
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   318
      \<Longrightarrow> P (\<Squnion>i. Y i)"
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   319
apply (erule infinite_chain_adm_lemma)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   320
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   321
apply (erule thin_rl)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   322
apply (unfold finite_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   323
apply (unfold max_in_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   324
apply (fast dest: le_imp_less_or_eq elim: chain_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   325
done
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
   326
16626
d28314d2dce3 cleaned up
huffman
parents: 16203
diff changeset
   327
end