src/HOL/Library/Product_Order.thy
 author haftmann Fri Mar 22 19:18:08 2019 +0000 (4 months ago) changeset 69946 494934c30f38 parent 69895 6b03a8cf092d permissions -rw-r--r--
improved code equations taken over from AFP
```     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\<in>A. fst x, INF x\<in>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\<in>A. fst x, SUP x\<in>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_Inf: "fst (Inf A) = (INF x\<in>A. fst x)"
```
```   189   by (simp add: Inf_prod_def)
```
```   190
```
```   191 lemma fst_INF: "fst (INF x\<in>A. f x) = (INF x\<in>A. fst (f x))"
```
```   192   by (simp add: fst_Inf image_image)
```
```   193
```
```   194 lemma fst_Sup: "fst (Sup A) = (SUP x\<in>A. fst x)"
```
```   195   by (simp add: Sup_prod_def)
```
```   196
```
```   197 lemma fst_SUP: "fst (SUP x\<in>A. f x) = (SUP x\<in>A. fst (f x))"
```
```   198   by (simp add: fst_Sup image_image)
```
```   199
```
```   200 lemma snd_Inf: "snd (Inf A) = (INF x\<in>A. snd x)"
```
```   201   by (simp add: Inf_prod_def)
```
```   202
```
```   203 lemma snd_INF: "snd (INF x\<in>A. f x) = (INF x\<in>A. snd (f x))"
```
```   204   by (simp add: snd_Inf image_image)
```
```   205
```
```   206 lemma snd_Sup: "snd (Sup A) = (SUP x\<in>A. snd x)"
```
```   207   by (simp add: Sup_prod_def)
```
```   208
```
```   209 lemma snd_SUP: "snd (SUP x\<in>A. f x) = (SUP x\<in>A. snd (f x))"
```
```   210   by (simp add: snd_Sup image_image)
```
```   211
```
```   212 lemma INF_Pair: "(INF x\<in>A. (f x, g x)) = (INF x\<in>A. f x, INF x\<in>A. g x)"
```
```   213   by (simp add: Inf_prod_def image_image)
```
```   214
```
```   215 lemma SUP_Pair: "(SUP x\<in>A. (f x, g x)) = (SUP x\<in>A. f x, SUP x\<in>A. g x)"
```
```   216   by (simp add: Sup_prod_def image_image)
```
```   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: \<^marker>\<open>contributor \<open>Alessandro Coglio\<close>\<close>
```
```   223   "Inf (f ` A) = (Inf ((fst \<circ> f) ` A), Inf ((snd \<circ> f) ` A))"
```
```   224   by (simp add: Inf_prod_def image_image)
```
```   225
```
```   226 lemma SUP_prod_alt_def: \<^marker>\<open>contributor \<open>Alessandro Coglio\<close>\<close>
```
```   227   "Sup (f ` A) = (Sup ((fst \<circ> f) ` A), Sup((snd \<circ> f) ` A))"
```
```   228   by (simp add: Sup_prod_def image_image)
```
```   229
```
```   230
```
```   231 subsection \<open>Complete distributive lattices\<close>
```
```   232
```
```   233 instance prod :: (complete_distrib_lattice, complete_distrib_lattice) complete_distrib_lattice \<^marker>\<open>contributor \<open>Alessandro Coglio\<close>\<close>
```
```   234 proof
```
```   235   fix A::"('a\<times>'b) set set"
```
```   236   show "Inf (Sup ` A) \<le> Sup (Inf ` {f ` A |f. \<forall>Y\<in>A. f Y \<in> Y})"
```
```   237     by (simp add: Inf_prod_def Sup_prod_def INF_SUP_set image_image)
```
```   238 qed
```
```   239
```
```   240 subsection \<open>Bekic's Theorem\<close>
```
```   241 text \<open>
```
```   242   Simultaneous fixed points over pairs can be written in terms of separate fixed points.
```
```   243   Transliterated from HOLCF.Fix by Peter Gammie
```
```   244 \<close>
```
```   245
```
```   246 lemma lfp_prod:
```
```   247   fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
```
```   248   assumes "mono F"
```
```   249   shows "lfp F = (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))),
```
```   250                  (lfp (\<lambda>y. snd (F (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))), y)))))"
```
```   251   (is "lfp F = (?x, ?y)")
```
```   252 proof(rule lfp_eqI[OF assms])
```
```   253   have 1: "fst (F (?x, ?y)) = ?x"
```
```   254     by (rule trans [symmetric, OF lfp_unfold])
```
```   255        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
```
```   256   have 2: "snd (F (?x, ?y)) = ?y"
```
```   257     by (rule trans [symmetric, OF lfp_unfold])
```
```   258        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
```
```   259   from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
```
```   260 next
```
```   261   fix z assume F_z: "F z = z"
```
```   262   obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
```
```   263   from F_z z have F_x: "fst (F (x, y)) = x" by simp
```
```   264   from F_z z have F_y: "snd (F (x, y)) = y" by simp
```
```   265   let ?y1 = "lfp (\<lambda>y. snd (F (x, y)))"
```
```   266   have "?y1 \<le> y" by (rule lfp_lowerbound, simp add: F_y)
```
```   267   hence "fst (F (x, ?y1)) \<le> fst (F (x, y))"
```
```   268     by (simp add: assms fst_mono monoD)
```
```   269   hence "fst (F (x, ?y1)) \<le> x" using F_x by simp
```
```   270   hence 1: "?x \<le> x" by (simp add: lfp_lowerbound)
```
```   271   hence "snd (F (?x, y)) \<le> snd (F (x, y))"
```
```   272     by (simp add: assms snd_mono monoD)
```
```   273   hence "snd (F (?x, y)) \<le> y" using F_y by simp
```
```   274   hence 2: "?y \<le> y" by (simp add: lfp_lowerbound)
```
```   275   show "(?x, ?y) \<le> z" using z 1 2 by simp
```
```   276 qed
```
```   277
```
```   278 lemma gfp_prod:
```
```   279   fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
```
```   280   assumes "mono F"
```
```   281   shows "gfp F = (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))),
```
```   282                  (gfp (\<lambda>y. snd (F (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))), y)))))"
```
```   283   (is "gfp F = (?x, ?y)")
```
```   284 proof(rule gfp_eqI[OF assms])
```
```   285   have 1: "fst (F (?x, ?y)) = ?x"
```
```   286     by (rule trans [symmetric, OF gfp_unfold])
```
```   287        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
```
```   288   have 2: "snd (F (?x, ?y)) = ?y"
```
```   289     by (rule trans [symmetric, OF gfp_unfold])
```
```   290        (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
```
```   291   from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
```
```   292 next
```
```   293   fix z assume F_z: "F z = z"
```
```   294   obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
```
```   295   from F_z z have F_x: "fst (F (x, y)) = x" by simp
```
```   296   from F_z z have F_y: "snd (F (x, y)) = y" by simp
```
```   297   let ?y1 = "gfp (\<lambda>y. snd (F (x, y)))"
```
```   298   have "y \<le> ?y1" by (rule gfp_upperbound, simp add: F_y)
```
```   299   hence "fst (F (x, y)) \<le> fst (F (x, ?y1))"
```
```   300     by (simp add: assms fst_mono monoD)
```
```   301   hence "x \<le> fst (F (x, ?y1))" using F_x by simp
```
```   302   hence 1: "x \<le> ?x" by (simp add: gfp_upperbound)
```
```   303   hence "snd (F (x, y)) \<le> snd (F (?x, y))"
```
```   304     by (simp add: assms snd_mono monoD)
```
```   305   hence "y \<le> snd (F (?x, y))" using F_y by simp
```
```   306   hence 2: "y \<le> ?y" by (simp add: gfp_upperbound)
```
```   307   show "z \<le> (?x, ?y)" using z 1 2 by simp
```
```   308 qed
```
```   309
```
```   310 end
```