LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
sav08:mapping_fixpoints_under_lattice_morphisms [2009/03/26 13:53]
vkuncak
sav08:mapping_fixpoints_under_lattice_morphisms [2015/04/21 17:30] (current)
Line 2: Line 2:
  
 **Definition:​** Let $(X,\le)$ and $(Y,​\sqsubseteq)$ be complete [[lattices]]. We call $F : X \to Y$ a **complete join-morphism** iff for each set $X_1 \subseteq X$ we have **Definition:​** Let $(X,\le)$ and $(Y,​\sqsubseteq)$ be complete [[lattices]]. We call $F : X \to Y$ a **complete join-morphism** iff for each set $X_1 \subseteq X$ we have
-\[+\begin{equation*}
    ​F(\sqcup X_1) = \sqcup \{ F(a).\ a \in X_1 \}    ​F(\sqcup X_1) = \sqcup \{ F(a).\ a \in X_1 \}
-\]+\end{equation*} 
 + 
 +For example, $F(a_1 \sqcup a_2 \sqcup a_3) = F(a_1) \sqcup F(a_2) \sqcup F(a_3)$.
  
-For example, $F(a_1 \sqcup a_2 \sqcup a_3) = F(a_1) \sqcup F(a_2) \sqcup F(a_3) 
  
 **Lemma:** Let $(X,\le)$ and $(Y,​\sqsubseteq)$ be complete lattices, and $F : X \to X$, $\Gamma : X \to Y$, $F^\# : Y \to Y$ be complete join-morphisms such that **Lemma:** Let $(X,\le)$ and $(Y,​\sqsubseteq)$ be complete lattices, and $F : X \to X$, $\Gamma : X \to Y$, $F^\# : Y \to Y$ be complete join-morphisms such that
-\[+\begin{equation*}
     F(\Gamma(y)) \le \Gamma(F^\#​(y))     F(\Gamma(y)) \le \Gamma(F^\#​(y))
-\]+\end{equation*}
 for all $y \in Y$.  If $lfp$ denotes least fixpoint of a function, then for all $y \in Y$.  If $lfp$ denotes least fixpoint of a function, then
-\[+\begin{equation*}
     lfp(F) \le \Gamma(lfp(F^\#​))     lfp(F) \le \Gamma(lfp(F^\#​))
-\]+\end{equation*}
  
 In other words, we can approximate $lfp(F)$ by computing $lfp(F^\#​)$. In other words, we can approximate $lfp(F)$ by computing $lfp(F^\#​)$.