src/HOLCF/Bifinite.thy
changeset 31076 99fe356cbbc2
parent 30729 461ee3e49ad3
child 31113 15cf300a742f
equal deleted inserted replaced
31075:a9d6cf6de9a8 31076:99fe356cbbc2
    17   assumes approx_idem: "approx i\<cdot>(approx i\<cdot>x) = approx i\<cdot>x"
    17   assumes approx_idem: "approx i\<cdot>(approx i\<cdot>x) = approx i\<cdot>x"
    18   assumes finite_fixes_approx: "finite {x. approx i\<cdot>x = x}"
    18   assumes finite_fixes_approx: "finite {x. approx i\<cdot>x = x}"
    19 
    19 
    20 class bifinite = profinite + pcpo
    20 class bifinite = profinite + pcpo
    21 
    21 
    22 lemma approx_less: "approx i\<cdot>x \<sqsubseteq> x"
    22 lemma approx_below: "approx i\<cdot>x \<sqsubseteq> x"
    23 proof -
    23 proof -
    24   have "chain (\<lambda>i. approx i\<cdot>x)" by simp
    24   have "chain (\<lambda>i. approx i\<cdot>x)" by simp
    25   hence "approx i\<cdot>x \<sqsubseteq> (\<Squnion>i. approx i\<cdot>x)" by (rule is_ub_thelub)
    25   hence "approx i\<cdot>x \<sqsubseteq> (\<Squnion>i. approx i\<cdot>x)" by (rule is_ub_thelub)
    26   thus "approx i\<cdot>x \<sqsubseteq> x" by simp
    26   thus "approx i\<cdot>x \<sqsubseteq> x" by simp
    27 qed
    27 qed
    30 proof
    30 proof
    31   fix x :: 'a
    31   fix x :: 'a
    32   show "approx i\<cdot>(approx i\<cdot>x) = approx i\<cdot>x"
    32   show "approx i\<cdot>(approx i\<cdot>x) = approx i\<cdot>x"
    33     by (rule approx_idem)
    33     by (rule approx_idem)
    34   show "approx i\<cdot>x \<sqsubseteq> x"
    34   show "approx i\<cdot>x \<sqsubseteq> x"
    35     by (rule approx_less)
    35     by (rule approx_below)
    36   show "finite {x. approx i\<cdot>x = x}"
    36   show "finite {x. approx i\<cdot>x = x}"
    37     by (rule finite_fixes_approx)
    37     by (rule finite_fixes_approx)
    38 qed
    38 qed
    39 
    39 
    40 interpretation approx: finite_deflation "approx i"
    40 interpretation approx: finite_deflation "approx i"
    47 
    47 
    48 lemma lub_approx [simp]: "(\<Squnion>i. approx i) = (\<Lambda> x. x)"
    48 lemma lub_approx [simp]: "(\<Squnion>i. approx i) = (\<Lambda> x. x)"
    49 by (rule ext_cfun, simp add: contlub_cfun_fun)
    49 by (rule ext_cfun, simp add: contlub_cfun_fun)
    50 
    50 
    51 lemma approx_strict [simp]: "approx i\<cdot>\<bottom> = \<bottom>"
    51 lemma approx_strict [simp]: "approx i\<cdot>\<bottom> = \<bottom>"
    52 by (rule UU_I, rule approx_less)
    52 by (rule UU_I, rule approx_below)
    53 
    53 
    54 lemma approx_approx1:
    54 lemma approx_approx1:
    55   "i \<le> j \<Longrightarrow> approx i\<cdot>(approx j\<cdot>x) = approx i\<cdot>x"
    55   "i \<le> j \<Longrightarrow> approx i\<cdot>(approx j\<cdot>x) = approx i\<cdot>x"
    56 apply (rule deflation_less_comp1 [OF deflation_approx deflation_approx])
    56 apply (rule deflation_below_comp1 [OF deflation_approx deflation_approx])
    57 apply (erule chain_mono [OF chain_approx])
    57 apply (erule chain_mono [OF chain_approx])
    58 done
    58 done
    59 
    59 
    60 lemma approx_approx2:
    60 lemma approx_approx2:
    61   "j \<le> i \<Longrightarrow> approx i\<cdot>(approx j\<cdot>x) = approx j\<cdot>x"
    61   "j \<le> i \<Longrightarrow> approx i\<cdot>(approx j\<cdot>x) = approx j\<cdot>x"
    62 apply (rule deflation_less_comp2 [OF deflation_approx deflation_approx])
    62 apply (rule deflation_below_comp2 [OF deflation_approx deflation_approx])
    63 apply (erule chain_mono [OF chain_approx])
    63 apply (erule chain_mono [OF chain_approx])
    64 done
    64 done
    65 
    65 
    66 lemma approx_approx [simp]:
    66 lemma approx_approx [simp]:
    67   "approx i\<cdot>(approx j\<cdot>x) = approx (min i j)\<cdot>x"
    67   "approx i\<cdot>(approx j\<cdot>x) = approx (min i j)\<cdot>x"
    97   have "P (\<Squnion>n. approx n\<cdot>x)"
    97   have "P (\<Squnion>n. approx n\<cdot>x)"
    98     by (rule admD [OF adm], simp, simp add: P)
    98     by (rule admD [OF adm], simp, simp add: P)
    99   thus "P x" by simp
    99   thus "P x" by simp
   100 qed
   100 qed
   101 
   101 
   102 lemma profinite_less_ext: "(\<And>i. approx i\<cdot>x \<sqsubseteq> approx i\<cdot>y) \<Longrightarrow> x \<sqsubseteq> y"
   102 lemma profinite_below_ext: "(\<And>i. approx i\<cdot>x \<sqsubseteq> approx i\<cdot>y) \<Longrightarrow> x \<sqsubseteq> y"
   103 apply (subgoal_tac "(\<Squnion>i. approx i\<cdot>x) \<sqsubseteq> (\<Squnion>i. approx i\<cdot>y)", simp)
   103 apply (subgoal_tac "(\<Squnion>i. approx i\<cdot>x) \<sqsubseteq> (\<Squnion>i. approx i\<cdot>y)", simp)
   104 apply (rule lub_mono, simp, simp, simp)
   104 apply (rule lub_mono, simp, simp, simp)
   105 done
   105 done
   106 
   106 
   107 subsection {* Instance for continuous function space *}
   107 subsection {* Instance for continuous function space *}