In "Mathematical Physics" by Robert Geroch, the following 'plausibility argument' is given for Zorn's Lemma [If every totally ordered subset of a partially ordered set $S$ is bounded above, $S$ has a maximal element]:

It is not difficult to convince onselef that this statement [Zorn's Lemma] seems "true". Pick $s_1$ in $S$. If this $s_1$ is not a maximal element, there is an $s_2$, different from $s_1$, with $s_1 \leq s_2$. If $s_2$ is not maximal, there is an $s_3$, different from $s_2$, with $s_2 \leq s_3$, etc. Either we eventually obtain a maximal element (in which case we are done), or we obtain $s_1 \leq s_3 \leq s_3 \leq ... $ . In this latter case, $\{s_1,s_2,...\}$ is a totally ordered subset of $S$, whence it is bounded above, say by $s_1'$. If $s_1'$ is not a maximal element, there is $s_2'$ with $s_1' \leq s_2'$, etc. (We "go right through infinity.") If we find no maximal element in $s_1', s_2', ...$, we obtain, again, a totally ordered set, which must be bounded above, say by $s_1''$, etc. Suppose we are unlucky and go through an infinite sequence of such sequences without finding a maximal element. Then we obtain totally ordered $s_{m}^{n} \{m,n = 1,2,...\}$, which must be bounded above, say by $t1$, etc. We "continue in this way. At every stage we have a totally ordered subset, which must be bounded above, so we add in this upper bound to obtain a new totally ordered subset. We can go through infinity, an infinity of infinities, etc. We never get stuck; we can always go on. We should obtain eventually a maximal element."

I don't see how this argument makes Zorn's Lemma plausible, however. If anything, it seems to say that it is possible that we can go through infinities of elements forever, always finding upper bounds and forming totally ordered sets with them, and doing this on and on, without ever finding a maximal element. In particularly, how does the last sentence above "We should obtain eventually a maximal element" at all follow from the argument?

  • 3
    $\begingroup$ It does not "follow" from the argument. It is some kind of intuition that the author has on order structures. And, actually, it is similar to the intuition that Halmos provides in "Naive Set Theory". $\endgroup$ – Steve Pap Dec 28 '13 at 23:55
  • 3
    $\begingroup$ Halmos does provide a similar idea, however, he is a little more pessimistic about it. He claims "Just how and when all this comes to an end is obscure, to say the least." $\endgroup$ – Pedro Tamaroff Dec 28 '13 at 23:58
  • $\begingroup$ @user114806 I also read this chapter and maybe what confused you was also what confused me at first: It is very important that all ordered subsets are bounded above. E.g. the natural numbers have no maximal element even though all subsets can be ordered because some of them are not bounded (e.g. 2,4,6,...). But e.g. to an infinite basis of a vector space, one can at some point not add elements any more without violating linear independence, thus there is an upper bound, satisfying the use of the lemma. Here is anoter site with examples. $\endgroup$ – exchange Dec 4 '16 at 18:13

This is not quite a mathematical argument. And since it is not really a proof, Zorn's lemma doesn't quite follow from it. What it is is an intuitive explanation trying to convince the reader to accept Zorn's lemma as an axiom.

The point that the paragraph is trying to make is that if we have a partial order satisfying the conditions in Zorn's lemma, then we can define this recursive process which will construct a chain, and if there is no maximal element then this process cannot terminate.

But when we say "terminate" we don't mean that in the "applied" kind of way. We mean that in the set theoretical way. Saying that we in fact defined an injective function from a proper class into a set, which is a contradiction. That what it means "go through infinity, an infinite of infinites etc.", that we go through the first $\omega$ steps, but we can continue, and we go through more and more and more steps and so on.

One reason to give this sort of... half-assed explanation lies in the third word of your question "Physics". To fully understand Zorn's lemma one has to understand some set theory first, to understand the axiom of choice, to understand the well-ordering principle, and so on. One can just write it up as a black box, or convince themselves that they understand how Zorn's lemma works. But I won't expect a physicist to sit down and understand the mechanics of transfinite induction, and the axiom of choice.

So in order to convince a physicist that Zorn's lemma is plausible, one has to resort to furious handwaving like in the quoted paragraph.

The paragraph is, in fact, a broad stroke of how to prove Zorn's lemma from the axiom of choice, using transfinite recursion. The "through infinity" part is what is known as a limit stage in transfinite recursion.

Finally, let me point that of course one has to be convinced about the plausibility of Zorn's lemma. It is unprovable without the axiom of choice (and indeed assuming Zorn's lemma we can prove the axiom of choice) and that makes the lemma very non-constructive. And one can see that from the formulation of the lemma. There exists a maximal element. We are not told how that element looks like, or what sort of properties it may have. It just exists.

  • 1
    $\begingroup$ But even as an intuitive explanation, I don't see how it is intuitive. Like you said, if there is no maximal element then this process cannot terminate. Ok, but so what? Does this non-termination (even in a set theoretical sense) lead to some sort of a contradiction? Maybe it just simply doesn't terminate, and that's that - without there being a maximal element after all? $\endgroup$ – user114806 Dec 29 '13 at 0:39
  • $\begingroup$ Yes, it leads to a contradiction. I've edited to spell it out. $\endgroup$ – Asaf Karagila Dec 29 '13 at 0:42
  • $\begingroup$ Sorry, I guess I still don't follow - can you please clarify what 1) the proper class and 2) the set are here, and what the injective function from 1) to 2) is? I'm trying to see what these could possibly be based on the recursive process described.. $\endgroup$ – user114806 Dec 29 '13 at 0:53
  • $\begingroup$ Proper classes are collections which are can talk about, but are not sets. Things like "the set of all sets" do not exist in most modern set theories, and instead we have "the class of all sets". One of these classes is the class of all ordinals, where ordinals are a generalization of the natural numbers in terms of order, and they allow us to perform inductive processes which may as well carry beyond the realm of the natural numbers. Like the construction described above. If the processes does not stop at any ordinal, [...] $\endgroup$ – Asaf Karagila Dec 29 '13 at 1:03
  • 1
    $\begingroup$ I think this handwaving is better than the convoluted "elementary" proofs of Zorn's lemma that try to avoid using ordinals and transfinite recursion. $\endgroup$ – Michael Greinecker Dec 29 '13 at 2:30

The main idea, which is not intuitive at all without some set theory background, is that if this process of going through infinity, infinities of infinities, etc., did not eventually result in a maximal element, then the original $S$ would be too large to be a set (it would be a proper class).

  • 1
    $\begingroup$ Well before that, you get a transfinite sequence of more different elements than the set they came from. $\endgroup$ – Michael Greinecker Dec 29 '13 at 2:33
  • $\begingroup$ @MichaelGreinecker The notion of "more different elements" seems to involve another use of the axiom of choice (in addition to the obvious use in successively choosing $s_1,s_2,\dots$), either via well-ordering or via comparability of cardinals. To make the argument precise, without talking about proper classes, I'd use Hartogs's theorem, which says that, for any set $S$, there is a well-ordered set that can't be mapped one-to-one into $S$. This theorem doesn't require the axiom of choice, and it gives a (somewhat weak) notion of "more" sufficient to make your comment work. $\endgroup$ – Andreas Blass Dec 5 '16 at 3:53

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.