Tarski's fixed point theorem
A complete lattice is a lattice where every set of elements has the least upper bound and the greatest lower bound (this implies that there is top and bottom as and .
(Note: if you know that you have least upper bounds for all sets, it follows that you also have greatest lower bounds, by taking the least upper bound of the lower bounds. Converse also holds, dually.)
Let be a complete lattice and a monotonic function.
the set of postfix points of (e.g. is a postfix point)
the set of fixed points of . Note that .
Theorem: Let . Then is the least element of .
Proof is amusing. Let range over elements of .
- applying monotonic from we get
- so is a lower bound on , but is the greatest lower bound, so
- is closed under , by monotonicity, so
- is a lower bound on , so
- from and we have , so
- is a lower bound on so it is also a lower bound on a smaller set
Dually, if the set of prefix points of , then is the largest element of .
Tarski's Fixed Point theorem shows that in a complete lattice with a monotonic function on this lattice, there is at least one fixed point of , namely the least fixed point .
To find this fixed point, we can start from . Then the sequence will converge to the least fixed point if is -continuous, i.e. if .
In order to converge faster, we can use techniques such as widening.