1 (* Title: HOLCF/Fix.thy |
1 (* Title: HOLCF/Fix.thy |
2 ID: $Id$ |
2 ID: $Id$ |
3 Author: Franz Regensburger |
3 Author: Franz Regensburger |
|
4 License: GPL (GNU GENERAL PUBLIC LICENSE) |
4 |
5 |
5 definitions for fixed point operator and admissibility |
6 definitions for fixed point operator and admissibility |
6 *) |
7 *) |
7 |
8 |
8 Fix = Cfun3 + |
9 theory Fix = Cfun: |
9 |
10 |
10 consts |
11 consts |
11 |
12 |
12 iterate :: "nat=>('a->'a)=>'a=>'a" |
13 iterate :: "nat=>('a->'a)=>'a=>'a" |
13 Ifix :: "('a->'a)=>'a" |
14 Ifix :: "('a->'a)=>'a" |
14 fix :: "('a->'a)->'a" |
15 "fix" :: "('a->'a)->'a" |
15 adm :: "('a::cpo=>bool)=>bool" |
16 adm :: "('a::cpo=>bool)=>bool" |
16 admw :: "('a=>bool)=>bool" |
17 admw :: "('a=>bool)=>bool" |
17 |
18 |
18 primrec |
19 primrec |
19 iterate_0 "iterate 0 F x = x" |
20 iterate_0: "iterate 0 F x = x" |
20 iterate_Suc "iterate (Suc n) F x = F$(iterate n F x)" |
21 iterate_Suc: "iterate (Suc n) F x = F$(iterate n F x)" |
21 |
22 |
22 defs |
23 defs |
23 |
24 |
24 Ifix_def "Ifix F == lub(range(%i. iterate i F UU))" |
25 Ifix_def: "Ifix F == lub(range(%i. iterate i F UU))" |
25 fix_def "fix == (LAM f. Ifix f)" |
26 fix_def: "fix == (LAM f. Ifix f)" |
26 |
27 |
27 adm_def "adm P == !Y. chain(Y) --> |
28 adm_def: "adm P == !Y. chain(Y) --> |
28 (!i. P(Y i)) --> P(lub(range Y))" |
29 (!i. P(Y i)) --> P(lub(range Y))" |
29 |
30 |
30 admw_def "admw P == !F. (!n. P (iterate n F UU)) --> |
31 admw_def: "admw P == !F. (!n. P (iterate n F UU)) --> |
31 P (lub(range (%i. iterate i F UU)))" |
32 P (lub(range (%i. iterate i F UU)))" |
32 |
33 |
|
34 (* Title: HOLCF/Fix.ML |
|
35 ID: $Id$ |
|
36 Author: Franz Regensburger |
|
37 License: GPL (GNU GENERAL PUBLIC LICENSE) |
|
38 |
|
39 fixed point operator and admissibility |
|
40 *) |
|
41 |
|
42 (* ------------------------------------------------------------------------ *) |
|
43 (* derive inductive properties of iterate from primitive recursion *) |
|
44 (* ------------------------------------------------------------------------ *) |
|
45 |
|
46 lemma iterate_Suc2: "iterate (Suc n) F x = iterate n F (F$x)" |
|
47 apply (induct_tac "n") |
|
48 apply auto |
|
49 done |
|
50 |
|
51 (* ------------------------------------------------------------------------ *) |
|
52 (* the sequence of function itertaions is a chain *) |
|
53 (* This property is essential since monotonicity of iterate makes no sense *) |
|
54 (* ------------------------------------------------------------------------ *) |
|
55 |
|
56 lemma chain_iterate2: "x << F$x ==> chain (%i. iterate i F x)" |
|
57 |
|
58 apply (unfold chain_def) |
|
59 apply (intro strip) |
|
60 apply (induct_tac "i") |
|
61 apply auto |
|
62 apply (erule monofun_cfun_arg) |
|
63 done |
|
64 |
|
65 |
|
66 lemma chain_iterate: "chain (%i. iterate i F UU)" |
|
67 apply (rule chain_iterate2) |
|
68 apply (rule minimal) |
|
69 done |
|
70 |
|
71 |
|
72 (* ------------------------------------------------------------------------ *) |
|
73 (* Kleene's fixed point theorems for continuous functions in pointed *) |
|
74 (* omega cpo's *) |
|
75 (* ------------------------------------------------------------------------ *) |
|
76 |
|
77 |
|
78 lemma Ifix_eq: "Ifix F =F$(Ifix F)" |
|
79 |
|
80 |
|
81 apply (unfold Ifix_def) |
|
82 apply (subst contlub_cfun_arg) |
|
83 apply (rule chain_iterate) |
|
84 apply (rule antisym_less) |
|
85 apply (rule lub_mono) |
|
86 apply (rule chain_iterate) |
|
87 apply (rule ch2ch_Rep_CFunR) |
|
88 apply (rule chain_iterate) |
|
89 apply (rule allI) |
|
90 apply (rule iterate_Suc [THEN subst]) |
|
91 apply (rule chain_iterate [THEN chainE]) |
|
92 apply (rule is_lub_thelub) |
|
93 apply (rule ch2ch_Rep_CFunR) |
|
94 apply (rule chain_iterate) |
|
95 apply (rule ub_rangeI) |
|
96 apply (rule iterate_Suc [THEN subst]) |
|
97 apply (rule is_ub_thelub) |
|
98 apply (rule chain_iterate) |
|
99 done |
|
100 |
|
101 |
|
102 lemma Ifix_least: "F$x=x ==> Ifix(F) << x" |
|
103 |
|
104 apply (unfold Ifix_def) |
|
105 apply (rule is_lub_thelub) |
|
106 apply (rule chain_iterate) |
|
107 apply (rule ub_rangeI) |
|
108 apply (induct_tac "i") |
|
109 apply (simp (no_asm_simp)) |
|
110 apply (simp (no_asm_simp)) |
|
111 apply (rule_tac t = "x" in subst) |
|
112 apply assumption |
|
113 apply (erule monofun_cfun_arg) |
|
114 done |
|
115 |
|
116 |
|
117 (* ------------------------------------------------------------------------ *) |
|
118 (* monotonicity and continuity of iterate *) |
|
119 (* ------------------------------------------------------------------------ *) |
|
120 |
|
121 lemma monofun_iterate: "monofun(iterate(i))" |
|
122 apply (unfold monofun) |
|
123 apply (intro strip) |
|
124 apply (induct_tac "i") |
|
125 apply (simp (no_asm_simp)) |
|
126 apply (simp add: less_fun monofun_cfun) |
|
127 done |
|
128 |
|
129 (* ------------------------------------------------------------------------ *) |
|
130 (* the following lemma uses contlub_cfun which itself is based on a *) |
|
131 (* diagonalisation lemma for continuous functions with two arguments. *) |
|
132 (* In this special case it is the application function Rep_CFun *) |
|
133 (* ------------------------------------------------------------------------ *) |
|
134 |
|
135 lemma contlub_iterate: "contlub(iterate(i))" |
|
136 |
|
137 apply (unfold contlub) |
|
138 apply (intro strip) |
|
139 apply (induct_tac "i") |
|
140 apply (simp (no_asm_simp)) |
|
141 apply (rule lub_const [THEN thelubI, symmetric]) |
|
142 apply (simp (no_asm_simp) del: range_composition) |
|
143 apply (rule ext) |
|
144 apply (simplesubst thelub_fun) |
|
145 apply (rule chainI) |
|
146 apply (rule less_fun [THEN iffD2]) |
|
147 apply (rule allI) |
|
148 apply (rule chainE) |
|
149 apply (rule monofun_Rep_CFun1 [THEN ch2ch_MF2LR]) |
|
150 apply (rule allI) |
|
151 apply (rule monofun_Rep_CFun2) |
|
152 apply assumption |
|
153 apply (rule ch2ch_fun) |
|
154 apply (rule monofun_iterate [THEN ch2ch_monofun]) |
|
155 apply assumption |
|
156 apply (subst thelub_fun) |
|
157 apply (rule monofun_iterate [THEN ch2ch_monofun]) |
|
158 apply assumption |
|
159 apply (rule contlub_cfun) |
|
160 apply assumption |
|
161 apply (erule monofun_iterate [THEN ch2ch_monofun, THEN ch2ch_fun]) |
|
162 done |
|
163 |
|
164 |
|
165 lemma cont_iterate: "cont(iterate(i))" |
|
166 apply (rule monocontlub2cont) |
|
167 apply (rule monofun_iterate) |
|
168 apply (rule contlub_iterate) |
|
169 done |
|
170 |
|
171 (* ------------------------------------------------------------------------ *) |
|
172 (* a lemma about continuity of iterate in its third argument *) |
|
173 (* ------------------------------------------------------------------------ *) |
|
174 |
|
175 lemma monofun_iterate2: "monofun(iterate n F)" |
|
176 apply (rule monofunI) |
|
177 apply (intro strip) |
|
178 apply (induct_tac "n") |
|
179 apply (simp (no_asm_simp)) |
|
180 apply (simp (no_asm_simp)) |
|
181 apply (erule monofun_cfun_arg) |
|
182 done |
|
183 |
|
184 lemma contlub_iterate2: "contlub(iterate n F)" |
|
185 apply (rule contlubI) |
|
186 apply (intro strip) |
|
187 apply (induct_tac "n") |
|
188 apply (simp (no_asm)) |
|
189 apply (simp (no_asm)) |
|
190 apply (rule_tac t = "iterate n F (lub (range (%u. Y u))) " and s = "lub (range (%i. iterate n F (Y i))) " in ssubst) |
|
191 apply assumption |
|
192 apply (rule contlub_cfun_arg) |
|
193 apply (erule monofun_iterate2 [THEN ch2ch_monofun]) |
|
194 done |
|
195 |
|
196 lemma cont_iterate2: "cont (iterate n F)" |
|
197 apply (rule monocontlub2cont) |
|
198 apply (rule monofun_iterate2) |
|
199 apply (rule contlub_iterate2) |
|
200 done |
|
201 |
|
202 (* ------------------------------------------------------------------------ *) |
|
203 (* monotonicity and continuity of Ifix *) |
|
204 (* ------------------------------------------------------------------------ *) |
|
205 |
|
206 lemma monofun_Ifix: "monofun(Ifix)" |
|
207 |
|
208 apply (unfold monofun Ifix_def) |
|
209 apply (intro strip) |
|
210 apply (rule lub_mono) |
|
211 apply (rule chain_iterate) |
|
212 apply (rule chain_iterate) |
|
213 apply (rule allI) |
|
214 apply (rule less_fun [THEN iffD1, THEN spec], erule monofun_iterate [THEN monofunE, THEN spec, THEN spec, THEN mp]) |
|
215 done |
|
216 |
|
217 (* ------------------------------------------------------------------------ *) |
|
218 (* since iterate is not monotone in its first argument, special lemmas must *) |
|
219 (* be derived for lubs in this argument *) |
|
220 (* ------------------------------------------------------------------------ *) |
|
221 |
|
222 lemma chain_iterate_lub: |
|
223 "chain(Y) ==> chain(%i. lub(range(%ia. iterate ia (Y i) UU)))" |
|
224 apply (rule chainI) |
|
225 apply (rule lub_mono) |
|
226 apply (rule chain_iterate) |
|
227 apply (rule chain_iterate) |
|
228 apply (intro strip) |
|
229 apply (erule monofun_iterate [THEN ch2ch_monofun, THEN ch2ch_fun, THEN chainE]) |
|
230 done |
|
231 |
|
232 (* ------------------------------------------------------------------------ *) |
|
233 (* this exchange lemma is analog to the one for monotone functions *) |
|
234 (* observe that monotonicity is not really needed. The propagation of *) |
|
235 (* chains is the essential argument which is usually derived from monot. *) |
|
236 (* ------------------------------------------------------------------------ *) |
|
237 |
|
238 lemma contlub_Ifix_lemma1: "chain(Y) ==>iterate n (lub(range Y)) y = lub(range(%i. iterate n (Y i) y))" |
|
239 apply (rule thelub_fun [THEN subst]) |
|
240 apply (erule monofun_iterate [THEN ch2ch_monofun]) |
|
241 apply (simp (no_asm_simp) add: contlub_iterate [THEN contlubE]) |
|
242 done |
|
243 |
|
244 |
|
245 lemma ex_lub_iterate: "chain(Y) ==> |
|
246 lub(range(%i. lub(range(%ia. iterate i (Y ia) UU)))) = |
|
247 lub(range(%i. lub(range(%ia. iterate ia (Y i) UU))))" |
|
248 apply (rule antisym_less) |
|
249 apply (rule is_lub_thelub) |
|
250 apply (rule contlub_Ifix_lemma1 [THEN ext, THEN subst]) |
|
251 apply assumption |
|
252 apply (rule chain_iterate) |
|
253 apply (rule ub_rangeI) |
|
254 apply (rule lub_mono) |
|
255 apply (erule monofun_iterate [THEN ch2ch_monofun, THEN ch2ch_fun]) |
|
256 apply (erule chain_iterate_lub) |
|
257 apply (intro strip) |
|
258 apply (rule is_ub_thelub) |
|
259 apply (rule chain_iterate) |
|
260 apply (rule is_lub_thelub) |
|
261 apply (erule chain_iterate_lub) |
|
262 apply (rule ub_rangeI) |
|
263 apply (rule lub_mono) |
|
264 apply (rule chain_iterate) |
|
265 apply (rule contlub_Ifix_lemma1 [THEN ext, THEN subst]) |
|
266 apply assumption |
|
267 apply (rule chain_iterate) |
|
268 apply (intro strip) |
|
269 apply (rule is_ub_thelub) |
|
270 apply (erule monofun_iterate [THEN ch2ch_monofun, THEN ch2ch_fun]) |
|
271 done |
|
272 |
|
273 |
|
274 lemma contlub_Ifix: "contlub(Ifix)" |
|
275 |
|
276 apply (unfold contlub Ifix_def) |
|
277 apply (intro strip) |
|
278 apply (subst contlub_Ifix_lemma1 [THEN ext]) |
|
279 apply assumption |
|
280 apply (erule ex_lub_iterate) |
|
281 done |
|
282 |
|
283 |
|
284 lemma cont_Ifix: "cont(Ifix)" |
|
285 apply (rule monocontlub2cont) |
|
286 apply (rule monofun_Ifix) |
|
287 apply (rule contlub_Ifix) |
|
288 done |
|
289 |
|
290 (* ------------------------------------------------------------------------ *) |
|
291 (* propagate properties of Ifix to its continuous counterpart *) |
|
292 (* ------------------------------------------------------------------------ *) |
|
293 |
|
294 lemma fix_eq: "fix$F = F$(fix$F)" |
|
295 |
|
296 apply (unfold fix_def) |
|
297 apply (simp (no_asm_simp) add: cont_Ifix) |
|
298 apply (rule Ifix_eq) |
|
299 done |
|
300 |
|
301 lemma fix_least: "F$x = x ==> fix$F << x" |
|
302 apply (unfold fix_def) |
|
303 apply (simp (no_asm_simp) add: cont_Ifix) |
|
304 apply (erule Ifix_least) |
|
305 done |
|
306 |
|
307 |
|
308 lemma fix_eqI: |
|
309 "[| F$x = x; !z. F$z = z --> x << z |] ==> x = fix$F" |
|
310 apply (rule antisym_less) |
|
311 apply (erule allE) |
|
312 apply (erule mp) |
|
313 apply (rule fix_eq [symmetric]) |
|
314 apply (erule fix_least) |
|
315 done |
|
316 |
|
317 |
|
318 lemma fix_eq2: "f == fix$F ==> f = F$f" |
|
319 apply (simp (no_asm_simp) add: fix_eq [symmetric]) |
|
320 done |
|
321 |
|
322 lemma fix_eq3: "f == fix$F ==> f$x = F$f$x" |
|
323 apply (erule fix_eq2 [THEN cfun_fun_cong]) |
|
324 done |
|
325 |
|
326 (* fun fix_tac3 thm i = ((rtac trans i) THEN (rtac (thm RS fix_eq3) i)) *) |
|
327 |
|
328 lemma fix_eq4: "f = fix$F ==> f = F$f" |
|
329 apply (erule ssubst) |
|
330 apply (rule fix_eq) |
|
331 done |
|
332 |
|
333 lemma fix_eq5: "f = fix$F ==> f$x = F$f$x" |
|
334 apply (rule trans) |
|
335 apply (erule fix_eq4 [THEN cfun_fun_cong]) |
|
336 apply (rule refl) |
|
337 done |
|
338 |
|
339 (* fun fix_tac5 thm i = ((rtac trans i) THEN (rtac (thm RS fix_eq5) i)) *) |
|
340 |
|
341 (* proves the unfolding theorem for function equations f = fix$... *) |
|
342 (* |
|
343 fun fix_prover thy fixeq s = prove_goal thy s (fn prems => [ |
|
344 (rtac trans 1), |
|
345 (rtac (fixeq RS fix_eq4) 1), |
|
346 (rtac trans 1), |
|
347 (rtac beta_cfun 1), |
|
348 (Simp_tac 1) |
|
349 ]) |
|
350 *) |
|
351 (* proves the unfolding theorem for function definitions f == fix$... *) |
|
352 (* |
|
353 fun fix_prover2 thy fixdef s = prove_goal thy s (fn prems => [ |
|
354 (rtac trans 1), |
|
355 (rtac (fix_eq2) 1), |
|
356 (rtac fixdef 1), |
|
357 (rtac beta_cfun 1), |
|
358 (Simp_tac 1) |
|
359 ]) |
|
360 *) |
|
361 (* proves an application case for a function from its unfolding thm *) |
|
362 (* |
|
363 fun case_prover thy unfold s = prove_goal thy s (fn prems => [ |
|
364 (cut_facts_tac prems 1), |
|
365 (rtac trans 1), |
|
366 (stac unfold 1), |
|
367 Auto_tac |
|
368 ]) |
|
369 *) |
|
370 (* ------------------------------------------------------------------------ *) |
|
371 (* better access to definitions *) |
|
372 (* ------------------------------------------------------------------------ *) |
|
373 |
|
374 |
|
375 lemma Ifix_def2: "Ifix=(%x. lub(range(%i. iterate i x UU)))" |
|
376 apply (rule ext) |
|
377 apply (unfold Ifix_def) |
|
378 apply (rule refl) |
|
379 done |
|
380 |
|
381 (* ------------------------------------------------------------------------ *) |
|
382 (* direct connection between fix and iteration without Ifix *) |
|
383 (* ------------------------------------------------------------------------ *) |
|
384 |
|
385 lemma fix_def2: "fix$F = lub(range(%i. iterate i F UU))" |
|
386 apply (unfold fix_def) |
|
387 apply (fold Ifix_def) |
|
388 apply (simp (no_asm_simp) add: cont_Ifix) |
|
389 done |
|
390 |
|
391 |
|
392 (* ------------------------------------------------------------------------ *) |
|
393 (* Lemmas about admissibility and fixed point induction *) |
|
394 (* ------------------------------------------------------------------------ *) |
|
395 |
|
396 (* ------------------------------------------------------------------------ *) |
|
397 (* access to definitions *) |
|
398 (* ------------------------------------------------------------------------ *) |
|
399 |
|
400 lemma admI: |
|
401 "(!!Y. [| chain Y; !i. P (Y i) |] ==> P (lub (range Y))) ==> adm P" |
|
402 apply (unfold adm_def) |
|
403 apply blast |
|
404 done |
|
405 |
|
406 lemma triv_admI: "!x. P x ==> adm P" |
|
407 apply (rule admI) |
|
408 apply (erule spec) |
|
409 done |
|
410 |
|
411 lemma admD: "[| adm(P); chain(Y); !i. P(Y(i)) |] ==> P(lub(range(Y)))" |
|
412 apply (unfold adm_def) |
|
413 apply blast |
|
414 done |
|
415 |
|
416 lemma admw_def2: "admw(P) = (!F.(!n. P(iterate n F UU)) --> |
|
417 P (lub(range(%i. iterate i F UU))))" |
|
418 apply (unfold admw_def) |
|
419 apply (rule refl) |
|
420 done |
|
421 |
|
422 (* ------------------------------------------------------------------------ *) |
|
423 (* an admissible formula is also weak admissible *) |
|
424 (* ------------------------------------------------------------------------ *) |
|
425 |
|
426 lemma adm_impl_admw: "adm(P)==>admw(P)" |
|
427 apply (unfold admw_def) |
|
428 apply (intro strip) |
|
429 apply (erule admD) |
|
430 apply (rule chain_iterate) |
|
431 apply assumption |
|
432 done |
|
433 |
|
434 (* ------------------------------------------------------------------------ *) |
|
435 (* fixed point induction *) |
|
436 (* ------------------------------------------------------------------------ *) |
|
437 |
|
438 lemma fix_ind: |
|
439 "[| adm(P); P(UU); !!x. P(x) ==> P(F$x)|] ==> P(fix$F)" |
|
440 apply (subst fix_def2) |
|
441 apply (erule admD) |
|
442 apply (rule chain_iterate) |
|
443 apply (rule allI) |
|
444 apply (induct_tac "i") |
|
445 apply simp |
|
446 apply simp |
|
447 done |
|
448 |
|
449 lemma def_fix_ind: "[| f == fix$F; adm(P); |
|
450 P(UU); !!x. P(x) ==> P(F$x)|] ==> P f" |
|
451 apply simp |
|
452 apply (erule fix_ind) |
|
453 apply assumption |
|
454 apply fast |
|
455 done |
|
456 |
|
457 (* ------------------------------------------------------------------------ *) |
|
458 (* computational induction for weak admissible formulae *) |
|
459 (* ------------------------------------------------------------------------ *) |
|
460 |
|
461 lemma wfix_ind: "[| admw(P); !n. P(iterate n F UU)|] ==> P(fix$F)" |
|
462 apply (subst fix_def2) |
|
463 apply (rule admw_def2 [THEN iffD1, THEN spec, THEN mp]) |
|
464 apply assumption |
|
465 apply (rule allI) |
|
466 apply (erule spec) |
|
467 done |
|
468 |
|
469 lemma def_wfix_ind: "[| f == fix$F; admw(P); |
|
470 !n. P(iterate n F UU) |] ==> P f" |
|
471 apply simp |
|
472 apply (erule wfix_ind) |
|
473 apply assumption |
|
474 done |
|
475 |
|
476 (* ------------------------------------------------------------------------ *) |
|
477 (* for chain-finite (easy) types every formula is admissible *) |
|
478 (* ------------------------------------------------------------------------ *) |
|
479 |
|
480 lemma adm_max_in_chain: |
|
481 "!Y. chain(Y::nat=>'a) --> (? n. max_in_chain n Y) ==> adm(P::'a=>bool)" |
|
482 apply (unfold adm_def) |
|
483 apply (intro strip) |
|
484 apply (rule exE) |
|
485 apply (rule mp) |
|
486 apply (erule spec) |
|
487 apply assumption |
|
488 apply (subst lub_finch1 [THEN thelubI]) |
|
489 apply assumption |
|
490 apply assumption |
|
491 apply (erule spec) |
|
492 done |
|
493 |
|
494 lemmas adm_chfin = chfin [THEN adm_max_in_chain, standard] |
|
495 |
|
496 (* ------------------------------------------------------------------------ *) |
|
497 (* some lemmata for functions with flat/chfin domain/range types *) |
|
498 (* ------------------------------------------------------------------------ *) |
|
499 |
|
500 lemma adm_chfindom: "adm (%(u::'a::cpo->'b::chfin). P(u$s))" |
|
501 apply (unfold adm_def) |
|
502 apply (intro strip) |
|
503 apply (drule chfin_Rep_CFunR) |
|
504 apply (erule_tac x = "s" in allE) |
|
505 apply clarsimp |
|
506 done |
|
507 |
|
508 (* adm_flat not needed any more, since it is a special case of adm_chfindom *) |
|
509 |
|
510 (* ------------------------------------------------------------------------ *) |
|
511 (* improved admisibility introduction *) |
|
512 (* ------------------------------------------------------------------------ *) |
|
513 |
|
514 lemma admI2: |
|
515 "(!!Y. [| chain Y; !i. P (Y i); !i. ? j. i < j & Y i ~= Y j & Y i << Y j |] |
|
516 ==> P(lub (range Y))) ==> adm P" |
|
517 apply (unfold adm_def) |
|
518 apply (intro strip) |
|
519 apply (erule increasing_chain_adm_lemma) |
|
520 apply assumption |
|
521 apply fast |
|
522 done |
|
523 |
|
524 |
|
525 (* ------------------------------------------------------------------------ *) |
|
526 (* admissibility of special formulae and propagation *) |
|
527 (* ------------------------------------------------------------------------ *) |
|
528 |
|
529 lemma adm_less: "[|cont u;cont v|]==> adm(%x. u x << v x)" |
|
530 apply (unfold adm_def) |
|
531 apply (intro strip) |
|
532 apply (frule_tac f = "u" in cont2mono [THEN ch2ch_monofun]) |
|
533 apply assumption |
|
534 apply (frule_tac f = "v" in cont2mono [THEN ch2ch_monofun]) |
|
535 apply assumption |
|
536 apply (erule cont2contlub [THEN contlubE, THEN spec, THEN mp, THEN ssubst]) |
|
537 apply assumption |
|
538 apply (erule cont2contlub [THEN contlubE, THEN spec, THEN mp, THEN ssubst]) |
|
539 apply assumption |
|
540 apply (blast intro: lub_mono) |
|
541 done |
|
542 declare adm_less [simp] |
|
543 |
|
544 lemma adm_conj: "[| adm P; adm Q |] ==> adm(%x. P x & Q x)" |
|
545 apply (fast elim: admD intro: admI) |
|
546 done |
|
547 declare adm_conj [simp] |
|
548 |
|
549 lemma adm_not_free: "adm(%x. t)" |
|
550 apply (unfold adm_def) |
|
551 apply fast |
|
552 done |
|
553 declare adm_not_free [simp] |
|
554 |
|
555 lemma adm_not_less: "cont t ==> adm(%x.~ (t x) << u)" |
|
556 apply (unfold adm_def) |
|
557 apply (intro strip) |
|
558 apply (rule contrapos_nn) |
|
559 apply (erule spec) |
|
560 apply (rule trans_less) |
|
561 prefer 2 apply (assumption) |
|
562 apply (erule cont2mono [THEN monofun_fun_arg]) |
|
563 apply (rule is_ub_thelub) |
|
564 apply assumption |
|
565 done |
|
566 |
|
567 lemma adm_all: "!y. adm(P y) ==> adm(%x.!y. P y x)" |
|
568 apply (fast intro: admI elim: admD) |
|
569 done |
|
570 |
|
571 lemmas adm_all2 = allI [THEN adm_all, standard] |
|
572 |
|
573 lemma adm_subst: "[|cont t; adm P|] ==> adm(%x. P (t x))" |
|
574 apply (rule admI) |
|
575 apply (simplesubst cont2contlub [THEN contlubE, THEN spec, THEN mp]) |
|
576 apply assumption |
|
577 apply assumption |
|
578 apply (erule admD) |
|
579 apply (erule cont2mono [THEN ch2ch_monofun]) |
|
580 apply assumption |
|
581 apply assumption |
|
582 done |
|
583 |
|
584 lemma adm_UU_not_less: "adm(%x.~ UU << t(x))" |
|
585 apply (simp (no_asm)) |
|
586 done |
|
587 |
|
588 |
|
589 lemma adm_not_UU: "cont(t)==> adm(%x.~ (t x) = UU)" |
|
590 |
|
591 apply (unfold adm_def) |
|
592 apply (intro strip) |
|
593 apply (rule contrapos_nn) |
|
594 apply (erule spec) |
|
595 apply (rule chain_UU_I [THEN spec]) |
|
596 apply (erule cont2mono [THEN ch2ch_monofun]) |
|
597 apply assumption |
|
598 apply (erule cont2contlub [THEN contlubE, THEN spec, THEN mp, THEN subst]) |
|
599 apply assumption |
|
600 apply assumption |
|
601 done |
|
602 |
|
603 lemma adm_eq: "[|cont u ; cont v|]==> adm(%x. u x = v x)" |
|
604 apply (simp (no_asm_simp) add: po_eq_conv) |
|
605 done |
|
606 |
|
607 |
|
608 |
|
609 (* ------------------------------------------------------------------------ *) |
|
610 (* admissibility for disjunction is hard to prove. It takes 10 Lemmas *) |
|
611 (* ------------------------------------------------------------------------ *) |
|
612 |
|
613 |
|
614 lemma adm_disj_lemma1: "!n. P(Y n)|Q(Y n) ==> (? i.!j. R i j --> Q(Y(j))) | (!i.? j. R i j & P(Y(j)))" |
|
615 apply fast |
|
616 done |
|
617 |
|
618 lemma adm_disj_lemma2: "[| adm(Q); ? X. chain(X) & (!n. Q(X(n))) & |
|
619 lub(range(Y))=lub(range(X))|] ==> Q(lub(range(Y)))" |
|
620 apply (force elim: admD) |
|
621 done |
|
622 |
|
623 lemma adm_disj_lemma3: "chain Y ==> chain (%m. if m < Suc i then Y (Suc i) else Y m)" |
|
624 apply (unfold chain_def) |
|
625 apply (simp (no_asm_simp)) |
|
626 apply safe |
|
627 apply (subgoal_tac "ia = i") |
|
628 apply (simp_all (no_asm_simp)) |
|
629 done |
|
630 |
|
631 lemma adm_disj_lemma4: "!j. i < j --> Q(Y(j)) ==> !n. Q( if n < Suc i then Y(Suc i) else Y n)" |
|
632 apply (simp (no_asm_simp)) |
|
633 done |
|
634 |
|
635 lemma adm_disj_lemma5: |
|
636 "!!Y::nat=>'a::cpo. [| chain(Y); ! j. i < j --> Q(Y(j)) |] ==> |
|
637 lub(range(Y)) = lub(range(%m. if m< Suc(i) then Y(Suc(i)) else Y m))" |
|
638 apply (safe intro!: lub_equal2 adm_disj_lemma3) |
|
639 prefer 2 apply (assumption) |
|
640 apply (rule_tac x = "i" in exI) |
|
641 apply (simp (no_asm_simp)) |
|
642 done |
|
643 |
|
644 lemma adm_disj_lemma6: |
|
645 "[| chain(Y::nat=>'a::cpo); ? i. ! j. i < j --> Q(Y(j)) |] ==> |
|
646 ? X. chain(X) & (! n. Q(X(n))) & lub(range(Y)) = lub(range(X))" |
|
647 apply (erule exE) |
|
648 apply (rule_tac x = "%m. if m<Suc (i) then Y (Suc (i)) else Y m" in exI) |
|
649 apply (rule conjI) |
|
650 apply (rule adm_disj_lemma3) |
|
651 apply assumption |
|
652 apply (rule conjI) |
|
653 apply (rule adm_disj_lemma4) |
|
654 apply assumption |
|
655 apply (rule adm_disj_lemma5) |
|
656 apply assumption |
|
657 apply assumption |
|
658 done |
|
659 |
|
660 lemma adm_disj_lemma7: |
|
661 "[| chain(Y::nat=>'a::cpo); ! i. ? j. i < j & P(Y(j)) |] ==> |
|
662 chain(%m. Y(Least(%j. m<j & P(Y(j)))))" |
|
663 apply (rule chainI) |
|
664 apply (rule chain_mono3) |
|
665 apply assumption |
|
666 apply (rule Least_le) |
|
667 apply (rule conjI) |
|
668 apply (rule Suc_lessD) |
|
669 apply (erule allE) |
|
670 apply (erule exE) |
|
671 apply (rule LeastI [THEN conjunct1]) |
|
672 apply assumption |
|
673 apply (erule allE) |
|
674 apply (erule exE) |
|
675 apply (rule LeastI [THEN conjunct2]) |
|
676 apply assumption |
|
677 done |
|
678 |
|
679 lemma adm_disj_lemma8: |
|
680 "[| ! i. ? j. i < j & P(Y(j)) |] ==> ! m. P(Y(LEAST j::nat. m<j & P(Y(j))))" |
|
681 apply (intro strip) |
|
682 apply (erule allE) |
|
683 apply (erule exE) |
|
684 apply (erule LeastI [THEN conjunct2]) |
|
685 done |
|
686 |
|
687 lemma adm_disj_lemma9: |
|
688 "[| chain(Y::nat=>'a::cpo); ! i. ? j. i < j & P(Y(j)) |] ==> |
|
689 lub(range(Y)) = lub(range(%m. Y(Least(%j. m<j & P(Y(j))))))" |
|
690 apply (rule antisym_less) |
|
691 apply (rule lub_mono) |
|
692 apply assumption |
|
693 apply (rule adm_disj_lemma7) |
|
694 apply assumption |
|
695 apply assumption |
|
696 apply (intro strip) |
|
697 apply (rule chain_mono) |
|
698 apply assumption |
|
699 apply (erule allE) |
|
700 apply (erule exE) |
|
701 apply (rule LeastI [THEN conjunct1]) |
|
702 apply assumption |
|
703 apply (rule lub_mono3) |
|
704 apply (rule adm_disj_lemma7) |
|
705 apply assumption |
|
706 apply assumption |
|
707 apply assumption |
|
708 apply (intro strip) |
|
709 apply (rule exI) |
|
710 apply (rule chain_mono) |
|
711 apply assumption |
|
712 apply (rule lessI) |
|
713 done |
|
714 |
|
715 lemma adm_disj_lemma10: "[| chain(Y::nat=>'a::cpo); ! i. ? j. i < j & P(Y(j)) |] ==> |
|
716 ? X. chain(X) & (! n. P(X(n))) & lub(range(Y)) = lub(range(X))" |
|
717 apply (rule_tac x = "%m. Y (Least (%j. m<j & P (Y (j))))" in exI) |
|
718 apply (rule conjI) |
|
719 apply (rule adm_disj_lemma7) |
|
720 apply assumption |
|
721 apply assumption |
|
722 apply (rule conjI) |
|
723 apply (rule adm_disj_lemma8) |
|
724 apply assumption |
|
725 apply (rule adm_disj_lemma9) |
|
726 apply assumption |
|
727 apply assumption |
|
728 done |
|
729 |
|
730 lemma adm_disj_lemma12: "[| adm(P); chain(Y);? i. ! j. i < j --> P(Y(j))|]==>P(lub(range(Y)))" |
|
731 apply (erule adm_disj_lemma2) |
|
732 apply (erule adm_disj_lemma6) |
|
733 apply assumption |
|
734 done |
|
735 |
|
736 |
|
737 lemma adm_lemma11: |
|
738 "[| adm(P); chain(Y); ! i. ? j. i < j & P(Y(j)) |]==>P(lub(range(Y)))" |
|
739 apply (erule adm_disj_lemma2) |
|
740 apply (erule adm_disj_lemma10) |
|
741 apply assumption |
|
742 done |
|
743 |
|
744 lemma adm_disj: "[| adm P; adm Q |] ==> adm(%x. P x | Q x)" |
|
745 apply (rule admI) |
|
746 apply (rule adm_disj_lemma1 [THEN disjE]) |
|
747 apply assumption |
|
748 apply (rule disjI2) |
|
749 apply (erule adm_disj_lemma12) |
|
750 apply assumption |
|
751 apply assumption |
|
752 apply (rule disjI1) |
|
753 apply (erule adm_lemma11) |
|
754 apply assumption |
|
755 apply assumption |
|
756 done |
|
757 |
|
758 lemma adm_imp: "[| adm(%x.~(P x)); adm Q |] ==> adm(%x. P x --> Q x)" |
|
759 apply (subgoal_tac " (%x. P x --> Q x) = (%x. ~P x | Q x) ") |
|
760 apply (erule ssubst) |
|
761 apply (erule adm_disj) |
|
762 apply assumption |
|
763 apply (simp (no_asm)) |
|
764 done |
|
765 |
|
766 lemma adm_iff: "[| adm (%x. P x --> Q x); adm (%x. Q x --> P x) |] |
|
767 ==> adm (%x. P x = Q x)" |
|
768 apply (subgoal_tac " (%x. P x = Q x) = (%x. (P x --> Q x) & (Q x --> P x))") |
|
769 apply (simp (no_asm_simp)) |
|
770 apply (rule ext) |
|
771 apply fast |
|
772 done |
|
773 |
|
774 |
|
775 lemma adm_not_conj: "[| adm (%x. ~ P x); adm (%x. ~ Q x) |] ==> adm (%x. ~ (P x & Q x))" |
|
776 apply (subgoal_tac " (%x. ~ (P x & Q x)) = (%x. ~ P x | ~ Q x) ") |
|
777 apply (rule_tac [2] ext) |
|
778 prefer 2 apply fast |
|
779 apply (erule ssubst) |
|
780 apply (erule adm_disj) |
|
781 apply assumption |
|
782 done |
|
783 |
|
784 lemmas adm_lemmas = adm_not_free adm_imp adm_disj adm_eq adm_not_UU |
|
785 adm_UU_not_less adm_all2 adm_not_less adm_not_conj adm_iff |
|
786 |
|
787 declare adm_lemmas [simp] |
|
788 |
33 end |
789 end |
34 |
790 |