Theory Pcpo

theory Pcpo
imports Porder
(*  Title:      HOL/HOLCF/Pcpo.thy
    Author:     Franz Regensburger

section {* Classes cpo and pcpo *}

theory Pcpo
imports Porder

subsection {* Complete partial orders *}

text {* The class cpo of chain complete partial orders *}

class cpo = po +
  assumes cpo: "chain S ==> ∃x. range S <<| x"

text {* in cpo's everthing equal to THE lub has lub properties for every chain *}

lemma cpo_lubI: "chain S ==> range S <<| (\<Squnion>i. S i)"
  by (fast dest: cpo elim: is_lub_lub)

lemma thelubE: "[|chain S; (\<Squnion>i. S i) = l|] ==> range S <<| l"
  by (blast dest: cpo intro: is_lub_lub)

text {* Properties of the lub *}

lemma is_ub_thelub: "chain S ==> S x \<sqsubseteq> (\<Squnion>i. S i)"
  by (blast dest: cpo intro: is_lub_lub [THEN is_lub_rangeD1])

lemma is_lub_thelub:
  "[|chain S; range S <| x|] ==> (\<Squnion>i. S i) \<sqsubseteq> x"
  by (blast dest: cpo intro: is_lub_lub [THEN is_lubD2])

lemma lub_below_iff: "chain S ==> (\<Squnion>i. S i) \<sqsubseteq> x <-> (∀i. S i \<sqsubseteq> x)"
  by (simp add: is_lub_below_iff [OF cpo_lubI] is_ub_def)

lemma lub_below: "[|chain S; !!i. S i \<sqsubseteq> x|] ==> (\<Squnion>i. S i) \<sqsubseteq> x"
  by (simp add: lub_below_iff)

lemma below_lub: "[|chain S; x \<sqsubseteq> S i|] ==> x \<sqsubseteq> (\<Squnion>i. S i)"
  by (erule below_trans, erule is_ub_thelub)

lemma lub_range_mono:
  "[|range X ⊆ range Y; chain Y; chain X|]
    ==> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
apply (erule lub_below)
apply (subgoal_tac "∃j. X i = Y j")
apply  clarsimp
apply  (erule is_ub_thelub)
apply auto

lemma lub_range_shift:
  "chain Y ==> (\<Squnion>i. Y (i + j)) = (\<Squnion>i. Y i)"
apply (rule below_antisym)
apply (rule lub_range_mono)
apply    fast
apply   assumption
apply (erule chain_shift)
apply (rule lub_below)
apply assumption
apply (rule_tac i="i" in below_lub)
apply (erule chain_shift)
apply (erule chain_mono)
apply (rule le_add1)

lemma maxinch_is_thelub:
  "chain Y ==> max_in_chain i Y = ((\<Squnion>i. Y i) = Y i)"
apply (rule iffI)
apply (fast intro!: lub_eqI lub_finch1)
apply (unfold max_in_chain_def)
apply (safe intro!: below_antisym)
apply (fast elim!: chain_mono)
apply (drule sym)
apply (force elim!: is_ub_thelub)

text {* the @{text "\<sqsubseteq>"} relation between two chains is preserved by their lubs *}

lemma lub_mono:
  "[|chain X; chain Y; !!i. X i \<sqsubseteq> Y i|] 
    ==> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
by (fast elim: lub_below below_lub)

text {* the = relation between two chains is preserved by their lubs *}

lemma lub_eq:
  "(!!i. X i = Y i) ==> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
  by simp

lemma ch2ch_lub:
  assumes 1: "!!j. chain (λi. Y i j)"
  assumes 2: "!!i. chain (λj. Y i j)"
  shows "chain (λi. \<Squnion>j. Y i j)"
apply (rule chainI)
apply (rule lub_mono [OF 2 2])
apply (rule chainE [OF 1])

lemma diag_lub:
  assumes 1: "!!j. chain (λi. Y i j)"
  assumes 2: "!!i. chain (λj. Y i j)"
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>i. Y i i)"
proof (rule below_antisym)
  have 3: "chain (λi. Y i i)"
    apply (rule chainI)
    apply (rule below_trans)
    apply (rule chainE [OF 1])
    apply (rule chainE [OF 2])
  have 4: "chain (λi. \<Squnion>j. Y i j)"
    by (rule ch2ch_lub [OF 1 2])
  show "(\<Squnion>i. \<Squnion>j. Y i j) \<sqsubseteq> (\<Squnion>i. Y i i)"
    apply (rule lub_below [OF 4])
    apply (rule lub_below [OF 2])
    apply (rule below_lub [OF 3])
    apply (rule below_trans)
    apply (rule chain_mono [OF 1 max.cobounded1])
    apply (rule chain_mono [OF 2 max.cobounded2])
  show "(\<Squnion>i. Y i i) \<sqsubseteq> (\<Squnion>i. \<Squnion>j. Y i j)"
    apply (rule lub_mono [OF 3 4])
    apply (rule is_ub_thelub [OF 2])

lemma ex_lub:
  assumes 1: "!!j. chain (λi. Y i j)"
  assumes 2: "!!i. chain (λj. Y i j)"
  shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>j. \<Squnion>i. Y i j)"
  by (simp add: diag_lub 1 2)


subsection {* Pointed cpos *}

text {* The class pcpo of pointed cpos *}

class pcpo = cpo +
  assumes least: "∃x. ∀y. x \<sqsubseteq> y"

definition bottom :: "'a"
  where "bottom = (THE x. ∀y. x \<sqsubseteq> y)"

notation (xsymbols)
  bottom ("⊥")

lemma minimal [iff]: "⊥ \<sqsubseteq> x"
unfolding bottom_def
apply (rule the1I2)
apply (rule ex_ex1I)
apply (rule least)
apply (blast intro: below_antisym)
apply simp


text {* Old "UU" syntax: *}

syntax UU :: logic

translations "UU" => "CONST bottom"

text {* Simproc to rewrite @{term "⊥ = x"} to @{term "x = ⊥"}. *}

setup {*
    (fn Const(@{const_name bottom}, _) => true | _ => false)

simproc_setup reorient_bottom ("⊥ = x") = Reorient_Proc.proc

text {* useful lemmas about @{term ⊥} *}

lemma below_bottom_iff [simp]: "(x \<sqsubseteq> ⊥) = (x = ⊥)"
by (simp add: po_eq_conv)

lemma eq_bottom_iff: "(x = ⊥) = (x \<sqsubseteq> ⊥)"
by simp

lemma bottomI: "x \<sqsubseteq> ⊥ ==> x = ⊥"
by (subst eq_bottom_iff)

lemma lub_eq_bottom_iff: "chain Y ==> (\<Squnion>i. Y i) = ⊥ <-> (∀i. Y i = ⊥)"
by (simp only: eq_bottom_iff lub_below_iff)

subsection {* Chain-finite and flat cpos *}

text {* further useful classes for HOLCF domains *}

class chfin = po +
  assumes chfin: "chain Y ==> ∃n. max_in_chain n Y"

subclass cpo
apply default
apply (frule chfin)
apply (blast intro: lub_finch1)

lemma chfin2finch: "chain Y ==> finite_chain Y"
  by (simp add: chfin finite_chain_def)


class flat = pcpo +
  assumes ax_flat: "x \<sqsubseteq> y ==> x = ⊥ ∨ x = y"

subclass chfin
apply default
apply (unfold max_in_chain_def)
apply (case_tac "∀i. Y i = ⊥")
apply simp
apply simp
apply (erule exE)
apply (rule_tac x="i" in exI)
apply clarify
apply (blast dest: chain_mono ax_flat)

lemma flat_below_iff:
  shows "(x \<sqsubseteq> y) = (x = ⊥ ∨ x = y)"
  by (safe dest!: ax_flat)

lemma flat_eq: "a ≠ ⊥ ==> a \<sqsubseteq> b = (a = b)"
  by (safe dest!: ax_flat)


subsection {* Discrete cpos *}

class discrete_cpo = below +
  assumes discrete_cpo [simp]: "x \<sqsubseteq> y <-> x = y"

subclass po
proof qed simp_all

text {* In a discrete cpo, every chain is constant *}

lemma discrete_chain_const:
  assumes S: "chain S"
  shows "∃x. S = (λi. x)"
proof (intro exI ext)
  fix i :: nat
  have "S 0 \<sqsubseteq> S i" using S le0 by (rule chain_mono)
  hence "S 0 = S i" by simp
  thus "S i = S 0" by (rule sym)

subclass chfin
  fix S :: "nat => 'a"
  assume S: "chain S"
  hence "∃x. S = (λi. x)" by (rule discrete_chain_const)
  hence "max_in_chain 0 S"
    unfolding max_in_chain_def by auto
  thus "∃i. max_in_chain i S" ..