Knaster Tarski theorem, example needed

Question

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 ?

Answer 1

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]]$.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

It can be used to give a quick solution for this problem:

A book consists of 100 pages and contains 100 lemmas and some images. Each lemma is at most one page long and can't be split into two pages (it has to fit in one page). The lemmas are numbered from 1 to 100 and are written in ascending order. Prove that there must be at least one lemma written on a page with the same number as the lemma's number.