src/HOL/Library/Lattice_Constructions.thy
changeset 60500 903bb1495239
parent 58310 91ea607a34d8
child 60508 2127bee2069a
equal deleted inserted replaced
60499:54a3db2ed201 60500:903bb1495239
     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)"