Choice implies Zorn's Lemma

We prove Choice $\implies$ Zorn's Lemma (the other equivalences are standard but longer; this direction is the one used constantly in algebra). Let $(P, \le)$ be a nonempty poset in which every chain has an upper bound in $P$, and suppose toward contradiction that $P$ has no maximal element.

Since $P$ has no maximal element, every $x \in P$ has some strict upper bound in $P$ (an element $y$ with $x < y$): otherwise that $x$ would itself be maximal. In particular, every chain $C \subseteq P$ has an upper bound (by hypothesis) which itself has a strict upper bound, so every chain has a strict upper bound in $P$.

By the Axiom of Choice, fix a choice function that selects, for every chain $C \subseteq P$, some strict upper bound $g(C)$ of $C$. Using $g$, build a transfinite sequence $(a_\alpha)$ indexed by all ordinals $\alpha$: let $a_0 = g(\emptyset)$, and for each ordinal $\alpha$, once $a_\beta$ has been defined for every $\beta < \alpha$, the set $\{a_\beta : \beta<\alpha\}$ is a chain (by construction each new term is a strict upper bound of all earlier ones), so define $a_\alpha = g(\{a_\beta : \beta<\alpha\})$, a strict upper bound of every earlier term.

This produces a strictly increasing map from the ordinals into $P$: $\alpha < \beta \implies a_\alpha < a_\beta$. But the ordinals do not form a set (there is no set of all ordinals), while $P$ is an ordinary set; a strictly increasing map from the ordinals into $P$ would make the ordinals no larger in cardinality than $P$, contradicting the fact (a consequence of Replacement) that no set can be mapped injectively onto a collection as large as all the ordinals. This contradiction shows the assumption "$P$ has no maximal element" is false, so $P$ has a maximal element, proving Zorn's Lemma from Choice.