Bourbaki–Witt theorem

Proof 1

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.

Proof 2

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

${\displaystyle g:\operatorname {Well} (X)\to X}$

given by ${\displaystyle g(S)=f(\sup S).}$ If ${\displaystyle f}$ has no fixed point, then ${\displaystyle g(S)}$ is a strict upper bound of ${\displaystyle S}$. From this, one concludes a contradiction as in a standard proof of Zorn’s lemma.^[6] For the sake of completeness, here is a sketch of the proof following T. Tao.

Let ${\displaystyle \operatorname {Well} }$ be the class of all well-ordered sets. Then for each ${\displaystyle A}$ in ${\displaystyle \operatorname {Well} }$, using an iteration of ${\displaystyle g}$, we construct a sequence ${\displaystyle x_{a}}$ of distinct elements in ${\displaystyle X}$ indexed by ${\displaystyle A}$. For example, if ${\displaystyle A=\mathbb {N} _{1}}$, then recursively we let ${\displaystyle x_{1}=g(\emptyset )}$ and ${\displaystyle x_{n}=g(x_{n-1})}$. For arbitrary ${\displaystyle A}$, 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)

${\displaystyle \rho$ :\operatorname {Well} \to \operatorname {Well} (X)}

by

${\displaystyle \rho (A)=\{x_{a}\mid a\in A\}}$.

It is not hard to see non-isomorphic ${\displaystyle A}$'s produce different sequences; i.e., ${\displaystyle \rho }$ is injective modulo isomorphisms. But ${\displaystyle \operatorname {Well} }$ 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 ${\displaystyle \operatorname {Well} (X)}$ is a set. ${\displaystyle \square }$

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 ${\displaystyle \sup S}$ only for well-ordered subsets ${\displaystyle S}$ of ${\displaystyle P}$. 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,^[7] used implicitly in a traditional proof of Hausdorff's maximal principle and also noted independently by Kneser^[8] as well as Guillermo L. Incatasciato and Pedro Sánchez Terraf.^[9]

The Bourbaki–Witt theorem follows since the function ${\displaystyle g(C)=f(\sup C)}$ has the property stated in the lemma if ${\displaystyle f}$ 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 ${\displaystyle g}$ exists, let ${\displaystyle C^{+}=C\cup \{g(C)\}}$ for each ${\displaystyle C}$ in ${\displaystyle F}$. We write ${\displaystyle S\trianglelefteq C}$ if ${\displaystyle S}$ is an initial segment of ${\displaystyle C}$,^[10] meaning ${\displaystyle S}$ is a subset and ${\displaystyle y\leq x\in S,\,y\in C\Rightarrow y\in S}$. Also, write ${\displaystyle S\triangleleft C}$ if ${\displaystyle S\trianglelefteq C,\,S\neq C}$.

Following the authors, we say a chain ${\displaystyle C\subset P}$ is good if for each ${\displaystyle S\trianglelefteq C}$, we have either ${\displaystyle S=C}$ or ${\displaystyle S^{+}\trianglelefteq C}$. Let ${\displaystyle \Gamma }$ be the set of all good chains in ${\displaystyle P}$. We claim

1. ${\displaystyle \Gamma }$ is totally ordered with respect to ${\displaystyle \trianglelefteq }$; i.e., good chains are comparable.
2. On ${\displaystyle \Gamma }$, ${\displaystyle \trianglelefteq }$ is the same as set inclusion.
3. If ${\displaystyle C}$ is a good chain in ${\displaystyle P}$, then ${\displaystyle C^{+}}$ is a good chain in ${\displaystyle P}$.

For (1), given two good chains ${\displaystyle C,D}$, let ${\displaystyle S}$ be the union of all chains that are both the initial segments of ${\displaystyle C}$ and ${\displaystyle D.}$ Clearly, ${\displaystyle S}$ itself is an initial segment of the two; i.e., it is the largest common initial segment. If ${\displaystyle S^{+}\trianglelefteq C,D}$, then that would contradict the largest-ness of ${\displaystyle S}$. Thus, either ${\displaystyle S=C}$ or ${\displaystyle D}$. For (2), suppose ${\displaystyle C\subsetneq D}$. By (1), either ${\displaystyle C\triangleleft D}$ or ${\displaystyle D\triangleleft C}$, but the latter is not possible. Finally, (3) is straightforward.

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

${\displaystyle S\triangleleft C}$.

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

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

${\displaystyle x=g(S_{x})}$.

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).