A statement equivalent to Zorn’s lemma

set-theory

In his book “Naive Set Theory”, Halmos asks reader to show that the axiom of choice is equivalent to the following statement: “Every partially ordered set in which each chain has a least upper bound has a maximal element.”

I think the easiest way of showing this is to show that this statement is equivalent to Zorn’s lemma. Moreover, it is trivial that if Zorn’s lemma is correct, then the statement is correct. To show the reverse implication, it is sufficient to show that if $C$ is a chain in a partially ordered set $X$ and $C$ has an upper bound, then $C$ has a least upper bound in $X$. However, I am not sure that this is correct. For example, let $X=(0,1)\cup [2,3]$. Then, an increasing sequence converging to 1 is a chain in $X$, and it has an upper bound in $X$, but it does not have a least upper bound in $X$.

Am I missing something? If I am mistaken, then could you help me prove the equivalence?

Best Answer

First of all, in $(0,1)\cup[2,3]$ the chain $(0,1)$ has a least upper bound, $2$. While $2$ is not the least upper bound in $\Bbb R$, this is not $\Bbb R$ that we're talking about.

Secondly, it is indeed not true that if "every chain has an upper bound", then "every chain has a least upper bound". The simplest example would be $\Bbb Q\cap[0,1]$, where every chain has an upper bound, $1$, but if you look at the chain $\left\{q\in\Bbb Q\cap[0,1]\mathrel{}\middle|\mathrel{} q<\sqrt\frac12\right\}$, then it does not have a least upper bound.

The easiest way to prove this is to find an intermediate partial order where every chain has a least upper bound. Here are two suggestions:

  1. Just prove the axiom of choice directly. Given a family of non-empty sets, consider all the choice functions from subfamilies, ordered by inclusion. It is not hard to show that if $C$ is a chain, then $\bigcup_{f\in C}f$ is a choice function, and it is the least upper bound of $C$.

  2. Given a partial order $P$ where every chain has an upper bound, consider the partial order of all chains in $P$, ordered by inclusion. Again, since this is inclusion of chains, a chain-of-chains has a least upper bound: its union, just as the previous example. Now, we get a maximal chain in $P$, but because it has an upper bound, it is easy to see that this upper bound is a maximal element, thus proving Zorn's lemma.

Related Question