Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 4 / 16G / Solution

For Hartogs theorem, collect all well-order relations on all subsets of a set $x$. They form a set, since the relations belong to the power set of $x\times x$. Replacement collects their ordinal order types in a set $T$. DefineIf there were an injection $\alpha \to x$, transfer the well-order of $\alpha$ to its image. Its type would put $\alpha$ in $T$, giving $\alpha +1\le \alpha$, impossible. Thus some ordinal does not inject into $x$, without using choice.

Assume the axiom of choice and let a nonempty partially ordered set $P$ have an upper bound for every chain. Suppose it has no maximal element. Choose, from every subset of $P$ with a nonempty set of strict upper bounds, one such strict upper bound. Every chain has a strict upper bound: first take an upper bound and then a strictly larger element, using the absence of maximal elements. Take a Hartogs ordinal $\alpha$ for $P$. Transfinite recursion chooses $p_{\beta }$, for each $\beta <\alpha$, strictly above all previously chosen elements. Their predecessors form a chain at every stage, so this recursion is defined and strictly increasing. It gives an injection $\alpha \to P$, contradicting the choice of $\alpha$. Hence $P$ has a maximal element, proving Zorn's lemma.

For the well-ordering theorem, take a choice function on the nonempty subsets of $x$ and recursively choose an element of $x$ not previously selected. If this process had not exhausted $x$ at any stage below its Hartogs ordinal $\alpha$, it would define an injection $\alpha \to x$, again impossible. Therefore it exhausts $x$ at some ordinal stage $\beta <\alpha$. Order each element by its unique selection index; this transfers the ordinal well-order to all of $x$. The empty set is already well-ordered. These proofs use transfinite recursion, not an unstated fixed-point theorem.