2
$\begingroup$

I'm trying to understand the proof of Zorn's Lemma but the one which does not use ordinals (Halmos' proof) is extremely long and I really feel I get lost somewhere along the way. On the other hand, I've found a couple of short proofs which use ordinals, so I think I could learn just the necessary stuff and go for them. So I would like to ask you about the prerequisites on ordinals to study them.

The proofs I found are:

(1) Zorn's Lemma And Axiom of Choice

(2) https://proofwiki.org/wiki/Axiom_of_Choice_Implies_Zorn%27s_Lemma

I have a preference for the first one.

$\endgroup$
  • $\begingroup$ I don't know what Halmos proof you mean: in his book "Naive Set Theory" he gives a rather looooong, slightly involved proof using a choice function, initial segments and stuff, but without ordinals, which I am unable to see what would their job be in this matter. $\endgroup$ – DonAntonio May 22 '14 at 14:08
  • $\begingroup$ @DonAntonio I said Halmos' Proof does not use ordinals, but it's too long for my taste. $\endgroup$ – Chirs Erickson May 22 '14 at 14:10
  • $\begingroup$ I see, @Chirs. Anyway, I am not aware of a proof using ordinals. Do you have any reference? $\endgroup$ – DonAntonio May 22 '14 at 14:12
  • 1
    $\begingroup$ @DonAntonio I linked two. $\endgroup$ – Chirs Erickson May 22 '14 at 14:14
  • $\begingroup$ Halmos's proof is involved but with perseverance you can untangle it. I found some help here (though I didn't agree with everything it contains) arxiv.org/pdf/1207.6698v1.pdf. $\endgroup$ – Tom Collinge May 22 '14 at 14:18
3
$\begingroup$

As some people remarked, you don't need to know about ordinals at all in order to understand a proof of Zorn's lemma. However, I think that ordinals make an incredibly lovely concept, and show a particularly great generalization of something we all know very well (the natural numbers and induction), so it is worth learning a little about them.

What do you need for understanding the classical proof of Zorn's lemma?

  1. What is a well-ordering, what are successor and limit points of a well-order.
  2. Transfinite induction/recursion on general well-orderings.
  3. Every two well-orders are comparable in the relation "isomorphic to an initial segment".
  4. If there is an isomorphism between two well-ordered sets, then there is exactly one.
  5. What is the von Neumann ordinal assignment, and why it's a good thing (in particular how $<$ is really $\in$, and $\leq$ is really $\subseteq$).
  6. Hartogs and Lindenbaum theorems.

Now it should be easy to understand the majority of the proofs of Zorn's lemma from the axiom of choice.

It should suffice for understanding the usual proof of the well-ordering theorem.


Of course, that you can decide that you want to do things a bit differently, and use some other principle and not the axiom of choice directly. For example "Every partial order has a maximal chain", then the proof of Zorn's lemma is trivial, since an upper bound of a maximal chain is a maximal element!

$\endgroup$
2
$\begingroup$

In the approach via ordinals, the most difficult part is establishing that one can define functions by transfinite recursion. Of course, one doesn't really need this general result in order to prove Zorn's Lemma; one needs only the particular transfinite recursion that keeps choosing higher and higher elements in the partially ordered set until it arrives at a maximal element.

My impression is that proofs that avoid ordinals usually include what amounts to a version of that particular case of the transfinite recursion theorem, phrased so as to not directly mention ordinals, and folded (or even mixed) in with the rest of the argument. To me, this folding or mixing makes the proof rather unintuitive, so I prefer an approach that establishes transfinite recursion separately. Usually, such an approach would use ordinals, but it can also be formulated in terms of any sufficiently long well-ordered set (obtainable by Hartogs's Theorem).

$\endgroup$

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.