Serge Lang in his book Algebra has a nice appendix on set theory at the end of the book. In particular, in paragraph 2, pp. 881-884 he provides a proof of Zorn's Lemma from "other properties of sets which everyone would immediately grant as acceptable psychologically" (see middle of p. 881). As i understand Zorn's Lemma is equivalent to the Axiom of Choice and to the Well Ordering Principle. However, in Lang's proof i can not identify a point where either of the above two axioms is used. At the top of p. 882 he gives an argument according to which "we can assume that the set under consideration has a least element", but this, "without loss of generality". So, even though this resembles the "well ordering principle", it does not seem to be it. My question is: Are indeed the axiom of choice or the well-ordering principle not used in Lang's proof? If yes where? If not, then what is the subtle set-theoretic axiom that this proof uses to deliver Zorn's Lemma?

Edited: In the appendix that i am referring to, Zorn's Lemma appears as Corollary 2.5. However, when by "proof of Zorn's Lemma", i mean all the material that Lang proves to get to Corollary 2.5, i.e. Theorem 2.1, Lemma 2.2, Lemma 2.3, Corollary 2.4.

  • 2
    $\begingroup$ One of them or something equivalent to them is necessarily used in the proof. Without seeing the proof, however, I have no idea exactly what is used. Depending on what the ‘set under consideration’ is, however, it sounds very much as if he may at that point be slipping in an instance of the well-ordering principle that happens to seem ‘acceptable psychologically’. $\endgroup$ – Brian M. Scott Dec 15 '12 at 0:23
  • $\begingroup$ @BrianM.Scott: Unfortunately the proof is too long to reproduce here. However, here is the point that he might be doing what you said: "Let $A$ be a non-empty partially ordered and strictly inductively ordered set. Then we can assume without loss of generality that $A$ has a least element $a$." The argument is that we can remove all elements $x$ that do not satisfy $x \ge a$. Then we obtain a subset with a least element. $\endgroup$ – Manos Dec 15 '12 at 1:00
  • $\begingroup$ @Manos: This WLOG is completely fine. You care about a maximal element, just pick an element and show that if it's not maximal then somewhere above it there is a maximal element. You do that by removing anyone which is not above your chosen element. $\endgroup$ – Asaf Karagila Dec 15 '12 at 1:03
  • $\begingroup$ @AsafKaragila: I thought its fine myself as well. Just mentioned it for confirmation. I still can not see where the well-ordering comes into play in the proof. $\endgroup$ – Manos Dec 15 '12 at 1:04

The proof I saw was using, essentially, the Hausdorff Maximality Principle.

Hausdorff Maximality Principle (HMP). Every partially ordered chain has a $\subseteq$-maximal chain.

Clearly if $(P,\leq)$ is a partially ordered set satisfying the conditions for Zorn's lemma, and $C\subseteq P$ is a maximal chain then $C$ has an upper bound $c$ and by the maximality of $C$ we have to have $c\in C$ and that it is a maximal element.

The proof seems to go through other means to prove HMP, and it uses the Bourbaki-Witt theorem.

The Bourbaki-Witt theorem does not rely on the axiom of choice at all. It is provable in ZF, as remarked by Brian here. The reason it is provable in ZF is that it assumes the existence of a least upper bound of every chain, and therefore allows a canonical choice for $a_1$ when moving from $D_0$ to $D_1$ (and so on).

The axiom of choice comes in, full-blown power, in the proof of Corollary 2.4:

Suppose that $A$ does not have a maximal element. Then for each $x\in A$ there is an element $y_x\in A$ such that $x<y_x$. Let $f\colon A\to A$ be the map such that $f(x)=y_x$ for all $x\in A$.

Here we actually say that $f$ is a choice function. In the proof of the Bourbaki-Witt theorem we needed to know what is the next step in "growing up", but we assumed that $f$ was given to us. From that it was just a matter of finishing the proof.

But in this corollary we need to actually define $f$. And this requires the axiom of choice.

I should add that there are books full of equivalents to the axiom of choice, and there are a lot of them which are very not-set theoretical axioms, or very unrelated to well-ordering (e.g. "Every non-empty set can be made into a group"). Since they are all equivalent to the axiom of choice, all of them are equivalent to Zorn's lemma.

  • $\begingroup$ My question refers to everything that Lang proves in order to get to the proof you mention of Zorn's Lemma (that would be Corollary 2.5). The Bourbaki-Witt Theorem is Theorem 2.1 p. 881. Does that use the Well-Ordering Principle? If yes where? $\endgroup$ – Manos Dec 15 '12 at 0:53
  • $\begingroup$ @Manos: Let me read. The proof is long and obfuscate choice well. $\endgroup$ – Asaf Karagila Dec 15 '12 at 1:03
  • 1
    $\begingroup$ Beautiful!!Thanks a lot :) $\endgroup$ – Manos Dec 15 '12 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.