[proofplan] We prove the equivalence by showing that each principle implies the next in a cycle. First, the [Axiom of Choice](/page/Axiom%20of%20Choice) well-orders an arbitrary set by recursively choosing the next unused element, with [Hartogs' lemma](/theorems/1472) forcing the process to stop. Second, a well-ordering gives a choice function by choosing the least element of each set. Third, the [Well-Ordering Theorem](/theorems/1227) proves [Zorn's Lemma](/theorems/1226) by constructing a strictly increasing transfinite sequence until no strict extension remains; Hartogs' lemma again prevents an endless construction. Finally, Zorn's Lemma proves the Well-Ordering Theorem by maximizing partial well-orderings ordered by end-extension. [/proofplan]

[step:Use Hartogs' lemma as the set-theoretic stopping device] We use the following ZF fact twice: for every set $X$, there exists an ordinal $\kappa$ such that there is no injection $\kappa \to X$. This is Hartogs' lemma. The role of $\kappa$ is to prevent a transfinite construction from producing distinct elements of $X$ indexed by all ordinals below $\kappa$. More precisely, whenever a construction produces a function $f: \kappa \to X$ such that $f(\alpha) \ne f(\beta)$ for $\alpha \ne \beta$, it contradicts the defining property of $\kappa$. Hence any recursive construction whose non-stopping stages produce new distinct elements of a fixed set must stop before stage $\kappa$. [/step]

[step:Derive the Well-Ordering Theorem from the Axiom of Choice] Assume the Axiom of Choice. Let $X$ be a set. If $X = \varnothing$, then the empty relation well-orders $X$, so suppose $X \ne \varnothing$. By the Axiom of Choice applied to the set $\mathcal P(X) \setminus \{\varnothing\}$, there exists a function \begin{align*} c: \mathcal P(X) \setminus \{\varnothing\} &\to X \end{align*} such that $c(A) \in A$ for every nonempty subset $A \subset X$. Let $\kappa$ be an ordinal admitting no injection into $X$, as supplied by Hartogs' lemma. By transfinite recursion, construct values $x(\alpha) \in X$ for as many ordinals $\alpha < \kappa$ as possible, as follows. At stage $\alpha < \kappa$, assume that $x(\beta) \in X$ has been defined for every $\beta < \alpha$. If \begin{align*} X \setminus \{x(\beta) : \beta < \alpha\} \ne \varnothing, \end{align*} define \begin{align*} x(\alpha) := c\bigl(X \setminus \{x(\beta) : \beta < \alpha\}\bigr). \end{align*} If the displayed set is empty, stop the construction and define $D$ to be the set of ordinals $\beta < \alpha$ at which values $x(\beta)$ were already defined. The construction must stop at some stage $\gamma < \kappa$. If it did not, then $x: \kappa \to X$ would be injective, because each $x(\alpha)$ is chosen outside the set of all previously chosen values. This contradicts the choice of $\kappa$. At the stopping stage $\gamma$, we have \begin{align*} X = \{x(\beta) : \beta < \gamma\}. \end{align*} Define a relation $\preceq$ on $X$ by declaring, for $a,b \in X$, \begin{align*} a \preceq b \quad \Longleftrightarrow \quad x^{-1}(a) \le x^{-1}(b) \end{align*} where $x^{-1}(a)$ denotes the unique ordinal $\beta < \gamma$ with $x(\beta)=a$. Since $\gamma$ is an ordinal and $x: \gamma \to X$ is a bijection, this relation is a well-ordering of $X$. Thus every set admits a well-ordering. [/step]

[step:Derive the Axiom of Choice from the Well-Ordering Theorem] Assume the Well-Ordering Theorem. Let $\mathcal A$ be a set whose elements are nonempty sets. Apply the Well-Ordering Theorem to the set \begin{align*} U := \bigcup \mathcal A. \end{align*} Let $\preceq$ be a well-ordering of $U$. Define a function \begin{align*} c: \mathcal A &\to U \end{align*} by letting $c(A)$ be the $\preceq$-least element of $A$ for each $A \in \mathcal A$. This is well-defined because each $A$ is a nonempty subset of $U$, and every nonempty subset of a well-ordered set has a least element. Therefore $c(A) \in A$ for every $A \in \mathcal A$, so $c$ is a choice function. Hence the Axiom of Choice holds. [/step]

[step:Derive Zorn's Lemma from the Well-Ordering Theorem] Assume the Well-Ordering Theorem. Let $(P,\le)$ be a nonempty partially ordered set such that every chain $C \subset P$ has an upper bound in $P$. We prove that $P$ has a maximal element. By nonemptiness, $P \ne \varnothing$. By the Well-Ordering Theorem, fix a well-ordering $\preceq$ of $P$. Let $\kappa$ be an ordinal admitting no injection into $P$, as supplied by Hartogs' lemma. We define a transfinite sequence as long as possible. Suppose that for some ordinal $\alpha < \kappa$ we have already chosen a strictly increasing chain \begin{align*} p: \alpha &\to P. \end{align*} Let \begin{align*} C_\alpha := \{p(\beta) : \beta < \alpha\}. \end{align*} This is a chain in $P$, because the construction always chooses later terms above earlier terms. By hypothesis, $C_\alpha$ has an upper bound in $P$. Consider the set \begin{align*} E_\alpha := \{q \in P : p(\beta) < q \text{ for every } \beta < \alpha\}, \end{align*} where $p(\beta) < q$ means $p(\beta) \le q$ and $p(\beta) \ne q$. If $E_\alpha$ is nonempty, define $p(\alpha)$ to be the $\preceq$-least element of $E_\alpha$. If $E_\alpha$ is empty, stop the construction. The construction must stop at some stage $\gamma < \kappa$. If it did not, then $p: \kappa \to P$ would be injective, since $\alpha < \beta$ implies $p(\alpha) < p(\beta)$ and hence $p(\alpha) \ne p(\beta)$. This contradicts the choice of $\kappa$. At the stopping stage $\gamma$, the set \begin{align*} C_\gamma := \{p(\beta) : \beta < \gamma\} \end{align*} is a chain, so it has an upper bound $m \in P$. We claim that $m$ is maximal. Suppose, toward a contradiction, that there exists $r \in P$ with $m < r$. Since $m$ is an upper bound for $C_\gamma$, we have $p(\beta) \le m < r$ for every $\beta < \gamma$, so $r \in E_\gamma$. This contradicts the fact that the construction stopped at $\gamma$, meaning $E_\gamma=\varnothing$. Therefore no element of $P$ strictly exceeds $m$, and $m$ is maximal. [/step]

[step:Derive the Well-Ordering Theorem from Zorn's Lemma] Assume Zorn's Lemma. Let $X$ be a set. We prove that $X$ admits a well-ordering. Define $\mathcal W$ to be the set of all pairs $(A,\preceq_A)$ such that $A \subset X$ and $\preceq_A$ is a well-ordering of $A$. Partially order $\mathcal W$ by end-extension: for $(A,\preceq_A),(B,\preceq_B) \in \mathcal W$, write \begin{align*} (A,\preceq_A) \trianglelefteq (B,\preceq_B) \end{align*} if $A \subset B$, the relation $\preceq_B$ restricted to $A$ equals $\preceq_A$, and every element of $A$ precedes every element of $B \setminus A$ with respect to $\preceq_B$. We verify the chain condition. Let $\mathcal C \subset \mathcal W$ be a chain under $\trianglelefteq$. Define \begin{align*} A_{\mathcal C} := \bigcup_{(A,\preceq_A)\in \mathcal C} A. \end{align*} Define a relation $\preceq_{\mathcal C}$ on $A_{\mathcal C}$ as follows: for $x,y \in A_{\mathcal C}$, set $x \preceq_{\mathcal C} y$ if and only if there exists $(A,\preceq_A)\in \mathcal C$ with $x,y \in A$ and $x \preceq_A y$. This relation is well-defined because $\mathcal C$ is linearly ordered by end-extension. If two members of $\mathcal C$ both contain $x$ and $y$, then one end-extends the other, so the two orderings agree on the smaller domain and hence give the same comparison. The relation $\preceq_{\mathcal C}$ is a well-ordering of $A_{\mathcal C}$: any nonempty subset $S \subset A_{\mathcal C}$ contains an element $s$ lying in some domain $A$, and the $\preceq_A$-least element of $S \cap A$ is also the $\preceq_{\mathcal C}$-least element of $S$, because all later end-extensions place new elements after the old ones. Thus $(A_{\mathcal C},\preceq_{\mathcal C})$ is an upper bound for $\mathcal C$ in $\mathcal W$. By Zorn's Lemma, $\mathcal W$ has a maximal element $(M,\preceq_M)$. We claim that $M=X$. Suppose not. Choose an element $x_0 \in X \setminus M$. Define \begin{align*} M' := M \cup \{x_0\}. \end{align*} Extend $\preceq_M$ to a relation $\preceq_{M'}$ on $M'$ by keeping the old order on $M$ and declaring \begin{align*} m \prec_{M'} x_0 \end{align*} for every $m \in M$. Then $\preceq_{M'}$ is a well-ordering of $M'$ and $(M,\preceq_M) \trianglelefteq (M',\preceq_{M'})$, with the extension proper. This contradicts the maximality of $(M,\preceq_M)$. Therefore $M=X$, and $\preceq_M$ is a well-ordering of $X$. Hence the Well-Ordering Theorem holds. [/step]

[step:Conclude the equivalence of the three principles] We have shown that the Axiom of Choice implies the Well-Ordering Theorem, the Well-Ordering Theorem implies the Axiom of Choice, the Well-Ordering Theorem implies Zorn's Lemma, and Zorn's Lemma implies the Well-Ordering Theorem. Therefore, over ZF, the Axiom of Choice, the Well-Ordering Theorem, and Zorn's Lemma are equivalent. [/step]