equal
deleted
inserted
replaced
5 |
5 |
6 theory Lattice_Constructions |
6 theory Lattice_Constructions |
7 imports Main |
7 imports Main |
8 begin |
8 begin |
9 |
9 |
10 subsection {* Values extended by a bottom element *} |
10 subsection \<open>Values extended by a bottom element\<close> |
11 |
11 |
12 datatype 'a bot = Value 'a | Bot |
12 datatype 'a bot = Value 'a | Bot |
13 |
13 |
14 instantiation bot :: (preorder) preorder |
14 instantiation bot :: (preorder) preorder |
15 begin |
15 begin |
104 end |
104 end |
105 |
105 |
106 instance bot :: (lattice) bounded_lattice_bot |
106 instance bot :: (lattice) bounded_lattice_bot |
107 by(intro_classes)(simp add: bot_bot_def) |
107 by(intro_classes)(simp add: bot_bot_def) |
108 |
108 |
109 section {* Values extended by a top element *} |
109 section \<open>Values extended by a top element\<close> |
110 |
110 |
111 datatype 'a top = Value 'a | Top |
111 datatype 'a top = Value 'a | Top |
112 |
112 |
113 instantiation top :: (preorder) preorder |
113 instantiation top :: (preorder) preorder |
114 begin |
114 begin |
203 end |
203 end |
204 |
204 |
205 instance top :: (lattice) bounded_lattice_top |
205 instance top :: (lattice) bounded_lattice_top |
206 by(intro_classes)(simp add: top_top_def) |
206 by(intro_classes)(simp add: top_top_def) |
207 |
207 |
208 subsection {* Values extended by a top and a bottom element *} |
208 subsection \<open>Values extended by a top and a bottom element\<close> |
209 |
209 |
210 datatype 'a flat_complete_lattice = Value 'a | Bot | Top |
210 datatype 'a flat_complete_lattice = Value 'a | Bot | Top |
211 |
211 |
212 instantiation flat_complete_lattice :: (type) order |
212 instantiation flat_complete_lattice :: (type) order |
213 begin |
213 begin |
294 fix v |
294 fix v |
295 assume "A - {Top} = {Value v}" |
295 assume "A - {Top} = {Value v}" |
296 from this have "(THE v. A - {Top} = {Value v}) = v" |
296 from this have "(THE v. A - {Top} = {Value v}) = v" |
297 by (auto intro!: the1_equality) |
297 by (auto intro!: the1_equality) |
298 moreover |
298 moreover |
299 from `x : A` `A - {Top} = {Value v}` have "x = Top \<or> x = Value v" |
299 from \<open>x : A\<close> \<open>A - {Top} = {Value v}\<close> have "x = Top \<or> x = Value v" |
300 by auto |
300 by auto |
301 ultimately have "Value (THE v. A - {Top} = {Value v}) <= x" |
301 ultimately have "Value (THE v. A - {Top} = {Value v}) <= x" |
302 by auto |
302 by auto |
303 } |
303 } |
304 from `x : A` this show "Inf A <= x" |
304 from \<open>x : A\<close> this show "Inf A <= x" |
305 unfolding Inf_flat_complete_lattice_def |
305 unfolding Inf_flat_complete_lattice_def |
306 by fastforce |
306 by fastforce |
307 next |
307 next |
308 fix z A |
308 fix z A |
309 assume z: "\<And>x. x : A ==> z <= (x :: 'a flat_complete_lattice)" |
309 assume z: "\<And>x. x : A ==> z <= (x :: 'a flat_complete_lattice)" |
353 fix v |
353 fix v |
354 assume "A - {Bot} = {Value v}" |
354 assume "A - {Bot} = {Value v}" |
355 from this have "(THE v. A - {Bot} = {Value v}) = v" |
355 from this have "(THE v. A - {Bot} = {Value v}) = v" |
356 by (auto intro!: the1_equality) |
356 by (auto intro!: the1_equality) |
357 moreover |
357 moreover |
358 from `x : A` `A - {Bot} = {Value v}` have "x = Bot \<or> x = Value v" |
358 from \<open>x : A\<close> \<open>A - {Bot} = {Value v}\<close> have "x = Bot \<or> x = Value v" |
359 by auto |
359 by auto |
360 ultimately have "x <= Value (THE v. A - {Bot} = {Value v})" |
360 ultimately have "x <= Value (THE v. A - {Bot} = {Value v})" |
361 by auto |
361 by auto |
362 } |
362 } |
363 from `x : A` this show "x <= Sup A" |
363 from \<open>x : A\<close> this show "x <= Sup A" |
364 unfolding Sup_flat_complete_lattice_def |
364 unfolding Sup_flat_complete_lattice_def |
365 by fastforce |
365 by fastforce |
366 next |
366 next |
367 fix z A |
367 fix z A |
368 assume z: "\<And>x. x : A ==> x <= (z :: 'a flat_complete_lattice)" |
368 assume z: "\<And>x. x : A ==> x <= (z :: 'a flat_complete_lattice)" |