Knaster-Tarski Lemma/Corollary
Jump to navigation
Jump to search
Theorem
Let $\struct {L, \preceq}$ be a complete lattice.
Let $f: L \to L$ be an increasing mapping.
Then $f$ has a fixed point
Power Set
Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
Let $f: \powerset S \to \powerset S$ be a $\subseteq$-increasing mapping.
That is, suppose that for all $T, U \in \powerset S$:
- $T \subseteq U \implies \map f T \subseteq \map f U$
Then $f$ has a fixed point.
Proof
By the Knaster-Tarski Lemma, $f$ has a least fixed point.
Thus it has a fixed point.
$\blacksquare$