Differences
This shows you the differences between two versions of the page.
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^\#)$. | ||