src/HOL/Algebra/Lattice.thy
changeset 66580 e5b1d4d55bf6
parent 65099 30d0b2f1df76
child 67091 1393c2340eec
equal deleted inserted replaced
66579:2db3fe23fdaf 66580:e5b1d4d55bf6
    49 definition
    49 definition
    50   meet :: "[_, 'a, 'a] => 'a" (infixl "\<sqinter>\<index>" 70)
    50   meet :: "[_, 'a, 'a] => 'a" (infixl "\<sqinter>\<index>" 70)
    51   where "x \<sqinter>\<^bsub>L\<^esub> y = \<Sqinter>\<^bsub>L\<^esub>{x, y}"
    51   where "x \<sqinter>\<^bsub>L\<^esub> y = \<Sqinter>\<^bsub>L\<^esub>{x, y}"
    52 
    52 
    53 definition
    53 definition
    54   LFP :: "('a, 'b) gorder_scheme \<Rightarrow> ('a \<Rightarrow> 'a) \<Rightarrow> 'a" ("\<mu>\<index>") where
    54   LEAST_FP :: "('a, 'b) gorder_scheme \<Rightarrow> ('a \<Rightarrow> 'a) \<Rightarrow> 'a" ("LFP\<index>") where
    55   "LFP L f = \<Sqinter>\<^bsub>L\<^esub> {u \<in> carrier L. f u \<sqsubseteq>\<^bsub>L\<^esub> u}"    --\<open>least fixed point\<close>
    55   "LEAST_FP L f = \<Sqinter>\<^bsub>L\<^esub> {u \<in> carrier L. f u \<sqsubseteq>\<^bsub>L\<^esub> u}"    --\<open>least fixed point\<close>
    56 
    56 
    57 definition
    57 definition
    58   GFP:: "('a, 'b) gorder_scheme \<Rightarrow> ('a \<Rightarrow> 'a) \<Rightarrow> 'a" ("\<nu>\<index>") where
    58   GREATEST_FP:: "('a, 'b) gorder_scheme \<Rightarrow> ('a \<Rightarrow> 'a) \<Rightarrow> 'a" ("GFP\<index>") where
    59   "GFP L f = \<Squnion>\<^bsub>L\<^esub> {u \<in> carrier L. u \<sqsubseteq>\<^bsub>L\<^esub> f u}"    --\<open>greatest fixed point\<close>
    59   "GREATEST_FP L f = \<Squnion>\<^bsub>L\<^esub> {u \<in> carrier L. u \<sqsubseteq>\<^bsub>L\<^esub> f u}"    --\<open>greatest fixed point\<close>
    60 
    60 
    61 
    61 
    62 subsection \<open>Dual operators\<close>
    62 subsection \<open>Dual operators\<close>
    63 
    63 
    64 lemma sup_dual [simp]: 
    64 lemma sup_dual [simp]: 
    84 lemma bottom_dual [simp]:
    84 lemma bottom_dual [simp]:
    85   "\<bottom>\<^bsub>inv_gorder L\<^esub> = \<top>\<^bsub>L\<^esub>"
    85   "\<bottom>\<^bsub>inv_gorder L\<^esub> = \<top>\<^bsub>L\<^esub>"
    86   by (simp add: top_def bottom_def)
    86   by (simp add: top_def bottom_def)
    87 
    87 
    88 lemma LFP_dual [simp]:
    88 lemma LFP_dual [simp]:
    89   "LFP (inv_gorder L) f = GFP L f"
    89   "LEAST_FP (inv_gorder L) f = GREATEST_FP L f"
    90   by (simp add:LFP_def GFP_def)
    90   by (simp add:LEAST_FP_def GREATEST_FP_def)
    91 
    91 
    92 lemma GFP_dual [simp]:
    92 lemma GFP_dual [simp]:
    93   "GFP (inv_gorder L) f = LFP L f"
    93   "GREATEST_FP (inv_gorder L) f = LEAST_FP L f"
    94   by (simp add:LFP_def GFP_def)
    94   by (simp add:LEAST_FP_def GREATEST_FP_def)
    95 
    95 
    96 
    96 
    97 subsection \<open>Lattices\<close>
    97 subsection \<open>Lattices\<close>
    98 
    98 
    99 locale weak_upper_semilattice = weak_partial_order +
    99 locale weak_upper_semilattice = weak_partial_order +