haftmann@51115: (*  Title:      HOL/Library/Product_Order.thy
huffman@44006:     Author:     Brian Huffman
huffman@44006: *)
huffman@44006: 
haftmann@51115: header {* Pointwise order on product types *}
huffman@44006: 
haftmann@51115: theory Product_Order
immler@54776: imports Product_plus Conditionally_Complete_Lattices
huffman@44006: begin
huffman@44006: 
huffman@44006: subsection {* Pointwise ordering *}
huffman@44006: 
huffman@44006: instantiation prod :: (ord, ord) ord
huffman@44006: begin
huffman@44006: 
huffman@44006: definition
huffman@44006:   "x \<le> y \<longleftrightarrow> fst x \<le> fst y \<and> snd x \<le> snd y"
huffman@44006: 
huffman@44006: definition
huffman@44006:   "(x::'a \<times> 'b) < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
huffman@44006: 
huffman@44006: instance ..
huffman@44006: 
huffman@44006: end
huffman@44006: 
huffman@44006: lemma fst_mono: "x \<le> y \<Longrightarrow> fst x \<le> fst y"
huffman@44006:   unfolding less_eq_prod_def by simp
huffman@44006: 
huffman@44006: lemma snd_mono: "x \<le> y \<Longrightarrow> snd x \<le> snd y"
huffman@44006:   unfolding less_eq_prod_def by simp
huffman@44006: 
huffman@44006: lemma Pair_mono: "x \<le> x' \<Longrightarrow> y \<le> y' \<Longrightarrow> (x, y) \<le> (x', y')"
huffman@44006:   unfolding less_eq_prod_def by simp
huffman@44006: 
huffman@44006: lemma Pair_le [simp]: "(a, b) \<le> (c, d) \<longleftrightarrow> a \<le> c \<and> b \<le> d"
huffman@44006:   unfolding less_eq_prod_def by simp
huffman@44006: 
huffman@44006: instance prod :: (preorder, preorder) preorder
huffman@44006: proof
huffman@44006:   fix x y z :: "'a \<times> 'b"
huffman@44006:   show "x < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
huffman@44006:     by (rule less_prod_def)
huffman@44006:   show "x \<le> x"
huffman@44006:     unfolding less_eq_prod_def
huffman@44006:     by fast
huffman@44006:   assume "x \<le> y" and "y \<le> z" thus "x \<le> z"
huffman@44006:     unfolding less_eq_prod_def
huffman@44006:     by (fast elim: order_trans)
huffman@44006: qed
huffman@44006: 
huffman@44006: instance prod :: (order, order) order
huffman@44006:   by default auto
huffman@44006: 
huffman@44006: 
huffman@44006: subsection {* Binary infimum and supremum *}
huffman@44006: 
immler@54776: instantiation prod :: (inf, inf) inf
huffman@44006: begin
huffman@44006: 
huffman@44006: definition
huffman@44006:   "inf x y = (inf (fst x) (fst y), inf (snd x) (snd y))"
huffman@44006: 
huffman@44006: lemma inf_Pair_Pair [simp]: "inf (a, b) (c, d) = (inf a c, inf b d)"
huffman@44006:   unfolding inf_prod_def by simp
huffman@44006: 
huffman@44006: lemma fst_inf [simp]: "fst (inf x y) = inf (fst x) (fst y)"
huffman@44006:   unfolding inf_prod_def by simp
huffman@44006: 
huffman@44006: lemma snd_inf [simp]: "snd (inf x y) = inf (snd x) (snd y)"
huffman@44006:   unfolding inf_prod_def by simp
huffman@44006: 
immler@54776: instance proof qed
immler@54776: end
immler@54776: 
immler@54776: instance prod :: (semilattice_inf, semilattice_inf) semilattice_inf
huffman@44006:   by default auto
huffman@44006: 
huffman@44006: 
immler@54776: instantiation prod :: (sup, sup) sup
huffman@44006: begin
huffman@44006: 
huffman@44006: definition
huffman@44006:   "sup x y = (sup (fst x) (fst y), sup (snd x) (snd y))"
huffman@44006: 
huffman@44006: lemma sup_Pair_Pair [simp]: "sup (a, b) (c, d) = (sup a c, sup b d)"
huffman@44006:   unfolding sup_prod_def by simp
huffman@44006: 
huffman@44006: lemma fst_sup [simp]: "fst (sup x y) = sup (fst x) (fst y)"
huffman@44006:   unfolding sup_prod_def by simp
huffman@44006: 
huffman@44006: lemma snd_sup [simp]: "snd (sup x y) = sup (snd x) (snd y)"
huffman@44006:   unfolding sup_prod_def by simp
huffman@44006: 
immler@54776: instance proof qed
immler@54776: end
immler@54776: 
immler@54776: instance prod :: (semilattice_sup, semilattice_sup) semilattice_sup
huffman@44006:   by default auto
huffman@44006: 
huffman@44006: instance prod :: (lattice, lattice) lattice ..
huffman@44006: 
huffman@44006: instance prod :: (distrib_lattice, distrib_lattice) distrib_lattice
huffman@44006:   by default (auto simp add: sup_inf_distrib1)
huffman@44006: 
huffman@44006: 
huffman@44006: subsection {* Top and bottom elements *}
huffman@44006: 
huffman@44006: instantiation prod :: (top, top) top
huffman@44006: begin
huffman@44006: 
huffman@44006: definition
huffman@44006:   "top = (top, top)"
huffman@44006: 
haftmann@52729: instance ..
haftmann@52729: 
haftmann@52729: end
haftmann@52729: 
huffman@44006: lemma fst_top [simp]: "fst top = top"
huffman@44006:   unfolding top_prod_def by simp
huffman@44006: 
huffman@44006: lemma snd_top [simp]: "snd top = top"
huffman@44006:   unfolding top_prod_def by simp
huffman@44006: 
huffman@44006: lemma Pair_top_top: "(top, top) = top"
huffman@44006:   unfolding top_prod_def by simp
huffman@44006: 
haftmann@52729: instance prod :: (order_top, order_top) order_top
huffman@44006:   by default (auto simp add: top_prod_def)
huffman@44006: 
huffman@44006: instantiation prod :: (bot, bot) bot
huffman@44006: begin
huffman@44006: 
huffman@44006: definition
huffman@44006:   "bot = (bot, bot)"
huffman@44006: 
haftmann@52729: instance ..
haftmann@52729: 
haftmann@52729: end
haftmann@52729: 
huffman@44006: lemma fst_bot [simp]: "fst bot = bot"
huffman@44006:   unfolding bot_prod_def by simp
huffman@44006: 
huffman@44006: lemma snd_bot [simp]: "snd bot = bot"
huffman@44006:   unfolding bot_prod_def by simp
huffman@44006: 
huffman@44006: lemma Pair_bot_bot: "(bot, bot) = bot"
huffman@44006:   unfolding bot_prod_def by simp
huffman@44006: 
haftmann@52729: instance prod :: (order_bot, order_bot) order_bot
huffman@44006:   by default (auto simp add: bot_prod_def)
huffman@44006: 
huffman@44006: instance prod :: (bounded_lattice, bounded_lattice) bounded_lattice ..
huffman@44006: 
huffman@44006: instance prod :: (boolean_algebra, boolean_algebra) boolean_algebra
huffman@44006:   by default (auto simp add: prod_eqI inf_compl_bot sup_compl_top diff_eq)
huffman@44006: 
huffman@44006: 
huffman@44006: subsection {* Complete lattice operations *}
huffman@44006: 
immler@54776: instantiation prod :: (Inf, Inf) Inf
immler@54776: begin
immler@54776: 
immler@54776: definition
immler@54776:   "Inf A = (INF x:A. fst x, INF x:A. snd x)"
immler@54776: 
immler@54776: instance proof qed
immler@54776: end
immler@54776: 
immler@54776: instantiation prod :: (Sup, Sup) Sup
huffman@44006: begin
huffman@44006: 
huffman@44006: definition
huffman@44006:   "Sup A = (SUP x:A. fst x, SUP x:A. snd x)"
huffman@44006: 
immler@54776: instance proof qed
immler@54776: end
huffman@44006: 
immler@54776: instance prod :: (conditionally_complete_lattice, conditionally_complete_lattice)
immler@54776:     conditionally_complete_lattice
immler@54776:   by default (force simp: less_eq_prod_def Inf_prod_def Sup_prod_def bdd_below_def bdd_above_def
haftmann@56166:     INF_def SUP_def simp del: Inf_image_eq Sup_image_eq intro!: cInf_lower cSup_upper cInf_greatest cSup_least)+
immler@54776: 
immler@54776: instance prod :: (complete_lattice, complete_lattice) complete_lattice
huffman@44006:   by default (simp_all add: less_eq_prod_def Inf_prod_def Sup_prod_def
haftmann@52729:     INF_lower SUP_upper le_INF_iff SUP_le_iff bot_prod_def top_prod_def)
huffman@44006: 
huffman@44006: lemma fst_Sup: "fst (Sup A) = (SUP x:A. fst x)"
huffman@44006:   unfolding Sup_prod_def by simp
huffman@44006: 
huffman@44006: lemma snd_Sup: "snd (Sup A) = (SUP x:A. snd x)"
huffman@44006:   unfolding Sup_prod_def by simp
huffman@44006: 
huffman@44006: lemma fst_Inf: "fst (Inf A) = (INF x:A. fst x)"
huffman@44006:   unfolding Inf_prod_def by simp
huffman@44006: 
huffman@44006: lemma snd_Inf: "snd (Inf A) = (INF x:A. snd x)"
huffman@44006:   unfolding Inf_prod_def by simp
huffman@44006: 
huffman@44006: lemma fst_SUP: "fst (SUP x:A. f x) = (SUP x:A. fst (f x))"
haftmann@56166:   using fst_Sup [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006: 
huffman@44006: lemma snd_SUP: "snd (SUP x:A. f x) = (SUP x:A. snd (f x))"
haftmann@56166:   using snd_Sup [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006: 
huffman@44006: lemma fst_INF: "fst (INF x:A. f x) = (INF x:A. fst (f x))"
haftmann@56166:   using fst_Inf [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006: 
huffman@44006: lemma snd_INF: "snd (INF x:A. f x) = (INF x:A. snd (f x))"
haftmann@56166:   using snd_Inf [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006: 
huffman@44006: lemma SUP_Pair: "(SUP x:A. (f x, g x)) = (SUP x:A. f x, SUP x:A. g x)"
haftmann@56166:   unfolding SUP_def Sup_prod_def by (simp add: comp_def)
huffman@44006: 
huffman@44006: lemma INF_Pair: "(INF x:A. (f x, g x)) = (INF x:A. f x, INF x:A. g x)"
haftmann@56166:   unfolding INF_def Inf_prod_def by (simp add: comp_def)
huffman@44006: 
nipkow@50535: 
nipkow@50535: text {* Alternative formulations for set infima and suprema over the product
nipkow@50535: of two complete lattices: *}
nipkow@50535: 
haftmann@56212: lemma INF_prod_alt_def:
haftmann@56218:   "INFIMUM A f = (INFIMUM A (fst o f), INFIMUM A (snd o f))"
haftmann@56166:   unfolding INF_def Inf_prod_def by simp
nipkow@50535: 
haftmann@56212: lemma SUP_prod_alt_def:
haftmann@56218:   "SUPREMUM A f = (SUPREMUM A (fst o f), SUPREMUM A (snd o f))"
haftmann@56166:   unfolding SUP_def Sup_prod_def by simp
nipkow@50535: 
nipkow@50535: 
nipkow@50535: subsection {* Complete distributive lattices *}
nipkow@50535: 
nipkow@50573: (* Contribution: Alessandro Coglio *)
nipkow@50535: 
nipkow@50535: instance prod ::
nipkow@50535:   (complete_distrib_lattice, complete_distrib_lattice) complete_distrib_lattice
nipkow@50535: proof
nipkow@50535:   case goal1 thus ?case
haftmann@56212:     by (auto simp: sup_prod_def Inf_prod_def INF_prod_alt_def sup_Inf sup_INF comp_def)
nipkow@50535: next
nipkow@50535:   case goal2 thus ?case
haftmann@56212:     by (auto simp: inf_prod_def Sup_prod_def SUP_prod_alt_def inf_Sup inf_SUP comp_def)
nipkow@50535: qed
nipkow@50535: 
haftmann@51115: end
nipkow@50535: