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 poset that is chain complete, meaning each chain has a least upper bound, and <math>f : X \to X</math> is a function such that <math>f (x) \geq x</math> for all <math>x,</math> then <math>f</math> 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,

: <math> x_{n+1}=f(x_n), n=0,1,2,\ldots, </math>

where x<sub>0</sub> is any element of X, is monotone increasing. By the finiteness of X, it stabilizes:

: <math> x_n=x_{\infty},</math> for n sufficiently large.

It follows that x<sub>∞</sub> is a fixed point of f.

Maximal elements

A maximal element, if any, is trivially a fixed point of the inflationary map <math>f</math>. In particular, if Zorn's lemma is available (which is equivalent to assuming the axiom of choice), then the theorem holds trivially. However, the theorem is typically used in a proof that the axiom of choice implies Zorn's lemma as follows.

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) - \{ \varnothing \}.</math>

Define a function

:<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 applied to the set <math>P'</math> of all chains in a given poset <math>P</math>, ordered by set inclusion. We get a maximal element in <math>P'</math>; i.e., a maximal chain in <math>P</math>. This proves the Hausdorff maximality principle, that every poset has a maximal chain, which is easily seen to be equivalent to Zorn's lemma (see also ).

Proofs

Proof 1

In the following, to say that an ordinal α is embeddable in a set X is to say that there exists an injection <math>f: U(\alpha) \hookrightarrow X</math> 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 <math>x_0</math> witness the non-emptiness of X, to serve as the basis for the following recursive construction of a chain in X.

For each ordinal <math>\alpha\isin\beta</math> such that <math>x_\alpha</math> is defined, define <math>x_{\alpha+1}=f(x_{\alpha}).</math> Since f is inflationary, <math>x_{\alpha}\le x_{\alpha+1}</math> in the poset X.

For each limit ordinal <math>\lambda\isin\beta</math> such that <math>x_\alpha</math> is defined for all <math>\alpha<\lambda</math>, define <math>x_\lambda=\sup\{x_\alpha|\alpha < \lambda\}.</math> Then <math>x_{\alpha}\le x_\lambda</math> for all <math>\alpha<\lambda</math>. The <math>\sup</math> 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 <math>\alpha<\beta</math> such that <math>x_{\alpha+1} = x_{\alpha}</math>, bringing the construction of the chain to a halt at <math>x_\alpha</math>, 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. 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.

Proof 2

The theorem can also be proved by adapting a typical proof showing that the axiom of choice implies Zorn’s lemma. Indeed, let <math>\operatorname{Well}(X)</math> denote the set of all well-ordered subsets of <math>X</math>. Then consider

:<math>g : \operatorname{Well}(X) \to X</math>

given by <math>g(S) = f(\sup S).</math> If <math>f</math> has no fixed point, then <math>g(S)</math> is a strict upper bound of <math>S</math>. From this, one concludes a contradiction as in a standard proof of Zorn’s lemma. For the sake of completeness, here is a sketch of the proof following T. Tao.

Let <math>\operatorname{Well}</math> be the class of all well-ordered sets. Then for each <math>A</math> in <math>\operatorname{Well}</math>, using an iteration of <math>g</math>, we construct a sequence <math>x_a</math> of distinct elements in <math>X</math> indexed by <math>A</math>. For example, if <math>A = \mathbb{N}_1</math>, then recursively we let <math>x_1 = g(\emptyset)</math> and <math>x_n = g(x_{n-1})</math>. For arbitrary <math>A</math>, we use transfinite recursion or transfinite induction to construct the sequences in a similar way. Now, this construction determines the map (class function to be precise)

:<math>\rho : \operatorname{Well} \to \operatorname{Well}(X)</math>

:<math>\rho(A) = \{ x_a \mid a \in A \}</math>.

It is not hard to see non-isomorphic <math>A</math>'s produce different sequences; i.e., <math>\rho</math> is injective modulo isomorphisms. But <math>\operatorname{Well}</math> contains all the ordinals in particular and it is known (the Burali-Forti paradox) that the class of all the ordinals is a proper class; i.e., not a set, contradicting that <math>\operatorname{Well}(X)</math> is a set. <math>\square</math>

Note the above argument does not rely on the axiom of choice. (In the case of a proof of Zorn's lemma, Choice is used to define an inflationary map.) Also, we needed <math>\sup S</math> only for well-ordered subsets <math>S</math> of <math>P</math>. The argument therefore establishes the following.

Proof 3

Just as Zorn's lemma can be proved without transfinite induction or the theory of well-ordering and ordinals, it is possible to give a proof of the theorem that only uses a basic set theory. The idea here is first to prove a general lemma below, used implicitly in a traditional proof of Hausdorff's maximal principle and also noted independently by Kneser as well as Guillermo L. Incatasciato and Pedro Sánchez Terraf.

The Bourbaki–Witt theorem follows since the function <math>g(C) = f(\sup C)</math> has the property stated in the lemma if <math>f</math> has no fixed point.

Proof of Lemma: For a textbook proof, see Hausdorff's maximal principle#Proof 1. Here, we follow Incatasciato and Terraf (in the well-ordered case, their proof is the same as Kneser's proof; see the remark below). Assuming such <math>g</math> exists, let <math>C^+ = C \cup \{ g(C) \}</math> for each <math>C</math> in <math>F</math>. We write <math>S \trianglelefteq C</math> if <math>S</math> is an initial segment of <math>C</math>, meaning <math>S</math> is a subset and <math>y \le x \in S, \, y \in C \Rightarrow y \in S</math>. Also, write <math>S \triangleleft C</math> if <math> S \trianglelefteq C, \, S \ne C</math>.

Following the authors, we say a chain <math>C \subset P</math> is good if for each <math>S \trianglelefteq C</math>, we have either <math>S = C</math> or <math>S^+ \trianglelefteq C</math>. Let <math>\Gamma</math> be the set of all good chains in <math>P</math>.

We claim

<math>\Gamma</math> is totally ordered with respect to <math>\trianglelefteq</math>; i.e., good chains are comparable.
On <math>\Gamma</math>, <math>\trianglelefteq</math> is the same as set inclusion.
If <math>C</math> is a good chain in <math>P</math>, then <math>C^+</math> is a good chain in <math>P</math>.

For (1), given two good chains <math>C, D</math>, let <math>S</math> be the union of all chains that are both the initial segments of <math>C</math> and <math>D.</math> Clearly, <math>S</math> itself is an initial segment of the two; i.e., it is the largest common initial segment. If <math>S^+ \trianglelefteq C, D</math>, then that would contradict the largest-ness of <math>S</math>. Thus, either <math>S = C</math> or <math>D</math>.

For (2), suppose <math>C \subsetneq D</math>. By (1), either <math>C \triangleleft D</math> or <math>D \triangleleft C</math>, but the latter is not possible. Finally, (3) is straightforward.

We can now finish. Let <math>U</math> be the union of <math>\Gamma</math>. By (1), <math>U</math> is a chain. To show it is good, suppose <math>S \triangleleft U</math>. Let <math>x</math> be in <math>U - S</math>. Pick a good chain <math>C</math> containing <math>x</math>. Then we have

:<math>S \triangleleft C</math>.

Indeed, if <math>y</math> is in <math>S</math>, then <math>y</math> is in a good chain <math>D</math>. If <math>D \trianglelefteq C</math>, then <math>y</math> is in <math>C</math>. Otherwise, by (1), <math>C \trianglelefteq D</math>. We have <math>y \le x</math> by <math>S \triangleleft U</math> and so again <math>y</math> is in <math>C</math>. Hence, <math>S \subset C</math> and that implies <math>S \triangleleft C</math> as <math>S</math> is already an initial segment of <math>U</math>. Finally, <math>S^+ \trianglelefteq C</math> and, by (2), <math>S^+ \trianglelefteq U</math>. This finishes the proof of the fact that <math>U</math> is good. Since <math>U^+ = U</math> then, this is a contradiction. <math>\square</math>

Remark: In the above, we could have used well-ordered subsets instead of chains. That is, let <math>U</math> be the union of all good well-ordered subsets of <math>P</math>. All the assertions hold with well-ordered subsets in place of chains. Note <math>U</math> is well-ordered not just totally ordered by (2). Thus, the above argument also shows the well-ordered version of the theorem stated at . Moreover, for a well-ordered set <math>C</math>, since an initial segment is of the form <math>S_x = \{ y \mid y < x \}</math>, explicitly, <math>C</math> is good if and only if, for each <math>x</math> in <math>C</math>, we have:

:<math>x = g(S_x)</math>.

Hence, a good well-ordered set is exactly the same as what Kneser calls Kette (and so the above proof reduces to Kneser's proof).

Applications

Besides a proof of Zorn's lemma, Bourbaki–Witt has some 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.

Notes

References

https://proofwiki.org/wiki/Bourbaki-Witt_Fixed_Point_Theorem
https://topology.lmf.cnrs.fr/bourbaki-witt-and-dito-pataraia/