MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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]]$.

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

share|cite|improve this answer

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.

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

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

share|cite|improve this answer

Your Answer


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.