22 abbreviation |
22 abbreviation |
23 bot :: "'a::order" where |
23 bot :: "'a::order" where |
24 "bot \<equiv> Sup {}" |
24 "bot \<equiv> Sup {}" |
25 |
25 |
26 lemma SUP_nat_conv: |
26 lemma SUP_nat_conv: |
27 "(SUP n::nat. M n::'a::comp_lat) = join (M 0) (SUP n. M(Suc n))" |
27 "(SUP n::nat. M n::'a::comp_lat) = sup (M 0) (SUP n. M(Suc n))" |
28 apply(rule order_antisym) |
28 apply(rule order_antisym) |
29 apply(rule SUP_leI) |
29 apply(rule SUP_leI) |
30 apply(case_tac n) |
30 apply(case_tac n) |
31 apply simp |
31 apply simp |
32 apply (blast intro:le_SUPI le_joinI2) |
32 apply (blast intro:le_SUPI le_supI2) |
33 apply(simp) |
33 apply(simp) |
34 apply (blast intro:SUP_leI le_SUPI) |
34 apply (blast intro:SUP_leI le_SUPI) |
35 done |
35 done |
36 |
36 |
37 lemma continuous_mono: fixes F :: "'a::comp_lat \<Rightarrow> 'a::comp_lat" |
37 lemma continuous_mono: fixes F :: "'a::comp_lat \<Rightarrow> 'a::comp_lat" |
38 assumes "continuous F" shows "mono F" |
38 assumes "continuous F" shows "mono F" |
39 proof |
39 proof |
40 fix A B :: "'a" assume "A <= B" |
40 fix A B :: "'a" assume "A <= B" |
41 let ?C = "%i::nat. if i=0 then A else B" |
41 let ?C = "%i::nat. if i=0 then A else B" |
42 have "chain ?C" using `A <= B` by(simp add:chain_def) |
42 have "chain ?C" using `A <= B` by(simp add:chain_def) |
43 have "F B = join (F A) (F B)" |
43 have "F B = sup (F A) (F B)" |
44 proof - |
44 proof - |
45 have "join A B = B" using `A <= B` by (simp add:join_absorp2) |
45 have "sup A B = B" using `A <= B` by (simp add:sup_absorb2) |
46 hence "F B = F(SUP i. ?C i)" by(simp add: SUP_nat_conv) |
46 hence "F B = F(SUP i. ?C i)" by(simp add: SUP_nat_conv) |
47 also have "\<dots> = (SUP i. F(?C i))" |
47 also have "\<dots> = (SUP i. F(?C i))" |
48 using `chain ?C` `continuous F` by(simp add:continuous_def) |
48 using `chain ?C` `continuous F` by(simp add:continuous_def) |
49 also have "\<dots> = join (F A) (F B)" by(simp add: SUP_nat_conv) |
49 also have "\<dots> = sup (F A) (F B)" by(simp add: SUP_nat_conv) |
50 finally show ?thesis . |
50 finally show ?thesis . |
51 qed |
51 qed |
52 thus "F A \<le> F B" by(subst le_def_join, simp) |
52 thus "F A \<le> F B" by(subst le_iff_sup, simp) |
53 qed |
53 qed |
54 |
54 |
55 lemma continuous_lfp: |
55 lemma continuous_lfp: |
56 assumes "continuous F" shows "lfp F = (SUP i. (F^i) bot)" |
56 assumes "continuous F" shows "lfp F = (SUP i. (F^i) bot)" |
57 proof - |
57 proof - |