src/HOL/LOrder.thy
author haftmann
Wed Nov 15 17:05:39 2006 +0100 (2006-11-15)
changeset 21380 c4f79922bc81
parent 21312 1d39091a3208
child 21733 131dd2a27137
permissions -rw-r--r--
added interpretation
obua@14738
     1
(*  Title:   HOL/LOrder.thy
obua@14738
     2
    ID:      $Id$
obua@14738
     3
    Author:  Steven Obua, TU Muenchen
obua@14738
     4
*)
obua@14738
     5
nipkow@21312
     6
header "Lattice Orders"
obua@14738
     7
nipkow@15131
     8
theory LOrder
haftmann@21249
     9
imports Lattices
nipkow@15131
    10
begin
obua@14738
    11
nipkow@21312
    12
text {* The theory of lattices developed here is taken from
nipkow@21312
    13
\cite{Birkhoff79}.  *}
obua@14738
    14
obua@14738
    15
constdefs
obua@14738
    16
  is_meet :: "(('a::order) \<Rightarrow> 'a \<Rightarrow> 'a) \<Rightarrow> bool"
obua@14738
    17
  "is_meet m == ! a b x. m a b \<le> a \<and> m a b \<le> b \<and> (x \<le> a \<and> x \<le> b \<longrightarrow> x \<le> m a b)"
obua@14738
    18
  is_join :: "(('a::order) \<Rightarrow> 'a \<Rightarrow> 'a) \<Rightarrow> bool"
obua@14738
    19
  "is_join j == ! a b x. a \<le> j a b \<and> b \<le> j a b \<and> (a \<le> x \<and> b \<le> x \<longrightarrow> j a b \<le> x)"  
obua@14738
    20
obua@14738
    21
lemma is_meet_unique: 
obua@14738
    22
  assumes "is_meet u" "is_meet v" shows "u = v"
obua@14738
    23
proof -
obua@14738
    24
  {
obua@14738
    25
    fix a b :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"
obua@14738
    26
    assume a: "is_meet a"
obua@14738
    27
    assume b: "is_meet b"
obua@14738
    28
    {
obua@14738
    29
      fix x y 
obua@14738
    30
      let ?za = "a x y"
obua@14738
    31
      let ?zb = "b x y"
obua@14738
    32
      from a have za_le: "?za <= x & ?za <= y" by (auto simp add: is_meet_def)
obua@14738
    33
      with b have "?za <= ?zb" by (auto simp add: is_meet_def)
obua@14738
    34
    }
obua@14738
    35
  }
obua@14738
    36
  note f_le = this
obua@14738
    37
  show "u = v" by ((rule ext)+, simp_all add: order_antisym prems f_le) 
obua@14738
    38
qed
obua@14738
    39
obua@14738
    40
lemma is_join_unique: 
obua@14738
    41
  assumes "is_join u" "is_join v" shows "u = v"
obua@14738
    42
proof -
obua@14738
    43
  {
obua@14738
    44
    fix a b :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"
obua@14738
    45
    assume a: "is_join a"
obua@14738
    46
    assume b: "is_join b"
obua@14738
    47
    {
obua@14738
    48
      fix x y 
obua@14738
    49
      let ?za = "a x y"
obua@14738
    50
      let ?zb = "b x y"
obua@14738
    51
      from a have za_le: "x <= ?za & y <= ?za" by (auto simp add: is_join_def)
obua@14738
    52
      with b have "?zb <= ?za" by (auto simp add: is_join_def)
obua@14738
    53
    }
obua@14738
    54
  }
obua@14738
    55
  note f_le = this
obua@14738
    56
  show "u = v" by ((rule ext)+, simp_all add: order_antisym prems f_le) 
obua@14738
    57
qed
obua@14738
    58
obua@14738
    59
axclass join_semilorder < order
obua@14738
    60
  join_exists: "? j. is_join j"
obua@14738
    61
obua@14738
    62
axclass meet_semilorder < order
obua@14738
    63
  meet_exists: "? m. is_meet m"
obua@14738
    64
obua@14738
    65
axclass lorder < join_semilorder, meet_semilorder
obua@14738
    66
obua@14738
    67
constdefs
obua@14738
    68
  meet :: "('a::meet_semilorder) \<Rightarrow> 'a \<Rightarrow> 'a"
obua@14738
    69
  "meet == THE m. is_meet m"
obua@14738
    70
  join :: "('a::join_semilorder) \<Rightarrow> 'a \<Rightarrow> 'a"
obua@14738
    71
  "join ==  THE j. is_join j"
obua@14738
    72
obua@14738
    73
lemma is_meet_meet: "is_meet (meet::'a \<Rightarrow> 'a \<Rightarrow> ('a::meet_semilorder))"
obua@14738
    74
proof -
obua@14738
    75
  from meet_exists obtain k::"'a \<Rightarrow> 'a \<Rightarrow> 'a" where "is_meet k" ..
obua@14738
    76
  with is_meet_unique[of _ k] show ?thesis
obua@14738
    77
    by (simp add: meet_def theI[of is_meet])    
obua@14738
    78
qed
obua@14738
    79
obua@14738
    80
lemma meet_unique: "(is_meet m) = (m = meet)" 
obua@14738
    81
by (insert is_meet_meet, auto simp add: is_meet_unique)
obua@14738
    82
obua@14738
    83
lemma is_join_join: "is_join (join::'a \<Rightarrow> 'a \<Rightarrow> ('a::join_semilorder))"
obua@14738
    84
proof -
obua@14738
    85
  from join_exists obtain k::"'a \<Rightarrow> 'a \<Rightarrow> 'a" where "is_join k" ..
obua@14738
    86
  with is_join_unique[of _ k] show ?thesis
obua@14738
    87
    by (simp add: join_def theI[of is_join])    
obua@14738
    88
qed
obua@14738
    89
obua@14738
    90
lemma join_unique: "(is_join j) = (j = join)"
obua@14738
    91
by (insert is_join_join, auto simp add: is_join_unique)
obua@14738
    92
haftmann@21380
    93
interpretation lattice:
haftmann@21380
    94
  lattice ["op \<le> \<Colon> 'a\<Colon>lorder \<Rightarrow> 'a \<Rightarrow> bool" "op <" meet join]
haftmann@21380
    95
proof unfold_locales
haftmann@21380
    96
  fix x y z :: "'a\<Colon>lorder"
haftmann@21380
    97
  from is_meet_meet have "is_meet meet" by blast
haftmann@21380
    98
  note meet = this is_meet_def
haftmann@21380
    99
  from meet show "meet x y \<le> x" by blast
haftmann@21380
   100
  from meet show "meet x y \<le> y" by blast
haftmann@21380
   101
  from meet show "x \<le> y \<Longrightarrow> x \<le> z \<Longrightarrow> x \<le> meet y z" by blast
haftmann@21380
   102
  from is_join_join have "is_join join" by blast
haftmann@21380
   103
  note join = this is_join_def
haftmann@21380
   104
  from join show "x \<le> join x y" by blast
haftmann@21380
   105
  from join show "y \<le> join x y" by blast
haftmann@21380
   106
  from join show "y \<le> x \<Longrightarrow> z \<le> x \<Longrightarrow> join y z \<le> x" by blast
haftmann@21380
   107
qed
haftmann@21380
   108
obua@14738
   109
lemma meet_left_le: "meet a b \<le> (a::'a::meet_semilorder)"
obua@14738
   110
by (insert is_meet_meet, auto simp add: is_meet_def)
obua@14738
   111
obua@14738
   112
lemma meet_right_le: "meet a b \<le> (b::'a::meet_semilorder)"
obua@14738
   113
by (insert is_meet_meet, auto simp add: is_meet_def)
obua@14738
   114
nipkow@21312
   115
(* intro! breaks a proof in Hyperreal/SEQ and NumberTheory/IntPrimes *)
nipkow@21312
   116
lemma le_meetI:
nipkow@21312
   117
 "x \<le> a \<Longrightarrow> x \<le> b \<Longrightarrow> x \<le> meet a (b::'a::meet_semilorder)"
obua@14738
   118
by (insert is_meet_meet, auto simp add: is_meet_def)
obua@14738
   119
obua@14738
   120
lemma join_left_le: "a \<le> join a (b::'a::join_semilorder)"
obua@14738
   121
by (insert is_join_join, auto simp add: is_join_def)
obua@14738
   122
obua@14738
   123
lemma join_right_le: "b \<le> join a (b::'a::join_semilorder)"
obua@14738
   124
by (insert is_join_join, auto simp add: is_join_def)
obua@14738
   125
nipkow@21312
   126
lemma join_leI:
nipkow@21312
   127
 "a \<le> x \<Longrightarrow> b \<le> x \<Longrightarrow> join a b \<le> (x::'a::join_semilorder)"
obua@14738
   128
by (insert is_join_join, auto simp add: is_join_def)
obua@14738
   129
nipkow@21312
   130
lemmas meet_join_le[simp] = meet_left_le meet_right_le join_left_le join_right_le
nipkow@21312
   131
nipkow@21312
   132
lemma le_meet[simp]: "(x <= meet y z) = (x <= y & x <= z)" (is "?L = ?R")
nipkow@21312
   133
proof
nipkow@21312
   134
  assume ?L
nipkow@21312
   135
  moreover have "meet y z \<le> y" "meet y z <= z" by(simp_all)
nipkow@21312
   136
  ultimately show ?R by(blast intro:order_trans)
nipkow@21312
   137
next
nipkow@21312
   138
  assume ?R thus ?L by (blast intro!:le_meetI)
nipkow@21312
   139
qed
nipkow@21312
   140
nipkow@21312
   141
lemma join_le[simp]: "(join x y <= z) = (x <= z & y <= z)" (is "?L = ?R")
nipkow@21312
   142
proof
nipkow@21312
   143
  assume ?L
nipkow@21312
   144
  moreover have "x \<le> join x y" "y \<le> join x y" by(simp_all)
nipkow@21312
   145
  ultimately show ?R by(blast intro:order_trans)
nipkow@21312
   146
next
nipkow@21312
   147
  assume ?R thus ?L by (blast intro:join_leI)
nipkow@21312
   148
qed
nipkow@21312
   149
obua@14738
   150
obua@14738
   151
lemma is_meet_min: "is_meet (min::'a \<Rightarrow> 'a \<Rightarrow> ('a::linorder))"
obua@14738
   152
by (auto simp add: is_meet_def min_def)
obua@14738
   153
obua@14738
   154
lemma is_join_max: "is_join (max::'a \<Rightarrow> 'a \<Rightarrow> ('a::linorder))"
obua@14738
   155
by (auto simp add: is_join_def max_def)
obua@14738
   156
obua@14738
   157
instance linorder \<subseteq> meet_semilorder
obua@14738
   158
proof
obua@14738
   159
  from is_meet_min show "? (m::'a\<Rightarrow>'a\<Rightarrow>('a::linorder)). is_meet m" by auto
obua@14738
   160
qed
obua@14738
   161
obua@14738
   162
instance linorder \<subseteq> join_semilorder
obua@14738
   163
proof
obua@14738
   164
  from is_join_max show "? (j::'a\<Rightarrow>'a\<Rightarrow>('a::linorder)). is_join j" by auto 
obua@14738
   165
qed
obua@14738
   166
    
obua@14738
   167
instance linorder \<subseteq> lorder ..
obua@14738
   168
obua@14738
   169
lemma meet_min: "meet = (min :: 'a\<Rightarrow>'a\<Rightarrow>('a::linorder))" 
obua@14738
   170
by (simp add: is_meet_meet is_meet_min is_meet_unique)
obua@14738
   171
obua@14738
   172
lemma join_max: "join = (max :: 'a\<Rightarrow>'a\<Rightarrow>('a::linorder))"
obua@14738
   173
by (simp add: is_join_join is_join_max is_join_unique)
obua@14738
   174
obua@14738
   175
lemma meet_idempotent[simp]: "meet x x = x"
nipkow@21312
   176
by (rule order_antisym, simp_all add: le_meetI)
obua@14738
   177
obua@14738
   178
lemma join_idempotent[simp]: "join x x = x"
nipkow@21312
   179
by (rule order_antisym, simp_all add: join_leI)
obua@14738
   180
obua@14738
   181
lemma meet_comm: "meet x y = meet y x" 
nipkow@21312
   182
by (rule order_antisym, (simp add: le_meetI)+)
obua@14738
   183
obua@14738
   184
lemma join_comm: "join x y = join y x"
nipkow@21312
   185
by (rule order_antisym, (simp add: join_leI)+)
nipkow@21312
   186
nipkow@21312
   187
lemma meet_leI1: "x \<le> z \<Longrightarrow> meet x y \<le> z"
nipkow@21312
   188
apply(subgoal_tac "meet x y <= x")
nipkow@21312
   189
 apply(blast intro:order_trans)
nipkow@21312
   190
apply simp
nipkow@21312
   191
done
nipkow@21312
   192
nipkow@21312
   193
lemma meet_leI2: "y \<le> z \<Longrightarrow> meet x y \<le> z"
nipkow@21312
   194
apply(subgoal_tac "meet x y <= y")
nipkow@21312
   195
 apply(blast intro:order_trans)
nipkow@21312
   196
apply simp
nipkow@21312
   197
done
obua@14738
   198
nipkow@21312
   199
lemma le_joinI1: "x \<le> y \<Longrightarrow> x \<le> join y z"
nipkow@21312
   200
apply(subgoal_tac "y <= join y z")
nipkow@21312
   201
 apply(blast intro:order_trans)
nipkow@21312
   202
apply simp
nipkow@21312
   203
done
nipkow@21312
   204
nipkow@21312
   205
lemma le_joinI2: "x \<le> z \<Longrightarrow> x \<le> join y z"
nipkow@21312
   206
apply(subgoal_tac "z <= join y z")
nipkow@21312
   207
 apply(blast intro:order_trans)
nipkow@21312
   208
apply simp
nipkow@21312
   209
done
obua@14738
   210
nipkow@21312
   211
lemma meet_assoc: "meet (meet x y) z = meet x (meet y z)"
nipkow@21312
   212
apply(rule order_antisym)
nipkow@21312
   213
apply (simp add:meet_leI1 meet_leI2)
nipkow@21312
   214
apply (simp add:meet_leI1 meet_leI2)
nipkow@21312
   215
done
nipkow@21312
   216
nipkow@21312
   217
lemma join_assoc: "join (join x y) z = join x (join y z)"
nipkow@21312
   218
apply(rule order_antisym)
nipkow@21312
   219
apply (simp add:le_joinI1 le_joinI2)
nipkow@21312
   220
apply (simp add:le_joinI1 le_joinI2)
nipkow@21312
   221
done
obua@14738
   222
obua@14738
   223
lemma meet_left_comm: "meet a (meet b c) = meet b (meet a c)"
obua@14738
   224
by (simp add: meet_assoc[symmetric, of a b c], simp add: meet_comm[of a b], simp add: meet_assoc)
obua@14738
   225
obua@14738
   226
lemma meet_left_idempotent: "meet y (meet y x) = meet y x"
obua@14738
   227
by (simp add: meet_assoc meet_comm meet_left_comm)
obua@14738
   228
obua@14738
   229
lemma join_left_comm: "join a (join b c) = join b (join a c)"
obua@14738
   230
by (simp add: join_assoc[symmetric, of a b c], simp add: join_comm[of a b], simp add: join_assoc)
obua@14738
   231
obua@14738
   232
lemma join_left_idempotent: "join y (join y x) = join y x"
obua@14738
   233
by (simp add: join_assoc join_comm join_left_comm)
obua@14738
   234
    
obua@14738
   235
lemmas meet_aci = meet_assoc meet_comm meet_left_comm meet_left_idempotent
obua@14738
   236
obua@14738
   237
lemmas join_aci = join_assoc join_comm join_left_comm join_left_idempotent
obua@14738
   238
nipkow@21312
   239
lemma le_def_meet: "(x <= y) = (meet x y = x)"
nipkow@21312
   240
apply rule
nipkow@21312
   241
apply(simp add: order_antisym)
nipkow@21312
   242
apply(subgoal_tac "meet x y <= y")
nipkow@21312
   243
apply(simp)
nipkow@21312
   244
apply(simp (no_asm))
nipkow@21312
   245
done
obua@14738
   246
nipkow@21312
   247
lemma le_def_join: "(x <= y) = (join x y = y)"
nipkow@21312
   248
apply rule
nipkow@21312
   249
apply(simp add: order_antisym)
nipkow@21312
   250
apply(subgoal_tac "x <= join x y")
nipkow@21312
   251
apply(simp)
nipkow@21312
   252
apply(simp (no_asm))
nipkow@21312
   253
done
nipkow@21312
   254
nipkow@21312
   255
lemma join_absorp2: "a \<le> b \<Longrightarrow> join a b = b" 
nipkow@21312
   256
by (simp add: le_def_join)
nipkow@21312
   257
nipkow@21312
   258
lemma join_absorp1: "b \<le> a \<Longrightarrow> join a b = a"
nipkow@21312
   259
by (simp add: le_def_join join_aci)
nipkow@21312
   260
nipkow@21312
   261
lemma meet_absorp1: "a \<le> b \<Longrightarrow> meet a b = a"
nipkow@21312
   262
by (simp add: le_def_meet)
nipkow@21312
   263
nipkow@21312
   264
lemma meet_absorp2: "b \<le> a \<Longrightarrow> meet a b = b"
nipkow@21312
   265
by (simp add: le_def_meet meet_aci)
obua@14738
   266
obua@14738
   267
lemma meet_join_absorp: "meet x (join x y) = x"
nipkow@21312
   268
by(simp add:meet_absorp1)
obua@14738
   269
obua@14738
   270
lemma join_meet_absorp: "join x (meet x y) = x"
nipkow@21312
   271
by(simp add:join_absorp1)
obua@14738
   272
obua@14738
   273
lemma meet_mono: "y \<le> z \<Longrightarrow> meet x y \<le> meet x z"
nipkow@21312
   274
by(simp add:meet_leI2)
obua@14738
   275
obua@14738
   276
lemma join_mono: "y \<le> z \<Longrightarrow> join x y \<le> join x z"
nipkow@21312
   277
by(simp add:le_joinI2)
obua@14738
   278
obua@14738
   279
lemma distrib_join_le: "join x (meet y z) \<le> meet (join x y) (join x z)" (is "_ <= ?r")
obua@14738
   280
proof -
nipkow@21312
   281
  have a: "x <= ?r" by (simp_all add:le_meetI)
nipkow@21312
   282
  have b: "meet y z <= ?r" by (simp add:le_joinI2)
nipkow@21312
   283
  from a b show ?thesis by (simp add: join_leI)
obua@14738
   284
qed
obua@14738
   285
  
nipkow@21312
   286
lemma distrib_meet_le: "join (meet x y) (meet x z) \<le> meet x (join y z)" (is "?l <= _")
obua@14738
   287
proof -
nipkow@21312
   288
  have a: "?l <= x" by (simp_all add: join_leI)
nipkow@21312
   289
  have b: "?l <= join y z" by (simp add:meet_leI2)
nipkow@21312
   290
  from a b show ?thesis by (simp add: le_meetI)
obua@14738
   291
qed
obua@14738
   292
obua@14738
   293
lemma meet_join_eq_imp_le: "a = c \<or> a = d \<or> b = c \<or> b = d \<Longrightarrow> meet a b \<le> join c d"
nipkow@21312
   294
by (auto simp:meet_leI2 meet_leI1)
obua@14738
   295
obua@14738
   296
lemma modular_le: "x \<le> z \<Longrightarrow> join x (meet y z) \<le> meet (join x y) z" (is "_ \<Longrightarrow> ?t <= _")
obua@14738
   297
proof -
obua@14738
   298
  assume a: "x <= z"
nipkow@21312
   299
  have b: "?t <= join x y" by (simp_all add: join_leI meet_join_eq_imp_le )
nipkow@21312
   300
  have c: "?t <= z" by (simp_all add: a join_leI)
nipkow@21312
   301
  from b c show ?thesis by (simp add: le_meetI)
obua@14738
   302
qed
obua@14738
   303
nipkow@15131
   304
end