LARA

Mapping Fixpoints Under Lattice Morphisms

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 \}
\end{equation*}

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 : Y \to X$, $F^\# : Y \to Y$ be complete join-morphisms such that

\begin{equation*}
    F(\Gamma(y)) \le \Gamma(F^\#(y))
\end{equation*}

for all $y \in Y$. If $lfp$ denotes least fixpoint of a function, then

\begin{equation*}
    lfp(F) \le \Gamma(lfp(F^\#))
\end{equation*}

In other words, we can approximate $lfp(F)$ by computing $lfp(F^\#)$.