src/HOL/Library/Product_Order.thy
changeset 63561 fba08009ff3e
parent 62343 24106dc44def
child 63972 c98d1dd7eba1
     1.1 --- a/src/HOL/Library/Product_Order.thy	Thu Jul 28 20:39:51 2016 +0200
     1.2 +++ b/src/HOL/Library/Product_Order.thy	Fri Jul 29 09:49:23 2016 +0200
     1.3 @@ -5,7 +5,7 @@
     1.4  section \<open>Pointwise order on product types\<close>
     1.5  
     1.6  theory Product_Order
     1.7 -imports Product_plus Conditionally_Complete_Lattices
     1.8 +imports Product_plus
     1.9  begin
    1.10  
    1.11  subsection \<open>Pointwise ordering\<close>
    1.12 @@ -243,5 +243,74 @@
    1.13      by (auto simp: inf_prod_def Sup_prod_def SUP_prod_alt_def inf_Sup inf_SUP comp_def)
    1.14  qed
    1.15  
    1.16 +subsection \<open>Bekic's Theorem\<close>
    1.17 +text \<open>
    1.18 +  Simultaneous fixed points over pairs can be written in terms of separate fixed points.
    1.19 +  Transliterated from HOLCF.Fix by Peter Gammie
    1.20 +\<close>
    1.21 +
    1.22 +lemma lfp_prod:
    1.23 +  fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
    1.24 +  assumes "mono F"
    1.25 +  shows "lfp F = (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))),
    1.26 +                 (lfp (\<lambda>y. snd (F (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))), y)))))"
    1.27 +  (is "lfp F = (?x, ?y)")
    1.28 +proof(rule lfp_eqI[OF assms])
    1.29 +  have 1: "fst (F (?x, ?y)) = ?x"
    1.30 +    by (rule trans [symmetric, OF lfp_unfold])
    1.31 +       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
    1.32 +  have 2: "snd (F (?x, ?y)) = ?y"
    1.33 +    by (rule trans [symmetric, OF lfp_unfold])
    1.34 +       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
    1.35 +  from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
    1.36 +next
    1.37 +  fix z assume F_z: "F z = z"
    1.38 +  obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
    1.39 +  from F_z z have F_x: "fst (F (x, y)) = x" by simp
    1.40 +  from F_z z have F_y: "snd (F (x, y)) = y" by simp
    1.41 +  let ?y1 = "lfp (\<lambda>y. snd (F (x, y)))"
    1.42 +  have "?y1 \<le> y" by (rule lfp_lowerbound, simp add: F_y)
    1.43 +  hence "fst (F (x, ?y1)) \<le> fst (F (x, y))"
    1.44 +    by (simp add: assms fst_mono monoD)
    1.45 +  hence "fst (F (x, ?y1)) \<le> x" using F_x by simp
    1.46 +  hence 1: "?x \<le> x" by (simp add: lfp_lowerbound)
    1.47 +  hence "snd (F (?x, y)) \<le> snd (F (x, y))"
    1.48 +    by (simp add: assms snd_mono monoD)
    1.49 +  hence "snd (F (?x, y)) \<le> y" using F_y by simp
    1.50 +  hence 2: "?y \<le> y" by (simp add: lfp_lowerbound)
    1.51 +  show "(?x, ?y) \<le> z" using z 1 2 by simp
    1.52 +qed
    1.53 +
    1.54 +lemma gfp_prod:
    1.55 +  fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
    1.56 +  assumes "mono F"
    1.57 +  shows "gfp F = (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))),
    1.58 +                 (gfp (\<lambda>y. snd (F (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))), y)))))"
    1.59 +  (is "gfp F = (?x, ?y)")
    1.60 +proof(rule gfp_eqI[OF assms])
    1.61 +  have 1: "fst (F (?x, ?y)) = ?x"
    1.62 +    by (rule trans [symmetric, OF gfp_unfold])
    1.63 +       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
    1.64 +  have 2: "snd (F (?x, ?y)) = ?y"
    1.65 +    by (rule trans [symmetric, OF gfp_unfold])
    1.66 +       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
    1.67 +  from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
    1.68 +next
    1.69 +  fix z assume F_z: "F z = z"
    1.70 +  obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
    1.71 +  from F_z z have F_x: "fst (F (x, y)) = x" by simp
    1.72 +  from F_z z have F_y: "snd (F (x, y)) = y" by simp
    1.73 +  let ?y1 = "gfp (\<lambda>y. snd (F (x, y)))"
    1.74 +  have "y \<le> ?y1" by (rule gfp_upperbound, simp add: F_y)
    1.75 +  hence "fst (F (x, y)) \<le> fst (F (x, ?y1))"
    1.76 +    by (simp add: assms fst_mono monoD)
    1.77 +  hence "x \<le> fst (F (x, ?y1))" using F_x by simp
    1.78 +  hence 1: "x \<le> ?x" by (simp add: gfp_upperbound)
    1.79 +  hence "snd (F (x, y)) \<le> snd (F (?x, y))"
    1.80 +    by (simp add: assms snd_mono monoD)
    1.81 +  hence "y \<le> snd (F (?x, y))" using F_y by simp
    1.82 +  hence 2: "y \<le> ?y" by (simp add: gfp_upperbound)
    1.83 +  show "z \<le> (?x, ?y)" using z 1 2 by simp
    1.84 +qed
    1.85 +
    1.86  end
    1.87 -