# Least common fixed-point

I have been reading a book, "Introduction to Lattices and Order", and I'm trying to solve exercise 8.29 as the following in it:

Suppose that $P$ is a complete lattice and let $F$ and $G$ be order-preserving maps. If $F$ and $G$ have a common fixed-point, then they have a least common fixed-point given by $a := \wedge \{x \in P \mid F(x) \le x \mathop{\&} G(x) \le x \}$.

My proof is: for all $y \in \{x \in P \mid F(x) \le x \mathop{\&} G(x) \le x \}$, I have $a \le y$, so $F(a) \le F(y) \le y$ and $G(a) \le G(y) \le y$. Therefore I have $F(a) \le a$ and $G(a) \le a$. Here I want to prove that $a \le F(a)$ and $a \le G(a)$, but it seems hard to do so because I don't assume that F and G are commute.

Could you advise me about this problem?

-
You haven't used the assumption that $F$ and $G$ have a common fixed point yet. There must be some use for that lurking in the wings somehow … –  Harald Hanche-Olsen Jan 2 '13 at 22:28
Your definition $a:=\vee \{x \in P \mid F(x) \leq x\; \& \; G(x)\leq x\}$ is not the least common fixed point. All common fixed points belong to $\{x \in P \mid F(x) \leq x\, \& \, G(x)\leq x\}$. Taking the join of this set you get a point that is above all common fixed points. The definition you want is $a:= \wedge \{x \in P \mid F(x) \leq x\; \& \; G(x)\leq x\}$. –  William DeMeo Jan 3 '13 at 21:03
@WilliamDeMeo I correct the definition. Thanks for pointing it out. –  skymountain Jan 4 '13 at 0:29
add comment

## 1 Answer

This bears no resemblance to the first version of this answer.

I’m going to assume that you’ve already seen the Knaster-Tarski theorem, since it seems unlikely that that exercise would precede it. The map

$$\varphi:P\times P\to P\times P:\langle x,y\rangle\mapsto\langle F(x),G(y)\rangle$$

is order-preserving, and $P\times P$ is a complete lattice with the usual product order, so by the Knaster-Tarski theorem the set $M$ of fixed points of $\varphi$ is a complete lattice. Let $$\Delta=\{\langle x,x\rangle\in P\times P:x\in P\}\;.$$ Then $M\cap\Delta$ is the set of common fixed points of $F$ and $G$, so by hypothesis $M\cap\Delta\ne\varnothing$. Thus $M\cap\Delta$ has a least element in $M$, which is what we wished to prove.

-
Why do $c \le F(c)$ and $c \le G(c)$ hold? –  skymountain Jan 11 '13 at 8:15
@skymountain: I’m no longer sure what I was thinking at that point. I’ll either fix or delete this in the next day or so. –  Brian M. Scott Jan 12 '13 at 2:47
I'm sorry for my late response. –  skymountain Jan 12 '13 at 6:27
@skymountain: No harm done; coming back to the problem with a fresh eye turned out to be a good thing. I’ve tackled it completely differently this time. –  Brian M. Scott Jan 12 '13 at 16:15
@skymountain: By definition the least element of any set belongs to that set; the only question is whether a set has a least element. The Knaster-Tarski theorem says that every non-empty subset of $M$ has a least element. $M\cap\Delta$ is non-empty by hypothesis. You don’t need to take an infimum, though of course it’s true that the least element of $M\cap\Delta$ is the infimum of $M\cap\Delta$ in $M$ (not necessarily in $P\times P$). –  Brian M. Scott Jan 18 '13 at 21:48
show 5 more comments