equal
deleted
inserted
replaced
54 apply (fast dest: le_imp_less_or_eq elim: chain_mono_less) |
54 apply (fast dest: le_imp_less_or_eq elim: chain_mono_less) |
55 done |
55 done |
56 |
56 |
57 lemma flatstream_adm_lemma: |
57 lemma flatstream_adm_lemma: |
58 assumes 1: "Porder.chain Y" |
58 assumes 1: "Porder.chain Y" |
59 assumes 2: "!i. P (Y i)" |
59 assumes 2: "\<forall>i. P (Y i)" |
60 assumes 3: "(!!Y. [| Porder.chain Y; !i. P (Y i); !k. ? j. enat k < #((Y j)::'a::flat stream)|] |
60 assumes 3: "(\<And>Y. [| Porder.chain Y; \<forall>i. P (Y i); \<forall>k. \<exists>j. enat k < #((Y j)::'a::flat stream)|] |
61 ==> P(LUB i. Y i))" |
61 ==> P(LUB i. Y i))" |
62 shows "P(LUB i. Y i)" |
62 shows "P(LUB i. Y i)" |
63 apply (rule increasing_chain_adm_lemma [OF 1 2]) |
63 apply (rule increasing_chain_adm_lemma [OF 1 2]) |
64 apply (erule 3, assumption) |
64 apply (erule 3, assumption) |
65 apply (erule thin_rl) |
65 apply (erule thin_rl) |
66 apply (rule allI) |
66 apply (rule allI) |
67 apply (case_tac "!j. stream_finite (Y j)") |
67 apply (case_tac "\<forall>j. stream_finite (Y j)") |
68 apply ( rule chain_incr) |
68 apply ( rule chain_incr) |
69 apply ( rule allI) |
69 apply ( rule allI) |
70 apply ( drule spec) |
70 apply ( drule spec) |
71 apply ( safe) |
71 apply ( safe) |
72 apply ( rule exI) |
72 apply ( rule exI) |
76 apply ( assumption) |
76 apply ( assumption) |
77 apply (metis enat_ord_code(4) slen_infinite) |
77 apply (metis enat_ord_code(4) slen_infinite) |
78 done |
78 done |
79 |
79 |
80 (* should be without reference to stream length? *) |
80 (* should be without reference to stream length? *) |
81 lemma flatstream_admI: "[|(!!Y. [| Porder.chain Y; !i. P (Y i); |
81 lemma flatstream_admI: "[|(\<And>Y. [| Porder.chain Y; \<forall>i. P (Y i); |
82 !k. ? j. enat k < #((Y j)::'a::flat stream)|] ==> P(LUB i. Y i))|]==> adm P" |
82 \<forall>k. \<exists>j. enat k < #((Y j)::'a::flat stream)|] ==> P(LUB i. Y i))|]==> adm P" |
83 apply (unfold adm_def) |
83 apply (unfold adm_def) |
84 apply (intro strip) |
84 apply (intro strip) |
85 apply (erule (1) flatstream_adm_lemma) |
85 apply (erule (1) flatstream_adm_lemma) |
86 apply (fast) |
86 apply (fast) |
87 done |
87 done |
90 (* context (theory "Extended_Nat");*) |
90 (* context (theory "Extended_Nat");*) |
91 lemma ile_lemma: "enat (i + j) <= x ==> enat i <= x" |
91 lemma ile_lemma: "enat (i + j) <= x ==> enat i <= x" |
92 by (rule order_trans) auto |
92 by (rule order_trans) auto |
93 |
93 |
94 lemma stream_monoP2I: |
94 lemma stream_monoP2I: |
95 "!!X. stream_monoP F ==> !i. ? l. !x y. |
95 "\<And>X. stream_monoP F \<Longrightarrow> \<forall>i. \<exists>l. \<forall>x y. |
96 enat l <= #x --> (x::'a::flat stream) << y --> x:(F ^^ i) top --> y:(F ^^ i) top" |
96 enat l \<le> #x \<longrightarrow> (x::'a::flat stream) << y --> x \<in> (F ^^ i) top \<longrightarrow> y \<in> (F ^^ i) top" |
97 apply (unfold stream_monoP_def) |
97 apply (unfold stream_monoP_def) |
98 apply (safe) |
98 apply (safe) |
99 apply (rule_tac x="i*ia" in exI) |
99 apply (rule_tac x="i*ia" in exI) |
100 apply (induct_tac "ia") |
100 apply (induct_tac "ia") |
101 apply ( simp) |
101 apply ( simp) |
117 apply (erule monofun_rt_mult) |
117 apply (erule monofun_rt_mult) |
118 apply (drule (1) mp) |
118 apply (drule (1) mp) |
119 apply (assumption) |
119 apply (assumption) |
120 done |
120 done |
121 |
121 |
122 lemma stream_monoP2_gfp_admI: "[| !i. ? l. !x y. |
122 lemma stream_monoP2_gfp_admI: "[| \<forall>i. \<exists>l. \<forall>x y. |
123 enat l <= #x --> (x::'a::flat stream) << y --> x:(F ^^ i) top --> y:(F ^^ i) top; |
123 enat l \<le> #x \<longrightarrow> (x::'a::flat stream) << y \<longrightarrow> x \<in> (F ^^ i) top \<longrightarrow> y \<in> (F ^^ i) top; |
124 inf_continuous F |] ==> adm (%x. x:gfp F)" |
124 inf_continuous F |] ==> adm (\<lambda>x. x \<in> gfp F)" |
125 apply (erule inf_continuous_gfp[of F, THEN ssubst]) |
125 apply (erule inf_continuous_gfp[of F, THEN ssubst]) |
126 apply (simp (no_asm)) |
126 apply (simp (no_asm)) |
127 apply (rule adm_lemmas) |
127 apply (rule adm_lemmas) |
128 apply (rule flatstream_admI) |
128 apply (rule flatstream_admI) |
129 apply (erule allE) |
129 apply (erule allE) |
141 done |
141 done |
142 |
142 |
143 lemmas fstream_gfp_admI = stream_monoP2I [THEN stream_monoP2_gfp_admI] |
143 lemmas fstream_gfp_admI = stream_monoP2I [THEN stream_monoP2_gfp_admI] |
144 |
144 |
145 lemma stream_antiP2I: |
145 lemma stream_antiP2I: |
146 "!!X. [|stream_antiP (F::(('a::flat stream)set => ('a stream set)))|] |
146 "\<And>X. [|stream_antiP (F::(('a::flat stream)set => ('a stream set)))|] |
147 ==> !i x y. x << y --> y:(F ^^ i) top --> x:(F ^^ i) top" |
147 ==> \<forall>i x y. x << y \<longrightarrow> y \<in> (F ^^ i) top \<longrightarrow> x \<in> (F ^^ i) top" |
148 apply (unfold stream_antiP_def) |
148 apply (unfold stream_antiP_def) |
149 apply (rule allI) |
149 apply (rule allI) |
150 apply (induct_tac "i") |
150 apply (induct_tac "i") |
151 apply ( simp) |
151 apply ( simp) |
152 apply (simp) |
152 apply (simp) |
168 apply (drule (1) mp) |
168 apply (drule (1) mp) |
169 apply (assumption) |
169 apply (assumption) |
170 done |
170 done |
171 |
171 |
172 lemma stream_antiP2_non_gfp_admI: |
172 lemma stream_antiP2_non_gfp_admI: |
173 "!!X. [|!i x y. x << y --> y:(F ^^ i) top --> x:(F ^^ i) top; inf_continuous F |] |
173 "\<And>X. [|\<forall>i x y. x << y \<longrightarrow> y \<in> (F ^^ i) top \<longrightarrow> x \<in> (F ^^ i) top; inf_continuous F |] |
174 ==> adm (%u. ~ u:gfp F)" |
174 ==> adm (\<lambda>u. \<not> u \<in> gfp F)" |
175 apply (unfold adm_def) |
175 apply (unfold adm_def) |
176 apply (simp add: inf_continuous_gfp) |
176 apply (simp add: inf_continuous_gfp) |
177 apply (fast dest!: is_ub_thelub) |
177 apply (fast dest!: is_ub_thelub) |
178 done |
178 done |
179 |
179 |
183 |
183 |
184 (**new approach for adm********************************************************) |
184 (**new approach for adm********************************************************) |
185 |
185 |
186 section "antitonP" |
186 section "antitonP" |
187 |
187 |
188 lemma antitonPD: "[| antitonP P; y:P; x<<y |] ==> x:P" |
188 lemma antitonPD: "[| antitonP P; y \<in> P; x<<y |] ==> x \<in> P" |
189 apply (unfold antitonP_def) |
189 apply (unfold antitonP_def) |
190 apply auto |
190 apply auto |
191 done |
191 done |
192 |
192 |
193 lemma antitonPI: "!x y. y:P --> x<<y --> x:P ==> antitonP P" |
193 lemma antitonPI: "\<forall>x y. y \<in> P \<longrightarrow> x<<y --> x \<in> P \<Longrightarrow> antitonP P" |
194 apply (unfold antitonP_def) |
194 apply (unfold antitonP_def) |
195 apply (fast) |
195 apply (fast) |
196 done |
196 done |
197 |
197 |
198 lemma antitonP_adm_non_P: "antitonP P ==> adm (%u. u~:P)" |
198 lemma antitonP_adm_non_P: "antitonP P \<Longrightarrow> adm (\<lambda>u. u \<notin> P)" |
199 apply (unfold adm_def) |
199 apply (unfold adm_def) |
200 apply (auto dest: antitonPD elim: is_ub_thelub) |
200 apply (auto dest: antitonPD elim: is_ub_thelub) |
201 done |
201 done |
202 |
202 |
203 lemma def_gfp_adm_nonP: "P \<equiv> gfp F \<Longrightarrow> {y. \<exists>x::'a::pcpo. y \<sqsubseteq> x \<and> x \<in> P} \<subseteq> F {y. \<exists>x. y \<sqsubseteq> x \<and> x \<in> P} \<Longrightarrow> |
203 lemma def_gfp_adm_nonP: "P \<equiv> gfp F \<Longrightarrow> {y. \<exists>x::'a::pcpo. y \<sqsubseteq> x \<and> x \<in> P} \<subseteq> F {y. \<exists>x. y \<sqsubseteq> x \<and> x \<in> P} \<Longrightarrow> |
208 apply (drule gfp_upperbound) |
208 apply (drule gfp_upperbound) |
209 apply (fast) |
209 apply (fast) |
210 done |
210 done |
211 |
211 |
212 lemma adm_set: |
212 lemma adm_set: |
213 "{\<Squnion>i. Y i |Y. Porder.chain Y & (\<forall>i. Y i \<in> P)} \<subseteq> P \<Longrightarrow> adm (\<lambda>x. x\<in>P)" |
213 "{\<Squnion>i. Y i |Y. Porder.chain Y \<and> (\<forall>i. Y i \<in> P)} \<subseteq> P \<Longrightarrow> adm (\<lambda>x. x\<in>P)" |
214 apply (unfold adm_def) |
214 apply (unfold adm_def) |
215 apply (fast) |
215 apply (fast) |
216 done |
216 done |
217 |
217 |
218 lemma def_gfp_admI: "P \<equiv> gfp F \<Longrightarrow> {\<Squnion>i. Y i |Y. Porder.chain Y \<and> (\<forall>i. Y i \<in> P)} \<subseteq> |
218 lemma def_gfp_admI: "P \<equiv> gfp F \<Longrightarrow> {\<Squnion>i. Y i |Y. Porder.chain Y \<and> (\<forall>i. Y i \<in> P)} \<subseteq> |