Knaster-Tarski Lemma/Power Set

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal P \left({S}\right)$ be the power set of $S$.

Let $f: \mathcal P \left({S}\right) \to \mathcal P \left({S}\right)$ be a $\subseteq$-increasing mapping.

That is, suppose that for all $T, U \in \mathcal P \left({S}\right)$:

$T \subseteq U \implies f \left({T}\right) \subseteq f \left({U}\right)$


Then $f$ has a greatest fixed point and a least fixed point.


Proof

By Power Set is Complete Lattice, $\left({\mathcal P\left({S}\right), \cap, \cup, \subseteq}\right)$ is a complete lattice.

Thus the theorem holds by the Knaster-Tarski Lemma.

$\blacksquare$


Source of Name

This entry was named for Bronisław Knaster and Alfred Tarski.


Sources