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.

The least ordinal that does not admit an injection into $X$. Its existence, supplied by Hartogs theorem, does not require the axiom of choice.

For infinite sets in ZFC, the Hartogs number is the successor of the input cardinal. Every smaller ordinal injects into the input, whereas that successor does not. An infinite successor cardinal ${\kappa }^{+}$ is regular: a cofinal family of at most $\kappa$ ordinals below it would have union of cardinal at most $\kappa \cdot \kappa =\kappa$, a contradiction. Finite inputs give finite successor cardinals, so the formulation in terms of alephs requires an infinite input. The general Hartogs theorem itself does not require choice.

In complex dimension at least two, a holomorphic function on a punctured coordinate ball extends holomorphically through its centre. Componentwise extension in a holomorphic local frame gives the same statement for holomorphic sections. This preserves global sections after removing finitely many points, but does not imply preservation of higher sheaf cohomology. This analytic theorem differs from the set-theoretic Hartogs theorem.

Hartogs theorem says that for every set $X$ there is a least ordinal $h(X)$ for which no injection $h(X)\to X$ exists. This does not require the axiom of choice. Form the set $W$ of well-orderings of subsets of $X$. It can be defined by the axiom schema of specification insiderecording a subset and its well-order. Each member of $W$ has a unique ordinal order type. Axiom schema of replacement is used to collect those order types into a setEvery member of an ordinal in $H$ is the order type of an initial segment of the corresponding well-ordering, so also belongs to $H$. Thus $H$ is a transitive set of ordinals and is itself an ordinal. An ordinal $\alpha$ belongs to $H$ exactly when it injects into $X$: use a bijection to a well-ordered subset in one direction, and transport the ordinal order along the injection in the other. If $H$ injected into $X$, this characterization would give $H\in H$, impossible for an ordinal. All smaller ordinals lie in $H$ and do inject into $X$. Therefore $H=h(X)$. Apart from the standard order-type theorem, the explicit collection of all order types is the Axiom schema of replacement step; no axiom of choice of a representative ordering for each type is needed.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Use the Hartogs bound on partial ordinal injections to obtain a set-sized partially ordered set. Consider the partial injections into $X$ whose domains are ordinals. Hartogs theorem bounds every such domain strictly below $h=h(X)$. Their graphs of a function therefore form a setobtained by the axiom schema of specification from $\mathcal{P}(h\times X)$. Order $P$ by extension. It is nonempty because it contains the empty function. A chain has as an upper bound the union of its graphs of a function: extension makes this a function, injectivity is preserved, and its domain is an union of ordinals and hence an ordinal. Its range is contained in $X$, so Hartogs theorem forces its domain to be strictly below $h$; thus it belongs to $P$. The empty chain also has the empty function as an upper bound.

By Zorn's lemma choose a maximal $f:\alpha \to X$. If an element $x\in X$ lay outside its range, appending $f(\alpha )=x$ would give a larger injection on $\alpha +1$. Such an injection itself guarantees $\alpha +1<h$ by Hartogs theorem, so it is a legitimate member of $P$, contradicting maximality in a partially ordered set. Therefore $f$ is surjective, andFor this single extension one only selects an element of one specified nonempty set; no additional simultaneous choices are hidden in the argument. Zorn's lemma is the form of the axiom of choice used to obtain maximality in a partially ordered set.

Finally work with cardinals, represented by initial ordinals, and put $\mu =\max (\kappa ,\lambda )$. It is infinite by hypothesis. Nonzeroness of each factor gives an injection of the larger cardinal into the Cartesian product by holding a coordinate of the other fixed. The supplied infinite-ordinal square result gives $|\mu \times \mu |=\mu$. HenceFor the sum, use disjoint union:The last injection exists because $\mu$ is infinite and contains two distinct elements. Cantor-Schröder-Bernstein theorem turns both pairs of bounds into equalities, provingThese final operations are cardinal sum and multiplication, measuring disjoint unions and Cartesian products. They are not the noncommutative ordinal arithmetic considered in question 5.

Hartogs theorem says that for every set $A$ there is a least ordinal $h(A)$ that does not inject into $A$. This theorem requires no axiom of choice.

To prove it, collect all well-orderings of subsets of $A$. They are set-sized data, coded by pairs from $\mathcal{P}(A)$ and $\mathcal{P}(A\times A)$. Each has a unique ordinal order type, so replacement gives a set $H$ of their order types. If $\eta \in H$ and $\xi <\eta$, restricting the corresponding well-order to an initial segment shows $\xi \in H$. Hence $H$ is an ordinal. If this ordinal itself injected into $A$, its transported well-order would put $H$ among its own elements, impossible for an ordinal. Every smaller ordinal does inject by definition. Thus $h(A)=H$ has the asserted property.

The recursion printed in the source needs two boundary restrictions. Its new-row successor clause allows $\beta =\alpha$, which would assign a value at $(\alpha ,\alpha +1)$ outside the declared domain. Also, at $\alpha =0$, its row-start clause gives $g_1(0,0)=0$ while its column-start clause gives $g_1(0,0)=g_1(0,0)+1$. Taken literally, these clauses do not define a function.

The intended extension fills the new row first and the remaining new column second. Restrict the row successor clause to $\beta <\alpha$, and apply the column-start clause only when $\alpha >0$. With these two restrictions the domains are disjoint:All successors here are ordinal successors. Simultaneous transfinite induction proves a stronger result: $g_{\alpha }$ is a bijection of $\alpha \times \alpha$ onto an ordinal ${\gamma }_{\alpha }$, and the functions extend one another.

At zero this is the empty function. Assuming it at $\alpha$, the least missing ordinal is ${\gamma }_{\alpha }$. Recursion down the new row gives values ${\gamma }_{\alpha }+\beta$ for $\beta \le \alpha$; recursion down the remaining column gives ${\gamma }_{\alpha }+(\alpha +1)+\beta$ for $\beta <\alpha$. These enumerate two disjoint consecutive ordinal intervals above the old range, so the extension is well defined and bijective, withAt a limit $\lambda$, take the union of the earlier functions. Compatibility makes it a function, and every pair of coordinates below $\lambda$ is already present at some earlier stage. Its range is the ordinal ${\bigcup }_{\alpha <\lambda }{\gamma }_{\alpha }$, and injectivity is preserved by the compatible union. This completes the construction of the row-and-column enumeration of an ordinal square.

For finite stages ${\gamma }_n=n^2$. For example the table of $g_3$, with the first coordinate indexing rows, isThe remaining parts refer to this domain-consistent construction. The source's literal boundary claims are preserved in the archive, rather than silently asserted as valid.

Assume the well-ordering theorem. Every set with a chosen well-order has an order isomorphism to a unique ordinal. Any two ordinals are comparable, and the smaller embeds into the larger as an initial segment. Transporting that embedding back to the original sets proves the cardinal comparability principle.

Conversely, assume the cardinal comparability principle and let $X$ be any set. The Hartogs theorem, provable in ZF, supplies an ordinal $h(X)$ for which no injection $h(X)\hookrightarrow X$ exists. Comparison forces an injection $X\hookrightarrow h(X)$. Pulling back the well-order on its image gives a well-order on $X$. ThereforeThe assumed ordinal facts are that every well-ordered set has an ordinal order type and that any two ordinals are comparable; the other assumed theorem is precisely the stated Hartogs theorem.

Zorn lemma states that a nonempty partially ordered set in which every chain has an upper bound contains a maximal element. To prove it from the axiom of choice and Hartogs theorem, suppose no element were maximal. Fix a choice function on the nonempty subsets of the poset. Every chain then has a strict upper bound: choose an upper bound, and, since it is not maximal, choose an element strictly above it. Let $\kappa$ be a Hartogs ordinal which cannot inject into the poset. By transfinite recursion for $\alpha <\kappa$, choose a strict upper bound $x_{\alpha }$ of all previously chosen $x_{\beta }$, $\beta <\alpha$; for the empty initial chain choose any element. The previous elements form a chain at every stage. The resulting strictly increasing sequence injects $\kappa$ into the poset, contradicting Hartogs. Hence a maximal element exists. Choice is used in fixing the function selecting a strict upper bound at every successor and limit stage; Hartogs and transfinite recursion themselves do not supply those selections.

Apply Zorn lemma to the linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$, ordered by inclusion. A chain's union is linearly independent because any finite linear relation is contained in one member of the chain. A maximal independent set $B$ must span $\mathbb{R}$, since otherwise one could append a vector outside its span. Thus $B$ is a rational-vector-space basis of $\mathbb{R}$.

It is infinite: a finite-dimensional rational vector space is countable, whereas $\mathbb{R}$ is not. If its cardinal is $\kappa$, finite rational linear combinations show $|\mathbb{R}|=\max ({\aleph }_0,\kappa )$; uncountability forces $\kappa =|\mathbb{R}|$. A basis of ${\mathbb{R}}^2$ is $(B\times \{0\})\cup (\{0\}\times B)$, where these expressions mean the vectors $(b,0)$ and $(0,b)$. Its cardinal is $\kappa +\kappa =\kappa$, using the infinite-cardinal arithmetic available under choice. A bijection between the two bases extends uniquely by finite rational linear combinations to a linear bijection. ThereforeThis is an algebraic isomorphism, with no assertion of continuity or real-linearity.

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.

Call a set function $f$ with ordinal domain $\gamma$ good if $f(\xi )=G(\xi ,\mathrm{ran}(f{|}_{\xi }))$ for every $\xi <\gamma$. Any two good functions agree on their common domain: otherwise their first disagreement has identical earlier ranges and hence identical values under $G$. This is transfinite induction, not an assumption of the desired recursion.

Good functions exist with every ordinal domain. At a successor stage extend the unique previous function by its prescribed value under $G$. At a limit stage, Axiom schema of replacement collects the unique good functions on all smaller domains into a set, and their compatible union is a good function on the limit domain. Each earlier range is a set, so $G$ is applied only to sets. Transfinite induction now establishes existence at all stages. Define $F(\alpha )$ to be the value at $\alpha$ of the unique good function on $\alpha +1$. This is a definable class function because goodness and the uniqueness assertion are formulas in the defining formula for $G$. Compatibility gives

An initial ordinal is an ordinal not bijective with any smaller ordinal. It is the canonical ordinal representative of a well-orderable cardinal, so cardinal arithmetic can be defined by taking the initial ordinal equinumerous with a disjoint union, Cartesian product or function set. In the usual setting with the axiom of choice, every cardinal has such a representative. Hartogs theorem says that for every set $A$ there is an ordinal $h(A)$ which does not inject into $A$, and there is a least such ordinal. For an initial ordinal $\kappa$ it is the next larger initial ordinal: every smaller ordinal injects into $\kappa$, and if $h(\kappa )$ were equinumerous with a smaller ordinal it too would inject into $\kappa$.

Use the recursion just proved to set ${\omega }_0=\omega$, ${\omega }_{\beta +1}=h({\omega }_{\beta })$ and ${\omega }_{\lambda }={\sup }_{\beta <\lambda }{\omega }_{\beta }$ for nonzero limit $\lambda$. These instructions use the earlier value set alone: at a successor it has a maximum, and at a limit its supremum is taken. They are therefore implemented by an appropriate definable $G$. The limit supremum is initial: if it were bijective with $\gamma$ below it, choose an earlier ${\omega }_{\beta }>\gamma$; then ${\omega }_{\beta }$ would inject into $\gamma$, contradicting initiality. The sequence is strictly increasing and continuous. There are no omitted infinite initial ordinals, since each successor chooses the least next one and each limit is the supremum; more formally, a least omitted initial ordinal cannot lie between successive terms, and the least term above it cannot be a limit term. Terms eventually exceed any prescribed ordinal, since a strictly increasing ordinal sequence satisfies ${\omega }_{\beta }\ge \beta$.

There is a fixed point of a normal ordinal function. Explicitly let ${\alpha }_0=0$, ${\alpha }_{n+1}={\omega }_{{\alpha }_n}$ and $\alpha ={\sup }_{n<\omega }{\alpha }_n$. The sequence is strictly increasing, by induction from $0<{\omega }_0$ and strict increase of the enumeration. It is cofinal in the limit $\alpha$, so continuity gives

Order the collection $\mathrm{Ch}(P)$ of every chain in a partial order, including the empty chain, by inclusion. Suppose that $j:\mathrm{Ch}(P)\to P$ is an order-preserving function and an injection. Let $\theta =h(P)$ be the Hartogs ordinal: by Hartogs theorem, no injection from $\theta$ to $P$ exists.

Use transfinite recursion to define, for $\alpha <\theta$,We verify both that $j(C_{\alpha })$ is defined and that the values are strictly increasing. Assume inductively that the earlier values are strictly increasing. Then $C_{\alpha }$ is a chain in a partial order. For any $\beta <\alpha$, $C_{\beta }\subseteq C_{\alpha }$, so the fact that $j$ is order-preserving gives $p_{\beta }\le p_{\alpha }$. Furthermore $p_{\beta }\in C_{\alpha }$, whereas $p_{\beta }\notin C_{\beta }$ by distinctness of the earlier values. Thus $C_{\beta }\ne C_{\alpha }$, and injectivity gives $p_{\beta }\ne p_{\alpha }$. We have provedThe empty initial chain starts the induction, and the same argument applies at every limit ordinal.

If a globally defined recursion rule is desired, apply $j$ when the earlier range is a chain and otherwise use the fixed value $j(\varnothing )$. The induction shows that the fallback case never occurs. Thus no choices of new points are being made: the function $j$ uniquely determines every stage.

The resulting function $\alpha \mapsto p_{\alpha }$ is an injection from $\theta$ to $P$, contrary to its defining Hartogs ordinal property. Hence the chain-poset nonembedding lemma gives

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.