src/HOL/Library/Product_Order.thy
 author haftmann Sun Mar 16 18:09:04 2014 +0100 (2014-03-16) changeset 56166 9a241bc276cd parent 56154 f0a927235162 child 56212 3253aaf73a01 permissions -rw-r--r--
normalising simp rules for compound operators
```     1 (*  Title:      HOL/Library/Product_Order.thy
```
```     2     Author:     Brian Huffman
```
```     3 *)
```
```     4
```
```     5 header {* Pointwise order on product types *}
```
```     6
```
```     7 theory Product_Order
```
```     8 imports Product_plus Conditionally_Complete_Lattices
```
```     9 begin
```
```    10
```
```    11 subsection {* Pointwise ordering *}
```
```    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 default auto
```
```    53
```
```    54
```
```    55 subsection {* Binary infimum and supremum *}
```
```    56
```
```    57 instantiation prod :: (inf, inf) inf
```
```    58 begin
```
```    59
```
```    60 definition
```
```    61   "inf x y = (inf (fst x) (fst y), inf (snd x) (snd y))"
```
```    62
```
```    63 lemma inf_Pair_Pair [simp]: "inf (a, b) (c, d) = (inf a c, inf b d)"
```
```    64   unfolding inf_prod_def by simp
```
```    65
```
```    66 lemma fst_inf [simp]: "fst (inf x y) = inf (fst x) (fst y)"
```
```    67   unfolding inf_prod_def by simp
```
```    68
```
```    69 lemma snd_inf [simp]: "snd (inf x y) = inf (snd x) (snd y)"
```
```    70   unfolding inf_prod_def by simp
```
```    71
```
```    72 instance proof qed
```
```    73 end
```
```    74
```
```    75 instance prod :: (semilattice_inf, semilattice_inf) semilattice_inf
```
```    76   by default 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 proof qed
```
```    95 end
```
```    96
```
```    97 instance prod :: (semilattice_sup, semilattice_sup) semilattice_sup
```
```    98   by default auto
```
```    99
```
```   100 instance prod :: (lattice, lattice) lattice ..
```
```   101
```
```   102 instance prod :: (distrib_lattice, distrib_lattice) distrib_lattice
```
```   103   by default (auto simp add: sup_inf_distrib1)
```
```   104
```
```   105
```
```   106 subsection {* Top and bottom elements *}
```
```   107
```
```   108 instantiation prod :: (top, top) top
```
```   109 begin
```
```   110
```
```   111 definition
```
```   112   "top = (top, top)"
```
```   113
```
```   114 instance ..
```
```   115
```
```   116 end
```
```   117
```
```   118 lemma fst_top [simp]: "fst top = top"
```
```   119   unfolding top_prod_def by simp
```
```   120
```
```   121 lemma snd_top [simp]: "snd top = top"
```
```   122   unfolding top_prod_def by simp
```
```   123
```
```   124 lemma Pair_top_top: "(top, top) = top"
```
```   125   unfolding top_prod_def by simp
```
```   126
```
```   127 instance prod :: (order_top, order_top) order_top
```
```   128   by default (auto simp add: top_prod_def)
```
```   129
```
```   130 instantiation prod :: (bot, bot) bot
```
```   131 begin
```
```   132
```
```   133 definition
```
```   134   "bot = (bot, bot)"
```
```   135
```
```   136 instance ..
```
```   137
```
```   138 end
```
```   139
```
```   140 lemma fst_bot [simp]: "fst bot = bot"
```
```   141   unfolding bot_prod_def by simp
```
```   142
```
```   143 lemma snd_bot [simp]: "snd bot = bot"
```
```   144   unfolding bot_prod_def by simp
```
```   145
```
```   146 lemma Pair_bot_bot: "(bot, bot) = bot"
```
```   147   unfolding bot_prod_def by simp
```
```   148
```
```   149 instance prod :: (order_bot, order_bot) order_bot
```
```   150   by default (auto simp add: bot_prod_def)
```
```   151
```
```   152 instance prod :: (bounded_lattice, bounded_lattice) bounded_lattice ..
```
```   153
```
```   154 instance prod :: (boolean_algebra, boolean_algebra) boolean_algebra
```
```   155   by default (auto simp add: prod_eqI inf_compl_bot sup_compl_top diff_eq)
```
```   156
```
```   157
```
```   158 subsection {* Complete lattice operations *}
```
```   159
```
```   160 instantiation prod :: (Inf, Inf) Inf
```
```   161 begin
```
```   162
```
```   163 definition
```
```   164   "Inf A = (INF x:A. fst x, INF x:A. snd x)"
```
```   165
```
```   166 instance proof qed
```
```   167 end
```
```   168
```
```   169 instantiation prod :: (Sup, Sup) Sup
```
```   170 begin
```
```   171
```
```   172 definition
```
```   173   "Sup A = (SUP x:A. fst x, SUP x:A. snd x)"
```
```   174
```
```   175 instance proof qed
```
```   176 end
```
```   177
```
```   178 instance prod :: (conditionally_complete_lattice, conditionally_complete_lattice)
```
```   179     conditionally_complete_lattice
```
```   180   by default (force simp: less_eq_prod_def Inf_prod_def Sup_prod_def bdd_below_def bdd_above_def
```
```   181     INF_def SUP_def simp del: Inf_image_eq Sup_image_eq intro!: cInf_lower cSup_upper cInf_greatest cSup_least)+
```
```   182
```
```   183 instance prod :: (complete_lattice, complete_lattice) complete_lattice
```
```   184   by default (simp_all add: less_eq_prod_def Inf_prod_def Sup_prod_def
```
```   185     INF_lower SUP_upper le_INF_iff SUP_le_iff bot_prod_def top_prod_def)
```
```   186
```
```   187 lemma fst_Sup: "fst (Sup A) = (SUP x:A. fst x)"
```
```   188   unfolding Sup_prod_def by simp
```
```   189
```
```   190 lemma snd_Sup: "snd (Sup A) = (SUP x:A. snd x)"
```
```   191   unfolding Sup_prod_def by simp
```
```   192
```
```   193 lemma fst_Inf: "fst (Inf A) = (INF x:A. fst x)"
```
```   194   unfolding Inf_prod_def by simp
```
```   195
```
```   196 lemma snd_Inf: "snd (Inf A) = (INF x:A. snd x)"
```
```   197   unfolding Inf_prod_def by simp
```
```   198
```
```   199 lemma fst_SUP: "fst (SUP x:A. f x) = (SUP x:A. fst (f x))"
```
```   200   using fst_Sup [of "f ` A", symmetric] by (simp add: comp_def)
```
```   201
```
```   202 lemma snd_SUP: "snd (SUP x:A. f x) = (SUP x:A. snd (f x))"
```
```   203   using snd_Sup [of "f ` A", symmetric] by (simp add: comp_def)
```
```   204
```
```   205 lemma fst_INF: "fst (INF x:A. f x) = (INF x:A. fst (f x))"
```
```   206   using fst_Inf [of "f ` A", symmetric] by (simp add: comp_def)
```
```   207
```
```   208 lemma snd_INF: "snd (INF x:A. f x) = (INF x:A. snd (f x))"
```
```   209   using snd_Inf [of "f ` A", symmetric] by (simp add: comp_def)
```
```   210
```
```   211 lemma SUP_Pair: "(SUP x:A. (f x, g x)) = (SUP x:A. f x, SUP x:A. g x)"
```
```   212   unfolding SUP_def Sup_prod_def by (simp add: comp_def)
```
```   213
```
```   214 lemma INF_Pair: "(INF x:A. (f x, g x)) = (INF x:A. f x, INF x:A. g x)"
```
```   215   unfolding INF_def Inf_prod_def by (simp add: comp_def)
```
```   216
```
```   217
```
```   218 text {* Alternative formulations for set infima and suprema over the product
```
```   219 of two complete lattices: *}
```
```   220
```
```   221 lemma Inf_prod_alt_def: "Inf A = (Inf (fst ` A), Inf (snd ` A))"
```
```   222 by (auto simp: Inf_prod_def)
```
```   223
```
```   224 lemma Sup_prod_alt_def: "Sup A = (Sup (fst ` A), Sup (snd ` A))"
```
```   225 by (auto simp: Sup_prod_def)
```
```   226
```
```   227 lemma INFI_prod_alt_def: "INFI A f = (INFI A (fst o f), INFI A (snd o f))"
```
```   228   unfolding INF_def Inf_prod_def by simp
```
```   229
```
```   230 lemma SUPR_prod_alt_def: "SUPR A f = (SUPR A (fst o f), SUPR A (snd o f))"
```
```   231   unfolding SUP_def Sup_prod_def by simp
```
```   232
```
```   233 lemma INF_prod_alt_def:
```
```   234   "(INF x:A. f x) = (INF x:A. fst (f x), INF x:A. snd (f x))"
```
```   235   by (simp add: INFI_prod_alt_def comp_def)
```
```   236
```
```   237 lemma SUP_prod_alt_def:
```
```   238   "(SUP x:A. f x) = (SUP x:A. fst (f x), SUP x:A. snd (f x))"
```
```   239   by (simp add: SUPR_prod_alt_def comp_def)
```
```   240
```
```   241
```
```   242 subsection {* Complete distributive lattices *}
```
```   243
```
```   244 (* Contribution: Alessandro Coglio *)
```
```   245
```
```   246 instance prod ::
```
```   247   (complete_distrib_lattice, complete_distrib_lattice) complete_distrib_lattice
```
```   248 proof
```
```   249   case goal1 thus ?case
```
```   250     by (auto simp: sup_prod_def Inf_prod_def INF_prod_alt_def sup_Inf sup_INF)
```
```   251 next
```
```   252   case goal2 thus ?case
```
```   253     by (auto simp: inf_prod_def Sup_prod_def SUP_prod_alt_def inf_Sup inf_SUP)
```
```   254 qed
```
```   255
```
```   256 end
```
```   257
```