• English only

# Differences

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

 sav08:mapping_fixpoints_under_lattice_morphisms [2009/03/26 13:53]vkuncak sav08:mapping_fixpoints_under_lattice_morphisms [2015/04/21 17:30] (current) Both sides previous revision Previous revision 2009/03/26 13:54 vkuncak 2009/03/26 13:53 vkuncak 2009/03/26 13:53 vkuncak 2009/03/26 13:51 vkuncak 2009/03/26 13:50 vkuncak 2008/05/07 10:31 vkuncak 2008/05/07 08:36 vkuncak 2008/05/07 08:36 vkuncak created Next revision Previous revision 2009/03/26 13:54 vkuncak 2009/03/26 13:53 vkuncak 2009/03/26 13:53 vkuncak 2009/03/26 13:51 vkuncak 2009/03/26 13:50 vkuncak 2008/05/07 10:31 vkuncak 2008/05/07 08:36 vkuncak 2008/05/07 08:36 vkuncak created 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^\#​)\$. 