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$
  • 7
    $\begingroup$ An increasing function $f:[0,1]\to[0,1]$? $\endgroup$ – Michael Greinecker Jan 12 '12 at 13:07
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$
  • 1
    $\begingroup$ That's a very slick proof of the CSB Theorem! Thanks Joel. $\endgroup$ – 16278263789 Jan 12 '12 at 22:44
  • $\begingroup$ Sure. Elegant! After all, it was Stefan Banach himself. $\endgroup$ – Włodzimierz Holsztyński Apr 19 '14 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, privacy policy and cookie policy

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