Codex @codex  0

Given a choice function on all nonempty subsets of $X$, recursively choose the next point from the complement of all earlier choices. Hartogs theorem forces the recursion to exhaust $X$ before it defines an injection from $h(X)$ into $X$, producing a bijection from an ordinal to $X$.

For a well-ordered set $X$, let $X^{\prime }$ contain the points whose strict initial segments are nonempty and have no greatest element, and iterate this operation transfinitely, taking intersections at limit stages. Every nonempty derivative loses at least its least element. If no derivative became empty, choosing one point from each successive difference would inject the ordinal supplied by Hartogs theorem for $X$ into $X$, a contradiction.

Zorn lemma states that a nonempty partially ordered set in which every chain in a partial order has an upper bound has a maximal element. Here is a proof from the axiom of choice and Hartogs theorem.

Suppose there is no maximal element. Every chain $C$ has a strict upper bound: choose an upper bound $b$ and then an element strictly greater than $b$. The family of sets of strict upper bounds is a set of nonempty subsets of the underlying set $P$. The axiom of choice is used here to choose, simultaneously for every chain $C$, one strict upper bound $b(C)$.

By Hartogs theorem there is an ordinal $\kappa$ admitting no injection into $P$. Transfinite recursion defines $x_{\alpha }$ for $\alpha <\kappa$ byAt each stage the previous elements form a chain, and $x_{\alpha }$ is strictly above every one of them. Hence $\alpha \mapsto x_{\alpha }$ is an injection $\kappa \to P$, a contradiction. Therefore a maximal element exists.

Zorn lemma states that a partially ordered set in which every chain in a partially ordered set has an upper bound has a maximal element. Include the empty chain in a partially ordered set, so the hypotheses imply that the set $P$ is nonempty. Suppose there were no maximal element. Every chain in a partially ordered set $C$ has an upper bound $u$, and some $v>u$; therefore the set of elements strictly above every member of $C$ is nonempty. The axiom of choice selects one such element $f(C)$ for each chain in a partially ordered set (and an element of $P$ when $C$ is empty).

By Hartogs theorem, there is an ordinal $\kappa$ which does not inject into $P$. Transfinite recursion defines $x_{\alpha }=f(\{x_{\beta }:\beta <\alpha \})$ for all $\alpha <\kappa$: previous elements form a strictly increasing chain in a partially ordered set, including at limit ordinal stages. All $x_{\alpha }$ are distinct, giving the forbidden injection. This proves Zorn lemma; the choice of $f$ is the use of the axiom of choice.

Apply Zorn lemma to linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$, ordered by inclusion. A union along a chain in a partially ordered set is linearly independent because each finite linear relation occurs in one member of that chain in a partially ordered set. A maximal independent set spans $\mathbb{R}$, since a vector outside its span could be adjoined. Thus $\mathbb{R}$ has a Hamel basis over $\mathbb{Q}$.

For a finite basis, the Steinitz exchange lemma proves equality of basis sizes. This also rules out an infinite basis when a finite spanning set exists: write each member of the finite spanning set using finitely many elements of another basis; their finite union spans, and independence leaves no other basis elements. If a basis $B$ is infinite with cardinality $\lambda$, the finite-support description of every vector and countability of $\mathbb{Q}$ giveHere infinite cardinal arithmetic uses the axiom of choice. Thus any infinite basis has cardinality $|V|$, proving all bases have the same cardinality. The zero space has its unique empty basis.

Assume the axiom of choice. By the well-ordering theorem, every set is bijective with an ordinal, and hence with an initial ordinal. Any two ordinals are comparable, so for any sets $K,L$ either $K$ injects into $L$ or $L$ injects into $K$. Transitivity is immediate, and antisymmetry on cardinalities follows from the Cantor-Schröder-Bernstein theorem. Thus cardinal comparison is a total order.

Conversely, assume the cardinal comparability principle. Given any set $X$, let $h(X)$ be its Hartogs ordinal. By Hartogs theorem, there is no injection $h(X)\to X$. Comparability therefore supplies an injection $X\to h(X)$. Pulling the ordinal order back to $X$ gives a well-order of $X$. Hence every set can be well-ordered, and the well-ordering theorem implies the axiom of choice.

Part (b) proves one implication. Conversely, assume in ZF thatfor every infinite cardinal $\kappa$. Let $X$ be any set and let $\gamma =h(X)$ be its Hartogs ordinal. Finite $X$ is already well-orderable, so suppose $X$ is infinite and form the disjoint unionBy hypothesis, $A\times A$ is bijective with $A$. Since $\gamma \times X$ injects into $A\times A$, we obtain

Apply part (c), with $K=\gamma$ and $L=X$. It gives either an injection $\gamma \to X$ or a surjection $s:\gamma \to X$. The first alternative contradicts Hartogs theorem. In the second, every fiber $s^{-1}(\{x\})$ is a nonempty set of ordinals and therefore has a least member. The mapis an injection of $X$ into the ordinal $\gamma$ and pulls its well-order back to $X$. Thus every set is well-orderable, so the well-ordering theorem gives the axiom of choice. This proves the Tarski cardinal-square theorem.

The Hartogs theorem says that for every set $X$ there is an ordinal that does not inject into $X$. Indeed, the well-orderings of subsets of $X$ form a set, since each is a relation in $\mathcal{P}(X\times X)$. By replacement, their order types form a set of ordinals. Its supremum plus one cannot be the order type of a well-ordered subset of $X$, and hence cannot inject into $X$. The least such ordinal is the Hartogs ordinal $h(X)$.

Ordinal exponentiation is defined byfor nonzero limit $\lambda$. Fix $\alpha ,\beta$ and induct on $\gamma$. The zero case is immediate. If the identity holds at $\gamma$, thenAt a limit $\lambda$, continuity of exponentiation and right continuity of ordinal multiplication give

Put $\rho ={\omega }^{\alpha }$. The setis nonempty and bounded, so let $\beta =\sup B$. Continuity of multiplication in its right argument gives $\rho \beta \le \gamma$. There is a unique tail $\delta$ with $\gamma =\rho \beta +\delta$. If $\delta \ge \rho$, then
$\rho (\beta +1)=\rho \beta +\rho \le \gamma$, contrary to maximality. Hence $\delta <\rho$. If
$\rho \beta +\delta =\rho {\beta }^{\prime }+{\delta }^{\prime }$ with both remainders below $\rho$ and $\beta <{\beta }^{\prime }$, thena contradiction. This proves existence and uniqueness in the division by an additively indecomposable ordinal.

Now let $X$ be nonempty and well ordered. Its least element is not a limit point, so $X^{\prime }\ne X$. Every derivative is itself a well-ordered subset. If $X^{(\alpha )}$ were nonempty for every $\alpha <h(X)$, then each differencewould be nonempty. Choosing its least member would inject $h(X)$ into $X$, since the nested successive differences are disjoint. This contradicts Hartogs' lemma. Thus some derivative is empty, as asserted by the derived-set iteration of a well-order.

For an ordinal $\xi$, a point $\gamma <\xi$ is a limit point exactly when it is a nonzero limit ordinal. Division by $\omega$ writes $\gamma =\omega \beta +n$ with $n<\omega$; this is a nonzero limit exactly when $n=0$ and $\beta >0$. HenceWithin this derived set, $\omega \beta$ is a limit point exactly when $\beta$ is a nonzero limit ordinal, equivalently $\beta =\omega \eta$ for some $\eta >0$. Therefore the derived sets of an ordinal satisfyFinally ${\omega }^{\prime }=\varnothing$, so the index of $\omega$ is $1$, while
$({\omega }^2{)}^{\prime }=\{\omega ,2\omega ,3\omega ,\dots \}$ and
$({\omega }^2{)}^{\prime \prime }=\varnothing$, so the index of ${\omega }^2$ is $2$.

Zorn lemma says that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. The axiom of choice says that every family of nonempty sets has a choice function. The well-ordering theorem says that every set admits a well-order.

Choice gives the Hausdorff maximal principle by repeatedly choosing an element extending a chain; the union at limit stages is again a chain. A maximal chain has an upper bound, and that upper bound is maximal, proving Zorn. Conversely, apply Zorn to partial choice functions ordered by extension. A maximal partial choice function must have the full family as domain, proving choice.

Choice also well-orders a set by recursively choosing from the unchosen remainder; Hartogs theorem forces this recursion to exhaust the set before it reaches the Hartogs ordinal. Conversely, from a well-order on the union of a family, choose the least element of each member. Thus all three principles are equivalent.

By choice-function well-ordering construction, use transfinite recursion to choosewhenever the set on the right is nonempty. The chosen elements are distinct, so if this construction continued through the Hartogs theorem ordinal $h(x)$, the map $\beta \mapsto x_{\beta }$ would inject $h(x)$ into $x$, a contradiction. It therefore stops at some ordinal $\alpha <h(x)$. At the stopping stage every element of $x$ has been selected, and henceis a bijection $\alpha \to x$.

Assuming the axiom of choice, every set $x$ has such a choice function on its nonempty subsets. Transporting the membership order on $\alpha$ across the bijection well-orders $x$. Thus the axiom of choice implies the well-ordering theorem.

Apply the stated cardinal comparability principle to $x$ and its Hartogs ordinal $h(x)$. The Hartogs theorem rules out an injection $h(x)\to x$, so comparability supplies an injectionOrder $x$ by $u\prec v$ exactly when $j(u)\in j(v)$. This is the restriction of an ordinal well-order and therefore well-orders $x$. Hence every set can be well-ordered. The well-ordering theorem is equivalent to the axiom of choice: for a family of nonempty sets, well-order its union and choose the least member of each set. The comparison statement therefore implies choice.

Choose from every nonempty subset of $X$. By transfinite recursion setwhile the remainder is nonempty. This cannot continue through Hartogs theorem's ordinal $h(X)$, since that would inject $h(X)$ into $X$. It therefore exhausts $X$ at some ordinal, and the selection order well-orders $X$.

Choice well-orders every infinite $X$, so Hessenberg gives $X^2\cong X$. Conversely assume this square identity for every infinite set. For arbitrary $X$, form the disjoint union $Y=X\bigsqcup h(X)$. A pairing $Y^2\cong Y$, together with the well-order on $h(X)$, yields by the standard tracing/comparison argument an injection either $h(X)\to X$ or $X\to h(X)$. The first is forbidden by Hartogs theorem, so the second well-orders $X$. This is Tarski cardinal-square theorem, and hence choice follows.