5
$\begingroup$

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.

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

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\}$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – parr1rt4 Sep 10 '13 at 1:07
  • $\begingroup$ @parr1rt4 What is $\alpha$? $\endgroup$ – Git Gud Sep 10 '13 at 1:07
  • $\begingroup$ α is the sup of A right? $\endgroup$ – parr1rt4 Sep 10 '13 at 1:10
  • $\begingroup$ Yes, now what is the definition of supremum of a set? $\endgroup$ – Git Gud Sep 10 '13 at 1:10
  • 1
    $\begingroup$ @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$. $\endgroup$ – Git Gud Nov 21 '17 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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