Least fixed point and monotone mappings in complete lattice

33 Views Asked by At

Let $(E_1,\leq_1)$ and $(E_2,\leq_2)$ be two complete lattices. also let $f_1 : E_1 \times E_2 \rightarrow E_1$ and $f_2 : E_1 \times E_2 \rightarrow E_2$ be mappings monotonic with respect to their two arguments. Fix an element $Y \in E_1$, and define two operators: $$ F_2^Y(Z)=f_2(Y,Z)\\ G_1(Y)=f_1(Y,\mu F_2^Y) $$ such that $\mu F_2^Y$ is minimal fixed point of $F_2^Y$. Clearly $F_2^Y$ is monotone and hence $\mu F_2^Y$ is well-defined (from knaster-tarski lemma). but how can i show that $G_1$ is monotone as well ?

Suppose $Y \leq_1 Y'$ , i have two show that $G_1(Y) \leq_1 G_1(Y')$ . it is suffice to show that $\mu F_2^Y \leq_2 \mu F_2^{Y'}$. we know that for all $W$ if $f_2(Y,W)=W$ then $\mu F_2^Y \leq_2 W$. also we know that, for all $W'$ if $f_2(Y',W')=W'$ then $\mu F_2^{Y'} \leq_2 W'$. but i could not go any further for the proof.

Because the real complete lattice which i concerened is finite powerset lattice with inclusion as ordering, so i try to break $Y'$ into $Y \cup Y''$, but that does not helps. because it is possible that $f_2(Y \cup Y'',W)=W$ but $f_2(Y,W) \neq W$. so i do not know how can i show that $\mu F_2^Y \leq_2 \mu F_2^{Y'}$.

1

There are 1 best solutions below

0
On BEST ANSWER

From the proof of the Knaster-Tarski lemma, we can express $\mu F_2^Y$ as an infimum computed in $E_2$ : $$\mu F_2^{Y} = {\bigwedge}_{\leq_2}\{ Z \in E_2|F_2^Y(Z) \leq Z\}$$

Then, if $Y\leq_1 Y'$, we have : $$\mu F_2^{Y'} = f_2(Y',\mu F_2^{Y'} ) \geq f_2(Y,\mu F_2^{Y'}) = F_2^{Y}\left(\mu F_2^{Y'}\right)$$ And therefore : $$ \mu F_2^Y \leq \mu F_2^{Y'}$$