9
$\begingroup$

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 ?

$\endgroup$
1
  • 8
    $\begingroup$ An increasing function $f:[0,1]\to[0,1]$? $\endgroup$ Jan 12, 2012 at 13:07

6 Answers 6

17
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ That's a very slick proof of the CSB Theorem! Thanks Joel. $\endgroup$ Jan 12, 2012 at 22:44
  • $\begingroup$ Sure. Elegant! After all, it was Stefan Banach himself. $\endgroup$ Apr 19, 2014 at 19:49
8
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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