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.
Answer
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.
No comments:
Post a Comment