Bourbaki-Witt Fixed Point Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({X, \le}\right)$ be a non-empty chain complete poset (that is, a poset in which every chain has a least upper bound).

Let $f : X \to X$ be an inflationary mapping, that is, so that $f \left({x}\right) \geq x$.


Then for every $x \in X$ there exists $y \in X$ where $y \geq x$ such that $f \left({y}\right) = y$.


Proof

Let $\gamma$ be the Hartogs number of $X$.

Suppose that $x \in X$.


Define $g : \gamma \to X$ by transfinite recursion as follows:

  • $g \left({0}\right) = x$
  • $g \left({\alpha + 1}\right) = f \left({g \left({\alpha}\right)}\right)$
  • $g \left({\alpha}\right) = \sup \left\{{g \left({\beta}\right) : \beta < \alpha}\right\}$ when $\alpha$ is a limit ordinal.


That $f$ is inflationary guarantees both that:

$(1) \quad \left\{{g \left({\beta}\right) : \beta < \alpha}\right\}$ is a chain for each $\alpha \lt \gamma$
$(2) \quad g$ is increasing.


If $g$ is strictly increasing, then $g$ is strictly monotone and, by Strictly Monotone Mapping with Totally Ordered Domain is Injective, an injection.

But by definition of Hartogs number, $\gamma$ is the least ordinal such that there is no injection from $\gamma$ to $X$.

Therefore there must be some $\alpha \lt \beta \lt \gamma$ with $g \left({\alpha}\right) = g \left({\beta}\right)$.

Then $\alpha + 1 \le \beta$, so $g \left({\alpha}\right) \le g \left({\alpha}+1\right) \le g \left({\beta}\right) = g \left({\alpha}\right)$, whence $f \left(g \left({\alpha}\right)\right) = g\left({\alpha}\right)$.

Since $x = g \left({0}\right)$:

$\exists y \in g \left({\gamma}\right) \subseteq \left\{{y \in X : x \leq y}\right\}: f \left({y}\right) = y$

$\blacksquare$


Source of Name

This entry was named for Nicolas Bourbaki and Ernst Witt.


Sources