Kleene fixed-point theorem

In the <a href="/facts/Mathematics/pxTouaz4">mathematical</a> areas of <a href="/facts/Order_theory/gn6fM3oJ">order</a> and <a href="/facts/Lattice_theory/5ak6ufky">lattice theory</a>, the Kleene fixed-point theorem, named after American mathematician <a href="/facts/Stephen_Cole_Kleene/sKSax2se">Stephen Cole Kleene</a>, states the following:

Kleene Fixed-Point Theorem. Suppose 
 
 
 
 (
 L
 ,
 ⊑
 )
 
 
 {\displaystyle (L,\sqsubseteq )}
 
 is a <a href="/facts/Complete_partial_order/a855Q53A">directed-complete partial order</a> (dcpo) with a least element, and let 
 
 
 
 f
 :
 L
 →
 L
 
 
 {\displaystyle f:L\to L}
 
 be a <a href="/facts/Scott_continuity/7CqoURj0">Scott-continuous</a> (and therefore <a href="/facts/Monotone_function/MjQK0YL2">monotone</a>) <a href="/facts/Function_(mathematics)/CdReEKCh">function</a>. Then 
 
 
 
 f
 
 
 {\displaystyle f}
 
 has a <a href="/facts/Least_fixed_point/JbcBLqTN">least fixed point</a>, which is the <a href="/facts/Supremum/oXCKVopz">supremum</a> of the ascending Kleene chain of 
 
 
 
 f
 .
 
 
 {\displaystyle f.}

The ascending Kleene chain of f is the <a href="/facts/Chain_(order_theory)/xnTtmuYJ">chain</a>

⊥
        ⊑
        f
        (
        ⊥
        )
        ⊑
        f
        (
        f
        (
        ⊥
        )
        )
        ⊑
        ⋯
        ⊑
        
          f
          
            n
          
        
        (
        ⊥
        )
        ⊑
        ⋯
      
    
    {\displaystyle \bot \sqsubseteq f(\bot )\sqsubseteq f(f(\bot ))\sqsubseteq \cdots \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots }

obtained by <a href="/facts/Iterated_function/Vzsx64An">iterating</a> f on the <a href="/facts/Least_element/JVn2B3mo">least element</a> ⊥ of L. Expressed in a formula, the theorem states that

lfp
          
        
        (
        f
        )
        =
        sup
        
          (
          
            {
            
              
                f
                
                  n
                
              
              (
              ⊥
              )
              ∣
              n
              ∈
              
                N
              
            
            }
          
          )
        
      
    
    {\displaystyle {\textrm {lfp}}(f)=\sup \left(\left\{f^{n}(\bot )\mid n\in \mathbb {N} \right\}\right)}

where 
 
 
 
 
 
 lfp
 
 
 
 
 {\displaystyle {\textrm {lfp}}}
 
 denotes the least fixed point.
Although <a href="/facts/Tarski%27s_fixed_point_theorem/QeXjysqQ">Tarski's fixed point theorem</a> 
does not consider how fixed points can be computed by iterating f from some seed (also, it pertains to <a href="/facts/Monotone_function/MjQK0YL2">monotone functions</a> on <a href="/facts/Complete_lattices/pQbphWeR">complete lattices</a>), this result is often attributed to <a href="/facts/Alfred_Tarski/7h6NySAj">Alfred Tarski</a> who proves it for additive functions. Moreover, Kleene Fixed-Point Theorem can be extended to <a href="/facts/Monotone_function/MjQK0YL2">monotone functions</a> using transfinite iterations.

Kleene fixed-point theorem open-in-new

Kleene fixed-point theorem