[proofplan] We derive Zorn's Lemma from the Axiom of Choice (in the form: every surjection has a right inverse). The strategy is to use the Axiom of Choice to define a "successor" function that, given any non-maximal element, produces a strictly larger one. We then use transfinite recursion to build a chain that must eventually terminate at a maximal element — for otherwise, the chain would exceed every set-sized ordinal, contradicting the Burali-Forti paradox. [/proofplan] [step:Define a successor function using the Axiom of Choice] Assume $(P, \le)$ satisfies the chain condition but has no maximal element. We derive a contradiction. Since $P$ has no maximal element, every $p \in P$ admits some $q \in P$ with $p < q$ (i.e., $p \le q$ and $p \neq q$). For each $p \in P$, define \begin{align*} S(p) := \{q \in P : p < q\}. \end{align*} By assumption, $S(p) \neq \varnothing$ for every $p \in P$. By the Axiom of Choice, there exists a function \begin{align*} f: P &\to P \\ p &\mapsto f(p), \end{align*} where $f(p) \in S(p)$, so that $p < f(p)$ for all $p \in P$. By the chain condition, every chain in $P$ has an upper bound. Define a function $g$ that assigns to each chain $C \subset P$ an upper bound $g(C) \in P$ (again using the Axiom of Choice to select one upper bound for each chain). [guided] We are proving the contrapositive: if $P$ has no maximal element, we will construct a chain with no upper bound, contradicting the hypothesis. The key use of the Axiom of Choice is twofold. First, for each element $p \in P$, the set $S(p) = \{q \in P : p < q\}$ is nonempty (since $p$ is not maximal). The Axiom of Choice provides a choice function $f: P \to P$ with $f(p) \in S(p)$, ensuring $p < f(p)$ for every $p$. Second, we need to select an upper bound for each chain. The hypothesis guarantees existence, but there may be many upper bounds; the Axiom of Choice selects one systematically. These two choice functions together allow us to build longer and longer chains by transfinite recursion. [/guided] [/step] [step:Build a chain by transfinite recursion and reach a contradiction] Fix any $p_0 \in P$. We define a transfinite sequence $(p_\alpha)_{\alpha < \gamma}$ of elements of $P$ by recursion on ordinals: - **Base:** $p_0$ is the chosen element. - **Successor:** $p_{\alpha + 1} := f(p_\alpha)$. Since $p_\alpha < f(p_\alpha)$, we have $p_\alpha < p_{\alpha + 1}$. - **Limit:** For a limit ordinal $\lambda$, the set $\{p_\alpha : \alpha < \lambda\}$ is a chain (by induction, $\alpha < \beta < \lambda$ implies $p_\alpha < p_\beta$). By the chain condition, it has an upper bound $u \in P$. Set $p_\lambda := f(u)$, so $p_\lambda > u \ge p_\alpha$ for all $\alpha < \lambda$. By transfinite induction, $\alpha < \beta$ implies $p_\alpha < p_\beta$. In particular, the map $\alpha \mapsto p_\alpha$ is injective (distinct ordinals map to distinct elements of $P$). If this construction could continue for all ordinals, it would inject the class of all ordinals into $P$, contradicting the fact that $P$ is a set (since the class of ordinals is a proper class, by the Burali-Forti paradox: if the class of all ordinals were a set, it would itself be an ordinal $\Omega$, and $\Omega < \Omega + 1$ would be an ordinal not in the class — a contradiction). Since $P$ is a set, there exists an ordinal $\gamma$ with $|\gamma| > |P|$, and the construction must fail before reaching $\gamma$. The only way the construction can fail is if some $p_\alpha$ is maximal (i.e., $S(p_\alpha) = \varnothing$), contradicting our assumption. Therefore $P$ has a maximal element. [guided] We build a strictly increasing transfinite sequence in $P$. The three cases of transfinite recursion are: **Base:** Choose any $p_0 \in P$. **Successor:** Given $p_\alpha \in P$, define $p_{\alpha+1} := f(p_\alpha)$, where $f$ is the choice function from the previous step. By construction, $p_\alpha < p_{\alpha+1}$. **Limit:** For a limit ordinal $\lambda$, consider the chain $C_\lambda := \{p_\alpha : \alpha < \lambda\}$. This is indeed a chain: for any $\alpha < \beta < \lambda$, we have $p_\alpha < p_\beta$ by the induction hypothesis (the sequence is strictly increasing up to $\lambda$). By the hypothesis of Zorn's Lemma, $C_\lambda$ has an upper bound $u \in P$, meaning $p_\alpha \le u$ for all $\alpha < \lambda$. We then set $p_\lambda := f(u)$, which gives $p_\lambda > u \ge p_\alpha$ for all $\alpha < \lambda$. The strict monotonicity $p_\alpha < p_\beta$ for $\alpha < \beta$ implies injectivity: the map $\alpha \mapsto p_\alpha$ sends distinct ordinals to distinct elements of $P$. Now here is the crux: $P$ is a set, so $|P|$ is some cardinal number. But the class of all ordinals is not a set (Burali-Forti). If the construction never terminates, we would obtain an injection from arbitrarily large ordinals into $P$. In particular, taking any ordinal $\gamma$ with $|\gamma| > |P|$ (which exists by Hartogs' lemma), the construction must fail before stage $\gamma$. The failure can only occur if we encounter an element with no strict successor — i.e., a maximal element. This contradicts our assumption that no maximal element exists. [/guided] [/step]