Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
2  
An increasing function $f:[0,1]\to[0,1]$? –  Michael Greinecker Jan 12 '12 at 13:07

3 Answers 3

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

share|improve this answer
1  
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 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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