src/HOL/Library/Product_Order.thy
 author haftmann Sun Nov 18 18:07:51 2018 +0000 (8 months ago) changeset 69313 b021008c5397 parent 69260 0a9688695a1b child 69861 62e47f06d22c permissions -rw-r--r--
removed legacy input syntax
1 (*  Title:      HOL/Library/Product_Order.thy
2     Author:     Brian Huffman
3 *)
5 section \<open>Pointwise order on product types\<close>
7 theory Product_Order
8 imports Product_Plus
9 begin
11 subsection \<open>Pointwise ordering\<close>
13 instantiation prod :: (ord, ord) ord
14 begin
16 definition
17   "x \<le> y \<longleftrightarrow> fst x \<le> fst y \<and> snd x \<le> snd y"
19 definition
20   "(x::'a \<times> 'b) < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
22 instance ..
24 end
26 lemma fst_mono: "x \<le> y \<Longrightarrow> fst x \<le> fst y"
27   unfolding less_eq_prod_def by simp
29 lemma snd_mono: "x \<le> y \<Longrightarrow> snd x \<le> snd y"
30   unfolding less_eq_prod_def by simp
32 lemma Pair_mono: "x \<le> x' \<Longrightarrow> y \<le> y' \<Longrightarrow> (x, y) \<le> (x', y')"
33   unfolding less_eq_prod_def by simp
35 lemma Pair_le [simp]: "(a, b) \<le> (c, d) \<longleftrightarrow> a \<le> c \<and> b \<le> d"
36   unfolding less_eq_prod_def by simp
38 instance prod :: (preorder, preorder) preorder
39 proof
40   fix x y z :: "'a \<times> 'b"
41   show "x < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
42     by (rule less_prod_def)
43   show "x \<le> x"
44     unfolding less_eq_prod_def
45     by fast
46   assume "x \<le> y" and "y \<le> z" thus "x \<le> z"
47     unfolding less_eq_prod_def
48     by (fast elim: order_trans)
49 qed
51 instance prod :: (order, order) order
52   by standard auto
55 subsection \<open>Binary infimum and supremum\<close>
57 instantiation prod :: (inf, inf) inf
58 begin
60 definition "inf x y = (inf (fst x) (fst y), inf (snd x) (snd y))"
62 lemma inf_Pair_Pair [simp]: "inf (a, b) (c, d) = (inf a c, inf b d)"
63   unfolding inf_prod_def by simp
65 lemma fst_inf [simp]: "fst (inf x y) = inf (fst x) (fst y)"
66   unfolding inf_prod_def by simp
68 lemma snd_inf [simp]: "snd (inf x y) = inf (snd x) (snd y)"
69   unfolding inf_prod_def by simp
71 instance ..
73 end
75 instance prod :: (semilattice_inf, semilattice_inf) semilattice_inf
76   by standard auto
79 instantiation prod :: (sup, sup) sup
80 begin
82 definition
83   "sup x y = (sup (fst x) (fst y), sup (snd x) (snd y))"
85 lemma sup_Pair_Pair [simp]: "sup (a, b) (c, d) = (sup a c, sup b d)"
86   unfolding sup_prod_def by simp
88 lemma fst_sup [simp]: "fst (sup x y) = sup (fst x) (fst y)"
89   unfolding sup_prod_def by simp
91 lemma snd_sup [simp]: "snd (sup x y) = sup (snd x) (snd y)"
92   unfolding sup_prod_def by simp
94 instance ..
96 end
98 instance prod :: (semilattice_sup, semilattice_sup) semilattice_sup
99   by standard auto
101 instance prod :: (lattice, lattice) lattice ..
103 instance prod :: (distrib_lattice, distrib_lattice) distrib_lattice
104   by standard (auto simp add: sup_inf_distrib1)
107 subsection \<open>Top and bottom elements\<close>
109 instantiation prod :: (top, top) top
110 begin
112 definition
113   "top = (top, top)"
115 instance ..
117 end
119 lemma fst_top [simp]: "fst top = top"
120   unfolding top_prod_def by simp
122 lemma snd_top [simp]: "snd top = top"
123   unfolding top_prod_def by simp
125 lemma Pair_top_top: "(top, top) = top"
126   unfolding top_prod_def by simp
128 instance prod :: (order_top, order_top) order_top
129   by standard (auto simp add: top_prod_def)
131 instantiation prod :: (bot, bot) bot
132 begin
134 definition
135   "bot = (bot, bot)"
137 instance ..
139 end
141 lemma fst_bot [simp]: "fst bot = bot"
142   unfolding bot_prod_def by simp
144 lemma snd_bot [simp]: "snd bot = bot"
145   unfolding bot_prod_def by simp
147 lemma Pair_bot_bot: "(bot, bot) = bot"
148   unfolding bot_prod_def by simp
150 instance prod :: (order_bot, order_bot) order_bot
151   by standard (auto simp add: bot_prod_def)
153 instance prod :: (bounded_lattice, bounded_lattice) bounded_lattice ..
155 instance prod :: (boolean_algebra, boolean_algebra) boolean_algebra
156   by standard (auto simp add: prod_eqI diff_eq)
159 subsection \<open>Complete lattice operations\<close>
161 instantiation prod :: (Inf, Inf) Inf
162 begin
164 definition "Inf A = (INF x\<in>A. fst x, INF x\<in>A. snd x)"
166 instance ..
168 end
170 instantiation prod :: (Sup, Sup) Sup
171 begin
173 definition "Sup A = (SUP x\<in>A. fst x, SUP x\<in>A. snd x)"
175 instance ..
177 end
179 instance prod :: (conditionally_complete_lattice, conditionally_complete_lattice)
180     conditionally_complete_lattice
181   by standard (force simp: less_eq_prod_def Inf_prod_def Sup_prod_def bdd_below_def bdd_above_def
182     intro!: cInf_lower cSup_upper cInf_greatest cSup_least)+
184 instance prod :: (complete_lattice, complete_lattice) complete_lattice
185   by standard (simp_all add: less_eq_prod_def Inf_prod_def Sup_prod_def
186     INF_lower SUP_upper le_INF_iff SUP_le_iff bot_prod_def top_prod_def)
188 lemma fst_Sup: "fst (Sup A) = (SUP x\<in>A. fst x)"
189   unfolding Sup_prod_def by simp
191 lemma snd_Sup: "snd (Sup A) = (SUP x\<in>A. snd x)"
192   unfolding Sup_prod_def by simp
194 lemma fst_Inf: "fst (Inf A) = (INF x\<in>A. fst x)"
195   unfolding Inf_prod_def by simp
197 lemma snd_Inf: "snd (Inf A) = (INF x\<in>A. snd x)"
198   unfolding Inf_prod_def by simp
200 lemma fst_SUP: "fst (SUP x\<in>A. f x) = (SUP x\<in>A. fst (f x))"
201   using fst_Sup [of "f ` A", symmetric] by (simp add: comp_def)
203 lemma snd_SUP: "snd (SUP x\<in>A. f x) = (SUP x\<in>A. snd (f x))"
204   using snd_Sup [of "f ` A", symmetric] by (simp add: comp_def)
206 lemma fst_INF: "fst (INF x\<in>A. f x) = (INF x\<in>A. fst (f x))"
207   using fst_Inf [of "f ` A", symmetric] by (simp add: comp_def)
209 lemma snd_INF: "snd (INF x\<in>A. f x) = (INF x\<in>A. snd (f x))"
210   using snd_Inf [of "f ` A", symmetric] by (simp add: comp_def)
212 lemma SUP_Pair: "(SUP x\<in>A. (f x, g x)) = (SUP x\<in>A. f x, SUP x\<in>A. g x)"
213   unfolding Sup_prod_def by (simp add: comp_def)
215 lemma INF_Pair: "(INF x\<in>A. (f x, g x)) = (INF x\<in>A. f x, INF x\<in>A. g x)"
216   unfolding Inf_prod_def by (simp add: comp_def)
219 text \<open>Alternative formulations for set infima and suprema over the product
220 of two complete lattices:\<close>
222 lemma INF_prod_alt_def:
223   "Inf (f ` A) = (Inf ((fst \<circ> f) ` A), Inf ((snd \<circ> f) ` A))"
224   unfolding Inf_prod_def by simp
226 lemma SUP_prod_alt_def:
227   "Sup (f ` A) = (Sup ((fst \<circ> f) ` A), Sup((snd \<circ> f) ` A))"
228   unfolding Sup_prod_def by simp
231 subsection \<open>Complete distributive lattices\<close>
233 (* Contribution: Alessandro Coglio *)
235 instance prod :: (complete_distrib_lattice, complete_distrib_lattice) complete_distrib_lattice
236 proof
237   fix A::"('a\<times>'b) set set"
238   show "Inf (Sup ` A) \<le> Sup (Inf ` {f ` A |f. \<forall>Y\<in>A. f Y \<in> Y})"
239     by (simp add: Sup_prod_def Inf_prod_def INF_SUP_set)
240 qed
242 subsection \<open>Bekic's Theorem\<close>
243 text \<open>
244   Simultaneous fixed points over pairs can be written in terms of separate fixed points.
245   Transliterated from HOLCF.Fix by Peter Gammie
246 \<close>
248 lemma lfp_prod:
249   fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
250   assumes "mono F"
251   shows "lfp F = (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))),
252                  (lfp (\<lambda>y. snd (F (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))), y)))))"
253   (is "lfp F = (?x, ?y)")
254 proof(rule lfp_eqI[OF assms])
255   have 1: "fst (F (?x, ?y)) = ?x"
256     by (rule trans [symmetric, OF lfp_unfold])
257        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
258   have 2: "snd (F (?x, ?y)) = ?y"
259     by (rule trans [symmetric, OF lfp_unfold])
260        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
261   from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
262 next
263   fix z assume F_z: "F z = z"
264   obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
265   from F_z z have F_x: "fst (F (x, y)) = x" by simp
266   from F_z z have F_y: "snd (F (x, y)) = y" by simp
267   let ?y1 = "lfp (\<lambda>y. snd (F (x, y)))"
268   have "?y1 \<le> y" by (rule lfp_lowerbound, simp add: F_y)
269   hence "fst (F (x, ?y1)) \<le> fst (F (x, y))"
270     by (simp add: assms fst_mono monoD)
271   hence "fst (F (x, ?y1)) \<le> x" using F_x by simp
272   hence 1: "?x \<le> x" by (simp add: lfp_lowerbound)
273   hence "snd (F (?x, y)) \<le> snd (F (x, y))"
274     by (simp add: assms snd_mono monoD)
275   hence "snd (F (?x, y)) \<le> y" using F_y by simp
276   hence 2: "?y \<le> y" by (simp add: lfp_lowerbound)
277   show "(?x, ?y) \<le> z" using z 1 2 by simp
278 qed
280 lemma gfp_prod:
281   fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
282   assumes "mono F"
283   shows "gfp F = (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))),
284                  (gfp (\<lambda>y. snd (F (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))), y)))))"
285   (is "gfp F = (?x, ?y)")
286 proof(rule gfp_eqI[OF assms])
287   have 1: "fst (F (?x, ?y)) = ?x"
288     by (rule trans [symmetric, OF gfp_unfold])
289        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
290   have 2: "snd (F (?x, ?y)) = ?y"
291     by (rule trans [symmetric, OF gfp_unfold])
292        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
293   from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
294 next
295   fix z assume F_z: "F z = z"
296   obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
297   from F_z z have F_x: "fst (F (x, y)) = x" by simp
298   from F_z z have F_y: "snd (F (x, y)) = y" by simp
299   let ?y1 = "gfp (\<lambda>y. snd (F (x, y)))"
300   have "y \<le> ?y1" by (rule gfp_upperbound, simp add: F_y)
301   hence "fst (F (x, y)) \<le> fst (F (x, ?y1))"
302     by (simp add: assms fst_mono monoD)
303   hence "x \<le> fst (F (x, ?y1))" using F_x by simp
304   hence 1: "x \<le> ?x" by (simp add: gfp_upperbound)
305   hence "snd (F (x, y)) \<le> snd (F (?x, y))"
306     by (simp add: assms snd_mono monoD)
307   hence "y \<le> snd (F (?x, y))" using F_y by simp
308   hence 2: "y \<le> ?y" by (simp add: gfp_upperbound)
309   show "z \<le> (?x, ?y)" using z 1 2 by simp
310 qed
312 end