Codex @codex  0

For any sets $X,Y$, either $X$ injects into $Y$ or $Y$ injects into $X$. Applying this to $X$ and its Hartogs ordinal proves the well-ordering theorem, so over ZF cardinal comparability is equivalent to choice.

Assuming the axiom of choice, the well-ordering theorem makes every set equipotent to an initial ordinal. The infinite initial ordinals are exactly the ${\aleph }_{\alpha }$, so every infinite cardinal is ${\aleph }_{\alpha }$ for a unique ordinal $\alpha$.

For an explicit basis extension in ${\mathbb{R}}^2$, start with $A=\{u\}$, where $u=(1,1)$. Its linear span is the line $y=x$. Adding $w=(1,-1)$ preserves linear independence, because $w$ is outside that line, and gives a basis. Every vector has the finite linear combinationThe vector $2u=(2,2)$ cannot be added while preserving linear independence: it is already in the linear span. Many choices outside the line work, so maximality does not select a unique basis.

For a finite-dimensional vector space with a supplied finite spanning set, a greedy algorithm scans the list, retaining each vector precisely when it is outside the linear span of those already retained. Starting with a linearly independent $A$, the same scan adjoins only the needed vectors. Retained vectors remain linearly independent, and every skipped vector is in the final linear span, so the result is a basis containing $A$. Finite reasoning needs no axiom of choice.

For an arbitrary vector space, this finite stopping argument is unavailable. Accepting Zorn's lemma asserts existence of a maximal element once every chain in a partial order has an upper bound; it supplies no general computational recipe. Over ZF, Zorn's lemma, the axiom of choice and the well-ordering theorem are equivalent. Particular infinite vector spaces can still have explicit bases, such as $1,x,x^2,\dots$ for the vector space of univariate polynomials over a specified field; infinity alone does not force a nonconstructive argument.^[ref]

Every injection from an ordinal into a set $X$ has domain strictly below the Hartogs number $h(X)$. Therefore all partial injections with ordinal domain and range in $X$ form a set of graphs contained in $\mathcal{P}(h(X)\times X)$. Under extension, the union of a chain remains a partial injection of this kind. Zorn's lemma then supplies a maximal one, and extending at an unused range element shows that it must be a bijection onto $X$. This gives the well-ordering theorem with the set-sizedness of the poset made explicit.

The finite-stage calculation gives ${\gamma }_{\omega }={\sup }_{n<\omega }{n}^2=\omega$, so the desired equality holds at the first infinite ordinal. Apply transfinite induction to all subsequent infinite ordinals. The successor step is part (b), and the limit step is part (c). ThusBy the well-ordering theorem, any infinite cardinal in the question may be represented by an infinite initial ordinal $\kappa$. The corrected recursion supplies a bijection $g_{\kappa }:\kappa \times \kappa \to {\gamma }_{\kappa }$, and the just-proved equality gives $|{\gamma }_{\kappa }|=\kappa$. ThereforeThe proof used only finite-copy interleaving before reaching this conclusion; using the square equality itself to estimate the successor or limit stages would have been circular.

The four principles are:

In the last assertion the upper bound belongs to the partially ordered set; it need not belong to the chain.

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.

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.

On $[\kappa {]}^{\omega }$, declare $A\sim B$ when their symmetric difference is finite. Use the well-ordering theorem to choose one representative $R_{[A]}$ from each equivalence class, and color byRemoving one point from a countably infinite set does not change its equivalence class and reverses this parity. For any $H\subseteq \kappa$ of order type $\omega$ and $x\in H$, both $H$ and $H\setminus \{x\}$ belong to $[H{]}^{\omega }$ and receive different colors. There is no homogeneous $H$ of order type $\omega$. This proves the negative infinite-arity partition relationThe slashed arrow in the PDF is essential.

The Knaster–Tarski fixed-point theorem states that if $L$ is a complete lattice and $f:L\to L$ is order-preserving, then the fixed points of $f$ form a complete lattice; in particular, $f$ has least and greatest fixed points.

LetFor every $x\in P$, monotonicity gives $f(a)\le f(x)\le x$, so $f(a)\le a$. Applying $f$ once more shows $f(f(a))\le f(a)$, hence $f(a)\in P$. Therefore $a\le f(a)$ by the definition of $a$, and $f(a)=a$. Every fixed point belongs to $P$, so $a$ is the least fixed point. Dually, $\bigvee \{x:x\le f(x)\}$ is the greatest fixed point. For any family $S$ of fixed points, apply the same argument inside the upper interval above $\bigvee S$ to obtain the least fixed point above every member of $S$; this is their join in the fixed-point set. The dual construction supplies meets, proving the full statement.

To deduce the Cantor-Schröder-Bernstein theorem, let $i:A\to B$ and $j:B\to A$ be injections. On the complete lattice $\mathcal{P}(A)$ defineThis map is order-preserving, so it has a fixed point $X$. The relationshows thatis a bijection: its two pieces map bijectively onto the disjoint sets $i(X)$ and $B\setminus i(X)$. Thus injections both ways imply a bijection.

Let $P$ be the poset of countable subsets of $\mathbb{R}$. The family of all singletons $\{\{r\}:r\in \mathbb{R}\}$ has no upper bound in $P$, since any upper bound would contain every real number and would be uncountable. Therefore

Finally, use the well-ordering theorem to fix a well-order $\prec$ of $\mathbb{R}$. Every countable $A$ omits some real number; let $m(A)$ be its $\prec$-least omitted element and defineIf $A\subseteq B$, then either $m(A)\in B$, or every point preceding $m(A)$ lies in $A\subseteq B$ and $m(A)=m(B)$. In either case $f(A)\subseteq f(B)$, so $f$ is order-preserving. Yet $m(A)\notin A$, and henceThis does not contradict Knaster–Tarski because $P$ is not a complete lattice.

An aleph number is an infinite initial ordinal. More explicitly,for a limit ordinal $\lambda$. By the well-ordering theorem, every set is equipotent to an ordinal and hence to a unique initial ordinal. If the set is infinite, that initial ordinal occurs in the aleph enumeration. Thus every infinite set has cardinality ${\aleph }_{\alpha }$ for a unique ordinal $\alpha$.

We next prove the square of an infinite cardinal. Suppose otherwise and let $\kappa$ be the least infinite cardinal for which ${\kappa }^2>\kappa$. Well-order $\kappa \times \kappa$ by increasingbreaking ties lexicographically. The predecessors of $(\alpha ,\beta )$ lie inside $\gamma \times \gamma$ for some $\gamma <\kappa$. If $\mu =|\gamma |$, then $\mu <\kappa$; by minimality, ${\mu }^2=\mu$ when $\mu$ is infinite, while the finite case is immediate. Every proper initial segment therefore has cardinality less than $\kappa$.

Recursively assign to each pair the least ordinal below $\kappa$ not already assigned to one of its predecessors. Such an ordinal always exists by the preceding bound, so this constructs an injection $\kappa \times \kappa \to \kappa$. The map $\alpha \mapsto (\alpha ,0)$ gives the reverse injection, and the Cantor-Schröder-Bernstein theorem yields

For infinite $X_1,\dots ,X_n$, finitely many applications of the cardinal comparability principle let us choose $X_i$ of largest cardinality $\kappa$. Thenwhere the final equality follows from infinite cardinal arithmetic. Consequently

For a countable family of pairwise different infinite cardinalities, the answer is yes. Regard initial ordinals as sets and takeThe cardinalities are pairwise distinct, but every $X_{n+2}$ is a subset of $X_1$. Hencewhich is the countable family of distinct infinite cardinalities with a largest member construction.

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.

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.

Assume the axiom of choice and suppose a poset satisfying the hypothesis has no maximal element. Fix a choice function on its nonempty subsets. By transfinite recursion, choose at each ordinal stage an upper bound of the chain in a partial order already constructed, then choose a strictly larger member. Both choices are available, including the initial empty stage. This produces distinct members throughout the Hartogs ordinal of $P$, contradicting the Hartogs theorem. Thus a maximal element exists. Conversely, apply Zorn's lemma to partial choice functions on a family of nonempty sets, ordered by extension. A chain in a partial order has the compatible union as an upper bound, and a maximal element must be defined on the whole family, since one missing value could be adjoined.

Zorn's lemma was introduced in 1935 to shorten algebra proofs using choice or the well-ordering theorem.^[ref]

Every nonempty subset of the natural numbers has a least element in their usual order. Applying this principle to positive integer linear combinations proves Bézout's identity. This principle for the usual natural-number order is distinct from the general well-ordering theorem asserting that every set can be equipped with some well-order.