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;
haftmann@51115
     1
(*  Title:      HOL/Library/Product_Order.thy
huffman@44006
     2
    Author:     Brian Huffman
huffman@44006
     3
*)
huffman@44006
     4
wenzelm@60500
     5
section \<open>Pointwise order on product types\<close>
huffman@44006
     6
haftmann@51115
     7
theory Product_Order
hoelzl@63972
     8
imports Product_Plus
huffman@44006
     9
begin
huffman@44006
    10
wenzelm@60500
    11
subsection \<open>Pointwise ordering\<close>
huffman@44006
    12
huffman@44006
    13
instantiation prod :: (ord, ord) ord
huffman@44006
    14
begin
huffman@44006
    15
huffman@44006
    16
definition
huffman@44006
    17
  "x \<le> y \<longleftrightarrow> fst x \<le> fst y \<and> snd x \<le> snd y"
huffman@44006
    18
huffman@44006
    19
definition
huffman@44006
    20
  "(x::'a \<times> 'b) < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
huffman@44006
    21
huffman@44006
    22
instance ..
huffman@44006
    23
huffman@44006
    24
end
huffman@44006
    25
huffman@44006
    26
lemma fst_mono: "x \<le> y \<Longrightarrow> fst x \<le> fst y"
huffman@44006
    27
  unfolding less_eq_prod_def by simp
huffman@44006
    28
huffman@44006
    29
lemma snd_mono: "x \<le> y \<Longrightarrow> snd x \<le> snd y"
huffman@44006
    30
  unfolding less_eq_prod_def by simp
huffman@44006
    31
huffman@44006
    32
lemma Pair_mono: "x \<le> x' \<Longrightarrow> y \<le> y' \<Longrightarrow> (x, y) \<le> (x', y')"
huffman@44006
    33
  unfolding less_eq_prod_def by simp
huffman@44006
    34
huffman@44006
    35
lemma Pair_le [simp]: "(a, b) \<le> (c, d) \<longleftrightarrow> a \<le> c \<and> b \<le> d"
huffman@44006
    36
  unfolding less_eq_prod_def by simp
huffman@44006
    37
huffman@44006
    38
instance prod :: (preorder, preorder) preorder
huffman@44006
    39
proof
huffman@44006
    40
  fix x y z :: "'a \<times> 'b"
huffman@44006
    41
  show "x < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
huffman@44006
    42
    by (rule less_prod_def)
huffman@44006
    43
  show "x \<le> x"
huffman@44006
    44
    unfolding less_eq_prod_def
huffman@44006
    45
    by fast
huffman@44006
    46
  assume "x \<le> y" and "y \<le> z" thus "x \<le> z"
huffman@44006
    47
    unfolding less_eq_prod_def
huffman@44006
    48
    by (fast elim: order_trans)
huffman@44006
    49
qed
huffman@44006
    50
huffman@44006
    51
instance prod :: (order, order) order
wenzelm@60679
    52
  by standard auto
huffman@44006
    53
huffman@44006
    54
wenzelm@60500
    55
subsection \<open>Binary infimum and supremum\<close>
huffman@44006
    56
immler@54776
    57
instantiation prod :: (inf, inf) inf
huffman@44006
    58
begin
huffman@44006
    59
wenzelm@60679
    60
definition "inf x y = (inf (fst x) (fst y), inf (snd x) (snd y))"
huffman@44006
    61
huffman@44006
    62
lemma inf_Pair_Pair [simp]: "inf (a, b) (c, d) = (inf a c, inf b d)"
huffman@44006
    63
  unfolding inf_prod_def by simp
huffman@44006
    64
huffman@44006
    65
lemma fst_inf [simp]: "fst (inf x y) = inf (fst x) (fst y)"
huffman@44006
    66
  unfolding inf_prod_def by simp
huffman@44006
    67
huffman@44006
    68
lemma snd_inf [simp]: "snd (inf x y) = inf (snd x) (snd y)"
huffman@44006
    69
  unfolding inf_prod_def by simp
huffman@44006
    70
wenzelm@60679
    71
instance ..
wenzelm@60679
    72
immler@54776
    73
end
immler@54776
    74
immler@54776
    75
instance prod :: (semilattice_inf, semilattice_inf) semilattice_inf
wenzelm@60679
    76
  by standard auto
huffman@44006
    77
huffman@44006
    78
immler@54776
    79
instantiation prod :: (sup, sup) sup
huffman@44006
    80
begin
huffman@44006
    81
huffman@44006
    82
definition
huffman@44006
    83
  "sup x y = (sup (fst x) (fst y), sup (snd x) (snd y))"
huffman@44006
    84
huffman@44006
    85
lemma sup_Pair_Pair [simp]: "sup (a, b) (c, d) = (sup a c, sup b d)"
huffman@44006
    86
  unfolding sup_prod_def by simp
huffman@44006
    87
huffman@44006
    88
lemma fst_sup [simp]: "fst (sup x y) = sup (fst x) (fst y)"
huffman@44006
    89
  unfolding sup_prod_def by simp
huffman@44006
    90
huffman@44006
    91
lemma snd_sup [simp]: "snd (sup x y) = sup (snd x) (snd y)"
huffman@44006
    92
  unfolding sup_prod_def by simp
huffman@44006
    93
wenzelm@60679
    94
instance ..
wenzelm@60679
    95
immler@54776
    96
end
immler@54776
    97
immler@54776
    98
instance prod :: (semilattice_sup, semilattice_sup) semilattice_sup
wenzelm@60679
    99
  by standard auto
huffman@44006
   100
huffman@44006
   101
instance prod :: (lattice, lattice) lattice ..
huffman@44006
   102
huffman@44006
   103
instance prod :: (distrib_lattice, distrib_lattice) distrib_lattice
wenzelm@60679
   104
  by standard (auto simp add: sup_inf_distrib1)
huffman@44006
   105
huffman@44006
   106
wenzelm@60500
   107
subsection \<open>Top and bottom elements\<close>
huffman@44006
   108
huffman@44006
   109
instantiation prod :: (top, top) top
huffman@44006
   110
begin
huffman@44006
   111
huffman@44006
   112
definition
huffman@44006
   113
  "top = (top, top)"
huffman@44006
   114
haftmann@52729
   115
instance ..
haftmann@52729
   116
haftmann@52729
   117
end
haftmann@52729
   118
huffman@44006
   119
lemma fst_top [simp]: "fst top = top"
huffman@44006
   120
  unfolding top_prod_def by simp
huffman@44006
   121
huffman@44006
   122
lemma snd_top [simp]: "snd top = top"
huffman@44006
   123
  unfolding top_prod_def by simp
huffman@44006
   124
huffman@44006
   125
lemma Pair_top_top: "(top, top) = top"
huffman@44006
   126
  unfolding top_prod_def by simp
huffman@44006
   127
haftmann@52729
   128
instance prod :: (order_top, order_top) order_top
wenzelm@60679
   129
  by standard (auto simp add: top_prod_def)
huffman@44006
   130
huffman@44006
   131
instantiation prod :: (bot, bot) bot
huffman@44006
   132
begin
huffman@44006
   133
huffman@44006
   134
definition
huffman@44006
   135
  "bot = (bot, bot)"
huffman@44006
   136
haftmann@52729
   137
instance ..
haftmann@52729
   138
haftmann@52729
   139
end
haftmann@52729
   140
huffman@44006
   141
lemma fst_bot [simp]: "fst bot = bot"
huffman@44006
   142
  unfolding bot_prod_def by simp
huffman@44006
   143
huffman@44006
   144
lemma snd_bot [simp]: "snd bot = bot"
huffman@44006
   145
  unfolding bot_prod_def by simp
huffman@44006
   146
huffman@44006
   147
lemma Pair_bot_bot: "(bot, bot) = bot"
huffman@44006
   148
  unfolding bot_prod_def by simp
huffman@44006
   149
haftmann@52729
   150
instance prod :: (order_bot, order_bot) order_bot
wenzelm@60679
   151
  by standard (auto simp add: bot_prod_def)
huffman@44006
   152
huffman@44006
   153
instance prod :: (bounded_lattice, bounded_lattice) bounded_lattice ..
huffman@44006
   154
huffman@44006
   155
instance prod :: (boolean_algebra, boolean_algebra) boolean_algebra
wenzelm@62053
   156
  by standard (auto simp add: prod_eqI diff_eq)
huffman@44006
   157
huffman@44006
   158
wenzelm@60500
   159
subsection \<open>Complete lattice operations\<close>
huffman@44006
   160
immler@54776
   161
instantiation prod :: (Inf, Inf) Inf
immler@54776
   162
begin
immler@54776
   163
wenzelm@60679
   164
definition "Inf A = (INF x:A. fst x, INF x:A. snd x)"
immler@54776
   165
wenzelm@60679
   166
instance ..
wenzelm@60679
   167
immler@54776
   168
end
immler@54776
   169
immler@54776
   170
instantiation prod :: (Sup, Sup) Sup
huffman@44006
   171
begin
huffman@44006
   172
wenzelm@60679
   173
definition "Sup A = (SUP x:A. fst x, SUP x:A. snd x)"
huffman@44006
   174
wenzelm@60679
   175
instance ..
wenzelm@60679
   176
immler@54776
   177
end
huffman@44006
   178
immler@54776
   179
instance prod :: (conditionally_complete_lattice, conditionally_complete_lattice)
immler@54776
   180
    conditionally_complete_lattice
wenzelm@60679
   181
  by standard (force simp: less_eq_prod_def Inf_prod_def Sup_prod_def bdd_below_def bdd_above_def
wenzelm@62053
   182
    intro!: cInf_lower cSup_upper cInf_greatest cSup_least)+
immler@54776
   183
immler@54776
   184
instance prod :: (complete_lattice, complete_lattice) complete_lattice
wenzelm@60679
   185
  by standard (simp_all add: less_eq_prod_def Inf_prod_def Sup_prod_def
haftmann@52729
   186
    INF_lower SUP_upper le_INF_iff SUP_le_iff bot_prod_def top_prod_def)
huffman@44006
   187
huffman@44006
   188
lemma fst_Sup: "fst (Sup A) = (SUP x:A. fst x)"
huffman@44006
   189
  unfolding Sup_prod_def by simp
huffman@44006
   190
huffman@44006
   191
lemma snd_Sup: "snd (Sup A) = (SUP x:A. snd x)"
huffman@44006
   192
  unfolding Sup_prod_def by simp
huffman@44006
   193
huffman@44006
   194
lemma fst_Inf: "fst (Inf A) = (INF x:A. fst x)"
huffman@44006
   195
  unfolding Inf_prod_def by simp
huffman@44006
   196
huffman@44006
   197
lemma snd_Inf: "snd (Inf A) = (INF x:A. snd x)"
huffman@44006
   198
  unfolding Inf_prod_def by simp
huffman@44006
   199
huffman@44006
   200
lemma fst_SUP: "fst (SUP x:A. f x) = (SUP x:A. fst (f x))"
haftmann@56166
   201
  using fst_Sup [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006
   202
huffman@44006
   203
lemma snd_SUP: "snd (SUP x:A. f x) = (SUP x:A. snd (f x))"
haftmann@56166
   204
  using snd_Sup [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006
   205
huffman@44006
   206
lemma fst_INF: "fst (INF x:A. f x) = (INF x:A. fst (f x))"
haftmann@56166
   207
  using fst_Inf [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006
   208
huffman@44006
   209
lemma snd_INF: "snd (INF x:A. f x) = (INF x:A. snd (f x))"
haftmann@56166
   210
  using snd_Inf [of "f ` A", symmetric] by (simp add: comp_def)
huffman@44006
   211
huffman@44006
   212
lemma SUP_Pair: "(SUP x:A. (f x, g x)) = (SUP x:A. f x, SUP x:A. g x)"
haftmann@62343
   213
  unfolding Sup_prod_def by (simp add: comp_def)
huffman@44006
   214
huffman@44006
   215
lemma INF_Pair: "(INF x:A. (f x, g x)) = (INF x:A. f x, INF x:A. g x)"
haftmann@62343
   216
  unfolding Inf_prod_def by (simp add: comp_def)
huffman@44006
   217
nipkow@50535
   218
wenzelm@60500
   219
text \<open>Alternative formulations for set infima and suprema over the product
wenzelm@60500
   220
of two complete lattices:\<close>
nipkow@50535
   221
haftmann@56212
   222
lemma INF_prod_alt_def:
haftmann@56218
   223
  "INFIMUM A f = (INFIMUM A (fst o f), INFIMUM A (snd o f))"
haftmann@62343
   224
  unfolding Inf_prod_def by simp
nipkow@50535
   225
haftmann@56212
   226
lemma SUP_prod_alt_def:
haftmann@56218
   227
  "SUPREMUM A f = (SUPREMUM A (fst o f), SUPREMUM A (snd o f))"
haftmann@62343
   228
  unfolding Sup_prod_def by simp
nipkow@50535
   229
nipkow@50535
   230
wenzelm@60500
   231
subsection \<open>Complete distributive lattices\<close>
nipkow@50535
   232
nipkow@50573
   233
(* Contribution: Alessandro Coglio *)
nipkow@50535
   234
wenzelm@60679
   235
instance prod :: (complete_distrib_lattice, complete_distrib_lattice) complete_distrib_lattice
wenzelm@61166
   236
proof (standard, goal_cases)
wenzelm@60580
   237
  case 1
wenzelm@60580
   238
  then show ?case
haftmann@56212
   239
    by (auto simp: sup_prod_def Inf_prod_def INF_prod_alt_def sup_Inf sup_INF comp_def)
nipkow@50535
   240
next
wenzelm@60580
   241
  case 2
wenzelm@60580
   242
  then show ?case
haftmann@56212
   243
    by (auto simp: inf_prod_def Sup_prod_def SUP_prod_alt_def inf_Sup inf_SUP comp_def)
nipkow@50535
   244
qed
nipkow@50535
   245
Andreas@63561
   246
subsection \<open>Bekic's Theorem\<close>
Andreas@63561
   247
text \<open>
Andreas@63561
   248
  Simultaneous fixed points over pairs can be written in terms of separate fixed points.
Andreas@63561
   249
  Transliterated from HOLCF.Fix by Peter Gammie
Andreas@63561
   250
\<close>
Andreas@63561
   251
Andreas@63561
   252
lemma lfp_prod:
Andreas@63561
   253
  fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
Andreas@63561
   254
  assumes "mono F"
Andreas@63561
   255
  shows "lfp F = (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))),
Andreas@63561
   256
                 (lfp (\<lambda>y. snd (F (lfp (\<lambda>x. fst (F (x, lfp (\<lambda>y. snd (F (x, y)))))), y)))))"
Andreas@63561
   257
  (is "lfp F = (?x, ?y)")
Andreas@63561
   258
proof(rule lfp_eqI[OF assms])
Andreas@63561
   259
  have 1: "fst (F (?x, ?y)) = ?x"
Andreas@63561
   260
    by (rule trans [symmetric, OF lfp_unfold])
Andreas@63561
   261
       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
Andreas@63561
   262
  have 2: "snd (F (?x, ?y)) = ?y"
Andreas@63561
   263
    by (rule trans [symmetric, OF lfp_unfold])
Andreas@63561
   264
       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono lfp_mono)+
Andreas@63561
   265
  from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
Andreas@63561
   266
next
Andreas@63561
   267
  fix z assume F_z: "F z = z"
Andreas@63561
   268
  obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
Andreas@63561
   269
  from F_z z have F_x: "fst (F (x, y)) = x" by simp
Andreas@63561
   270
  from F_z z have F_y: "snd (F (x, y)) = y" by simp
Andreas@63561
   271
  let ?y1 = "lfp (\<lambda>y. snd (F (x, y)))"
Andreas@63561
   272
  have "?y1 \<le> y" by (rule lfp_lowerbound, simp add: F_y)
Andreas@63561
   273
  hence "fst (F (x, ?y1)) \<le> fst (F (x, y))"
Andreas@63561
   274
    by (simp add: assms fst_mono monoD)
Andreas@63561
   275
  hence "fst (F (x, ?y1)) \<le> x" using F_x by simp
Andreas@63561
   276
  hence 1: "?x \<le> x" by (simp add: lfp_lowerbound)
Andreas@63561
   277
  hence "snd (F (?x, y)) \<le> snd (F (x, y))"
Andreas@63561
   278
    by (simp add: assms snd_mono monoD)
Andreas@63561
   279
  hence "snd (F (?x, y)) \<le> y" using F_y by simp
Andreas@63561
   280
  hence 2: "?y \<le> y" by (simp add: lfp_lowerbound)
Andreas@63561
   281
  show "(?x, ?y) \<le> z" using z 1 2 by simp
Andreas@63561
   282
qed
Andreas@63561
   283
Andreas@63561
   284
lemma gfp_prod:
Andreas@63561
   285
  fixes F :: "'a::complete_lattice \<times> 'b::complete_lattice \<Rightarrow> 'a \<times> 'b"
Andreas@63561
   286
  assumes "mono F"
Andreas@63561
   287
  shows "gfp F = (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))),
Andreas@63561
   288
                 (gfp (\<lambda>y. snd (F (gfp (\<lambda>x. fst (F (x, gfp (\<lambda>y. snd (F (x, y)))))), y)))))"
Andreas@63561
   289
  (is "gfp F = (?x, ?y)")
Andreas@63561
   290
proof(rule gfp_eqI[OF assms])
Andreas@63561
   291
  have 1: "fst (F (?x, ?y)) = ?x"
Andreas@63561
   292
    by (rule trans [symmetric, OF gfp_unfold])
Andreas@63561
   293
       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
Andreas@63561
   294
  have 2: "snd (F (?x, ?y)) = ?y"
Andreas@63561
   295
    by (rule trans [symmetric, OF gfp_unfold])
Andreas@63561
   296
       (blast intro!: monoI monoD[OF assms(1)] fst_mono snd_mono Pair_mono gfp_mono)+
Andreas@63561
   297
  from 1 2 show "F (?x, ?y) = (?x, ?y)" by (simp add: prod_eq_iff)
Andreas@63561
   298
next
Andreas@63561
   299
  fix z assume F_z: "F z = z"
Andreas@63561
   300
  obtain x y where z: "z = (x, y)" by (rule prod.exhaust)
Andreas@63561
   301
  from F_z z have F_x: "fst (F (x, y)) = x" by simp
Andreas@63561
   302
  from F_z z have F_y: "snd (F (x, y)) = y" by simp
Andreas@63561
   303
  let ?y1 = "gfp (\<lambda>y. snd (F (x, y)))"
Andreas@63561
   304
  have "y \<le> ?y1" by (rule gfp_upperbound, simp add: F_y)
Andreas@63561
   305
  hence "fst (F (x, y)) \<le> fst (F (x, ?y1))"
Andreas@63561
   306
    by (simp add: assms fst_mono monoD)
Andreas@63561
   307
  hence "x \<le> fst (F (x, ?y1))" using F_x by simp
Andreas@63561
   308
  hence 1: "x \<le> ?x" by (simp add: gfp_upperbound)
Andreas@63561
   309
  hence "snd (F (x, y)) \<le> snd (F (?x, y))"
Andreas@63561
   310
    by (simp add: assms snd_mono monoD)
Andreas@63561
   311
  hence "y \<le> snd (F (?x, y))" using F_y by simp
Andreas@63561
   312
  hence 2: "y \<le> ?y" by (simp add: gfp_upperbound)
Andreas@63561
   313
  show "z \<le> (?x, ?y)" using z 1 2 by simp
Andreas@63561
   314
qed
Andreas@63561
   315
haftmann@51115
   316
end