Exercise 8.1.4

Proof. $\text{(→)}$ First, suppose that Zorn’s Lemma is true, and let $C$ be the set of all chains of $(A,\le )$. First, it is trivial to show that $\subseteq$ is a partial order on $C$, i.e. that it is reflexive, antisymmetric, and transitive. Let $B\subseteq C$ be any $\subseteq$-chain, and let $U=\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$.

First we claim that that $U\in C$, which requires that we show that $U$ is a chain of $(A,\le )$. So consider any $x,y\in U=\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ so that there are sets $X,Y\in B$ such that $x\in X$ and $y\in Y$. Since $B$ is a $\subseteq$-chain it follows that either $X\subseteq Y$ or $Y\subseteq X$. In the case of $X\subseteq Y$ then clearly both $x$ and $y$ are in $Y$ (since $x\in X$ and $X\subseteq Y$). Then, since $Y\in C$ (since $Y\in B$ and $B\subseteq C$), we have that $Y$ is a $\le$-chain. Hence $x$ and $y$ are comparable in $\le$. The case in which $Y\subseteq X$ is analogous. Since $x,y\in U$ were arbitrary, this shows that $U$ is a $\le$-chain so that $U\in C$.

We also claim that $U$ is an upper bound (with respect to $\subseteq$) of $B$. To show this, consider any $X\in B$ and any $x\in X$. Then clearly $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->B=U$. Hence $X\subseteq U$ since $x$ was arbitrary. Since also $X\in B$ was arbitrary, this shows that $U$ is an upper bound of $B$.

Thus, since $B$ was an arbitrary $\subseteq$-chain, this shows that every chain of $(C,\subseteq )$ has an upper bound. It then follows from Zorn’s Lemma that $C$ has a $\subseteq$-maximal element as desired.

$\text{(←)}$ Suppose that the set of all chains of $(A,\le )$ has a $\subseteq$-maximal element for any $(A,\le )$. So consider any such ordered set $(A,\le )$ where every chain has a upper bound. Let $C$ be the set of all chains of $(A,\le )$ so that $C$ has a $\subseteq$-maximal element $M$ by our initial supposition. Then, since $M\in C$, it is a chain so it has an upper bound $a\in A$. We claim that $a$ is a maximal element of $(A,\le )$.

To show this, assume to the contrary that there is a $b\in A$ such that $a<b$, and let $M^{\prime }=M\cup \left\{b\right\}$. Consider any $x,y\in M^{\prime }$. If $x,y\in M$ then clearly $x$ and $y$ are comparable in $\le$ since $M$ is a chain. On the other hand, if $x\in M$ but $y=b$, then $x\le a$ since $a$ is an upper bound of $M$. We also have that $a<b=y$ so that $x<y$ since orders are transitive. The case in which $y\in M$ but $x=b$ similarly leads to $y<x$. Lastly, if $x=y=b$ then clearly $x\le y$ is true. Hence in all cases $x$ and $y$ are comparable in $\le$, which shows that $M^{\prime }$ is a chain since $x$ and $y$ were arbitrary. Therefore $M^{\prime }\in C$.

Now, it has to be that $b\notin M$ since, if it were, $a$ could not be an upper bound of $M$ since $a<b$ (and therefore it cannot be that $b\le a$ since the strict ordering is asymmetric). So, since $b\notin M$ it follows that $M\subset M\cup \left\{b\right\}=M^{\prime }$, which contradicts the fact that $M$ is a $\subseteq$-maximal element of $C$ since also $M^{\prime }\in C$. So it has to be that there is no such $b$ where $a<b$, which shows that $a$ is in fact a maximal element of $(A,\le )$. This proves Zorn’s Lemma since $(A,\le )$ was arbitrary. □