Knaster Tarski theorem, example needed

http://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem

Let $L$ be a complete lattice and let $f : L \to L$ be an order-preserving function. Then the set of fixed points of $f$ in $L$ is also a complete lattice.

Can someone think of a non-trivial example for which the theorem applies ?

-
An increasing function $f:[0,1]\to[0,1]$? – Michael Greinecker Jan 12 '12 at 13:07

You can use this to prove the Cantor-Schröder-Bernstein theorem, which asserts that whenever $A$ injects into $B$ and $B$ injects into $A$, then they are bijective. Namely, suppose that $f:A\to B$ and $g:B\to A$ are both injective functions. If there were a set $X\subset A$ such that $A-X=g[B-f[X]]$, then the function $h=(f\upharpoonright X)\cup (g^{-1}\upharpoonright A-X)$ is a bijection between $A$ and $B$. Such a set $X$ exists by the Knaster-Tarski theorem, since the powerset $P(A)$ is a complete lattice under inclusion and the function $\varphi(X)=A-g[B-f[X]]$ is $\subset$-preserving, since $$X\subset Y\implies f[X]\subset f[Y]\implies B-f[X]\supset B-f[Y]$$ $$\implies A-g[B-f[X]]\subset A-g[B-f[Y]]\implies \varphi(X)\subset\varphi(Y).$$ A fixed point $X=\varphi(x)$ means $A-X=g[B-f[X]]$.

-
That's a very slick proof of the CSB Theorem! Thanks Joel. – Carlo Von Schnitzel Jan 12 '12 at 22:44
Sure. Elegant! After all, it was Stefan Banach himself. – Włodzimierz Holsztyński Apr 19 '14 at 19:49

A useful application of Tarski's fixed point theorem is that every supermodular game (mostly games with strategic complementarities) has a smallest and a largest pure strategy Nash equilibrium. For surveys of supermodular games, see here, here, or here. The literature is huge. By a slight modification of the theorem, one can actually show that the set of pure strategy Nash equilibria forms a complete lattice in itself.

-

In computer science, it is used in the field of denotational semantics and abstract interpretation, where the existence of fixed points can be exploited to guarantee well-defined semantics for a recursive algorithm, see this for an example.

-

There are applications to finding invariant sets of iterated function systems (a notion related to fractals). See this survey by K. Leśniak.

-

In this graph-theoretical post you find a very nice application of Knaster-Tarski to a generalization of Hall's Marriage Theorem.

-