Knaster-Tarski Lemma/Corollary/Power Set

From ProofWiki
Jump to navigation Jump to search


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 fixed point.

Proof 1

By the Knaster-Tarski Lemma: Power Set, $f$ has a least fixed point.

Thus it has a fixed point.


Proof 2

Let $P = \left\{{x \in \mathcal P \left({S}\right): x \subseteq f \left({x}\right) }\right\}$.

Let $\bigcup P$ be the union of $P$.

Let $x \in P$.

Then by Set is Subset of Union: General Result, $x \subseteq \bigcup P$.

Since $f$ is increasing, $f \left({x}\right) \subseteq f \left({\bigcup P}\right)$.

By the definition of $P$, $x \subseteq f \left({x}\right)$.

Thus $x \subseteq f \left({\bigcup P}\right)$ by Subset Relation is Transitive:

As this holds for all $x \in P$, $\bigcup P \subseteq f \left({\bigcup P}\right)$ by Union is Smallest Superset: General Result.

Now since $f$ is increasing:

$f \left({\bigcup P}\right) \subseteq f \left({ f \left({\bigcup P}\right)}\right)$

Thus $f \left({\bigcup P}\right) \in P$ by the definition of $P$.

Therefore by Set is Subset of Union: General Result:

$f \left({\bigcup P}\right) \subseteq \bigcup P$

We have that:

$\bigcup P \subseteq f \left({\bigcup P}\right)$

Thus by definition of set equality:

$f \left({\bigcup P}\right) = \bigcup P$

Thus $\bigcup P$ is a fixed point of $f$.


Source of Name

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