src/HOL/HOLCF/FOCUS/Stream_adm.thy
changeset 67613 ce654b0e6d69
parent 66453 cc19f7ca2ed6
equal deleted inserted replaced
67610:4939494ed791 67613:ce654b0e6d69
    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>