src/HOL/Library/Product_Order.thy
author wenzelm
Wed Mar 08 10:50:59 2017 +0100 (2017-03-08)
changeset 65151 a7394aa4d21c
parent 63972 c98d1dd7eba1
child 67091 1393c2340eec
permissions -rw-r--r--
tuned proofs;
     1 (*  Title:      HOL/Library/Product_Order.thy
     2     Author:     Brian Huffman
     3 *)
     4 
     5 section \<open>Pointwise order on product types\<close>
     6 
     7 theory Product_Order
     8 imports Product_Plus
     9 begin
    10 
    11 subsection \<open>Pointwise ordering\<close>
    12 
    13 instantiation prod :: (ord, ord) ord
    14 begin
    15 
    16 definition
    17   "x \<le> y \<longleftrightarrow> fst x \<le> fst y \<and> snd x \<le> snd y"
    18 
    19 definition
    20   "(x::'a \<times> 'b) < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
    21 
    22 instance ..
    23 
    24 end
    25 
    26 lemma fst_mono: "x \<le> y \<Longrightarrow> fst x \<le> fst y"
    27   unfolding less_eq_prod_def by simp
    28 
    29 lemma snd_mono: "x \<le> y \<Longrightarrow> snd x \<le> snd y"
    30   unfolding less_eq_prod_def by simp
    31 
    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
    34 
    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
    37 
    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
    50 
    51 instance prod :: (order, order) order
    52   by standard auto
    53 
    54 
    55 subsection \<open>Binary infimum and supremum\<close>
    56 
    57 instantiation prod :: (inf, inf) inf
    58 begin
    59 
    60 definition "inf x y = (inf (fst x) (fst y), inf (snd x) (snd y))"
    61 
    62 lemma inf_Pair_Pair [simp]: "inf (a, b) (c, d) = (inf a c, inf b d)"
    63   unfolding inf_prod_def by simp
    64 
    65 lemma fst_inf [simp]: "fst (inf x y) = inf (fst x) (fst y)"
    66   unfolding inf_prod_def by simp
    67 
    68 lemma snd_inf [simp]: "snd (inf x y) = inf (snd x) (snd y)"
    69   unfolding inf_prod_def by simp
    70 
    71 instance ..
    72 
    73 end
    74 
    75 instance prod :: (semilattice_inf, semilattice_inf) semilattice_inf
    76   by standard auto
    77 
    78 
    79 instantiation prod :: (sup, sup) sup
    80 begin
    81 
    82 definition
    83   "sup x y = (sup (fst x) (fst y), sup (snd x) (snd y))"
    84 
    85 lemma sup_Pair_Pair [simp]: "sup (a, b) (c, d) = (sup a c, sup b d)"
    86   unfolding sup_prod_def by simp
    87 
    88 lemma fst_sup [simp]: "fst (sup x y) = sup (fst x) (fst y)"
    89   unfolding sup_prod_def by simp
    90 
    91 lemma snd_sup [simp]: "snd (sup x y) = sup (snd x) (snd y)"
    92   unfolding sup_prod_def by simp
    93 
    94 instance ..
    95 
    96 end
    97 
    98 instance prod :: (semilattice_sup, semilattice_sup) semilattice_sup
    99   by standard auto
   100 
   101 instance prod :: (lattice, lattice) lattice ..
   102 
   103 instance prod :: (distrib_lattice, distrib_lattice) distrib_lattice
   104   by standard (auto simp add: sup_inf_distrib1)
   105 
   106 
   107 subsection \<open>Top and bottom elements\<close>
   108 
   109 instantiation prod :: (top, top) top
   110 begin
   111 
   112 definition
   113   "top = (top, top)"
   114 
   115 instance ..
   116 
   117 end
   118 
   119 lemma fst_top [simp]: "fst top = top"
   120   unfolding top_prod_def by simp
   121 
   122 lemma snd_top [simp]: "snd top = top"
   123   unfolding top_prod_def by simp
   124 
   125 lemma Pair_top_top: "(top, top) = top"
   126   unfolding top_prod_def by simp
   127 
   128 instance prod :: (order_top, order_top) order_top
   129   by standard (auto simp add: top_prod_def)
   130 
   131 instantiation prod :: (bot, bot) bot
   132 begin
   133 
   134 definition
   135   "bot = (bot, bot)"
   136 
   137 instance ..
   138 
   139 end
   140 
   141 lemma fst_bot [simp]: "fst bot = bot"
   142   unfolding bot_prod_def by simp
   143 
   144 lemma snd_bot [simp]: "snd bot = bot"
   145   unfolding bot_prod_def by simp
   146 
   147 lemma Pair_bot_bot: "(bot, bot) = bot"
   148   unfolding bot_prod_def by simp
   149 
   150 instance prod :: (order_bot, order_bot) order_bot
   151   by standard (auto simp add: bot_prod_def)
   152 
   153 instance prod :: (bounded_lattice, bounded_lattice) bounded_lattice ..
   154 
   155 instance prod :: (boolean_algebra, boolean_algebra) boolean_algebra
   156   by standard (auto simp add: prod_eqI diff_eq)
   157 
   158 
   159 subsection \<open>Complete lattice operations\<close>
   160 
   161 instantiation prod :: (Inf, Inf) Inf
   162 begin
   163 
   164 definition "Inf A = (INF x:A. fst x, INF x:A. snd x)"
   165 
   166 instance ..
   167 
   168 end
   169 
   170 instantiation prod :: (Sup, Sup) Sup
   171 begin
   172 
   173 definition "Sup A = (SUP x:A. fst x, SUP x:A. snd x)"
   174 
   175 instance ..
   176 
   177 end
   178 
   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)+
   183 
   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)
   187 
   188 lemma fst_Sup: "fst (Sup A) = (SUP x:A. fst x)"
   189   unfolding Sup_prod_def by simp
   190 
   191 lemma snd_Sup: "snd (Sup A) = (SUP x:A. snd x)"
   192   unfolding Sup_prod_def by simp
   193 
   194 lemma fst_Inf: "fst (Inf A) = (INF x:A. fst x)"
   195   unfolding Inf_prod_def by simp
   196 
   197 lemma snd_Inf: "snd (Inf A) = (INF x:A. snd x)"
   198   unfolding Inf_prod_def by simp
   199 
   200 lemma fst_SUP: "fst (SUP x:A. f x) = (SUP x:A. fst (f x))"
   201   using fst_Sup [of "f ` A", symmetric] by (simp add: comp_def)
   202 
   203 lemma snd_SUP: "snd (SUP x:A. f x) = (SUP x:A. snd (f x))"
   204   using snd_Sup [of "f ` A", symmetric] by (simp add: comp_def)
   205 
   206 lemma fst_INF: "fst (INF x:A. f x) = (INF x:A. fst (f x))"
   207   using fst_Inf [of "f ` A", symmetric] by (simp add: comp_def)
   208 
   209 lemma snd_INF: "snd (INF x:A. f x) = (INF x:A. snd (f x))"
   210   using snd_Inf [of "f ` A", symmetric] by (simp add: comp_def)
   211 
   212 lemma SUP_Pair: "(SUP x:A. (f x, g x)) = (SUP x:A. f x, SUP x:A. g x)"
   213   unfolding Sup_prod_def by (simp add: comp_def)
   214 
   215 lemma INF_Pair: "(INF x:A. (f x, g x)) = (INF x:A. f x, INF x:A. g x)"
   216   unfolding Inf_prod_def by (simp add: comp_def)
   217 
   218 
   219 text \<open>Alternative formulations for set infima and suprema over the product
   220 of two complete lattices:\<close>
   221 
   222 lemma INF_prod_alt_def:
   223   "INFIMUM A f = (INFIMUM A (fst o f), INFIMUM A (snd o f))"
   224   unfolding Inf_prod_def by simp
   225 
   226 lemma SUP_prod_alt_def:
   227   "SUPREMUM A f = (SUPREMUM A (fst o f), SUPREMUM A (snd o f))"
   228   unfolding Sup_prod_def by simp
   229 
   230 
   231 subsection \<open>Complete distributive lattices\<close>
   232 
   233 (* Contribution: Alessandro Coglio *)
   234 
   235 instance prod :: (complete_distrib_lattice, complete_distrib_lattice) complete_distrib_lattice
   236 proof (standard, goal_cases)
   237   case 1
   238   then show ?case
   239     by (auto simp: sup_prod_def Inf_prod_def INF_prod_alt_def sup_Inf sup_INF comp_def)
   240 next
   241   case 2
   242   then show ?case
   243     by (auto simp: inf_prod_def Sup_prod_def SUP_prod_alt_def inf_Sup inf_SUP comp_def)
   244 qed
   245 
   246 subsection \<open>Bekic's Theorem\<close>
   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