src/HOL/Library/Product_Order.thy
 changeset 63561 fba08009ff3e parent 62343 24106dc44def child 63972 c98d1dd7eba1
equal inserted replaced
63559:113cee845044 63561:fba08009ff3e
`     3 *)`
`     3 *)`
`     4 `
`     4 `
`     5 section \<open>Pointwise order on product types\<close>`
`     5 section \<open>Pointwise order on product types\<close>`
`     6 `
`     6 `
`     7 theory Product_Order`
`     7 theory Product_Order`
`     8 imports Product_plus Conditionally_Complete_Lattices`
`     8 imports Product_plus`
`     9 begin`
`     9 begin`
`    10 `
`    10 `
`    11 subsection \<open>Pointwise ordering\<close>`
`    11 subsection \<open>Pointwise ordering\<close>`
`    12 `
`    12 `
`    13 instantiation prod :: (ord, ord) ord`
`    13 instantiation prod :: (ord, ord) ord`
`   241   case 2`
`   241   case 2`
`   242   then show ?case`
`   242   then show ?case`
`   243     by (auto simp: inf_prod_def Sup_prod_def SUP_prod_alt_def inf_Sup inf_SUP comp_def)`
`   243     by (auto simp: inf_prod_def Sup_prod_def SUP_prod_alt_def inf_Sup inf_SUP comp_def)`
`   244 qed`
`   244 qed`
`   245 `
`   245 `
`   246 end`
`   246 subsection \<open>Bekic's Theorem\<close>`
`   247 `
`   247 text \<open>`
`       `
`   248   Simultaneous fixed points over pairs can be written in terms of separate fixed points.`
`       `
`   249   Transliterated from HOLCF.Fix by Peter Gammie`
`       `
`   250 \<close>`
`       `
`   251 `
`       `
`   252 lemma lfp_prod:`
`       `
`   253   fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"`
`       `
`   254   assumes "mono F"`
`       `
`   255   shows "lfp F = (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))),`
`       `
`   256                  (lfp (\<lambda>y. snd (F (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))), y)))))"`
`       `
`   257   (is "lfp F = (?x, ?y)")`
`       `
`   258 proof(rule lfp_eqI[OF assms])`
`       `
`   259   have 1: "fst (F (?x, ?y)) = ?x"`
`       `
`   260     by (rule trans [symmetric, OF lfp_unfold])`
`       `
`   261        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+`
`       `
`   262   have 2: "snd (F (?x, ?y)) = ?y"`
`       `
`   263     by (rule trans [symmetric, OF lfp_unfold])`
`       `
`   264        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+`
`       `
`   265   from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)`
`       `
`   266 next`
`       `
`   267   fix z assume F_z: "F z = z"`
`       `
`   268   obtain x y where z: "z = (x, y)" by (rule prod.exhaust)`
`       `
`   269   from F_z z have F_x: "fst (F (x, y)) = x" by simp`
`       `
`   270   from F_z z have F_y: "snd (F (x, y)) = y" by simp`
`       `
`   271   let ?y1 = "lfp (\<lambda>y. snd (F (x, y)))"`
`       `
`   272   have "?y1 \<le> y" by (rule lfp_lowerbound, simp add: F_y)`
`       `
`   273   hence "fst (F (x, ?y1)) \<le> fst (F (x, y))"`
`       `
`   274     by (simp add: assms fst_mono monoD)`
`       `
`   275   hence "fst (F (x, ?y1)) \<le> x" using F_x by simp`
`       `
`   276   hence 1: "?x \<le> x" by (simp add: lfp_lowerbound)`
`       `
`   277   hence "snd (F (?x, y)) \<le> snd (F (x, y))"`
`       `
`   278     by (simp add: assms snd_mono monoD)`
`       `
`   279   hence "snd (F (?x, y)) \<le> y" using F_y by simp`
`       `
`   280   hence 2: "?y \<le> y" by (simp add: lfp_lowerbound)`
`       `
`   281   show "(?x, ?y) \<le> z" using z 1 2 by simp`
`       `
`   282 qed`
`       `
`   283 `
`       `
`   284 lemma gfp_prod:`
`       `
`   285   fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"`
`       `
`   286   assumes "mono F"`
`       `
`   287   shows "gfp F = (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))),`
`       `
`   288                  (gfp (\<lambda>y. snd (F (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))), y)))))"`
`       `
`   289   (is "gfp F = (?x, ?y)")`
`       `
`   290 proof(rule gfp_eqI[OF assms])`
`       `
`   291   have 1: "fst (F (?x, ?y)) = ?x"`
`       `
`   292     by (rule trans [symmetric, OF gfp_unfold])`
`       `
`   293        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+`
`       `
`   294   have 2: "snd (F (?x, ?y)) = ?y"`
`       `
`   295     by (rule trans [symmetric, OF gfp_unfold])`
`       `
`   296        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+`
`       `
`   297   from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)`
`       `
`   298 next`
`       `
`   299   fix z assume F_z: "F z = z"`
`       `
`   300   obtain x y where z: "z = (x, y)" by (rule prod.exhaust)`
`       `
`   301   from F_z z have F_x: "fst (F (x, y)) = x" by simp`
`       `
`   302   from F_z z have F_y: "snd (F (x, y)) = y" by simp`
`       `
`   303   let ?y1 = "gfp (\<lambda>y. snd (F (x, y)))"`
`       `
`   304   have "y \<le> ?y1" by (rule gfp_upperbound, simp add: F_y)`
`       `
`   305   hence "fst (F (x, y)) \<le> fst (F (x, ?y1))"`
`       `
`   306     by (simp add: assms fst_mono monoD)`
`       `
`   307   hence "x \<le> fst (F (x, ?y1))" using F_x by simp`
`       `
`   308   hence 1: "x \<le> ?x" by (simp add: gfp_upperbound)`
`       `
`   309   hence "snd (F (x, y)) \<le> snd (F (?x, y))"`
`       `
`   310     by (simp add: assms snd_mono monoD)`
`       `
`   311   hence "y \<le> snd (F (?x, y))" using F_y by simp`
`       `
`   312   hence 2: "y \<le> ?y" by (simp add: gfp_upperbound)`
`       `
`   313   show "z \<le> (?x, ?y)" using z 1 2 by simp`
`       `
`   314 qed`
`       `
`   315 `
`       `
`   316 end`