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$.

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.

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.