Bourbaki–Witt theorem

In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed-point theorem for partially ordered sets. It states that if X is a non-empty chain complete poset, and ${\displaystyle f:X\to X}$ such that ${\displaystyle f(x)\geq x}$ for all ${\displaystyle x,}$ then f has a fixed point. Such a function f is called inflationary or progressive.

Special case of a finite poset

If the poset X is finite then the statement of the theorem has a clear interpretation that leads to the proof. The sequence of successive iterates,

${\displaystyle x_{n+1}=f(x_{n}),n=0,1,2,\ldots ,}$

where x₀ is any element of X, is monotone increasing. By the finiteness of X, it stabilizes:

${\displaystyle x_{n}=x_{\infty },}$ for n sufficiently large.

It follows that x_∞ is a fixed point of f.

Proof of the theorem

In the following, to say that an ordinal α is embeddable in a set X is to say that there exists an injection ${\displaystyle f:U(\alpha )\hookrightarrow X}$ from the underlying set of α to X. Such an injection amounts to a well-ordering of the image of f as a subset of X, thereby witnessing that that subset can be well-ordered.

Let β be the Hartogs number for the set U(X) of the given poset X. By definition this is the set of all ordinals embeddable in U(X), itself an ordinal not embeddable in U(X) or we would have β ϵ β. (Equivalently, β is the least ordinal not embeddable in U(X), necessarily a cardinal.) Let ${\displaystyle x_{0}}$ witness the non-emptiness of X, to serve as the basis for the following recursive construction of a chain in X.

For each ordinal ${\displaystyle \alpha \in \beta }$ such that ${\displaystyle x_{\alpha }}$ is defined, define ${\displaystyle x_{\alpha +1}=f(x_{\alpha }).}$ Since f is inflationary, ${\displaystyle x_{\alpha }\leq x_{\alpha +1}}$ in the poset X.

For each limit ordinal ${\displaystyle \lambda \in \beta }$ such that ${\displaystyle x_{\alpha }}$ is defined for all ${\displaystyle \alpha <\lambda }$, define ${\displaystyle x_{\lambda }=\sup\{x_{\alpha }|\alpha <\lambda \}.}$ Then ${\displaystyle x_{\alpha }\leq x_{\lambda }}$ for all ${\displaystyle \alpha <\lambda }$. The ${\displaystyle \sup }$ exists by chain-completeness of the poset X.

Now if f is strictly increasing on all of β, this would constitute an embedding of β, the order type of that chain, in X. But that's impossible by Hartogs' Lemma.

Hence there must exist ${\displaystyle \alpha <\beta }$ such that ${\displaystyle x_{\alpha +1}=x_{\alpha }}$, bringing the construction of the chain to a halt at ${\displaystyle x_{\alpha }}$, the promised fixed point. Q.E.D.

Independence of Choice

The foregoing argument avoids anything that depends on the Axiom of Choice.

Now it is tempting to argue that the Hartogs number for the set X must be the least cardinal greater than the cardinality of X. After all, surely the above recursive construction must eventually exhaust all the elements of X long before exhausting all the ordinals.

However a set that can only embed finite ordinals is called Dedekind-finite and ZF can have models in which infinite Dedekind-finite sets exist.^[1][2] The Hartogs number for such sets is therefore ω, and posets on them cannot contain any infinite chains.

To be sure we have not somehow smuggled in anything not provable in ZF without choice, we should stick to what is provable in ZF alone. Otherwise applications of the Bourbaki–Witt theorem to proofs relating equivalences between variants of the Axiom of Choice, such as done below, may introduce circularities into the reasoning.

Applications

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 ${\displaystyle P(X)-\{\varnothing \}.}$ Define a function ${\displaystyle f:X\to X}$ by ${\displaystyle f(x)=g(\{y\$ :\ y>x\}).}

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 computable functions. It is also used to define recursive data types, e.g. linked lists, in domain theory.

See also

• Kleene fixed-point theorem for Scott-continuous functions
• Knaster–Tarski theorem for complete lattices