In a complete lattice every monotone function has a fixpoint (Knaster–Tarski Theorem)

L is a complete lattice, so every subset has a supremum and infimum. In addition, there exists a function $f:L \rightarrow L$ such that $a \leq b$ implies $f(a) \leq f(b)$. Prove that there exists some $k$ in L such that $f(k) = k$

I started by taking the set $S = \{a | f(a) \geq a\}$, but I am now stuck on this.

• Hi, parr; you can use \geq for >=, and \leq for <= ; I just edited, hope it's O.K . – DBFdalwayse Sep 10 '13 at 0:44
• oh great thanks for the infos – parr1rt4 Sep 10 '13 at 0:46

1 Answer

This is called the Knaster-Tarski Fixpoint Theorem.

Define $A:=\{x\in L\colon x\leq f(x)\}$.

Since $L$ is a complete lattice you can define $\alpha :=\bigvee _LA$.

By definition $\alpha \in L$ so it makes sense to consider $f(\alpha)$.

Note that $A\neq \varnothing$, (why?).

Let's prove that $f(\alpha)$ is an upperbound of $A$. Let $x\in A$. Since $f$ is order-preserving (or monotone), then $f(x)\leq f(\alpha)$. On the other hand, by definition of $A$ it also holds that $x\leq f(x)$, therefore $x\leq f(\alpha)$.
Since $x$ was arbitrary it was proven that $f(\alpha)$ in an upperbound of $A$ and therefore $\color{blue}{\alpha \leq f(\alpha)}$.

Now using this last inequality and the fact that $f$ is order-preserving yields $f(\alpha)\leq f(f(\alpha))$, therefore $f(\alpha)\in A$, thus $\color{blue}{f(\alpha)\leq\alpha}$.

Hence $f(\alpha)=\alpha$.

You should emulate the proof by using meet instead of join. Consider the set $B=\{x\in L\colon f(x)\leq x\}$.

• you said "f(α) in an upperbound of A and therefore α≤f(α)". Why is this true? It is not necessary that the upper bound of a set be a member of the set right? So I don't follow why your statement is true. Any help? – parr1rt4 Sep 10 '13 at 1:07
• @parr1rt4 What is $\alpha$? – Git Gud Sep 10 '13 at 1:07
• α is the sup of A right? – parr1rt4 Sep 10 '13 at 1:10
• Yes, now what is the definition of supremum of a set? – Git Gud Sep 10 '13 at 1:10
• @jesterII Exactly. The entity $\inf(L)$ exists because $L$ is a complete lattice. And obviously $\inf(L)\leq f\left(\inf(L)\right)$, hence $\inf(L)\in A$. – Git Gud Nov 21 '17 at 19:47