Knaster-Tarski Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({L, \preceq}\right)$ be a complete lattice.

Let $f: L \to L$ be an increasing mapping.

Let $F$ be the set (or class) of fixed points of $f$.


Then $\left({F, \preceq}\right)$ is a complete lattice.


Proof

Let $S \subseteq F$.

Let $s = \bigvee S$ be the supremum of $S$.

We wish to show that there is an element of $F$ that succeeds all elementd of $S$ and is the smallest element of $F$ to do so.

By the definition of supremum, an element succeeds all elements of $S$ if and only if it succeeds $s$.

Let $U = s^\succeq$ be the upper closure of $s$.

Thus we seek the smallest fixed point of $f$ that lies in $U$.

Note that $U = \left[{s \,.\,.\, \top}\right]$, the closed interval between $s$ and the top element of $L$.

First we show that $U$ is closed under $f$.

We have that:

$\forall a \in S: a \preceq s$

so: $a = f \left({a}\right) \preceq f \left({s}\right)$

Thus $f \left({s}\right)$ is an upper bound of $S$, so by the definition of supremum, $s \preceq f \left({s}\right)$.

Let $x \in U$.

Then $s \preceq x$.

So:

$f \left({s}\right) \preceq f \left({x}\right)$

Since $s \preceq f \left({s}\right)$, it follows that:

$s \preceq f \left({x}\right)$

so:

$f \left({x}\right) \in U$

Thus the restriction of $f$ to $U$ is an increasing mapping from $U$ to $U$.

By Interval in Complete Lattice is Complete Lattice, $\left({U, \preceq}\right)$ is a complete lattice.

Thus by Knaster-Tarski Lemma, $f$ has a smallest fixed point in $U$.

Thus $S$ has a supremum in $F$.

A precisely similar argument shows that $S$ has an infimum in $F$.

Since this holds for all $S \subseteq F$, it follows that $\left({F, \preceq}\right)$ is a complete lattice.

$\blacksquare$


Also see


Source of Name

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

Tarski, however, appears to claim sole credit.


Sources