# Bourbaki-Witt fixed point theorem: two questions

Consider the following theorem:

Let $f\colon E \to E$ have the propery that $f(x)\geq x$, where $(E,\leq)$ is a non-void partially ordered set with the property that every totally ordered subset of $E$ has a least upper bound. Then there is an element $a$ in $E$ such that $a=f(a)$.

My first question is:

does this theorem hold for sets like $[0,1[$? In general, does it hold for generic subsets of $\mathbb{R}$?

This theorem "implies" the Hausdorff maximality theorem, that is "every partially ordered system contains a maximally ordered subsystem."

Proof. If $E$ has no maximal element, then to every $A \in E$ there corresponds an $f(A)$ containing $A$ properly. Thus the preceding theorem is contradicted by the function $f\colon E \to E. \quad \blacksquare$

My second question is:

in proving this statement it seems that we are not taking into account only the fixed point theorem, but the fact that the function $f$ is not defined "concretely". Are we invoking implicitly the axiom of choice?

-
To your second question, I would say that Bourbaki-Witt theorem can be used to show that AC implies ZL is more precise than the statement Bourbaki-Witt theorem implies ZL. You're right that the above proof uses AC implicitly; in some places the use of AC is more explicit; see e.g. files.nyu.edu/eo1/public/Book-PDF/CHAPTER%205%20(Zorn).pdf and artofproblemsolving.com/Wiki/index.php/Zorn%27s_Lemma –  Martin Sleziak Apr 6 '12 at 10:31

The set $[0,1[$ does not have a least upper bound in itself, so the theorem does not apply to it. It also does not hold: consider the map $$f:[0,1[\to[0,1[:x\mapsto \frac{x+1}2\;.$$ Clearly $f(x)>x$ for each $x\in[0,1[$.

Added: The answer to the second question is yes: the Hausdorff maximality principle [HMP] is equivalent to the axiom of choice [AC}, but the Bourbaki-Witt theorem can be proved in ZF without AC. Since AC is independent of ZF, the HMP cannot possibly follow from the Bourbaki-Witt theorem. What is true is that the Bourbaki-Witt theorem allows an easy proof that AC implies HMP, as may be seen here.

-

I looked at the proof appearing in Wikipedia, the proof of the theorem goes like this:

Let $x_0\in E$. Suppose $x_\alpha$ was defined, let $x_{\alpha+1}=f(x_\alpha)$, and if $\beta$ is a limit ordinal and $x_\alpha$ was defined for all $\alpha<\beta$ then $x_\beta=\sup\{x_\alpha\mid\alpha<\beta\}$ (this is well defined because we ensured that $\{x_\alpha\mid\alpha<\beta\}$ is a chain, therefore it has a supremum)

So far there is no use in the axiom of choice. The assumption on $E$ was that every chain has a supremum. In the usual proof of AC from Zorn's Lemma there is no supremum and we need to choose an upper bound at limit stages.

Now, a very good construction related to the axiom of choice is Hartogs number, let us denote $X$'s Hartogs by $\aleph(X)$: the least ordinal which cannot be injected into $X$. Assuming the axiom of choice $\aleph(X)=|X|^+$, but without the axiom of choice this is a good measure on "how much of $X$ can be well ordered".

We return to the above $x_\alpha$'s, if $x_\alpha=x_{\alpha+1}$ then $f(x_\alpha)=x_{\alpha+1}$ and we found the fixed point; otherwise we can contintue and define an injection from $\aleph(E)$ into $E$ which is a contradiction.

The key point, here, is that $f(x)\geq x$ and that $E$ has the property that every chain has a least upper bound. From these two properties the proof becomes constructive. Not everything which is "general" requires the axiom of choice. It is possible to have general, nontrivial theorems which do not require the axiom of choice (e.g. Cantor's theorem; Cantor-Bernstein theorem). Furthermore, the generality is quite restrictive in the form mentioned above with the property of $E$.

-