Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.