src/HOLCF/Adm.thy
author paulson
Tue May 24 10:55:11 2005 +0200 (2005-05-24)
changeset 16062 f8110bd9957f
parent 16056 32c3b7188c28
child 16070 4a83dd540b88
permissions -rw-r--r--
cannot have files named adm.ML and Adm.ML on Macs, so deleted one and renamed the other
huffman@16056
     1
(*  Title:      HOLCF/Adm.thy
huffman@16056
     2
    ID:         $Id$
huffman@16056
     3
    Author:     Franz Regensburger
huffman@16056
     4
    License:    GPL (GNU GENERAL PUBLIC LICENSE)
huffman@16056
     5
*)
huffman@16056
     6
huffman@16056
     7
header {* Admissibility *}
huffman@16056
     8
huffman@16056
     9
theory Adm
huffman@16056
    10
imports Cfun
huffman@16056
    11
begin
huffman@16056
    12
huffman@16056
    13
defaultsort cpo
huffman@16056
    14
huffman@16056
    15
subsection {* Definitions *}
huffman@16056
    16
huffman@16056
    17
consts
huffman@16056
    18
adm		:: "('a::cpo=>bool)=>bool"
huffman@16056
    19
huffman@16056
    20
defs
huffman@16056
    21
adm_def:       "adm P == !Y. chain(Y) --> 
huffman@16056
    22
                        (!i. P(Y i)) --> P(lub(range Y))"
huffman@16056
    23
huffman@16056
    24
subsection {* Admissibility and fixed point induction *}
huffman@16056
    25
huffman@16056
    26
text {* access to definitions *}
huffman@16056
    27
huffman@16056
    28
lemma admI:
huffman@16056
    29
   "(!!Y. [| chain Y; !i. P (Y i) |] ==> P (lub (range Y))) ==> adm P"
huffman@16056
    30
apply (unfold adm_def)
huffman@16056
    31
apply blast
huffman@16056
    32
done
huffman@16056
    33
huffman@16056
    34
lemma triv_admI: "!x. P x ==> adm P"
huffman@16056
    35
apply (rule admI)
huffman@16056
    36
apply (erule spec)
huffman@16056
    37
done
huffman@16056
    38
huffman@16056
    39
lemma admD: "[| adm(P); chain(Y); !i. P(Y(i)) |] ==> P(lub(range(Y)))"
huffman@16056
    40
apply (unfold adm_def)
huffman@16056
    41
apply blast
huffman@16056
    42
done
huffman@16056
    43
huffman@16056
    44
text {* for chain-finite (easy) types every formula is admissible *}
huffman@16056
    45
huffman@16056
    46
lemma adm_max_in_chain: 
huffman@16056
    47
"!Y. chain(Y::nat=>'a) --> (? n. max_in_chain n Y) ==> adm(P::'a=>bool)"
huffman@16056
    48
apply (unfold adm_def)
huffman@16056
    49
apply (intro strip)
huffman@16056
    50
apply (rule exE)
huffman@16056
    51
apply (rule mp)
huffman@16056
    52
apply (erule spec)
huffman@16056
    53
apply assumption
huffman@16056
    54
apply (subst lub_finch1 [THEN thelubI])
huffman@16056
    55
apply assumption
huffman@16056
    56
apply assumption
huffman@16056
    57
apply (erule spec)
huffman@16056
    58
done
huffman@16056
    59
huffman@16056
    60
lemmas adm_chfin = chfin [THEN adm_max_in_chain, standard]
huffman@16056
    61
huffman@16056
    62
text {* some lemmata for functions with flat/chfin domain/range types *}
huffman@16056
    63
huffman@16056
    64
lemma adm_chfindom: "adm (%(u::'a::cpo->'b::chfin). P(u$s))"
huffman@16056
    65
apply (unfold adm_def)
huffman@16056
    66
apply (intro strip)
huffman@16056
    67
apply (drule chfin_Rep_CFunR)
huffman@16056
    68
apply (erule_tac x = "s" in allE)
huffman@16056
    69
apply clarsimp
huffman@16056
    70
done
huffman@16056
    71
huffman@16056
    72
(* adm_flat not needed any more, since it is a special case of adm_chfindom *)
huffman@16056
    73
huffman@16056
    74
text {* improved admissibility introduction *}
huffman@16056
    75
huffman@16056
    76
lemma admI2:
huffman@16056
    77
 "(!!Y. [| chain Y; !i. P (Y i); !i. ? j. i < j & Y i ~= Y j & Y i << Y j |] 
huffman@16056
    78
  ==> P(lub (range Y))) ==> adm P"
huffman@16056
    79
apply (unfold adm_def)
huffman@16056
    80
apply (intro strip)
huffman@16056
    81
apply (erule increasing_chain_adm_lemma)
huffman@16056
    82
apply assumption
huffman@16056
    83
apply fast
huffman@16056
    84
done
huffman@16056
    85
huffman@16056
    86
text {* admissibility of special formulae and propagation *}
huffman@16056
    87
huffman@16056
    88
lemma adm_less [simp]: "[|cont u;cont v|]==> adm(%x. u x << v x)"
huffman@16056
    89
apply (unfold adm_def)
huffman@16056
    90
apply (intro strip)
huffman@16056
    91
apply (frule_tac f = "u" in cont2mono [THEN ch2ch_monofun])
huffman@16056
    92
apply assumption
huffman@16056
    93
apply (frule_tac f = "v" in cont2mono [THEN ch2ch_monofun])
huffman@16056
    94
apply assumption
huffman@16056
    95
apply (erule cont2contlub [THEN contlubE, THEN spec, THEN mp, THEN ssubst])
huffman@16056
    96
apply assumption
huffman@16056
    97
apply (erule cont2contlub [THEN contlubE, THEN spec, THEN mp, THEN ssubst])
huffman@16056
    98
apply assumption
huffman@16056
    99
apply (blast intro: lub_mono)
huffman@16056
   100
done
huffman@16056
   101
huffman@16056
   102
lemma adm_conj [simp]: "[| adm P; adm Q |] ==> adm(%x. P x & Q x)"
huffman@16056
   103
by (fast elim: admD intro: admI)
huffman@16056
   104
huffman@16056
   105
lemma adm_not_free [simp]: "adm(%x. t)"
huffman@16056
   106
apply (unfold adm_def)
huffman@16056
   107
apply fast
huffman@16056
   108
done
huffman@16056
   109
huffman@16056
   110
lemma adm_not_less: "cont t ==> adm(%x.~ (t x) << u)"
huffman@16056
   111
apply (unfold adm_def)
huffman@16056
   112
apply (intro strip)
huffman@16056
   113
apply (rule contrapos_nn)
huffman@16056
   114
apply (erule spec)
huffman@16056
   115
apply (rule trans_less)
huffman@16056
   116
prefer 2 apply (assumption)
huffman@16056
   117
apply (erule cont2mono [THEN monofun_fun_arg])
huffman@16056
   118
apply (rule is_ub_thelub)
huffman@16056
   119
apply assumption
huffman@16056
   120
done
huffman@16056
   121
huffman@16056
   122
lemma adm_all: "!y. adm(P y) ==> adm(%x.!y. P y x)"
huffman@16056
   123
by (fast intro: admI elim: admD)
huffman@16056
   124
huffman@16056
   125
lemmas adm_all2 = allI [THEN adm_all, standard]
huffman@16056
   126
huffman@16056
   127
lemma adm_subst: "[|cont t; adm P|] ==> adm(%x. P (t x))"
huffman@16056
   128
apply (rule admI)
huffman@16056
   129
apply (simplesubst cont2contlub [THEN contlubE, THEN spec, THEN mp])
huffman@16056
   130
apply assumption
huffman@16056
   131
apply assumption
huffman@16056
   132
apply (erule admD)
huffman@16056
   133
apply (erule cont2mono [THEN ch2ch_monofun])
huffman@16056
   134
apply assumption
huffman@16056
   135
apply assumption
huffman@16056
   136
done
huffman@16056
   137
huffman@16056
   138
lemma adm_UU_not_less: "adm(%x.~ UU << t(x))"
huffman@16056
   139
by simp
huffman@16056
   140
huffman@16056
   141
lemma adm_not_UU: "cont(t)==> adm(%x.~ (t x) = UU)"
huffman@16056
   142
apply (unfold adm_def)
huffman@16056
   143
apply (intro strip)
huffman@16056
   144
apply (rule contrapos_nn)
huffman@16056
   145
apply (erule spec)
huffman@16056
   146
apply (rule chain_UU_I [THEN spec])
huffman@16056
   147
apply (erule cont2mono [THEN ch2ch_monofun])
huffman@16056
   148
apply assumption
huffman@16056
   149
apply (erule cont2contlub [THEN contlubE, THEN spec, THEN mp, THEN subst])
huffman@16056
   150
apply assumption
huffman@16056
   151
apply assumption
huffman@16056
   152
done
huffman@16056
   153
huffman@16056
   154
lemma adm_eq: "[|cont u ; cont v|]==> adm(%x. u x = v x)"
huffman@16056
   155
by (simp add: po_eq_conv)
huffman@16056
   156
huffman@16056
   157
text {* admissibility for disjunction is hard to prove. It takes 7 Lemmas *}
huffman@16056
   158
huffman@16056
   159
lemma adm_disj_lemma1:
huffman@16056
   160
  "\<forall>n::nat. P n \<or> Q n \<Longrightarrow> (\<forall>i. \<exists>j\<ge>i. P j) \<or> (\<forall>i. \<exists>j\<ge>i. Q j)"
huffman@16056
   161
apply (erule contrapos_pp)
huffman@16056
   162
apply clarsimp
huffman@16056
   163
apply (rule exI)
huffman@16056
   164
apply (rule conjI)
huffman@16056
   165
apply (drule spec, erule mp)
huffman@16056
   166
apply (rule le_maxI1)
huffman@16056
   167
apply (drule spec, erule mp)
huffman@16056
   168
apply (rule le_maxI2)
huffman@16056
   169
done
huffman@16056
   170
huffman@16056
   171
lemma adm_disj_lemma2: "[| adm P; \<exists>X. chain X & (!n. P(X n)) & 
huffman@16056
   172
      lub(range Y)=lub(range X)|] ==> P(lub(range Y))"
huffman@16056
   173
by (force elim: admD)
huffman@16056
   174
huffman@16056
   175
lemma adm_disj_lemma3: 
huffman@16056
   176
  "[| chain(Y::nat=>'a::cpo); \<forall>i. \<exists>j\<ge>i. P (Y j) |] ==> 
huffman@16056
   177
            chain(%m. Y (LEAST j. m\<le>j \<and> P(Y j)))"
huffman@16056
   178
apply (rule chainI)
huffman@16056
   179
apply (erule chain_mono3)
huffman@16056
   180
apply (rule Least_le)
huffman@16056
   181
apply (rule conjI)
huffman@16056
   182
apply (rule Suc_leD)
huffman@16056
   183
apply (erule allE)
huffman@16056
   184
apply (erule exE)
huffman@16056
   185
apply (erule LeastI [THEN conjunct1])
huffman@16056
   186
apply (erule allE)
huffman@16056
   187
apply (erule exE)
huffman@16056
   188
apply (erule LeastI [THEN conjunct2])
huffman@16056
   189
done
huffman@16056
   190
huffman@16056
   191
lemma adm_disj_lemma4: 
huffman@16056
   192
  "[| \<forall>i. \<exists>j\<ge>i. P (Y j) |] ==> ! m. P(Y(LEAST j::nat. m\<le>j & P(Y j)))"
huffman@16056
   193
apply (rule allI)
huffman@16056
   194
apply (erule allE)
huffman@16056
   195
apply (erule exE)
huffman@16056
   196
apply (erule LeastI [THEN conjunct2])
huffman@16056
   197
done
huffman@16056
   198
huffman@16056
   199
lemma adm_disj_lemma5: 
huffman@16056
   200
  "[| chain(Y::nat=>'a::cpo); \<forall>i. \<exists>j\<ge>i. P(Y j) |] ==> 
huffman@16056
   201
            lub(range(Y)) = (LUB m. Y(LEAST j. m\<le>j & P(Y j)))"
huffman@16056
   202
 apply (rule antisym_less)
huffman@16056
   203
  apply (rule lub_mono)
huffman@16056
   204
    apply assumption
huffman@16056
   205
   apply (erule adm_disj_lemma3)
huffman@16056
   206
   apply assumption
huffman@16056
   207
  apply (rule allI)
huffman@16056
   208
  apply (erule chain_mono3)
huffman@16056
   209
  apply (erule allE)
huffman@16056
   210
  apply (erule exE)
huffman@16056
   211
  apply (erule LeastI [THEN conjunct1])
huffman@16056
   212
 apply (rule lub_mono3)
huffman@16056
   213
   apply (erule adm_disj_lemma3)
huffman@16056
   214
   apply assumption
huffman@16056
   215
  apply assumption
huffman@16056
   216
 apply (rule allI)
huffman@16056
   217
 apply (rule exI)
huffman@16056
   218
 apply (rule refl_less)
huffman@16056
   219
done
huffman@16056
   220
huffman@16056
   221
lemma adm_disj_lemma6:
huffman@16056
   222
  "[| chain(Y::nat=>'a::cpo); \<forall>i. \<exists>j\<ge>i. P(Y j) |] ==> 
huffman@16056
   223
            \<exists>X. chain X & (\<forall>n. P(X n)) & lub(range Y) = lub(range X)"
huffman@16056
   224
apply (rule_tac x = "%m. Y (LEAST j. m\<le>j & P (Y j))" in exI)
huffman@16056
   225
apply (fast intro!: adm_disj_lemma3 adm_disj_lemma4 adm_disj_lemma5)
huffman@16056
   226
done
huffman@16056
   227
huffman@16056
   228
lemma adm_disj_lemma7:
huffman@16056
   229
"[| adm(P); chain(Y); \<forall>i. \<exists>j\<ge>i. P(Y j) |]==>P(lub(range(Y)))"
huffman@16056
   230
apply (erule adm_disj_lemma2)
huffman@16056
   231
apply (erule adm_disj_lemma6)
huffman@16056
   232
apply assumption
huffman@16056
   233
done
huffman@16056
   234
huffman@16056
   235
lemma adm_disj: "[| adm P; adm Q |] ==> adm(%x. P x | Q x)"
huffman@16056
   236
apply (rule admI)
huffman@16056
   237
apply (erule adm_disj_lemma1 [THEN disjE])
huffman@16056
   238
apply (rule disjI1)
huffman@16056
   239
apply (erule adm_disj_lemma7)
huffman@16056
   240
apply assumption
huffman@16056
   241
apply assumption
huffman@16056
   242
apply (rule disjI2)
huffman@16056
   243
apply (erule adm_disj_lemma7)
huffman@16056
   244
apply assumption
huffman@16056
   245
apply assumption
huffman@16056
   246
done
huffman@16056
   247
huffman@16056
   248
lemma adm_imp: "[| adm(%x.~(P x)); adm Q |] ==> adm(%x. P x --> Q x)"
huffman@16056
   249
by (subst imp_conv_disj, rule adm_disj)
huffman@16056
   250
huffman@16056
   251
lemma adm_iff: "[| adm (%x. P x --> Q x); adm (%x. Q x --> P x) |]  
huffman@16056
   252
            ==> adm (%x. P x = Q x)"
huffman@16056
   253
by (subst iff_conv_conj_imp, rule adm_conj)
huffman@16056
   254
huffman@16056
   255
lemma adm_not_conj: "[| adm (%x. ~ P x); adm (%x. ~ Q x) |] ==> adm (%x. ~ (P x & Q x))"
huffman@16056
   256
by (subst de_Morgan_conj, rule adm_disj)
huffman@16056
   257
huffman@16056
   258
lemmas adm_lemmas = adm_not_free adm_imp adm_disj adm_eq adm_not_UU
huffman@16056
   259
        adm_UU_not_less adm_all2 adm_not_less adm_not_conj adm_iff
huffman@16056
   260
huffman@16056
   261
declare adm_lemmas [simp]
huffman@16056
   262
paulson@16062
   263
(* legacy ML bindings *)
paulson@16062
   264
ML
paulson@16062
   265
{*
paulson@16062
   266
val adm_def = thm "adm_def";
paulson@16062
   267
val admI = thm "admI";
paulson@16062
   268
val triv_admI = thm "triv_admI";
paulson@16062
   269
val admD = thm "admD";
paulson@16062
   270
val adm_max_in_chain = thm "adm_max_in_chain";
paulson@16062
   271
val adm_chfin = thm "adm_chfin";
paulson@16062
   272
val adm_chfindom = thm "adm_chfindom";
paulson@16062
   273
val admI2 = thm "admI2";
paulson@16062
   274
val adm_less = thm "adm_less";
paulson@16062
   275
val adm_conj = thm "adm_conj";
paulson@16062
   276
val adm_not_free = thm "adm_not_free";
paulson@16062
   277
val adm_not_less = thm "adm_not_less";
paulson@16062
   278
val adm_all = thm "adm_all";
paulson@16062
   279
val adm_all2 = thm "adm_all2";
paulson@16062
   280
val adm_subst = thm "adm_subst";
paulson@16062
   281
val adm_UU_not_less = thm "adm_UU_not_less";
paulson@16062
   282
val adm_not_UU = thm "adm_not_UU";
paulson@16062
   283
val adm_eq = thm "adm_eq";
paulson@16062
   284
val adm_disj_lemma1 = thm "adm_disj_lemma1";
paulson@16062
   285
val adm_disj_lemma2 = thm "adm_disj_lemma2";
paulson@16062
   286
val adm_disj_lemma3 = thm "adm_disj_lemma3";
paulson@16062
   287
val adm_disj_lemma4 = thm "adm_disj_lemma4";
paulson@16062
   288
val adm_disj_lemma5 = thm "adm_disj_lemma5";
paulson@16062
   289
val adm_disj_lemma6 = thm "adm_disj_lemma6";
paulson@16062
   290
val adm_disj_lemma7 = thm "adm_disj_lemma7";
paulson@16062
   291
val adm_disj = thm "adm_disj";
paulson@16062
   292
val adm_imp = thm "adm_imp";
paulson@16062
   293
val adm_iff = thm "adm_iff";
paulson@16062
   294
val adm_not_conj = thm "adm_not_conj";
paulson@16062
   295
val adm_lemmas = [adm_not_free, adm_imp, adm_disj, adm_eq, adm_not_UU,
paulson@16062
   296
        adm_UU_not_less, adm_all2, adm_not_less, adm_not_conj, adm_iff]
paulson@16062
   297
*}
paulson@16062
   298
huffman@16056
   299
end
huffman@16056
   300