0
$\begingroup$

The version of Zorn's lemma that I have found more often is

Zorn's Lemma (1) If every chain belonging to the partially ordered set $S$ has an upper bound in $S$ then $S$ contains a maximal element.

I read the following version of Zorn's lemma, which I find somewhat seemingly different from (1):

Zorn's lemma (2) In any ordered set where every chain has a supremum in the set, any element $b$ has a maximal element $m$ such that $m\ge b$.

where a chain is a totally ordered subset and the supremum is defined as the least upper bound. As to the ordered set, the book does not define what it means to be ordered, but I know that many authors define an ordered set as a set where a partial ordering is defined, although I am not sure that a total ordering is not what is intended here. My translation is literal. This version of Zorn's lemma is said to be equivalent to in an ordered set every chain is included in a maximal chain (with respect to inclusion), and I know that this last lemma, if we mean partially ordered by ordered, is the "usual" Hausdorff maximal principle, which I know to be equivalent to (1).

In particular I am not sure that we can substitute the upper bound with the supremum and the maximal element with $m$. Moreover, I suppose, although the wording of the book is not very clear to me, that any element $b$ has a maximal element $m$ such that $m\ge b$ means that there exists a $m$ in the ordered set h that, for all $b$ in the ordered set, $m\ge b$; but if the ordering is not total, I do not think that we generally can compare the maximal element of the "usual version" of Zorn's lemma with all $b\in S$.

Are such two versions of Zorn's lemma equivalent and, if they are, how can it be seen? I heartily thank you for any answer!

$^1$V. Manca, Logica matematica, an Italian book of introductory mathematical logic and theoretical informatics.

$\endgroup$
4
  • 1
    $\begingroup$ Your question is composed of two blockquotes with a mathematical statement, each preceded by a single line, and followed by a block of text. Can you make the question clear? $\endgroup$ – Asaf Karagila Jan 26 '15 at 15:28
  • $\begingroup$ @AsafKaragila I have moved the two versions of Zorn's lemma to the top of the post and numbered them. I hope it's clearer now. Thank you for pointing out that it wasn't easily readable! $\endgroup$ – Self-teaching worker Jan 26 '15 at 15:47
  • 1
    $\begingroup$ In formulation (1), I think you mean "contains a maximal element" rather than "contains one maximal element" - the latter suggests that the maximal element is unique. $\endgroup$ – Rob Arthan Jan 26 '15 at 20:50
  • $\begingroup$ @RobArthan Yes: edited. Thank you very much! $\endgroup$ – Self-teaching worker Jan 27 '15 at 8:26
2
$\begingroup$

Zorn's lemma implies the axiom of choice. But we can ask whether or not we can restrict Zorn's lemma to a seemingly smaller class of partial order, and still have the axiom of choice (which would then suggests that the restricted version is equivalent to the full version, since choice implies Zorn's lemma in full).

The answer is positive. For example, it suffices to require that only well-ordered chains have upper bounds. You can also demand more that above every elements lies a maximal element, not just that there exists one.

You ask about an additional requirement, not just that the chain has an upper bound. We want that chains will have a supremum, which is a much stronger requirement indeed.

But analyzing the proofs that start from Zorn's lemma and prove various choice-equivalent principles, we see that in all of them the chains have supremums. For example the usual proof that Zorn's lemma implies the axiom of choice take as a partial order all the partial choice functions ordered by inclusion. Since the union of a chain of choice functions is a choice function, every chain has a supremum. So the axiom of choice holds.

You could also consider the proof of Hausdorff's maximality principle, every partial order has a maximal chain; or every chain can be extended to a maximal chain. Again here we have that given a chain $\mathcal C$ in the partial order considered for Zorn's lemma, $\bigcup\mathcal C$ is an element in the partial order as well, and it is the supremum of the chain.

So the answer is positive. Both statements are equivalent.


Note the difference, and how you changed the order of quantification, by the way. From $\forall b\in S\exists m\in S(b\leq m\land m\text{ is maximal}$ to $\exists m\in S\forall b\in S(b\leq m\land m\text{ is maximal}$. The second statement says, essentially that $m$ is a maximum which is a stronger condition.

It is also provably false. Just look at the partial order on $\{a,b\}$, where $a\neq b$ and $x\leq y\iff x=y$. There, every chain is a singleton, so it has a supremum. And there is a maximal element. But there is no maximum.

$\endgroup$
4
  • $\begingroup$ Thank you very much for your answer! There is one important thing that isn't clear to me at all: should we interpretate "any element $b$ [of the ordered set, which I'll call $S$] has a maximal element $m$ such that $m\ge b$" as $\exists m\in S:\forall b\in S\quad m\ge b$, in order for (1) and (2) to be equivalent? ... $\endgroup$ – Self-teaching worker Jan 26 '15 at 16:21
  • $\begingroup$ ...I suppose so, but I'm not sure because, after the statement of the lemma, the book says that (2) "follows from Hausdorff maximality principle. Let us consider a chain including $b$ and let us extend it in a maximal way: such a maximal chain will have a maximum and that maximum is the maximal element $\ge b$ of the lemma [(2)]" and this reasoning doesn't seem to me to prove that $\exists m\in S$ such that for all $b\in S\quad m\ge b$... $\infty$ thanks!!! $\endgroup$ – Self-teaching worker Jan 26 '15 at 16:21
  • 1
    $\begingroup$ Saying that there is $m$ which is larger than all the members of $S$ is saying that $m$ is a maximum, and that is flat out false that every partial order where every chain is bounded, or has a supremum, will have a maximum. Take $(S,=)$ as a partial order and see for yourself. $\endgroup$ – Asaf Karagila Jan 26 '15 at 16:34
  • $\begingroup$ Some searching has lead me here: euclid.colorado.edu/~monkd/m6730/gradsets05.pdf whose proof I've been able to adapt for lemma (2). $\aleph_1$ thanks! $\endgroup$ – Self-teaching worker Jan 26 '15 at 18:56

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.