Bourbaki-Witt theorem

In mathematics, the Bourbaki-Witt theorem in order theory is a basic fixed-point theorem for partially ordered sets. It states that for X be a chain complete poset, and

<math>f : X \to X<math>

such that

<math>f (x) \geq x<math>,

f has a fixed point. Such a function f is called inflationary.

The most common proof of it is unwieldy and involved, so this is often thought of as a hard theorem. Here is a sketch of a shorter proof, done by recursion on the ordinals.

Pick some <math>y \in X<math>. Define a function K recursively on the ordinals as follows:

<math> K(0) = y <math>

<math>K( \alpha^+ ) = f( K( \alpha ) ). <math>

If <math> \beta <math> is a limit ordinal, then by construction

<math>\{ K( \alpha ) \ : \ \alpha < \beta \}<math>

is a chain in X. Define

<math>K( \beta ) = \sup \{ K( \alpha ) \ : \ \alpha < \beta \}.<math>

This is now an increasing function from the ordinals into X. It cannot be strictly increasing, as if it were we would have an injective function from the ordinals into a set. Therefore the function must be eventually constant, so for some

<math> \alpha , \ \ K( \alpha^+ ) = K ( \alpha ) <math>;

that is,

<math>f( K( \alpha ) ) = K ( \alpha )<math>.

So letting

<math>x = K ( \alpha )<math>

we have our desired fixed point.

The Bourbaki-Witt theorem has various important applications. One of the most common is in the proof that the Axiom of Choice implies Zorn's Lemma. We first prove it for the case where X is chain complete and has no maximal element. Let g be a choice function on

<math>P(X) – \{ \emptyset \}<math>.

Define a function

<math>f : X \to X<math>

by

<math>f(x) = g( \{ y \ : \ y > x \} )<math>.

This is allowed as, by assumption, the set is non-empty. Then f(x) > x, so f is an inflationary function with no fixed point, contradicting the theorem.

This special case of Zorn's lemma is then used to prove the Hausdorff maximality principle, that every poset has a maximal chain, which is easily seen to be equivalent to Zorn's Lemma.

Bourbaki-Witt has other applications. In particular in computer science, it is used in the theory of recursive functions.