src/HOLCF/Porder.thy
author haftmann
Tue Jul 10 17:30:50 2007 +0200 (2007-07-10)
changeset 23709 fd31da8f752a
parent 23284 07ae93e58fea
child 24728 e2b3a1065676
permissions -rw-r--r--
moved lfp_induct2 here
huffman@15600
     1
(*  Title:      HOLCF/Porder.thy
nipkow@243
     2
    ID:         $Id$
clasohm@1479
     3
    Author:     Franz Regensburger
nipkow@243
     4
*)
nipkow@243
     5
huffman@15587
     6
header {* Partial orders *}
huffman@15576
     7
huffman@15577
     8
theory Porder
huffman@19621
     9
imports Finite_Set
huffman@15577
    10
begin
huffman@15576
    11
huffman@15587
    12
subsection {* Type class for partial orders *}
huffman@15587
    13
huffman@23284
    14
class sq_ord = type +
huffman@23284
    15
  fixes sq_le :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
huffman@15576
    16
huffman@23284
    17
notation
huffman@23284
    18
  sq_le (infixl "<<" 55)
huffman@15576
    19
huffman@23284
    20
notation (xsymbols)
huffman@23284
    21
  sq_le (infixl "\<sqsubseteq>" 55)
huffman@15576
    22
huffman@15576
    23
axclass po < sq_ord
huffman@23284
    24
  refl_less [iff]: "x \<sqsubseteq> x"
huffman@17810
    25
  antisym_less:    "\<lbrakk>x \<sqsubseteq> y; y \<sqsubseteq> x\<rbrakk> \<Longrightarrow> x = y"    
huffman@17810
    26
  trans_less:      "\<lbrakk>x \<sqsubseteq> y; y \<sqsubseteq> z\<rbrakk> \<Longrightarrow> x \<sqsubseteq> z"
huffman@15576
    27
huffman@15576
    28
text {* minimal fixes least element *}
huffman@15576
    29
huffman@17810
    30
lemma minimal2UU[OF allI] : "\<forall>x::'a::po. uu \<sqsubseteq> x \<Longrightarrow> uu = (THE u. \<forall>y. u \<sqsubseteq> y)"
huffman@15930
    31
by (blast intro: theI2 antisym_less)
huffman@15576
    32
huffman@15576
    33
text {* the reverse law of anti-symmetry of @{term "op <<"} *}
huffman@15576
    34
huffman@17810
    35
lemma antisym_less_inverse: "(x::'a::po) = y \<Longrightarrow> x \<sqsubseteq> y \<and> y \<sqsubseteq> x"
huffman@17810
    36
by simp
huffman@15576
    37
huffman@17810
    38
lemma box_less: "\<lbrakk>(a::'a::po) \<sqsubseteq> b; c \<sqsubseteq> a; b \<sqsubseteq> d\<rbrakk> \<Longrightarrow> c \<sqsubseteq> d"
huffman@18088
    39
by (rule trans_less [OF trans_less])
huffman@15576
    40
huffman@17810
    41
lemma po_eq_conv: "((x::'a::po) = y) = (x \<sqsubseteq> y \<and> y \<sqsubseteq> x)"
huffman@17810
    42
by (fast elim!: antisym_less_inverse intro!: antisym_less)
huffman@17810
    43
huffman@17810
    44
lemma rev_trans_less: "\<lbrakk>(y::'a::po) \<sqsubseteq> z; x \<sqsubseteq> y\<rbrakk> \<Longrightarrow> x \<sqsubseteq> z"
huffman@17810
    45
by (rule trans_less)
huffman@15576
    46
huffman@18647
    47
lemma sq_ord_less_eq_trans: "\<lbrakk>a \<sqsubseteq> b; b = c\<rbrakk> \<Longrightarrow> a \<sqsubseteq> c"
huffman@18647
    48
by (rule subst)
huffman@18647
    49
huffman@18647
    50
lemma sq_ord_eq_less_trans: "\<lbrakk>a = b; b \<sqsubseteq> c\<rbrakk> \<Longrightarrow> a \<sqsubseteq> c"
huffman@18647
    51
by (rule ssubst)
huffman@18647
    52
huffman@18647
    53
lemmas HOLCF_trans_rules [trans] =
huffman@18647
    54
  trans_less
huffman@18647
    55
  antisym_less
huffman@18647
    56
  sq_ord_less_eq_trans
huffman@18647
    57
  sq_ord_eq_less_trans
huffman@18647
    58
huffman@15587
    59
subsection {* Chains and least upper bounds *}
nipkow@243
    60
huffman@18071
    61
constdefs  
huffman@18071
    62
huffman@18071
    63
  -- {* class definitions *}
huffman@18071
    64
  is_ub :: "['a set, 'a::po] \<Rightarrow> bool"       (infixl "<|" 55)
huffman@18071
    65
  "S <| x \<equiv> \<forall>y. y \<in> S \<longrightarrow> y \<sqsubseteq> x"
huffman@18071
    66
huffman@18071
    67
  is_lub :: "['a set, 'a::po] \<Rightarrow> bool"       (infixl "<<|" 55)
huffman@18071
    68
  "S <<| x \<equiv> S <| x \<and> (\<forall>u. S <| u \<longrightarrow> x \<sqsubseteq> u)"
huffman@18071
    69
huffman@18071
    70
  -- {* Arbitrary chains are total orders *}
huffman@18071
    71
  tord :: "'a::po set \<Rightarrow> bool"
huffman@18071
    72
  "tord S \<equiv> \<forall>x y. x \<in> S \<and> y \<in> S \<longrightarrow> (x \<sqsubseteq> y \<or> y \<sqsubseteq> x)"
huffman@18071
    73
huffman@18071
    74
  -- {* Here we use countable chains and I prefer to code them as functions! *}
huffman@18071
    75
  chain :: "(nat \<Rightarrow> 'a::po) \<Rightarrow> bool"
huffman@18071
    76
  "chain F \<equiv> \<forall>i. F i \<sqsubseteq> F (Suc i)"
huffman@18071
    77
huffman@18071
    78
  -- {* finite chains, needed for monotony of continuous functions *}
huffman@18071
    79
  max_in_chain :: "[nat, nat \<Rightarrow> 'a::po] \<Rightarrow> bool"
huffman@18071
    80
  "max_in_chain i C \<equiv> \<forall>j. i \<le> j \<longrightarrow> C i = C j" 
huffman@18071
    81
huffman@18071
    82
  finite_chain :: "(nat \<Rightarrow> 'a::po) \<Rightarrow> bool"
huffman@18071
    83
  "finite_chain C \<equiv> chain(C) \<and> (\<exists>i. max_in_chain i C)"
huffman@18071
    84
huffman@18071
    85
  lub :: "'a set \<Rightarrow> 'a::po"
huffman@18071
    86
  "lub S \<equiv> THE x. S <<| x"
nipkow@243
    87
wenzelm@21524
    88
abbreviation
wenzelm@21524
    89
  Lub  (binder "LUB " 10) where
wenzelm@21524
    90
  "LUB n. t n == lub (range t)"
oheimb@2394
    91
wenzelm@21524
    92
notation (xsymbols)
wenzelm@21524
    93
  Lub  (binder "\<Squnion> " 10)
nipkow@243
    94
huffman@15562
    95
huffman@15576
    96
text {* lubs are unique *}
huffman@15562
    97
huffman@17810
    98
lemma unique_lub: "\<lbrakk>S <<| x; S <<| y\<rbrakk> \<Longrightarrow> x = y"
huffman@15562
    99
apply (unfold is_lub_def is_ub_def)
huffman@15562
   100
apply (blast intro: antisym_less)
huffman@15562
   101
done
huffman@15562
   102
huffman@15576
   103
text {* chains are monotone functions *}
huffman@15562
   104
huffman@17810
   105
lemma chain_mono [rule_format]: "chain F \<Longrightarrow> x < y \<longrightarrow> F x \<sqsubseteq> F y"
huffman@15562
   106
apply (unfold chain_def)
huffman@17810
   107
apply (induct_tac y)
huffman@17810
   108
apply simp
huffman@17810
   109
apply (blast elim: less_SucE intro: trans_less)
huffman@15562
   110
done
huffman@15562
   111
huffman@17810
   112
lemma chain_mono3: "\<lbrakk>chain F; x \<le> y\<rbrakk> \<Longrightarrow> F x \<sqsubseteq> F y"
huffman@15562
   113
apply (drule le_imp_less_or_eq)
huffman@15562
   114
apply (blast intro: chain_mono)
huffman@15562
   115
done
huffman@15562
   116
huffman@15576
   117
text {* The range of a chain is a totally ordered *}
huffman@15562
   118
huffman@17810
   119
lemma chain_tord: "chain F \<Longrightarrow> tord (range F)"
huffman@17810
   120
apply (unfold tord_def, clarify)
huffman@15562
   121
apply (rule nat_less_cases)
huffman@15562
   122
apply (fast intro: chain_mono)+
huffman@15562
   123
done
huffman@15562
   124
huffman@15576
   125
text {* technical lemmas about @{term lub} and @{term is_lub} *}
huffman@15562
   126
huffman@15562
   127
lemmas lub = lub_def [THEN meta_eq_to_obj_eq, standard]
huffman@15562
   128
huffman@17810
   129
lemma lubI: "M <<| x \<Longrightarrow> M <<| lub M"
huffman@15930
   130
apply (unfold lub_def)
huffman@17810
   131
apply (rule theI)
huffman@15930
   132
apply assumption
huffman@17810
   133
apply (erule (1) unique_lub)
huffman@15562
   134
done
huffman@15562
   135
huffman@17810
   136
lemma thelubI: "M <<| l \<Longrightarrow> lub M = l"
huffman@18088
   137
by (rule unique_lub [OF lubI])
huffman@15562
   138
huffman@17810
   139
lemma lub_singleton [simp]: "lub {x} = x"
huffman@17810
   140
by (simp add: thelubI is_lub_def is_ub_def)
huffman@15562
   141
huffman@15576
   142
text {* access to some definition as inference rule *}
huffman@15562
   143
huffman@17810
   144
lemma is_lubD1: "S <<| x \<Longrightarrow> S <| x"
huffman@17810
   145
by (unfold is_lub_def, simp)
huffman@15562
   146
huffman@17810
   147
lemma is_lub_lub: "\<lbrakk>S <<| x; S <| u\<rbrakk> \<Longrightarrow> x \<sqsubseteq> u"
huffman@17810
   148
by (unfold is_lub_def, simp)
huffman@15562
   149
huffman@17810
   150
lemma is_lubI: "\<lbrakk>S <| x; \<And>u. S <| u \<Longrightarrow> x \<sqsubseteq> u\<rbrakk> \<Longrightarrow> S <<| x"
huffman@17810
   151
by (unfold is_lub_def, fast)
nipkow@243
   152
huffman@17810
   153
lemma chainE: "chain F \<Longrightarrow> F i \<sqsubseteq> F (Suc i)"
huffman@17810
   154
by (unfold chain_def, simp)
huffman@15562
   155
huffman@17810
   156
lemma chainI: "(\<And>i. F i \<sqsubseteq> F (Suc i)) \<Longrightarrow> chain F"
huffman@17810
   157
by (unfold chain_def, simp)
huffman@15562
   158
huffman@17810
   159
lemma chain_shift: "chain Y \<Longrightarrow> chain (\<lambda>i. Y (i + j))"
huffman@15562
   160
apply (rule chainI)
huffman@16318
   161
apply simp
huffman@15562
   162
apply (erule chainE)
huffman@15562
   163
done
huffman@15562
   164
huffman@15576
   165
text {* technical lemmas about (least) upper bounds of chains *}
huffman@15562
   166
huffman@17810
   167
lemma ub_rangeD: "range S <| x \<Longrightarrow> S i \<sqsubseteq> x"
huffman@17810
   168
by (unfold is_ub_def, simp)
huffman@15562
   169
huffman@17810
   170
lemma ub_rangeI: "(\<And>i. S i \<sqsubseteq> x) \<Longrightarrow> range S <| x"
huffman@17810
   171
by (unfold is_ub_def, fast)
huffman@15562
   172
huffman@17810
   173
lemma is_ub_lub: "range S <<| x \<Longrightarrow> S i \<sqsubseteq> x"
huffman@17810
   174
by (rule is_lubD1 [THEN ub_rangeD])
huffman@15562
   175
huffman@16318
   176
lemma is_ub_range_shift:
huffman@16318
   177
  "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <| x = range S <| x"
huffman@16318
   178
apply (rule iffI)
huffman@16318
   179
apply (rule ub_rangeI)
huffman@16318
   180
apply (rule_tac y="S (i + j)" in trans_less)
huffman@16318
   181
apply (erule chain_mono3)
huffman@16318
   182
apply (rule le_add1)
huffman@16318
   183
apply (erule ub_rangeD)
huffman@16318
   184
apply (rule ub_rangeI)
huffman@16318
   185
apply (erule ub_rangeD)
huffman@16318
   186
done
huffman@16318
   187
huffman@16318
   188
lemma is_lub_range_shift:
huffman@16318
   189
  "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <<| x = range S <<| x"
huffman@16318
   190
by (simp add: is_lub_def is_ub_range_shift)
huffman@16318
   191
huffman@15576
   192
text {* results about finite chains *}
huffman@15562
   193
huffman@17810
   194
lemma lub_finch1: "\<lbrakk>chain C; max_in_chain i C\<rbrakk> \<Longrightarrow> range C <<| C i"
huffman@15562
   195
apply (unfold max_in_chain_def)
huffman@15562
   196
apply (rule is_lubI)
huffman@17810
   197
apply (rule ub_rangeI, rename_tac j)
huffman@17810
   198
apply (rule_tac x=i and y=j in linorder_le_cases)
huffman@17810
   199
apply simp
huffman@17810
   200
apply (erule (1) chain_mono3)
huffman@15562
   201
apply (erule ub_rangeD)
huffman@15562
   202
done
huffman@15562
   203
huffman@15562
   204
lemma lub_finch2: 
huffman@17810
   205
        "finite_chain C \<Longrightarrow> range C <<| C (LEAST i. max_in_chain i C)"
huffman@15562
   206
apply (unfold finite_chain_def)
huffman@17810
   207
apply (erule conjE)
huffman@17810
   208
apply (erule LeastI2_ex)
huffman@17810
   209
apply (erule (1) lub_finch1)
huffman@15562
   210
done
huffman@15562
   211
huffman@19621
   212
lemma finch_imp_finite_range: "finite_chain Y \<Longrightarrow> finite (range Y)"
huffman@19621
   213
 apply (unfold finite_chain_def, clarify)
huffman@19621
   214
 apply (rule_tac f="Y" and n="Suc i" in nat_seg_image_imp_finite)
huffman@19621
   215
 apply (rule equalityI)
huffman@19621
   216
  apply (rule subsetI)
huffman@19621
   217
  apply (erule rangeE, rename_tac j)
huffman@19621
   218
  apply (rule_tac x=i and y=j in linorder_le_cases)
huffman@19621
   219
   apply (subgoal_tac "Y j = Y i", simp)
huffman@19621
   220
   apply (simp add: max_in_chain_def)
huffman@19621
   221
  apply simp
huffman@19621
   222
 apply fast
huffman@19621
   223
done
huffman@19621
   224
huffman@19621
   225
lemma finite_tord_has_max [rule_format]:
huffman@19621
   226
  "finite S \<Longrightarrow> S \<noteq> {} \<longrightarrow> tord S \<longrightarrow> (\<exists>y\<in>S. \<forall>x\<in>S. x \<sqsubseteq> y)"
huffman@19621
   227
 apply (erule finite_induct, simp)
huffman@19621
   228
 apply (rename_tac a S, clarify)
huffman@19621
   229
 apply (case_tac "S = {}", simp)
huffman@19621
   230
 apply (drule (1) mp)
huffman@19621
   231
 apply (drule mp, simp add: tord_def)
huffman@19621
   232
 apply (erule bexE, rename_tac z)
huffman@19621
   233
 apply (subgoal_tac "a \<sqsubseteq> z \<or> z \<sqsubseteq> a")
huffman@19621
   234
  apply (erule disjE)
huffman@19621
   235
   apply (rule_tac x="z" in bexI, simp, simp)
huffman@19621
   236
  apply (rule_tac x="a" in bexI)
huffman@19621
   237
   apply (clarsimp elim!: rev_trans_less)
huffman@19621
   238
  apply simp
huffman@19621
   239
 apply (simp add: tord_def)
huffman@19621
   240
done
huffman@19621
   241
huffman@19621
   242
lemma finite_range_imp_finch:
huffman@19621
   243
  "\<lbrakk>chain Y; finite (range Y)\<rbrakk> \<Longrightarrow> finite_chain Y"
huffman@19621
   244
 apply (subgoal_tac "\<exists>y\<in>range Y. \<forall>x\<in>range Y. x \<sqsubseteq> y")
huffman@19621
   245
  apply (clarsimp, rename_tac i)
huffman@19621
   246
  apply (subgoal_tac "max_in_chain i Y")
huffman@19621
   247
   apply (simp add: finite_chain_def exI)
huffman@19621
   248
  apply (simp add: max_in_chain_def po_eq_conv chain_mono3)
huffman@19621
   249
 apply (erule finite_tord_has_max, simp)
huffman@19621
   250
 apply (erule chain_tord)
huffman@19621
   251
done
huffman@19621
   252
huffman@17810
   253
lemma bin_chain: "x \<sqsubseteq> y \<Longrightarrow> chain (\<lambda>i. if i=0 then x else y)"
huffman@17810
   254
by (rule chainI, simp)
huffman@17810
   255
huffman@17810
   256
lemma bin_chainmax:
huffman@17810
   257
  "x \<sqsubseteq> y \<Longrightarrow> max_in_chain (Suc 0) (\<lambda>i. if i=0 then x else y)"
huffman@17810
   258
by (unfold max_in_chain_def, simp)
huffman@15562
   259
huffman@17810
   260
lemma lub_bin_chain:
huffman@17810
   261
  "x \<sqsubseteq> y \<Longrightarrow> range (\<lambda>i::nat. if i=0 then x else y) <<| y"
huffman@17810
   262
apply (frule bin_chain)
huffman@17810
   263
apply (drule bin_chainmax)
huffman@17810
   264
apply (drule (1) lub_finch1)
huffman@17810
   265
apply simp
huffman@15562
   266
done
huffman@15562
   267
huffman@15576
   268
text {* the maximal element in a chain is its lub *}
huffman@15562
   269
huffman@17810
   270
lemma lub_chain_maxelem: "\<lbrakk>Y i = c; \<forall>i. Y i \<sqsubseteq> c\<rbrakk> \<Longrightarrow> lub (range Y) = c"
huffman@17810
   271
by (blast dest: ub_rangeD intro: thelubI is_lubI ub_rangeI)
huffman@15562
   272
huffman@15576
   273
text {* the lub of a constant chain is the constant *}
huffman@15562
   274
huffman@18071
   275
lemma chain_const [simp]: "chain (\<lambda>i. c)"
huffman@17372
   276
by (simp add: chainI)
huffman@17372
   277
huffman@17810
   278
lemma lub_const: "range (\<lambda>x. c) <<| c"
huffman@17810
   279
by (blast dest: ub_rangeD intro: is_lubI ub_rangeI)
regensbu@1274
   280
huffman@18071
   281
lemma thelub_const [simp]: "(\<Squnion>i. c) = c"
huffman@18071
   282
by (rule lub_const [THEN thelubI])
regensbu@1168
   283
huffman@18071
   284
end